Burnling's Blog
0%

220908 总结

发表于 更新于

预计：$100+100+?$

实际：$90+10+30$

T1 Z 君的密码

一道巨简单的模拟

开始理解错题意了以为是字符映射那样子

但是看了看样例发现相同字符对应的字符不一样…

重读题，跟着样例才明白，是该组内的字符在原串的位置的移动

T1 写了 45min 不知道说点什么好了（

乐了 因为测试文件读写的时候写错文件名没结果所以把 scanf/printf 换成了 cin/cout ，导致最后 TLE 了一个点 关了流同步就过了

T2 保护费

令 $\text{protected}$ 的道路边权为 $0$ ，$\text{unprotected}$ 的道路边权为 $1$

由于这是一棵树，所以可以保证从 $1$ 号城市开始可以把所有城市都经过恰好一次。

显然如果到某个城市是不安全的话应该缴纳离 $1$ 号城市最近的危险边的保护费。

那么就可以从 $1$ 号城市进行 DFS ，

如果当前城市到达下一个城市是不安全的，那么缴纳当前边的保护费并将该边修改为 $\text{protected}$

但是这个思路并不是正确的，无法正确解答如下图的情况

graphpng

正解是 DFS 的同时维护经过的所有危险边，如果当前点是不安全的，则将队列中第一条边缴纳保护费并移出队列（因为危险边在队列中的顺序即为离 $1$ 号城市的远近）

由于交保护费是需要队列头出队，DFS 回溯需要从队尾删边，所以最好使用双端队列。

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
#include<bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 10;

struct Edge {
    int u, v, sf;
    Edge(int u, int v, int w): u(u), v(v), sf(w) {};
    friend bool operator == (Edge A, Edge B) {
        return A.u == B.u && A.v == B.v;
    }
};

vector<Edge> G[maxN];

int N, E;

int cnt;

deque<Edge> Q;

void dfs(int k, int fa, int dep) {
    while (dep < int(Q.size()) << 1) {
        Q.pop_front();
        cnt++;
    }
    for (auto i : G[k]) {
        if (i.v == fa) continue;
        if (i.sf == 1) Q.push_back(i);
        dfs(i.v, k, dep + 1);
        if(!Q.empty() && Q.back() == i) Q.pop_back();
    }
}

char S[50];

int main() {
    freopen("protect.in", "r", stdin);
    freopen("protect.out", "w", stdout);

    scanf("%d%d", &N, &E);
    for (int i = 1; i < N; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        scanf("%s", S);
        int us = S[0] == 'u';
        G[u].push_back(Edge(u, v, us));
        G[v].push_back(Edge(v, u, us));
    }
    dfs(1, 0, 0);

    printf("%lld", 1ll * cnt * E);
    return 0;
}

T3 疏导交通

当大模拟做的

先用四个方向的优先队列输入车辆信息并自动按到达时间排序。

对于每个时间 $t$ ，先将当前时刻能到达的车分别放入四个方向的等待队列

然后检查四个方向等待队列内的车的数量并找到最大值

那么这一秒就应该开等待车数最多的方向的红绿灯

每秒每个单向只能放走一辆车。

放完车后，统计四个方向等待队列的车的数量 $s$ ，这一秒每辆车等待 $1s$ ，总等待用时增加 $s$ 秒

然后检查四个方向的车辆数

然后就只得了 $30$ pts /kel

正解是五维 dp

看了 !樱雪! 神仙的码 直接大受震撼

牺牲一点性能换来了更高的可读性（然后就明白了应该怎么转移

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
103
104
#include<bits/stdc++.h>
using namespace std;

#define openNS (!(nextNextNum[1]>L||nextNextNum[2]>L||nextNum[3]>L||nextNum[4]>L))
#define openWE (!(nextNum[1]>L||nextNum[2]>L||nextNextNum[3]>L||nextNextNum[4]>L))

const int maxN = 210;
const int maxL= 6;
const int maxT = 70;
const int INF = 0x7f7f7f7f;

int N,L;

int cnc(char c){
	if(c == 'N') return 1;
	if(c == 'S') return 2;
	if(c == 'W') return 3;
	return 4;
}

struct Car{
	int from,t;
	
	Car(){};
	Car(char fro,int t):from(cnc(fro)),t(t){};
	
	friend bool operator < (Car A,Car B){
		return A.t < B.t;
	}
}C[maxN];

int dp[maxT][maxL][maxL][maxL][maxL];

int waitingNum[maxL];//四个方向等待车数
int nextNum[maxL];//四个方向来车后的等待车数
int nextNextNum[maxL];//四个方向来车后走了一辆的等待车数

int main(){
	freopen("traffic.in","r",stdin);
	freopen("traffic.out","w",stdout);
	
	scanf("%d%d",&N,&L);
	
	for(int i = 1;i<=N;i++){
		getchar();
		int T;
		char X;
		scanf("%c%d",&X,&T);
		C[i] = Car(X,T);
	}
	sort(C+1,C+1+N);

	memset(dp,0x7f,sizeof(dp));
	dp[0][0][0][0][0] = 0;
	
	int p = 1;
	
	for(int t = 1;t<=60;t++){
		memset(waitingNum,0,sizeof(waitingNum));
		while(C[p].t == t){
			waitingNum[C[p].from]++;
			p++;
		}
		
		for(int i = 0;i<=L;i++)
		for(int j = 0;j<=L;j++)
		for(int k = 0;k<=L;k++)
		for(int l = 0;l<=L;l++){
			if(dp[t-1][i][j][k][l] == INF) continue;
			
			int Tt[] = {0,i,j,k,l};
			for(int r = 1;r<=4;r++){
				nextNum[r] = Tt[r] + waitingNum[r];
				nextNextNum[r] = max(nextNum[r]-1,0);
			}
			if(openNS){
				int a = nextNextNum[1];
				int b = nextNextNum[2];
				int c = nextNum[3];
				int d = nextNum[4];
				dp[t][a][b][c][d] = min(dp[t][a][b][c][d],dp[t-1][i][j][k][l]+a+b+c+d);
			}
			if(openWE){
				int a = nextNum[1];
				int b = nextNum[2];
				int c = nextNextNum[3];
				int d = nextNextNum[4];
				dp[t][a][b][c][d] = min(dp[t][a][b][c][d],dp[t-1][i][j][k][l]+a+b+c+d);
			}
		}
	}
	
	int mi = INF;
	for(int i = 0;i<=L;i++)
	for(int j = 0;j<=L;j++)
	for(int k = 0;k<=L;k++)
	for(int l = 0;l<=L;l++){
		mi = min(mi,dp[60][i][j][k][l]);
	}
	
	if(mi == INF) printf("No solution");
	else printf("%d",mi);
	return 0;
}

总结

  • “反正样例过了” 的心态不可取，应该主动思考算法是不是假了

  • 远离没关流同步的 cin/cout ，会变得不幸

  • 想用贪心首先要考虑能不能找到不适用贪心的证据，找不到再用