20190723的test

Traffic

Description

​ 工人打算用一组传感器测量公路上的车流量,每个传感器被用来测量一小段路面上的车流量的数值。不幸的是,某一天装有传感器的盒子进了水,之后它们就不能精确的测量了。现在每个传感器只能输出一个可能结果的范围。例如,一个传感器可能会给出范围[7,13],表示在这段路面上的车流量不小于7,并且不大于13。

​ 高速路要测量的这一段长N英里,当然高速路都是单向的,从第1英里驶向第N英里。工人想要安装N个传感器——每个监测1英里长的路段。在其中某些路段上,有能够使得车辆进入高速公路的上匝道,在这样的路段上,工人会将传感器装在上匝道上,测量流入的车流量。在某些路段上有能够使得车辆离开高速公路的下匝道,在这样的路段上,工人会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下匝道,工人就将传感器装在高速公路的主路上。

​ 给定N个传感器的读数,请求出在高速公路第1英里之前和第N英里之后车流量的最为准确的可能范围。这些范围应当与所有N个传感器的读数相一致。

Input

​ 输入的第一行包含N(1≤N≤100)。余下N行每行按从第1英里至第N英里的顺序描述一段1英里长的路段。每行包含一个字符串,为”on”(如果这段路上有一个上匝道),”off”(如果这段路上有一个下匝道),或者是”none”(如果这段路上没有匝道),然后是两个范围为0…1000的整数,表示这段路上的传感器的读数所给出的下界、上界。至少一个高速公路路段的描述会是”none”。

Output

​ 输出的第一行包含两个整数,为第1英里之前的车流量的最准确的可能范围。第二行包含两个整数,为第N英里之后的车流量的最准确的可能范围。输入保证存在符合要求的解。

Analysis

前后扫一遍即可

Codes

//正反各自扫一遍?过程中求交集和加减?  
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define max(x,y) (x>y)?x:y
#define min(x,y) (x<y)?x:y
using namespace std;

int N;
struct data{
char op[5];
int L,R;
}d[maxn];

int main(){
freopen("traffic.in","r",stdin);
freopen("traffic.out","w",stdout);
scanf("%d",&N);
int fs=0,fe=0;
for(int i=1;i<=N;i++){
scanf("%s%d%d",d[i].op,&d[i].L,&d[i].R);
}

int FL=-inf,FR=inf,EL=-inf,ER=inf;

for(int i=N;i>=1;i--){
if(d[i].op[0]=='n'){
FL=max(FL,d[i].L);
FR=min(FR,d[i].R);
}
if(d[i].op[0]=='o'&&d[i].op[1]=='n'){
FL-=max(d[i].R,d[i].L);
FR-=min(d[i].L,d[i].R);
}
if(d[i].op[1]=='f'){
FL+=min(d[i].L,d[i].R);
FR+=max(d[i].R,d[i].L);
}
}
printf("%d %d\n",max(FL,0),FR);

for(int i=fe;i<=N;i++){
if(d[i].op[0]=='o'&&d[i].op[1]=='n'){
EL+=min(d[i].L,d[i].R);
ER+=max(d[i].L,d[i].R);
}
if(d[i].op[1]=='f'){
EL-=max(d[i].R,d[i].L);
ER-=min(d[i].L,d[i].R);
}
if(d[i].op[0]=='n'){
EL=max(EL,d[i].L);
ER=min(ER,d[i].R);
}
}
printf("%d %d",max(EL,0),ER);
fclose(stdin);
fclose(stdout);
return 0;
}

Paint

Description

​ $Todobe$要把她的寝室弄得漂漂酿酿,所以她管$Yashem66$要了一些墙纸。

​ $Todobe$有一面墙,可分为n块,$Yashem66$提供的所有墙纸都是统一规格的,均只可覆盖连续k块完整的墙面,但是有m种不同的颜色的墙纸,每种颜色的墙纸都有无限张。$Todobe$要用这些墙纸把墙贴满,墙纸不可以裁剪,墙纸与墙纸之间可以有重叠部分。当墙纸重叠时,只能看到最外层的墙纸颜色。

​ $Todobe$想知道她以不同的方式贴墙纸,共能贴出多少种不同配色方案的墙面,两种方案不同当且仅当两种方案中至少有一块墙面的颜色不同。

Input

输入一行3个整数n,m,k。

Output

输出一行一个整数代表方案数量,答案取模$1e9+7$

Analysis

这一道题目很不好想,首先,对于$N$个块,$M$个颜色,一共有$M^N$种方案,然后通过模拟可以发现,这里面肯定有一个连续K个块是同一个颜色的,这就好了,联想到核电站问题的做法就可以了.但是因为数据范围很大,所以要用到矩阵乘法来优化,注意快速幂要开$long;long$否则会出错

Codes

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll mod=(ll)1e9+7;
int N,M,K;
ll A[105][105];

ll qkpow(ll d,ll p){
ll res=1;
while(p){
if(p&1)res=(res*d)%mod;
d=(d*d)%mod;
p>>=1;
}
return res;
}

void mul(ll *a,ll (*b)[105]){
ll tmp[105];
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=K-1;i++)
for(int j=1;j<=K-1;j++)
(tmp[i]+=(a[j]*b[j][i]))%=mod;
memcpy(a,tmp,sizeof(tmp));
}

void mulslf(ll (*a)[105]){
ll tmp[105][105];
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=K-1;i++){
for(int j=1;j<=K-1;j++){
for(int k=1;k<=K-1;k++){
(tmp[i][j]+=a[i][k]*a[k][j])%=mod;
}
}
}
memcpy(a,tmp,sizeof(tmp));
}

ll mtrqkpow(int p){
ll f[105];
memset(f,0,sizeof(f));
f[K-1]=M;
for(int i=K-2;i>=1;i--){
f[i]=(f[i+1]*M)%mod;
}

while(p){
if(p&1)mul(f,A);
mulslf(A);
p>>=1;
}
return f[1];
}


int main(){
freopen("paint.in","r",stdin);
freopen("paint.out","w",stdout);
scanf("%d%d%d",&N,&M,&K);
ll res1=qkpow(M,N);//总的可能性
for(int i=1;i<=K-1;i++){
A[i][1]=M-1;
A[i][i+1]=1;
}
printf("%lld",(((res1-mtrqkpow(N-K+1))%mod)+mod)%mod);
fclose(stdin);
fclose(stdout);
return 0;
}

Airline

Description

​ $Todobe$Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000),编号为1到T。这些城镇之间通过R条道路 (1 <= R <= 50,000,编号为1到R) 和P条航线 (1 <= P <= 50,000,编号为1到P) 连接。每条道路i或者航线i连接城镇$A_i$ (1 <= $A_i$ <= T)到$B_i$ (1 <= $B_i$ <= T),花费为$C_i$。对于道路,0 <= $C_i$ <= 10,000;然而航线的花费很神奇,花费$C_i$可能是负数(-10,000 <= $C_i$ <= 10,000)。道路是双向的,可以从$A_i$到$B_i$,也可以从$B_i$到$A_i$,花费都是$C_i$。然而航线与之不同,只可以从$A_i$到$B_i$。事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策保证:如果有一条航线可以从$A_i$到$B_i$,那么保证不可能通过一些道路和航线从$B_i$回到$A_i$。由于$FJ$的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

Input

第1行:四个空格隔开的整数: T, R, P, and S ,第2到R+1行:三个空格隔开的整数(表示一条道路):$A_i$, $B_i$ 和 $C_i$, 第R+2到R+P+1行:三个空格隔开的整数(表示一条航线):$A_i$,$ B_i$ 和$ C_i$

Output

第1到T行:从S到达城镇i的最小花费,如果不存在输出”NO PATH”

Analysis

题目分析

你以为这是一道$SPFA$水题?至少我当时是这么以为的,但是这一道题要卡你的$SPFA$所以说直接来就会爆,因此必须要想办法来优化

SLF优化

这一个$SLF$优化说起来并不难,它将原来的队列转换成为了双端队列,对于加入的点$v$,如果说$dist[v]<=dist[Q.top()]$,那么就把这个点放在队列的顶部,反之则将这个点放在最后面

Codes

#include<bits/stdc++.h>
#define maxn 25005
#define maxe 50005
#define Int64 long long
#define max(x,y) (x>y)?x:y
#define min(x,y) (x<y)?x:y
using namespace std;

int head[maxn],to[maxe<<2],nxt[maxe<<2],wel[maxe<<2],tot=0;;
Int64 dis[maxn];int N,R,P,S;bool vis[maxn];
int dfn[maxn],low[maxn],dfst=0,stk[maxn],top=0;
int block[maxn],cnt=0;

template<typename t>inline void read(t &x){
x=0;int sign=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')sign=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
x*=sign;
}

inline void add(int x,int y,int z){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
wel[tot]=z;
}

void tarjan(int u){
dfn[u]=low[u]=++dfst;
stk[++top]=u;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!block[v]){
low[u]=min(dfn[v],low[u]);
}
}
if(low[u]==dfn[u]){
block[u]=++cnt;
while(stk[top]!=u){
block[stk[top]]=cnt;
top--;
}
top--;
}
}

void SPFA(int R,int w){
deque<int>D;
dis[R]=w;
vis[R]=true;
D.push_front(R);
while(!D.empty()){
int u=D.front();D.pop_front();
vis[u]=false;
for(int i=head[u];i;i=nxt[i]){
int v=to[i],w=wel[i];
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
if(D.size()&&dis[v]<=dis[D.front()])D.push_front(v);
else D.push_back(v);
vis[v]=true;
}
}
}
}
}


int main(){
#ifndef ONLINE_JUDGE
freopen("airline.in","r",stdin);
freopen("airline.out","w",stdout);
#endif
read(N);read(R);read(P);read(S);
for(int i=1;i<=R;i++){
int x,y,z;read(x);read(y);read(z);
add(x,y,z);add(y,x,z);
}
for(int i=1;i<=P;i++){
int x,y,z;read(x);read(y);read(z);
add(x,y,z);
}

tarjan(S);

memset(dis,0x3f,sizeof(dis));
SPFA(S,0);

for(int i=1;i<=N;i++){
if(dis[i]==0x3f3f3f3f3f3f3f3fl)printf("NO PATH\n");
else printf("%lld\n",dis[i]);
}

fclose(stdin);
fclose(stdout);
return 0;
}