Codeforces Round 970 (Div. 3) （个人题解）（未补完）

前言：

昨天晚上的比赛，可惜E题太笨了没想到如何解决，不过好在看到F过的多直接跳过去写F了，能过个5个也还不错了，而且一个罚时也没吃。之后的题我还是会再能补的时候补完的噢！

正文：

链接：Dashboard - Codeforces Round 970 (Div. 3) - Codeforces

题目：

A. Sakurako's Exam：

#include<bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){int a,b;cin>>a>>b;if(b==0&&a%2==0&&a!=0){cout<<"YES"<<endl;}else if(a==0&&b%2==0){cout<<"YES"<<endl;}else if(a%2==0&&a!=0){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}

简单的数字逻辑题，情况并不多，慢慢讨论就行了。

B. Square or Not：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
string a;
int main(){int t;cin>>t;while(t--){int n,cnt=0;cin>>n;cin>>a;for(int i=0;i<n;i++){if(cnt==0&&a[i]=='0'){cnt=i+1;}}if(cnt==0)cnt=n;else cnt-=2;int cnt2=n/cnt;if(cnt2!=cnt){if((cnt==1&&n==1)||(cnt==4&&n==4)){cout<<"YES"<<endl;continue;}cout<<"NO"<<endl;continue;}if(n/cnt!=cnt&&n%cnt!=0){cout<<"NO"<<endl;continue;}//cout<<cnt<<endl;int res=0;for(int i=1;i<=n;i++){int j,k,flag=0;j=i/cnt;if(i%cnt)j++;k=i%cnt;if(k==0)k=cnt;//cout<<j<<k<<endl;if(j==1||j==cnt||k==1||k==cnt){flag=1;}if(flag==1){if(a[i-1]=='0'){res=1;break;}}else{if(a[i-1]=='1'){res=1;break;}}//cout<<res<<endl;}if(res==1){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;}}return 0;
}

这题我太笨了，调了很久，并且做法也十分愚笨。题目的思路还是很好理解的，就是直接模拟一个矩阵看是否合理即可（矩阵的行列一定要相等）。

C. Longest Good Array：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000005];
void init(){a[1]=1;for(int i=2;i<1000000;i++){a[i]=i-1;}for(int i=1;i<1000000;i++){a[i]+=a[i-1];}
}
int main(){init();int t;cin>>t;while(t--){int l,r,res;cin>>l>>r;res=r-l;int low=1,high=1000000,mid;while(low<high){mid=low+high+1>>1;if(a[mid]-1<=res)low=mid;else high=mid-1;//cout<<low<<" "<<mid<<" "<<high<<endl;}cout<<low<<endl;}return 0;
}

贪心的令相邻数的间隔最小且递增，即 1,2,3，第 1 个数为 l，第 n+1个数为l+n*(n+1)/2，二分答案 n 即可。

D. Sakurako's Hobby：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],ans[N];
string s;
bool book[N];
int n,cnt;
void dfs(int x){book[x]=1;if(s[x-1]=='0')cnt++;if(book[a[x]]==0){dfs(a[x]);}ans[x]=cnt;
}
void init(){memset(book,0,sizeof(book));
}
int main(){int t;cin>>t;while(t--){cin>>n;init();for(int i=1;i<=n;i++){cin>>a[i];}cin>>s;for(int i=1;i<=n;i++){cnt=0;if(book[i]==0)dfs(i);}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}cout<<endl;}return 0;
}

这题我用的是dfs递归+数组标记，其实用并查集也行，直接将搜索到的黑块的数量存进根节点，不过这两个做法大差不差，时间复杂度应该差不多。

E. Alternating String：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
int read(){int x = 0; bool f = false; char c = getchar();while(c < '0' || c > '9') f |= (c == '-'), c = getchar();while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();return f ? -x : x;
}
const int N = 2e5 + 5;
char s[N];
int odd[N][26], even[N][26];
void solve(){int n = read();scanf("%s", s + 1);for(int i = 1; i <= n; ++i){for(int j = 0; j <= 25; ++j) odd[i][j] = even[i][j] = 0;if(i & 1) odd[i][s[i] - 'a'] = 1;else even[i][s[i] - 'a'] = 1;for(int j = 0; j <= 25; ++j) odd[i][j] += odd[i - 1][j], even[i][j] += even[i - 1][j];}int ans = 0x7fffffff;if(n & 1){for(int i = 1; i <= n; ++i){for(int j = 0; j <= 25; ++j)for(int k = 0; k <= 25; ++k){int x = odd[i - 1][j] + even[n][j] - even[i][j];int y = even[i - 1][k] + odd[n][k] - odd[i][k];ans = min(ans, n - 1 - x - y);}}printf("%d\n", ans + 1);}else{for(int i = 0; i <= 25; ++i)for(int j = 0; j <= 25; ++j)ans = min(ans, n - (odd[n][i] + even[n][j]));printf("%d\n", ans);}
}
int main(){int T = read();while(T--) solve();return 0;
}

这是我看别人的博客学来的做法，读题后我们可以很容易知道偶数情况很容易考虑，直接枚举偶数奇数位字母出现的次数即可，但奇数情况是一定要进行删除操作的，删除的话会影响后面奇数偶数位的位置，这时如果直接暴力枚举所有的点，删除后在枚举剩下的点，我们是一定会超时的，不过我们可以用前缀和的思想，记 odd[i][j] 为前个数，奇数位字符为 j的个数，even[i][j] 为偶数位字符为 j的个数，再枚举删去哪个点，最终序列的奇数位是这个点前面的奇数位和后面的偶数位，再分别枚举奇数位和偶数位的最终字符，这样就能得到正确答案。

F. Sakurako's Box：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int modInverse(int a, int m) {int res = 1, exp = m - 2;while (exp > 0) {if (exp % 2 == 1) {res = (1LL * res * a) % m;}a = (1LL * a * a) % m;exp /= 2;}return res;
}
int main(){int t;cin >> t;while (t--) {int n;cin >> n;vector<int> a(n);map<int, int> freq;long long sum = 0, sumOfSquares = 0;for (int i = 0; i < n; i++) {cin >> a[i];freq[a[i]]++;sum = (sum + a[i]) % MOD;sumOfSquares = (sumOfSquares + 1LL * a[i] * a[i]) % MOD;}long long P = (sum * sum % MOD - sumOfSquares + MOD) % MOD;P = P * modInverse(2, MOD) % MOD;long long Q = 1LL * n * (n - 1) / 2 % MOD;long long Q_inverse = modInverse(Q, MOD);long long result = P * Q_inverse % MOD;cout << result << endl;}return 0;
}

这题太直接了，答案就是 $\sum_{}^{}ai*aj(i<j)/C_{n}^{2}$ ，可能是在考逆元吧。