The Second Test
死亡回放 比赛时间线
- 6:38 打开题面
- 发现前 4 题原题我都押对了！
qwq - 光速开始写
T1 第二饭堂 - 约 6:50 写完了
T1 第二饭堂第一版代码但是样例没过 - 约 7:00 在紧张中往
T1 第二饭堂第一版代码中多加了个转移数组，然后过了样例 - 然后开始写
T2 飞行路线，因为这是我唯一一道完全是自己想、自己写过的蓝题所以印象特别深刻 - 约 7:15 一遍过掉样例，但总感觉原题目是双向边但给的题面没说清，然后就去问了老师
- 然后就先去写
T3 最大半连通子图 - 约 7:30 写掉第一版代码，发现缩点缩炸了
- 约 7:35 改掉了缩点BUG，然后样例输出了
3 2 - 之前 wsr 输出这个样例之后就再也没有调出来
- 所以我有点崩溃
qwq - 但是在 7:40 的时候我调对啦！最后拓扑求答案的时候有个转移忘了写力！
qwq - 然后开始写
T4 种树 - 约 8:00 在我零碎的记忆中终于把差分约束的边建对来了，样例也就过了
- 然后就得到了
T2 飞行路线的路线都是双向边 - 剩下一个小时都在打
T6 JOIOJI的 20\% 的暴力（奇迹般地拿了 40\%qwq） - 全场最错误的选择：没有去骗
T5 染色的分！！！
死因分析 错误点分析
- 没有去骗
T5的分！ 后面的时间其实挺充足的但是都在摸鱼qwq - 没有去推
T6的式子！ cym 推了式子之后就把T6给过了awa
死亡证明 成绩
遗书 各题错误思路 & 正解
T1 第二饭堂
由于一饭班长表示各种鸭梨，美丽的纪中决定历史性地启用第二饭堂。
而部分领导觉得，二饭依山傍水，环境优美，未免有不和谐的事情（你懂的）发生，决定到二饭巡视同学们用餐时的就座情况。
为了应付这一情况，同学们决定联合起来“布阵”。
方便起见，同学们已经把座位情况抽象成一个长度为n的仅含数字及字母的字符串，他们想请你帮忙算算这个字符串的和谐程度。
已知一个字符串被称为k-回文串的充要条件是它自身是回文串，并且它长为⌊n/2⌋（下取整）的前缀和后缀是（k-1）-回文串。根据定义，任意字符串
（包括空串）都是0-回文串。
一个字符串的回文度数就是这个字符串的k的最大值。
而对于一个给定的字符串，它的和谐程度就是其所有前缀的回文度数之和。
你的任务就是算出这个和谐程度具体是多少。
正解
-
分别记录两个字符串哈希值，一个记录正着的，一个记录反着的
-
从 1 到 n 扫一遍，如果正反两个哈希值相等则可以更新答案
-
当天的笔记：day 9 拓扑排序和哈希笔记
#include<bits/stdc++.h> #define ll unsigned long long using namespace std; const int maxn = 5000005,BASE = 27; char s[maxn]; int n; ll p = 0,t = 0,e = 1; long long f[maxn],g[maxn]; int main() { scanf("%s",s + 1); n = strlen(s + 1); for (int i = 1;i <= n;i ++) { p = p * BASE + s[i], t = t + s[i] * e, e *= BASE; if (p == t) f[i] = f[i >> 1] + 1; g[i] = g[i - 1] + f[i]; } printf("%lld",g[n]); return 0; }
T2 JLOI2011 飞行路线
爱丽丝和鲍勃现在乘飞机旅行，他们选择了一个相对便宜的航空公司。该航空公司在 n 个城市提供服务。这些城市标记为 0 到 n-1 ，并且有m种类型的路线。每条路线连接两个城市，路线有一定的价格。爱丽丝和鲍勃现在正沿着这条路从一个城市前往另一个城市，并且可以在途中进行过境。航空公司还为他们的旅行提供折扣，他们可以乘坐 k 条免费路线。那么 Alice 和 Bob 的旅行的最低费用是多少？
正解
-
注意：此题的路线为双向边，建议去洛谷上看
-
这题在洛谷上是个蓝题但是我徒手切爆力
qwq -
设 dp[i][j] 表示走到 i 城市，消耗 j 条免费路线的最小代价
-
初始化 dp[i][0] = dis[i] ，其中 dis[i] 表示从起点到 i 城市的最短路
-
转移的时候枚举 k ，假设当前点为 v ，从 u 点进行转移， (u,v) 之间的连边的代价为 w(u\to v)
-
转移方程为：
dp[v][k] = \min(dp[u][k - 1],dp[u][k] + w(u\to v)) -
初始化和转移的过程都可以用最短路进行维护
-
最后答案从 dp[t][0\to k] 中取最小值，其中 t 表示终点
-
当天的笔记：day10 最短路
#include<bits/stdc++.h> #define type pair<int,int> #define mk make_pair using namespace std; const int maxn = 100005; int n,m,k,s,t,f[maxn][15]; vector<type> mp[maxn]; bool vis[maxn]; void addEdge(int u,int v,int w) { mp[u].push_back(mk(v,w)); } void Init() { priority_queue<type,vector<type>,greater<type> > q; q.push(mk(0,s)); memset(f,0x3f,sizeof(f)); f[s][0] = 0; while (!q.empty()) { type top = q.top(); q.pop(); int u = top.second; vis[u] = true; for (auto v : mp[u]) if (f[v.first][0] > f[u][0] + v.second) { f[v.first][0] = f[u][0] + v.second; if (!vis[v.first]) q.push(mk(f[v.first][0],v.first)); } } } void Dijkstra() { priority_queue<type,vector<type>,greater<type> > q; q.push(mk(0,s)); memset(vis,false,sizeof(vis)); while (!q.empty()) { type top = q.top(); q.pop(); int u = top.second; vis[u] = true; for (auto v : mp[u]) for (int p = 1;p <= k;p ++) if (f[v.first][p] > min(f[u][p - 1],f[u][p] + v.second)) { f[v.first][p] = min(f[u][p - 1],f[u][p] + v.second); if (!vis[v.first]) q.push(mk(f[v.first][p],v.first)); } } } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); for (int i = 1,u,v,w;i <= m;i ++) { scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } Init(); Dijkstra(); int ans = 0x3f3f3f3f; for (int i = 0;i <= k;i ++) ans = min(ans,f[t][k]); printf("%d",ans); return 0; }
T3 最大半连通子图
正解
-
先把所有的强连通分量缩成一个点并记录大小，因为一个强连通分量中的点要么都在最大半连通子图里，要么都不在（自己体会一下
qwq -
然后就可以在拓扑的时候 dp 计算答案
-
设 f,g 分别表示最大半连通子图的大小，和最大半连通子图的数量
-
初始化 f[i] = siz[i],g[i] = 1 其中 siz[i] 表示编号为 i 的强连通分量的大小
-
假设当前点为 v ，从 u 点进行转移
-
如果 f[u]+siz[v]>f[v] ，则
f[v]=f[u]+siz[v],g[v]=g[u] -
如果 f[u] + siz[v] = f[v]，则
g[v] = g[v] + g[u]
-
-
最后答案从每个强连通分量里去求
-
当天的笔记：day 11 强连通等
#include<bits/stdc++.h> #define mk make_pair using namespace std; const int maxn = 1e5 + 5,maxm = 1e6 + 5; int n,m,P,dfn[maxn],low[maxn],tot,top,d[maxn],st[maxm],b[maxn],siz[maxn],cnt; bool vis[maxn]; vector<int> mp[maxn]; vector<int> nmp[maxn]; vector<pair<int,int> > e; int f[maxn],g[maxn]; void addEdge(int u,int v) { mp[u].push_back(v); } void addnewEdge(int u,int v) { nmp[u].push_back(v); d[v] ++; } void Tarjan(int u) { dfn[u] = low[u] = ++ tot, st[++ top] = u, vis[u] = true; for (auto v : mp[u]) if (!dfn[v]) { Tarjan(v); low[u] = min(low[u],low[v]); } else if (vis[v]) low[u] = min(low[u],dfn[v]); if (dfn[u] == low[u]) { siz[++ cnt] = 1, b[u] = cnt; while (st[top] != u) siz[cnt] ++, b[st[top]] = cnt, vis[st[top]] = false, top --; vis[u] = false, top --; } } void Solve() { queue<int> q; for (int i = 1;i <= cnt;i ++) { f[i] = siz[i], g[i] = 1; if (d[i] == 0) q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); for (auto v : nmp[u]) { d[v] --; if (f[v] < f[u] + siz[v]) g[v] = g[u], f[v] = f[u] + siz[v]; else if (f[v] == f[u] + siz[v]) g[v] = (g[u] + g[v]) % P; if (d[v] == 0) q.push(v); } } } void build() { for (int u = 1;u <= n;u ++) for (auto v : mp[u]) if (b[u] != b[v]) e.push_back(mk(b[u],b[v])); sort(e.begin(),e.end()); int i = 0; for (auto E : e) { int u = E.first, v = E.second; if (i > 0 && u == e[i - 1].first && v == e[i - 1].second) { i ++; continue; } addnewEdge(u,v); i ++; } } int main() { scanf("%d%d%d",&n,&m,&P); for (int i = 1,u,v;i <= m;i ++) { scanf("%d%d",&u,&v); addEdge(u,v); } for (int i = 1;i <= n;i ++) if (!dfn[i]) Tarjan(i); build(); Solve(); int pos = 0,ans = 0; f[0] = -1; for (int i = 1;i <= cnt;i ++) if (f[i] > f[pos]) pos = i, ans = g[i]; else if (f[i] == f[pos]) ans = (ans + g[i]) % P; printf("%d\n%d",f[pos],ans); return 0; }
T4 种树
为了绿化乡村，H村积极响应号召，开始种树了。
H村里有 n 幢房屋，这些屋子的排列顺序很有特点，在一条直线上。于是方便起见，我们给它们标上 1\to n 。树就种在房子前面的空地上。
同时，村民们向村长提出了 m 个意见，每个意见都是按如下格式：希望第 l_i 个房子到第 r_i 个房子的房前至少有 c_i 棵树。
因为每个房屋前的空地面积有限，所以每个房屋前最多只能种 k_i 棵树。
村长希望在满足村民全部要求的同时，种最少的树以节约资金。请你帮助村长。
正解
-
对前缀和数组建立差分约束系统
-
总共有三个约束：（设前缀和数组为 sum ）
- sum[r]-sum[l-1]\ge c
- sum[i]-sum[i-1]\ge0
- sum[i-1]-sum[i]\ge -k
-
把边建完之后跑最长路即可
-
当天的笔记：day10 最短路
#include<bits/stdc++.h> #define mk make_pair #define type pair<int,int> using namespace std; const int maxn = 500005; int n,m,tree[maxn]; vector<type> mp[maxn]; bool vis[maxn]; int dis[maxn]; void addEdge(int u,int v,int w) { mp[u].push_back(mk(v,w)); } void SPFA() { queue<int> q; q.push(1); memset(dis,-0x3f,sizeof(dis)); dis[1] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (auto v : mp[u]) if (dis[v.first] < dis[u] + v.second) { dis[v.first] = dis[u] + v.second; if (!vis[v.first]) { vis[v.first] = true; q.push(v.first); } } } } int main() { scanf("%d%d",&n,&m); for (int i = 1,x;i <= n;i ++) { scanf("%d",&x); tree[i] = tree[i - 1] + x; addEdge(i + 1, i,-x); addEdge(i,i + 1,0); } addEdge(0,1,0); for (int i = 1,u,v,k;i <= m;i ++) { scanf("%d%d%d",&u,&v,&k); addEdge(u,v + 1,k); } SPFA(); printf("%d",dis[n + 1]); return 0; } // OHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
T5 区间染色
假设你现在有一块白板，想要仿照着一幅简单的油画进行创作。这个油画比较特殊，它将画板分成了 n 个区间，每个区间都画了不同的颜色。使用笔刷一次可以将任意长度的区间刷成同样的颜色。后刷的颜色会覆盖先刷的颜色。现在你想知道最少要多少次可以画出这幅简单的油画。
错误思路
-
完全不知道暴力怎么打就直接
不可以，总司令
-
qwq#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n,ans = 1,a[maxn]; char s[maxn]; int main() { scanf("%s",s + 1); printf("%d",ans); return 0; }
正解
-
区间 dp ，设 f[i][j] 表示把 [i,j] 区间刷成一种颜色的最小代价
-
初始化 f[i][j] =+\infty,f[i][i] = 1
-
假设当前枚举的区间为 [i,j] ，区间内一点为 k ，从小区间往大区间计算，则转译为：
f[i][j] = \min(f[i][k]+f[k + 1][j],f[i][j]) -
如果 s[i] 与 s[j] 相等（ s 为原字符串），则
f[i][j] = \min(f[i][j - 1],f[i + 1][j]) -
答案即为 f[1][n] ，其中 n 为 s 的长度
#include<bits/stdc++.h> using namespace std; const int maxn = 505; const int inf = 0x3f3f3f3f; char s[maxn]; int f[maxn][maxn],len; int main() { scanf("%s",s + 1); len = strlen(s + 1); memset(f,0x3f,sizeof(f)); for (int i = 1;i <= len;i ++) f[i][i] = 1; for (int l = 1;l <= len;l ++) for (int i = 1,j = l + 1;j <= len;i ++,j ++) { if (i == j) continue; for (int k = i;k < j;k ++) f[i][j] = min(f[i][k] + f[k + 1][j],f[i][j]); if (s[i] == s[j]) f[i][j] = min(f[i][j - 1],f[i + 1][j]); } printf("%d",f[1][len]); return 0; }
T6 JOIOJI
JOIOJI 桑是 JOI 君的叔叔。JOIOJI 这个名字是由 J, O , I 三种字母各两个构成的。
最近，JOIOJI 桑喜当爹。JOIOJI 桑想让自己孩子的名字和自己一样由 J , O, I 三种字母构成，并且想让 J , O, I 三个字母的出现次数恰好相同。
JOIOJI 桑家有一份祖传的卷轴，上面写着一首长诗 S ，长度为 N ，由 J , O, I 三种字母组成。JOIOJI 桑想用诗中最长的满足要求的连续子串作为孩子的名字。
现在 JOIOJI 桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的 J , O , I 三种字母的连续子串。
错误思路
-
瞅着这 20\% 的暴力分我很馋啊！
-
然后就打了个暴力，奇迹般地拿了 40\%
qwq#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n,ans,a[maxn]; char s[maxn]; int main() { scanf("%d",&n); scanf("%s",s + 1); for (int len = 1;len <= n;len ++) { a['J'] = a['O'] = a['I'] = 0; for (int i = 1;i <= len;i ++) a[s[i]] ++; for (int i = 1,j = i + len - 1;j <= n;i ++,j ++) { if (a['J'] == a['O'] && a['O'] == a['I']) { ans = len; break; } a[s[i]] --, a[s[j + 1]] ++; } } printf("%d",ans); return 0; }
正解
-
cym 神犇的思路：
sJ[j]-sJ[i-1]=sO[j]-sO[i-1]=sI[j]-sI[i-1]
减 sJ[j]-sJ[i-1]
sJ[j]-sO[j]-(sI[i-1]-sO[i-1])=sI[j]-sJ[j]-(sI[i-1]-sJ[i-1])，
x[i]=sO[i]-sJ[i],y[i]=sI[i]-sJ[i]
x[i-1]=x[j] 且 y[i-1]=y[j]
如果当前字符是“J”，s1[i]=s1[i-1]+1 ，s2[i],s3[i] 不变 则 x[i]=x[i-1]-1,y[i]=y[i-1]-1;
如果当前字符是“O”，即 s2[i]=s2[i-1]+1 ，s1[i],s3[i] 不变 则$x[i]=x[i-1]+1,y[i]=y[i-1] $;
如果当前字符是“I”，即 s3[i]=s3[i-1]+1 ，s1[i],s2[i] 不变 则$x[i]=x[i-1],y[i]=y[i-1]+1$;
令一个点 i 为 (x[i],y[i]) 点权为 i 相当于查询最大的相同位置的差 快排一下扫一遍 -
自己对着代码意会一下吧 qwq#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n, j[maxn], o[maxn], I[maxn], ans; char c; map<int, map<int, int> > joi; int main() { scanf("%d", &n); getchar(); for (int i = 1; i <= n; i ++) { c = getchar(); if (c == 'J') j[i] = 1; if (c == 'O') o[i] = 1; if (c == 'I') I[i] = 1; } for (int i = 1; i <= n; i ++) j[i] = j[i - 1] + j[i], o[i] = o[i - 1] + o[i], I[i] = I[i - 1] + I[i]; for (int i = 1; i <= n; i ++) if (!joi[j[i] - o[i]][o[i] - I[i]]) joi[j[i] - o[i]][o[i] - I[i]] = i; else ans = max(ans, i - joi[j[i] - o[i]][o[i] - I[i]]); for (int i = 1; i <= n; i ++) if (j[i] == o[i] && o[i] == I[i]) ans = max(ans, i); printf("%d", ans); return 0; }
葬礼 总结
- 至少比上次好
qwq - 然后会做的题分都拿到了
投胎转世 目标
- 如果下次还是原题的话那在保持原题都能过的情况下多过一道题
各位dalao给蒟蒻一个赞呗，写这个总结真的不容易 qwq
