20190723的test

20190723的test

九月 05, 2021

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//正反各自扫一遍?过程中求交集和加减?  
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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;
}
  1. 1. Traffic
    1. 1.1. Description
    2. 1.2. Input
    3. 1.3. Output
    4. 1.4. Analysis
    5. 1.5. Codes
  2. 2. Paint
    1. 2.1. Description
    2. 2.2. Input
    3. 2.3. Output
    4. 2.4. Analysis
    5. 2.5. Codes
  3. 3. Airline
    1. 3.1. Description
    2. 3.2. Input
    3. 3.3. Output
    4. 3.4. Analysis
      1. 3.4.1. 题目分析
      2. 3.4.2. SLF优化
    5. 3.5. Codes