Codeforces Round 970 (Div. 3)A~F
A. Sakurako's Exam
把1的个数和2的个数按奇偶分类讨论即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int a,b; cin>>a>>b;
if(a % 2){
cout<<"NO\n";
continue;
}
if(a % 2 == 0 && b % 2 == 0) cout<<"YES\n";
else{
if(a >= 2)
cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
B. Square or Not
映射到矩阵暴力判断就行了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
set<int>st;
int x = 1;
while(x < N){
st.insert(x*x);
x++;
}
int t; cin>>t;
while(t--)
{
int n; cin>>n;
string s; cin>>s;
if(st.find(n) == st.end()){
cout<<"No\n";
continue;
}
int m = sqrt(n);
s = "?" + s;
char a[m+10][m+10];
int idx = 0;
for(int i = 1;i <= m; i++)
{
for(int j = 1;j <= m; j++){
a[i][j] = s[++idx];
}
}
// for(int i = 1;i <= m; i++)
// {
// for(int j = 1;j <= m; j++){
// cout<<a[i][j];
// }
// cout<<"\n";
// }
// cout<<"\n";
bool ok = true;
for(int i = 1;i <= m; i++)
{
if(a[i][1] != '1' || a[i][m] != '1')ok = false;
if(a[1][i] != '1' || a[m][i] != '1')ok = false;
if(!ok)break;
}
for(int i = 2;i <= m-1; i++)
{
for(int j = 2;j <= m-1; j++)
{
if(a[i][j] != '0'){
ok = false;
break;
}
}
if(!ok)break;
}
if(!ok)cout<<"No\n";
else cout<<"Yes\n";
}
return 0;
}
C. Longest Good Array
发现是个等差，二分求最多能到哪。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
ll L,R; cin>>L>>R;
ll l = 1,r = R-L+1;
while(l <= r)
{
ll mid = (l + r)>>1;
if((1+mid)*mid/2 >= R-L+1)r = mid - 1;
else l = mid + 1;
}
cout<<r + 1<<"\n";
}
return 0;
}
D. Sakurako's Hobby
思路：因为是个排列，那么就不会有多个环连起来的情况。我们画个图就能发现，在一个环上的都可相互到达。那么连通性可以用并查集来维护。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int val[N],p[N],siz[N];
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
for(int i = 1;i <= n; i++)
{
int x; cin>>x;
val[i] = x;
p[i] = i;
siz[i] = 1;
}
string s; cin>>s;
s = "?"+s;
for(int i = 1;i <= n; i++)
{
if(p[i] == i){
bool notself = false;
int last = i,now = val[i];
while(1)
{
if(now == i){
break;
}
last = now,now = val[now];
// cout<<"last = "<<last<<" now = "<<now<<"\n";
merge(last,now);
}
}
}
map<int,int>mp;
for(int i = 1;i <= n; i++)
{
if(s[i] == '0')//black
{
mp[p[i]]++;
}
}
for(int i = 1;i <= n; i++)
{
cout<<mp[p[i]]<<" ";
}
cout<<"\n";
}
return 0;
}
E. Alternating String
思路：因为要求长度是偶数，且奇数位相同，偶数位相同。且删数操作只能最多一次，那么肯定是长度奇数的时候必须要用删数，长度偶数只能进行改数。
我们注意到如果是偶数长度，只考虑该数。统计哪个字母出现最多就行了。
如果是奇数呢？考虑先删再改。删哪个呢？我们枚举删每一个点的代价，且注意到这个被删的点之后的奇偶性发生互换，写的时候要小心边界。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
char a[N],b[N];
int cnta[N][30],cntb[N][30];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
int n; cin>>n;
string s; cin>>s;
if(n == 1){
cout<<1<<"\n";
continue;
}
s = "?" + s;
int n1 = 0,n2 = 0;
memset(cnta,0,sizeof(a));
memset(cntb,0,sizeof(b));
for(int i = 1;i <= n; i++)
{
if(i % 2)a[++n1] = s[i];
else b[++n2] = s[i];
}
// for(int i = 1;i <= n1; i++)
// cout<<a[i];
// cout<<"\n";
// for(int i = 1;i <= n2; i++)
// cout<<b[i];
// cout<<"\n";
// cout<<"____________________\n";
for(int i = 1;i <= n1; i++){
for(int j = 0;j < 26; j++){
cnta[i][j] = cnta[i-1][j];
}
// cout<<"a[i] - 'a' ="<<a[i]-'a'<<"\n";
cnta[i][a[i]-'a']++;
// for(int j = 0;j < 26; j++){
// cout<<cnta[i][j]<<" ";
// }
// cout<<"\n";
}
for(int i = 1;i <= n2; i++){
for(int j = 0;j < 26; j++){
cntb[i][j] = cntb[i-1][j];
}
cntb[i][b[i]-'a']++;
}
// cout<<"n = "<<n<<"\n";
// for(int i = 0;i < 26; i++)
// cout<<cnta[n1][i]<<" ";
// cout<<"\n";
// for(int i = 0;i < 26; i++)
// cout<<cntb[n2][i]<<" ";
// cout<<"\n";
if(n % 2 == 0){
int ans1 = 0,ans2 = 0;
for(int i = 0;i < 26; i++)
ans1 = max(ans1,cnta[n1][i]);
ans1 = n1-ans1;
for(int i = 0;i < 26; i++)
ans2 = max(ans2,cntb[n2][i]);
ans2 = n2-ans2;
cout<<ans1+ans2<<"\n";
}else{
n--;
int res = 1e9;
int ans1 = 0,ans2 = 0;
for(int i = 1;i <= n1; i++){//删奇数位置
// cout<<"i = "<<i<<"\n";
ans1 = 0,ans2 = 0;
for(int j = 0;j < 26; j++){
// cout<<"j = "<<j<<"\n";
ans1 = max(ans1,cnta[i-1][j] + cntb[n2][j]-cntb[i-1][j]);
ans2 = max(ans2,cntb[i-1][j] + cnta[n1][j]-cnta[i][j]);
// cout<<"cnta[i-1][j] = "<<cnta[i-1][j]<<" cntb[n2][j]-cntb[i-1][j] = "<<cntb[n2][j]-cntb[i-1][j]<<"\n";
// cout<<"cntb[n2][j]="<<cntb[n2][j]<<" cntb[i-1][j]="<<cntb[i-1][j]<<"\n";
// cout<<"ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
}
ans1 = n/2-ans1;
ans2 = n/2-ans2;
// cout<<"i = "<<i<<" ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
res = min(res,ans1+ans2);
}
ans1 = 0,ans2 = 0;
for(int i = 1;i <= n2; i++){//删偶数位置
ans1 = 0,ans2 = 0;
for(int j = 0;j < 26; j++){
ans1 = max(ans1,cnta[i][j] + cntb[n2][j]-cntb[i][j]);
ans2 = max(ans2,cntb[i-1][j] + cnta[n1][j]-cnta[i][j]);
}
ans1 = n/2-ans1;
ans2 = n/2-ans2;
// cout<<"i = "<<i<<" ans1 = "<<ans1<<" ans2 = "<<ans2<<"\n";
res = min(res,ans1+ans2);
}
cout<<res+1<<"\n";
}
}
return 0;
}
F. Sakurako's Box
思路：不难发现答案是：\(\dfrac{\sum_{i = 1}^{n-1}\sum_{j = i+1}^na_ia_j}{\dfrac{n(n+1)}{2}}\)
做一个化简：\(\dfrac{2\times\sum_{i = 1}^{n-1}a_i\sum_{j = i+1}^na_j}{n(n+1)}\)
那么可以对后面的\(\sum_{j = i+1}^na_j\)做一个前缀和的预处理。然后算就行了。取模要千万小心！当然你也可以直接用python写。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
a %= mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll a[N];
ll s[N];
ll n;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin>>t;
while(t--)
{
cin>>n;
ll inv = qmi(n*(n-1),mod-2,mod);
for(int i = 1;i <= n; i++)
cin>>a[i];
for(int i = 1;i <= n; i++)
{
s[i] = (s[i-1]+a[i])%mod;
}
__int128 ans = 0;
for(int i = 1;i <= n-1; i++){
ll t = (s[n]-s[i])%mod;
if(t < 0) t += mod;
t %= mod;
t *= a[i];
ans = ans + t;
ans %= mod;
}
ans *= 2ll;
ans %= mod;
ans *= inv;
ans %= mod;
cout<<(ll)ans<<"\n";
}
return 0;
}