CodeForces Round 545(div 2) 题解

跟个sb一样比赛链接 今天来改题了。

A

题意：找出最长的一段区间使得区间长度是偶数，且区间前一半只有一种数，后一半只有一种数。

\(a[i] \in [1,2], n \leq 100000\).

A solution

解：考虑分段。

举个例子：[1 2 2 1 2 2 2 1 1 2 1] 按相同的值分为一段之后就会变成 [1 | 2 2 | 1 | 2 2 2 | 1 1 | 2 | 1]

显然目标区间一定会在相邻的两个段里，正确性显然。 于是直接计算即可。

/** * @Author: Mingyu Li * @Date: 2019-03-08T17:07:17+08:00 * @Email: class11limingyu@126.com * @Filename: c1138A.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-09T09:16:10+08:00 */ #include <bits/stdc++.h> #define tpname typename #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } const int N = 100000 + 10; int pref[3][N] , suf[3][N]; int n , ans = 0 , t[N]; int main() { sc(n); Go(i,1,n) sc(t[i]); std::vector < int > v; int cnt = 1; Go(i , 2 , n+1) { if(t[i] != t[i - 1]) { v.push_back(cnt); cnt = 0; } cnt++; } Go(i , 0 , (int)v.size() - 2) ans = std::max(ans , std::min(v[i] , v[i + 1]) * 2); std::cout << ans << " \n"; return 0; }

B

题意：给定一张\(2\)行\(n\)列的表格\(A\).\(A[i][j]\)代表第\(j\)个人擅不擅长项目\(i\). 要求将\(n\)个人分成2组，每组\(n/2\)个人。（保证\(n\)是偶数）并满足第一组擅长项目1的人数=第二组擅长项目2的人数。 输出方案。\(n \leq 5000\).

B solution

解：下文中将默认\((i,j)\)为是否擅长项目1与项目2。 看起来好像很难下手，但是只需要枚举即可。 枚举第一组中\((1,0)\)的人数与\((1,1)\)的人数。

接着，第一组擅长项目1的人数就确定了，第二组\((1,1)\)的人数也确定了，那就可以确定第二组\((0,1)\)的人数了。 第二组确定了，第一组也能确定。 于是第一组的\((0,0)\)人数也确定了。第二组随之确定。 如果所有人数都合法就输出。如果没有任何一组人数合法，输出\(-1\).

/** * @Author: Mingyu Li * @Date: 2019-03-08T17:51:24+08:00 * @Email: class11limingyu@126.com * @Filename: c1138B.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-09T10:47:22+08:00 */ #include <bits/stdc++.h> #define tpname typename #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } int n; std::string a , b; std::vector < int > v00 , v01 , v10 , v11; int main() { v00.clear(); v11.clear(); v01.clear(); v10.clear(); std::cin >> n; std::cin >> a >> b; a = "%" + a; b = "%" + b; Go(i , 1 , n) { if(a[i] == '1' && b[i] == '1') v11.push_back(i); else if(a[i] == '0' && b[i] == '0') v00.push_back(i); else if(a[i] == '0' && b[i] == '1') v01.push_back(i); else if(a[i] == '1' && b[i] == '0') v10.push_back(i); } Go(s10 , 0 , (int)(v10.size())) Go(s11 , 0 , (int)(v11.size())) { if(s10 + s11 > n/2) continue; // 选完之后 剩下的s10和s11进入第二组 // 对答案有贡献的只有s11 int g2_s01 = s10 + 2 * s11 - (int)((int)(v11.size())); int g1_s01 = (int)(v01.size()) - g2_s01; if(g2_s01 >= 0 && g2_s01 <= (int)(v01.size())) { int g1_s00 = n/2 - g1_s01 - s10 - s11; if(g1_s00 >= 0 && g1_s00 <= (int)(v00.size())) { Go(i , 0 , s11 - 1) std::cout << v11[i] << " "; Go(i , 0 , s10 - 1) std::cout << v10[i] << " "; Go(i , 0 , g1_s01 - 1) std::cout << v01[i] << " "; Go(i , 0 , g1_s00 - 1) std::cout << v00[i] << " "; puts(""); return 0; } } } puts("-1"); return 0; }

C

给定一个\(n\times m\)大小的表格。 要求对于每一个位置\((i,j)\),求出\(ans(i,j)\). 其中\(ans(i,j)\)表示将第i行和第j列的某些数更改后使得在满足行内所有数相对大小关系不变，列内所有数相对大小关系不变的情况下，行列内最大值 的最小值。

\(n,m \leq 1000\). 时限2s.

C solution

解：发现除了\(a[i][j]\)一个交界点之外，行列之间是独立的。所以，只需要确定\(a[i][j]\)重新排列之后的排名即可。 这玩意很好确定。因为行列之间是独立的，所以答案就是

\[max(行内比a[i][j]小的数的种数,列内比a[i][j]小的数的种数)+1\]

同理，题目要求最小化最大值。由于行列独立，所以最大值的编号就是

\[a[i][j]排名+max(行内比a[i][j]大的数的种数,列内比a[i][j]大的数的种数)\]

这个东西可以每行每列一起预处理，复杂度\(\Theta(n^2 log(n))\).

/** * @Author: Mingyu Li * @Date: 2019-03-09T10:47:43+08:00 * @Email: class11limingyu@126.com * @Filename: c1138C.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-09T11:57:03+08:00 */ #include <bits/stdc++.h> #define tpname typename #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } const int N = 1000 + 10; int ans[N][N]; int n , m , it; int a[N][N] , b[N]; int ans1[N][N] , ans2[N][N] , big1[N][N] , big2[N][N]; int p = 0; int main() { sc(n , m); Go(i , 1 , n) Go(j , 1 , m) sc(a[i][j]); Go(i , 1 , n) { p = 0; Go(j , 1 , m) b[++p] = a[i][j]; std::sort(b + 1 , b + p + 1); p = std::unique(b + 1 , b + p + 1) - (b + 1); Go(j , 1 , m) { ans1[i][j] = std::lower_bound(b+1 , b+p+1 , a[i][j]) - b; big1[i][j] = p - ans1[i][j]; } } Go(i , 1 , m) { p = 0; Go(j , 1 , n) b[++p] = a[j][i]; std::sort(b + 1 , b + p + 1); p = std::unique(b + 1 , b + p + 1) - (b + 1); Go(j , 1 , n) { ans2[j][i] = std::lower_bound(b+1 , b+p+1 , a[j][i]) - b; big2[j][i] = p - ans2[j][i]; } } Go(i , 1 , n) { Go(j , 1 , m) printf("%d " , std::max(ans1[i][j] , ans2[i][j]) + std::max(big1[i][j] , big2[i][j])); puts(""); } return 0; }

D

给定只包含01的字符串\(s\)和\(t\)，重排列\(s\)字符串使得\(t\)在其中作为子串出现的次数最多。

\(|s|,|t| \leq 500000\).

D solution

首先考虑最优解一定长成什么样子——一定是一个t串加很多个小节，每加一个小节就会多产生一个\(t\)子串。 有了这部转化就很简单了。容易发现这个小节即为长度为\(|t|-border(t)\)的\(t\)串后缀。 能输出多少份输出多少份。\(border\)用\(KMP\)或\(Hash\)维护都可以（注意\(Hash\)被卡）

/** * @Author: Mingyu Li * @Date: 2019-03-09T12:54:42+08:00 * @Email: class11limingyu@126.com * @Filename: c1138D.cpp * @Last modified by: Mingyu Li * @Last modified time: 2019-03-09T22:14:16+08:00 */ #include <bits/stdc++.h> #define tpname typename #define Go(i , x , y) for(register int i = x; i <= y; i++) #define God(i , y , x) for(register int i = y; i >= x; i--) typedef long long LL; typedef long double ld; typedef unsigned long long ULL; template < tpname T > void sc(T& t) { char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();} while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x; } template < tpname T , tpname... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);} template < tpname T > T mul(T x , T y , T _) { x %= _,y %= _; return ((x * y - (T)(((ld)x * y + 0.5) / _) * _) % _ + _) % _; } const int N = 500000 + 5; const ULL P1 = 13331; const ULL P2 = 19260817; const ULL MOD1 = 314159; const ULL MOD2 = (1000000007); ULL Hash1[N] , Hash2[N] , pw1[N] , pw2[N]; int cnt[2] , cnt1[2] , n , m; char a[N + 5] , b[N + 5]; void Prework() { pw1[0] = pw2[0] = 1; Go(i , 1 , n) pw1[i] = pw1[i - 1] * P1 % MOD1 , pw2[i] = pw2[i - 1] * P2 % MOD2; Go(i , 1 , n) { Hash1[i] = (Hash1[i - 1] * P1 % MOD1 + b[i]) % MOD1; Hash2[i] = (Hash2[i - 1] * P2 % MOD2 + b[i]) % MOD2; } } bool same(int l1, int r1, int l2, int r2) { return ((Hash2[r2] + MOD2 - Hash2[l2 - 1] * pw2[r2 - l2 + 1] % MOD2) % MOD2 == (Hash2[r1] + MOD2 - Hash2[l1 - 1] * pw2[r1 - l1 + 1] % MOD2) % MOD2 && (Hash1[r2] + MOD1 - Hash1[l2 - 1] * pw1[r2 - l2 + 1] % MOD1) % MOD1 == (Hash1[r1] + MOD1 - Hash1[l1 - 1] * pw1[r1 - l1 + 1] % MOD1) % MOD1); } int LCP() { int ans = 0; Go(i , 1 , n-1) { if(same(1 , i , n-i+1 , n)) ans = i; } return ans; } int main() { scanf("%s" , (a + 1)); scanf("%s" , (b + 1)); m = strlen(a + 1) , n = strlen(b + 1); Prework(); Go(i , 1 , m) cnt[a[i] - '0']++; Go(i , 1 , n) cnt1[b[i] - '0']++; int fill = n - LCP(); if(cnt[0] < cnt1[0] || cnt[1] < cnt1[1]) { Go(i , 1 , m) putchar(a[i]); puts(""); return 0; } cnt[0] -= cnt1[0] , cnt[1] -= cnt1[1]; cnt1[0] = cnt1[1] = 0; Go(i , n - fill + 1 , n) ++cnt1[b[i] - '0']; Go(i , 1 , n) putchar(b[i]); Go(i , 1 , 2147483647) { bool f = 1; Go(j , n - fill + 1 , n) { if(!cnt[b[j] - '0']) { f = 0; break; } putchar(b[j]); cnt[b[j] - '0']--; } if(!f) break; } if(cnt[1]) Go(i , 1 , cnt[1]) putchar('1'); if(cnt[0]) Go(i , 1 , cnt[0]) putchar('0'); return 0; }

转载于:https://www.cnblogs.com/LiM-817/p/10887210.html