Codeforces Round 970 (Div. 3)(ABCDEF)

Codeforces Round 970 (Div. 3)

A:Sakurako's Exams

签到

题意:给定1,2的数量,判断是否能用加减符号使得这些1,2计算出0

void solve()
{cin>>n>>m;if(n%2)cout<<"NO\n";else{if(m%2==0||n)cout<<"YES\n";else cout<<"NO\n";}return ;
}

B:Square or Not

签到

题意:给定01序列,问从上到下，从左到右排列是否可以得到一个周围为1,内部为0的正方形

void solve()
{string s;cin>>n;cin>>s;int t=sqrt(n);if(t*t!=n){cout<<"No\n";return;}else {int idx=0;for(int i=0;i<t;i++){for(int j=0;j<t;j++){int now=i*t+j;if(i==0||j==0||i==t-1||j==t-1){if(s[now]=='0'){cout<<"No\n";return;}}else if(s[now]=='1'){cout<<"No\n";return;}}}}cout<<"Yes\n";return ;
}

C:Longest Good Arrays

题意:给定左右边界了l,r,问在范围内凑出最长的满足a[i]-a[i-1]<a[i+1]-a[i](i>=2)的最长数组的长度

思路:最优一定是前后两项差从左到右分别为1,2,3,4...,所以二分数组最后一个元素,满足小于r-l的第一个元素位置，再+1就是答案

int n,m;
int cha;
bool check(int x)
{return (x+1)*x/2>cha;
}
void solve()
{cin>>n>>m;cha=m-n;int l=0,r=1e8;while(l+1<r){int mid=l+r>>1;check(mid)?r=mid:l=mid;}cout<<l+1<<'\n';return ;
}

D:Sakurako's Hobby

题意:输入一个数组大小n,然后输入n个数q[i](1<=i<=n)代表i可以到达q[i]（保证q数组一定是一个排列）,然后输入一个01串,当第i个位置为‘1’代表为白块，为'0'代表为黑块,f[i]为能够到达i这个点的所有黑块的数量,输出所有f[i](1<=i<=n)

例如:

输入

2

2 1

00

输出

2 2 

(因为1位置的点都能由1,2到达)

思路:并查集,把所有有联系的点都缩到一个根上(由于是一个排列，所以所有可以直接可以到达或者间接到达的点都可以形成一个环，也就是相互到达)，最后问f[i]只需要把一个环中的所有店都累加到find(i),也就是根节点上

代码:

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int f[N],q[N],cnt[N];
bool st[N];
int find(int x)
{if(x!=f[x])return f[x]=find(f[x]);return f[x];
}
void root(int a,int b)
{int x=find(a),y=find(b);if(x!=y)f[x]=y;
}
void solve()
{cin>>n;_rep(i,1,n)cin>>q[i],f[i]=i,st[i]=false,cnt[i]=0;string s;cin>>s;s=" "+s;_rep(i,1,n){int now=i;while(!st[now]){st[now]=true;root(now,q[now]);now=q[now];}}	_rep(i,1,n)if(s[i]=='0')cnt[find(i)]++;_rep(i,1,n)cout<<cnt[find(i)]<<" ";cout<<'\n';return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}

E:Alternating String

题意:给定一个字符串,现在有两个操作

1:选一个字母删除(但是这个最多只能操作一次)

2:将一个位置的字母改成另一个字母

问你把这个字符串变成一个:奇数位置字母都相同,偶数位置字母都相同 的字符串的最小操作次数

思路

只要发现一个特点就可以想到这个思路,那就是当你选择把当前这个点i的字母删除之后，后面所有的字母所在的奇偶位置就发生了互换

1.首先考虑不删除字母的情况

维护一个hou[26][2]的数组,其中第一维代表哪个字母(0~25),第二维 0/1 代表 奇数位/偶数位 

那么我首先遍历奇数位置的所有字母,求和sum就是奇数位置字母的数量,求最大值ma就是奇数位置 字母的众数那么sum-ma就是奇数位置最少需要改变的字母的数量

偶数位置同理，那么就能求导不删除字母情况下最小操作次数

2,考虑删除字母的情况

假如我现在删除的是i号点,那么1~i-1号点的奇偶性质未发生改变,那么我就从小到大遍历即可,i+1~n号点的奇偶性质全部发生了改变,那么显然如果我能预处理出i+1~n的所有状态，也就是前面说到的hou[26][2],那么奇数位本来是hou[0~25][0]现在只需要考虑hou[0~25][1]，偶数位置同理，那么就可以发现这个hou[0~25][2]显然可以提前预处理出来，然后遍历到第i个点的时候把1~i的状态删去就行，这些都可以线性处理，时间复杂度O(26*n)

代码:

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int now[26][2],hou[26][2];//now储存1~i-1的状态,hou储存i+1~n的状态
void solve()
{cin>>n;string s;cin>>s;memset(now,0,sizeof(now));memset(hou,0,sizeof(hou));s=" "+s;_rep(i,1,n)hou[s[i]-'a'][i%2]++;int res=0,sum,ma;_rep(j,0,1){sum=0;	ma=0;_rep(i,0,25){sum+=hou[i][j];ma=max(hou[i][j],ma);}res+=sum-ma;}if(n%2){res=INF;_rep(i,1,n){int nowres=0;hou[s[i]-'a'][i%2]--;_rep(j,0,1){sum=0;ma=0;_rep(k,0,25){sum+=hou[k][j];sum+=now[k][j^1];ma=max(ma,hou[k][j]+now[k][j^1]);}nowres+=sum-ma;}now[s[i]-'a'][i%2]++;res=min(res,nowres+1);}}cout<<res<<"\n";return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}

F:Sakurako's Boxt

题意:给定一个数组,为元素之间两两相乘(a[1]*a[2]和a[2]*a[1]重复不算)的平均数是什么

思路:

假设四个元素

那么答案就是

等价于

用一个后缀和维护形如的东西这道题就轻松解决了,只需要注意一下取模和乘法逆元的问题就行了

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18,P=1e9+7;
int n,m;
int hou[N],q[N];
int qmi(int a,int b)
{int res=1;while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}return res;
}
void solve()
{cin>>n;_rep(i,1,n)cin>>q[i];hou[n+1]=0;_pre(i,n,1)hou[i]=hou[i+1]+q[i];int res=0;_rep(i,1,n){res+=(q[i]*(hou[i+1]%P)%P);res%=P;}
//	cout<<"res="<<res<<" "<<n<<endl;cout<<(res*qmi((n*(n-1)/2)%P,P-2)%P)<<'\n';return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}