Codeforces Round #597 (Div. 2)

洛谷博客传送门

A - Good ol’ Numbers Coloring

猜了个 $GCD=1$ 过了

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} template <class T> void read(T &x) { static char ch; static bool neg; for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar()); for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar()); x = neg ? -x : x; } const int maxn = 1e6 + 10; int main(){ int T; read(T); while(T--){ int a,b; read(a); read(b); if (Gcd(a,b) != 1) cout << "Infinite" << endl; else cout << "Finite" << endl; } return 0; }

B - Restricted RPS

暴力模拟就好，被清空搞了一发

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} template <class T> void read(T &x) { static char ch; static bool neg; for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar()); for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar()); x = neg ? -x : x; } const int maxn = 1e4 + 10; char s[maxn],ans[maxn]; int vis[maxn]; int main(){ int T; read(T); while(T--){ memset(ans,0,sizeof(ans)); memset(vis,0,sizeof(vis)); int n,a,b,c; read(n); read(a); read(b); read(c); scanf("%s",s); int len = n; int res = 0; for(int i=0; i<len; i++){ if (s[i] == 'S' && a > 0){ a--; ans[i] = 'R'; vis[i] = 1; res++; } if (s[i] == 'R' && b > 0){ b--; ans[i] = 'P'; vis[i] = 1; res++; } if (s[i] == 'P' && c > 0){ c--; ans[i] = 'S'; vis[i] = 1; res++; } } for(int i=0; i<len; i++){ if (vis[i] == 0){ if (a > 0){ a--; ans[i] = 'R'; }else if (b > 0){ b--; ans[i] = 'P'; }else if (c > 0){ c--; ans[i] = 'S'; } } vis[i] = 0; } if (res >= (n+1)/2) printf("YES\n%s\n",ans); else printf("NO\n"); } return 0; }

C - Constanze’s Machine

答案就是 u 和 n 连续段的答案的乘，一个连续段的答案可以dp预处理出来

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} template <class T> void read(T &x) { static char ch; static bool neg; for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar()); for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar()); x = neg ? -x : x; } const int maxn = 1e6 + 10; const LL mod = 1e9 + 7; LL dp[maxn][2],len[maxn]; int main(){ dp[2][1] = dp[2][0] = 1; len[2] = 2; len[1] = 1; for(int i=3; i<=1E5; i++){ dp[i][1] = dp[i-1][0]; dp[i][0] = (dp[i-1][1] + dp[i-1][0]) % mod; len[i] = (dp[i][1] + dp[i][0]) % mod; } string s; cin >> s; LL ans = 1,tot = 1,tag = 1; for(int i=0; i < (int)s.length()-1; i++){ if (s[i] == 'm' || s[i] == 'w'){ tag = 0; break; } if (s[i] == s[i+1]){ tot++; }else{ if (s[i] == 'u' || s[i] == 'n'){ ans = ans * len[tot] % mod; } tot = 1; } } char ch = s[s.length()-1]; if (tot > 1 && (ch == 'u'||ch == 'n')){ ans = ans * len[tot] % mod; } if (tag) cout << ans << endl; else cout << 0 << endl; return 0; }

D - Shichikuji and Power Grid

贪心，每次在花费最小的地方建立一个基站，每建完了一个基站，去更新其他基站的最小花费即可。

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} template <class T> void read(T &x) { static char ch; static bool neg; for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar()); for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar()); x = neg ? -x : x; } const int maxn = 1e6 + 10; struct node{ int x,y,id; }p[maxn]; LL c[maxn],k[maxn]; int ok[maxn],pre[maxn]; vector<int> Node; vector<pair<int,int> > Edge; LL getdis(node a,node b){ LL dis = abs(a.x-b.x) + abs(a.y-b.y); return dis * (k[a.id] + k[b.id]); } int main(){ int n; read(n); for(int i=1; i<=n; i++) { read(p[i].x); read(p[i].y); p[i].id = i; } for(int i=1; i<=n; i++){ read(c[i]); } for(int j=1; j<=n; j++){ read(k[j]); } LL ans = 0; for(int i=1; i<=n; i++){ int mn = INT_MAX,u = 0; for(int j=1; j<=n; j++){ if (!ok[j] && c[j] < mn){ mn = c[j]; u = j; } } ans += mn; if (pre[u] == 0) Node.push_back(u); else Edge.push_back(make_pair(pre[u],u)); ok[u] = 1; for(int j=1; j<=n; j++){ if (!ok[j]){ LL dis = getdis(p[u],p[j]); if (dis < c[j]){ c[j] = dis; pre[j] = u; } } } } cout << ans << endl; cout << Node.size() << endl; for(auto u : Node){ cout << u << ' '; } cout << endl; cout << Edge.size() << endl; for(auto now : Edge){ cout << now.first << ' ' << now.second << endl; } return 0; }

F - Daniel and Spring Cleaning

推公式的题目，看了题解才会，定义 $f(l,r)$ 为$[l,r)$ 区间内满足条件的 $(x,y)$ 的个数。

首先是一个很重要的结论，直接可以降低复杂度

$$f(2l,2r)=3\ast f(l,r)$$

证明也很好懂，乘2相当于左移一位，因此在 $l,r$ 最后都多了一位，对于这一位来说，必须是 $(0,1),(1,0),(0,1)$ 中的一种，才能满足 $x+y=xxory$，原来本身满足条件的数量是 $f(l,r)$ 因此 $f(2l,2r)=3\ast f(l,r)$

当 $l,r$ 都是偶数的时候，我们可以直接除2计算，复杂度可以向 $O(log)$ 靠拢。

不过当其中一个是奇数的时候，我们就可以通过+1，或者-1把它变成偶数。

首先定义 $g(x,n)$ 是 $1\le y<n$，中满足 $x+y=xxory$ 的个数，

当 $l$ 是偶数的时候，$f(l,r)=f(l+1,r)+2\ast (g(l,r)-g(l,l))$

当 $r$ 是偶数的时候，$f(l,r)=f(l,r-1)+2\ast (g(r-1,r)-g(r-1,l))$

现在只需要快速计算 $g(x,y)$ 即可

对 $g(x,n)$ 分段计算，每一段就是

$$g(x,n)=2^{zeros}+g(x,n-lowbit(n))$$

每lowbit是一段，相当从b的二进制最后一位往前数，数到一个1就分一段，这样分段保证了当前的二进制位前面的位，在这个段内，是完全相同的。

那么这个段内的答案，和a的二进制串在段之内的0的个数有关，只要a的那一位是0，b的对应位是0或者1都可以，而a那一位是1，b必须是0，对答案没有贡献。a二进制串后缀的0的个数记为 zeros ，那么段内的答案就是 $2^{zeros}$

统计答案即可，复杂度 $O(lo{g}^2(n))$

代码

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} template <class T> void read(T &x) { static char ch; static bool neg; for(ch = neg = 0; ch < '0' || '9' < ch; neg |= ch == '-', ch = getchar()); for(x = 0; '0' <= ch && ch <= '9'; (x *= 10) += ch - '0', ch = getchar()); x = neg ? -x : x; } const int maxn = 1e6 + 10; LL g(LL a,LL b){ LL ans = 0,cnt = 0; for(LL i=1; i<=b; i<<=1){ if (b & i){ b ^= i; // b -= lowbit(b); if (!(a & b)) ans += (1 << cnt); // 后面的位也满足 a + b = a ^ b 这个区间段上就有答案 // a的某bit是0，那b的那个bit随便是0还是1，如果a是1，b必须是0，相当于 ans *= 1 没有贡献 } if (! (a & i)) cnt++; } return ans; } int tot = 0; LL f(LL l,LL r){ if (l == r) return 0; if (l == 0) return 2*r - 1 + f(1,r); LL ans = 0; if (l & 1){ ans += 2 * (g(l,r) - g(l,l)); l++; } if (r & 1){ ans += 2 * (g(r-1,r) - g(r-1,l)); r--; } return ans + 3 * f(l/2,r/2); } int main(){ int T; read(T); while(T--){ int l,r; read(l); read(r); cout << f(l,r+1) << endl; } return 0; }