Codeforces Round #827 (Div. 4) 復盤＋題解
復盤：
ABC簽到，手速太慢了。
D搗鼓了好久才想起來從更小的值域出發去做。
E簡單二分答案。
然后就time out了。D題搞錯方向浪費太久時間了。
F思維題，考慮到初值、字符集，然后是$\text{rearranged}$的，情況就很簡單。
G簡單位性質，拐一個彎就能想到了。
題解
D.Coprime
題意簡述
給定正整數數組$a$，長度$2e5$，值域$1\le a_i \le 1000$，求最大的$i+j$滿足$a_i$和$a_j$互質。
分析做法
①預處理得到$1000$以內的$gcd[i][j]$和$coprime[i][j]$。
②讀入數組，對于每個$a_i$，嘗試用$i$對$id[a_i]$求$\max$并更新。
③枚舉$x$和$y$（$1\sim1000$），如果$id[x]$和$id[y]$有值，且$x$和$y$互質，那么嘗試用$id[x]+id[y]$對$ans$求$\max$并更新。
注：枚舉$i+j$和$i$會$T$掉。
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int N = 2e5; const int M = 1000; int gcd[M + 3][M + 3]; int n, a[N + 3]; int id[M + 3]; int fgcd(int a, int b){ if(a >= b) return gcd[a][b]; return gcd[b][a]; } bool cop(int a, int b){ return fgcd(a, b) == 1; } void sol(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); memset(id, 0, sizeof id); for(int i = 1; i <= n; i++) id[a[i]] = max(id[a[i]], i); int ans = -1; for(int x = 1; x <= M; x++) for(int y = 1; y <= M; y++){ if(id[x] > 0 && id[y] > 0 && fgcd(x, y) == 1) ans = max(ans, id[x] + id[y]); } printf("%d\n", ans); } int main(){ int a, b, r; for(int i = 1; i <= M; i++) for(int j = 1; j <= i; j++){ a = i; b = j; r = a % b; while(r > 0){ a = b; b = r; r = a % b; } gcd[i][j] = b; } int T; scanf("%d", &T); while(T--) sol(); return 0; }
E.Scuza
題意簡述
給定每個臺階之間的高度差（臺階數量$2e5$，臺階高度$1e9$）。多次詢問，給出腿長$k$，從頭開始登臺階，問最多上到多高？（$k\ge a_i$才能登上這個臺階）
分析做法
記得開$\mathrm{long\,long}$存數值。
設$premax_i=\mathop{\max}\limits_{1\le j \le i}\{a_j\}$，則$f(i)=[k\ge premax_i]$在$i\in [1,n]$上是單調的，可以二分得到能上幾個臺階，預處理前綴最大值和前綴和就行。
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const int N = 2e5; int n, q; LL pmax[N + 3], sum[N + 3]; void sol(){ scanf("%d%d", &n, &q); LL k; pmax[0] = sum[0] = 0; for(int i = 1; i <= n; i++){ scanf("%lld", &k); pmax[i] = max(pmax[i - 1], k); sum[i] = sum[i - 1] + k; } pmax[n + 1] = 1e9 + 1; // // while(q--){ // scanf("%lld", &k); // // // for(int i = 1; i <= n + 1; i++) // if(k < pmax[i]){ // printf("%lld ", sum[i - 1]); // break; // // } // // } int l, r, mid, ans; while(q--){ scanf("%lld", &k); l = 1; r = n + 1; ans = 0; while(l <= r){ mid = (l + r) >> 1; if(pmax[mid] <= k){ l = mid + 1; ans = mid; } else r = mid - 1; } printf("%lld ", sum[ans]); } putchar('\n'); } int main(){ int T; scanf("%d", &T); while(T--) sol(); return 0; }
F.Smaller
題意簡述
初始兩個字符串$s=t=\mathtt{a}$，然后$q$次操作，分別給$s$或$t$末尾加上$k$遍字符串$x$。
每次操作后，問能否重排$s$和$t$，使得$s$的字典序小于$t$。注意，操作影響會累積。
分析做法
因為$s$和$t$初始有一個$\mathtt{a}$，所以
①如果$t$中出現了非$\mathtt{a}$的字符，則重排時將其排在第一位，就能使得$s<t$，輸出$\mathbf{YES}$
②保證$t$全部為$\mathtt{a}$，如果$s$中含有非$\mathtt{a}$的字符……
$\mathrm{i.}$要么$s$中$\mathtt{a}$個數少于$t$，情況形如$\mathtt{aab}>\mathtt{aaa}$
$\mathrm{ii.}$要么$s$中$\mathtt{a}$個數等于$t$，情況形如$\mathtt{aaab}>\mathtt{aaa}$
$\mathrm{iii.}$要么$s$中$\mathtt{a}$個數多于$t$，情況形如$\mathtt{aaaab}>\mathtt{aaa}$
所以一定輸出$\mathbf{NO}$
③保證$s$和$t$全部為$\mathtt{a}$，那么如果$s$中$\mathtt{a}$個數少于$t$結果為$\mathbf{YES}$，否則為$\mathbf{NO}$。
所以實際上只需要維護$f[1]$和$f[2]$分別表示$s$和$t$是否只含$\mathtt{a}$，$c[1]$和$c[2]$分別表示$s$和$t$含有$\mathtt{a}$的個數即可。
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const int N = 5e5; char s[N + 3]; void sol(){ int q, k, d; bool f[3]; //only a? LL c[3]; //cnt of a f[1] = f[2] = true; c[1] = c[2] = 1LL; scanf("%d\n", &q); while(q--){ scanf("%d %d %s", &d, &k, s); if(f[d]) for(int i = 0; s[i]; i++) if(s[i] != 'a'){ f[d] = false; break; } else c[d] += 1LL * k; if(!f[2]) printf("YES\n"); else if(f[1] && c[1] < c[2]) printf("YES\n"); else printf("NO\n"); } } int main(){ int T; scanf("%d\n", &T); while(T--) sol(); return 0; }
G.Orray
題意簡述
給非負整數數列$a$，重排$a$，字典序地最大化其前綴按位$\mathrm{OR}$數列。
分析做法
首先把最大值排到第一位，這樣就“點亮”了一些二進制位。
接下來每步，把“已點亮”的位屏蔽之后，還沒用上的元素之中找出最大值，又“點亮”了一些二進制位。
簡單實現：使用$\mathrm{unsigned\,int}$類存儲$a$，和“掩碼”$mask$；$visit[]$數組。
每輪循環找個最大值填到下一個位置，如果沒找到新的，說明沒有新的二進制位可以點亮，直接把剩下的元素隨便填上。
代碼
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef unsigned int UI; const int N = 2e5; const int inf = 1e9 + 1; int n; UI a[N + 3], b[N + 3]; //b save id bool vis[N + 3]; void sol(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); int bpos = 0, pic; UI mask = 0; memset(vis, 0, sizeof vis); while(bpos <= n){ pic = -1; for(int i = 1; i <= n; i++) if(!vis[i] && (a[i] & ~mask) > 0) if(pic == -1 || (a[i] & ~mask) > (a[pic] & ~mask)) pic = i; if(pic == -1) break; vis[pic] = true; b[++bpos] = pic; mask |= a[pic]; } for(int i = 1; i <= n && bpos < n; i++) if(!vis[i]) b[++bpos] = i; for(int i = 1; i <= n; i++) printf("%d ", a[b[i]]); printf("\n"); } int main(){ int T; scanf("%d\n", &T); while(T--) sol(); return 0; }
浙公網安備 33010602011771號