摸了一个寒假的鱼，赛前各种被奶，就感觉自己要凉，我的感觉向来是对的，结果真的凉透了QAQ。
开场就是裸题各种bug各种WA，心态爆炸，确实还是造成了不小的影响。后面真的怀疑人生到不想写，挂机（然后被骂了orz）。我每次都控制不好比赛的心态和节奏唉_(:з」∠)_
比较意外的是小伙伴们和大佬们也emmmm 凉得挺厉害……跟学长们同时期是完全不能比的吧……直接造成了我们有个一周的contest补题……
补完之后的感受是……真的基本都是裸题。然而赛场上发挥正常最多也只是再出1题2题，很多地方都差临门一脚的感觉，前段时间死磕DP感觉会一点了，比赛的时候还是一个也没做出来= =。暴力又不敢打。补题暴力A的时候真是心情复杂……真的是明白了什么叫菜是原罪
下周ccf，下下周多校，下下下周C4和蓝桥杯，有几位新大佬我都没他们一半努力，我可能要抢救一下。
A. 灾区重建
题意：N个城市由M条道路互相连通，每条道路最大承重量是w，要选出一条从一个城市到达另外N-1个城市的路径使一次能承受的重量最大，求这个最大重量
数据范围：T组样例（T <= 10）, N <= 1e5, M <= 1e6, u,v <= N, w <= 1e9
思路：一条路径能承受的最大重量是这几条路w的最小值，连通N个节点只需要N-1条边，把所有边按从大到小排序，求出一棵最大生成树，最小的那条边就是答案
1 #include<cstdio>
2 #include<algorithm>
3 #define INF 0x3f3f3f3f
4 using namespace std;
5
6 const int mx = 1e6+10;
7 int pa[mx];
8
9 struct edge{
10 int u, v, w;
11 edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
12 bool operator < (const edge& a) const{
13 return w > a.w;
14 }
15 }e[mx];
16
17 int findset(int x){
18 return pa[x] == x ? x : pa[x] = findset(pa[x]);
19 }
20
21 int main(){
22 int t, kase = 0;
23 scanf("%d", &t);
24 while (t--){
25 for (int i = 0; i < mx; i++) pa[i] = i;
26 int n, m, u, v, w;
27 scanf("%d%d", &n, &m);
28 for (int i = 0; i < m; i++){
29 scanf("%d%d%d", &u, &v, &w);
30 e[i] = edge(u, v, w);
31 }
32 int ans = INF, sum = 0;
33 sort(e, e+m);
34 for (int i = 0; i < m; i++){
35 int a = findset(e[i].u), b = findset(e[i].v);
36 if (a != b){
37 pa[a] = b;
38 sum++;
39 ans = min(ans, e[i].w);
40 }
41 if (sum == n-1) break;
42 }
43 printf("Case #%d: %d\n", ++kase, ans);
44 }
45 return 0;
46 }
B. 洗衣
题意：durong有N件衣服要洗，洗衣机一次洗一件衣服，每件衣服只能在固定的一个区间内洗，问需要多少洗衣机
数据范围：1 <= N <= 1e5, 1 <= st < en <= 1e9
思路1：一道裸贪心，至少大佬们都觉得它裸，原题是POJ3190。挑战题单上是有这题的，但我拉了没刷= =。我是真的不会。诶，基础不牢。
首先为了方便遍历按开始时间从小到大排序。为了找出正确的贪心策略，先模仿人的思路：对于新拿到的一件衣服，尝试能不能放在空闲的洗衣机后面，能就更新洗衣机的结束时间，不能就新加洗衣机。
至于实现的方法，用一个优先队列维护每件衣服的结束时间即可。因为队列中的元素都是在洗衣机里的，重载小于号让结束时间早的优先，如果最早洗衣机的结束时间还晚于当前的开始时间，那就必须新开洗衣机了。
1 #include<cstdio>
2 #include<queue>
3 #include<algorithm>
4 using namespace std;
5
6 const int mx = 1e5+10;
7
8 struct Node{
9 int s, t;
10 bool operator < (const Node& a) const{
11 return t > a.t || (t == a.t && s > a.s);
12 }
13 }p[mx];
14
15 bool cmp(Node a, Node b){
16 return a.s < b.s || (a.s == b.s && a.t < b.t);
17 }
18
19 int main(){
20 int n;
21 while (scanf("%d", &n) == 1){
22 int ans = 1;
23 for (int i = 0; i < n; i++)
24 scanf("%d%d", &p[i].s, &p[i].t);
25 sort(p, p+n, cmp);
26 priority_queue<Node> q;
27 q.push(p[0]);
28 for (int i = 1; i < n; i++){
29 Node u = q.top();
30 if (p[i].s >= u.t) q.pop();
31 else ans++;
32 q.push(p[i]);
33 }
34 printf("%d\n", ans);
35 }
36 return 0;
37 }
另外不得不说，杜荣菊苣真有钱，洗衣机也多，衣服还有1e5件Σ(ﾟдﾟlll)
思路2：赛场上不会上面的贪心做法，倒是想到了等价于选择一个点在尽量多的区间内，需要用洗衣机的数量等于最多的重合区间数量，想到了线段树的染色问题。那么就是区间更新+查询最大值了。不过1e9的数据范围需要离散化，我还写得不熟练，比赛时我没带线段树板子，甚至连I题裸的区间更新都忘了，手推线段树，WA到我不敢写，这个思路就没在赛场上实现。补完这种做法以后再附代码，就当练下离散化了。
C. 先有durong后有天
题意：N个点M条无向边的连通图，在满足s1到e1的距离不大于t1，s2到e2的距离不大于t2的情况下，拆掉尽可能多的边，求拆掉的边数
数据范围：N <= 3000, N-1 <= M <= N*(N-1)/2
思路：原题codeforces 543B，我感觉我是不是打过这场……
不知道从哪下手，首先可以知道的是，如果不拆的距离都大于了题目要求，那就是-1，否则肯定有拆法（或不拆）。那么就考虑最短路，边权为1用bfs就可以搞了。
这里zz了一下，以前做bfs都是迷宫题，给的都是n*n的矩阵，习惯性觉得跑一遍bfs复杂度是O(n^2)，但其实这里是O(n)，N才只有3000个点……所以贼暴力的跑出每两个点的最短路就行了。
至于为什么要求出所有最短路，因为这两条路线分为有重合部分和没有重合部分的两种情况，想了好久也不知道怎么优雅的判断，最后发现暴力的判断重合部分两个端点最优雅了，n^2验证emm。
要注意的一点是只写成s1->i->j->e1，s2->i->j->e2是不行的，这样写有方向性，是默认s1->t1, s2->t2是一个方向，所以还要检查s2->j->i->e2是不是更小。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 #include<vector>
6 #define INF 0x3f3f3f3f
7 using namespace std;
8
9 const int mx = 3010;
10 vector<int> G[mx];
11 int d[mx][mx];
12
13 void bfs(int x){
14 queue<int> q;
15 q.push(x);
16 d[x][x] = 0;
17 while (!q.empty()){
18 int u = q.front(); q.pop();
19 int len = G[u].size();
20 for (int i = 0; i < len; i++){
21 int v = G[u][i];
22 if (d[x][v] > d[x][u]+1){
23 d[x][v] = d[x][u]+1;
24 q.push(v);
25 }
26 }
27 }
28 }
29
30 int main(){
31 int n, m, u, v;
32 while (scanf("%d%d", &n, &m) == 2){
33 for (int i = 0; i < mx; i++){
34 G[i].clear();
35 for (int j = 0; j < mx; j++)
36 d[i][j] = INF;
37 }
38 for (int i = 1; i <= m; i++){
39 scanf("%d%d", &u, &v);
40 G[u].push_back(v);
41 G[v].push_back(u);
42 }
43 int s1, e1, t1, s2, e2, t2;
44 scanf("%d%d%d", &s1, &e1, &t1);
45 scanf("%d%d%d", &s2, &e2, &t2);
46 for (int i = 1; i <= n; i++) bfs(i);
47 if (d[s1][e1] > t1 || d[s2][e2] > t2){
48 printf("-1\n");
49 continue;
50 }
51 int ans = d[s1][e1] + d[s2][e2];
52 for (int i = 1; i <= n; i++){
53 for (int j = 1; j <= n; j++){
54 int v0 = d[s1][i]+d[i][j]+d[j][e1];
55 int v1 = d[s2][i]+d[i][j]+d[j][e2], v2 = d[e2][i]+d[i][j]+d[j][s2];
56 if (v0 <= t1 && v1 <= t2) ans = min(ans, v0+v1-d[i][j]);
57 if (v0 <= t1 && v2 <= t2) ans = min(ans, v0+v2-d[i][j]);
58 }
59 }
60 printf("%d\n", m-ans);
61 }
62 return 0;
63 }
后来的新大佬和学弟学妹们（如果有），彪神出的先有durong后有天系列（现在有5题了）要慎做，比赛看到就别开了orz