2023ICPC亚洲区域赛(合肥)VP补题题解记录
文章目录
2023ICPC亚洲区域赛(合肥)VP补题题解记录写在前面已更新 E F G J B，待更新 I C F and E(签到题和简单题)G. Streak Manipulation题目大意题目分析ac代码参考 J. Takeout Delivering题目大意题目分析ac代码参考 B. Queue Sorting题目大意题目分析ac代码参考
写在前面
已更新 E F G J B，待更新 I C
比赛补题链接：Dashboard - The 2023 ICPC Asia Hefei Regional Contest (The 2nd Universal Cup. Stage 12: Hefei) - Codeforces
F and E(签到题和简单题)
F直接计数即可
ac代码参考(FastIO已省略)
def solve(): n = I() dic = {} for i in range(n): c = S() dic[c] = dic.get(c,0) + 1 mx = 0 ans = '' su = 0 for k,v in dic.items(): su += v if v > mx: mx = v ans = k print1(ans if mx > su/2 else "uh-oh")solve()E 分离 x 和 y。
ac代码参考
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e3+5;int n,m;map<int,int> mp;int cnt;int a[N][N];vector<int> nx[1000005];vector<int> ny[1000005];void solve(){cin>>n>>m;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin>>a[i][j]; }for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){int x=a[i][j];if(!mp[x])mp[x]=++cnt;int idx=mp[x];nx[idx].push_back(i);ny[idx].push_back(j);}ll ans=0;for(int i=1;i<=cnt;++i){ll sum=0;for(int j=0;j<nx[i].size();++j){ans-=sum;ans+=j*1ll*nx[i][j]; sum+=nx[i][j];}sum=0;sort(ny[i].begin(),ny[i].end());for(int j=0;j<ny[i].size();++j){ans-=sum;ans+=j*1ll*ny[i][j];sum+=ny[i][j];}}cout<<ans*2ll<<'\n';}int main(){ios::sync_with_stdio(false);cin.tie(0);int t=1;//cin>>t;while(t--)solve();return 0;} G. Streak Manipulation
题目大意
给你一个01串，告诉你串的长度 n ∈ [ 1 , 2 × 1 0 5 ] n\in[1,2\times10^5] n∈[1,2×105]，最多可操作次数 m ∈ [ 1 , n ] m\in[1,n] m∈[1,n], 以及 k ∈ min ( n , 5 ) k\in\min(n,5) k∈min(n,5)。每次操作可将一个 0 0 0 变为 1 1 1。要我们求，在不超过 m m m 次操作时，第 k k k 长的连续为 1 1 1 的串最长是多少。
题目分析
我们考虑二分答案，即二分在最多 m m m 次操作后，第 k k k 长的最小是多少(看到这个最大值最小的是不是很容易想到二分)。想想check函数怎么实现，注意到 k ∈ min ( n , 5 ) k\in\min(n,5) k∈min(n,5)。我们考虑dp，以当前是考虑前几个字符为阶段，与 前面有 j j j 个长度大于 m i d mid mid 的连续 1 1 1 串和当前字符是0还是1共同构成状态。对于当前的 m i d mid mid, 设 d p [ i ] [ j ] [ 0 / 1 ] dp[i][j][0/1] dp[i][j][0/1] 为前 i i i 个字符，有 j j j 段长度大于等于 m i d mid mid 的连续 1 1 1 串，且当前字符是否位于第 j j j 段连续 1 1 1 串的末尾（0为假1为真）所需的最少操作次数。考虑状态转移： 如果 s [ i ] = = ′ 0 ′ s[i] == '0' s[i]==′0′ d p [ i ] [ j ] [ 0 ] = m i n ( d p [ i ] [ j ] [ 0 ] , d p [ i − 1 ] [ j ] [ 0 ] , d p [ i − 1 ] [ j ] [ 1 ] ) dp[i][j][0] = min({dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1]}) dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0],dp[i−1][j][1]) d p [ i ] [ j ] [ 1 ] = m i n ( d p [ i ] [ j ] [ 1 ] , d p [ i − 1 ] [ j ] [ 1 ] + 1 ) dp[i][j][1] = min({dp[i][j][1], dp[i-1][j][1] + 1}) dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]+1) 否则： d p [ i ] [ j ] [ 0 ] = m i n ( d p [ i ] [ j ] [ 0 ] , d p [ i − 1 ] [ j ] [ 0 ] ) dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]) dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0]) d p [ i ] [ j ] [ 1 ] = m i n ( d p [ i ] [ j ] [ 1 ] , d p [ i − 1 ] [ j ] [ 1 ] ) dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1]) dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]) 此外在 i ≥ m i d a n d j ≥ 0 i\ge mid\ and \ j \ge0 i≥mid and j≥0 时 d p [ i ] [ j ] [ 1 ] = m i n ( d p [ i ] [ j ] [ 1 ] , d p [ i − m i d ] [ j − 1 ] [ 0 ] + p r e [ i ] − p r e [ i − m i d ] ) dp[i][j][1] = min(dp[i][j][1], dp[i-mid][j-1][0] + pre[i] - pre[i-mid]) dp[i][j][1]=min(dp[i][j][1],dp[i−mid][j−1][0]+pre[i]−pre[i−mid]) p r e pre pre 记录的是前缀中 0 0 0 的数量。总的时间复杂度为 O ( k n log ( n ) ) O(\ kn\log(n)\ ) O( knlog(n) )ac代码参考
#include <bits/stdc++.h>using namespace std;const int N = 2e5+5;int dp[N][6][2], pre[N];int n,m,k;string s;void solve(){auto check = [&](int mid){for (int i = 0; i <= n; i++)for(int j = 0; j <= k; j++)dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f;dp[0][0][0] = 0;for (int i = 1; i <= n; i++){for(int j = 0; j <= k; j++){if(s[i]=='0'){dp[i][j][0] = min({dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1]});dp[i][j][1] = min({dp[i][j][1], dp[i-1][j][1] + 1});}else{dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]);dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1]);}if (i >= mid && j >= 1)dp[i][j][1] = min(dp[i][j][1], dp[i-mid][j-1][0] + pre[i] - pre[i-mid]);}}return min(dp[n][k][0], dp[n][k][1]) <= m;};cin>>n>>m>>k>>s;s = "@" + s;for(int i = 1; i<=n; i++){pre[i] += pre[i-1] + (s[i] == '0');}int l = 0, r = 2e5;while (l < r){int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}if(l)cout<<l<<'\n';else cout << "-1\n";}int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;while (t--)solve();return 0;}J. Takeout Delivering
题目大意
给你一个无向连通图，定义最短路为 path 中最贵的两条边之和，只有一条边时就是边权。求1到n的最短路。
n ∈ [ 2 , 3 × 1 0 5 ] , m ∈ [ max ( 1 , n − 1 ) , 1 0 6 ] n\in[2,3\times10^5],m\in[\max(1,n-1),10^6] n∈[2,3×105],m∈[max(1,n−1),106]
题目分析
我们考虑枚举每条边 E d g e ( x , y , z ) Edge(x,y,z) Edge(x,y,z) 以该条边作为路径上的最大边权的边。考虑第二大边权的边在哪？一定在 p a t h ( 1 , x ) , p a t h ( y , n ) path(1,x),path(y,n) path(1,x),path(y,n) 或 p a t h ( 1 , y ) , p a t h ( x , n ) path(1,y),path(x,n) path(1,y),path(x,n)对于第二大边权的边，我们只需要预处理出从 1 1 1 和从 n n n 到各个点的最大边权即可。具体实现见代码，总的时间复杂度为 O ( m log m ) O(m\log m) O(mlogm)ac代码参考
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N=3e5+5;const int M=1e6+5;struct Edge{int x,y,z;}; int n,m,tot;int ver[M+M],head[N],edge[M+M],nxt[M+M];int d1[N],d2[N];bool vis[N];Edge ls[M];void solve(){auto add = [&](int x,int y,int z){ver[++tot]=y,edge[tot]=z;nxt[tot]=head[x],head[x]=tot;};auto dijkstra = [&](int st,int *dist){priority_queue<pair<int, int> > q;memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i)dist[i]=1e9+7;dist[st]=0;q.push({-0,st});while(!q.empty()){pair<int, int> tmp = q.top();q.pop();int x = tmp.second;if(vis[x]) continue; vis[x] = 1;for(int i=head[x];i;i=nxt[i]){int y=ver[i];int w=edge[i];if (dist[y] > max(dist[x], w)){dist[y] = max(dist[x], w);q.push({-dist[y], y});}}}};cin>>n>>m;for(int i=1;i<=m;++i){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);ls[i]={u,v,w};}dijkstra(1,d1);dijkstra(n,d2);int ans=2e9;for(int i=1;i<=m;++i){int x=ls[i].x,y=ls[i].y,z=ls[i].z;int tmp = min(max(d1[x],d2[y]), max(d1[y],d2[x]));if(tmp<=z)ans=min(ans,tmp+z);}cout<<ans<<'\n';}int main(){ios::sync_with_stdio(false);cin.tie(0);int t=1;while(t--)solve(); return 0;}B. Queue Sorting
题目大意
给一个可重数集， n n n ( 1 ≤ n ≤ 500 ) (1≤n≤500) (1≤n≤500) 有 a i a_i ai ( ∑ a i ≤ 500 ) (∑a_i≤500) (∑ai≤500) 个，问有多少序列符合能拆成最多两个不降子序列。
题目分析
根据 Dilworth 定理，最小链分解数等于最长反链长度，即最长下降子序列长度不能超过 2 。(类似比较经典的题目有如 拦截导弹)
我们现在问题变成了：有多少种不同的序列，它的最长下降子序列长度不能超过 2 。
考虑计数 DP 的方法，一开始构造一个空序列，接着将数字按从小到大的顺序插入到序列之中。
对于每次加入的数字 i i i ，只要不是最后一个，必定形成一个长度为 2 的下降子序列。
设 d p ( i , j ) dp(i,j) dp(i,j) 表示，数字 1 1 1∼ i i i 已经全部插入，最后一个长度为 2 的下降子序列靠前前的那个数字的位置是 j j j 。
令 s u m x = ∑ y ≤ x a y sum_x=∑_{y≤x}a_y sumx=∑y≤xay，每次 i + 1 i+1 i+1 插入的时候是不能放到位置 j j j 前面的，插在后面不改变最长下降子序列的长度，所以相当于对 [ j + 1 , s u m i ] [j+1,sum_i] [j+1,sumi] 和 a i + 1 a_{i+1} ai+1 个位置的组合。
状态转移要考虑新的 j ′ j′ j′ 的位置，所以枚举有 x x x 个 i + 1 i+1 i+1 直接加到最后了，第一个不是最后的位置是 k k k ，转移是:
d p ( i + 1 , k ) = ∑ j , x d p ( i , j ) × ( k − j − 1 a i + 1 − x − 1 ) dp(i+1,k)=\sum_{j,x}{dp(i,j)\times{\left( \begin{aligned} &\ \ \ k-j-1 \\ &a_{i+1}-x-1 \\ \end{aligned} \right)}} dp(i+1,k)=j,x∑dp(i,j)×( k−j−1ai+1−x−1)
ac代码参考
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;const int N = 507, mod = 998244353;int a[N], sum[N], dp[N][N], c[N][N];int n;void solve(){cin >> n;for(int i = 1; i <= n; i++) {cin>>a[i];sum[i] = sum[i - 1] + a[i];}c[0][0] = 1;for(int i = 1; i <= sum[n]; i++) {c[i][0] = 1;for(int j = 1; j <= i; j++) c[i][j] = (c[i][j] + c[i - 1][j - 1] + c[i - 1][j]) % mod;}dp[0][0] = 1;for(int i = 0; i < n; i++) for(int j = 0; j <= sum[i]; j++) if (dp[i][j]) {dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;for (int k = j + 1; k < sum[i + 1]; k++) { // 如果边界比较复杂，可以使用if 代替直接计算int lb = max(0, a[i + 1] - (k - j));int ub = min(a[i + 1] - 1, sum[i + 1] - k - 1);for(int x = lb; x <= ub; x++) dp[i + 1][k] = (dp[i+1][k] + (1ll * dp[i][j] * c[k - j - 1][a[i + 1] - x - 1] % mod)) % mod;}}int ans = 0;for(int i = 0; i <= sum[n]; i++) ans = (ans + dp[n][i]) % mod;cout<<ans<<'\n';}int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;while(t--)solve();return 0;}