\(A. green_gold_dog, array and permutation\)
让大的数减小的数就可以制造更多的不同。
PII a[N];
int ans[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=make_pair(read(),i);
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
ans[a[i].second]=(n-i+1);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(B. XOR Palindromes\)
首先答案显然对称。
找到最小的变化次数然后依次加 \(2\) 因为每次可以多变一对，直到加到答案对称的位置。
如果是奇数显然可以多变一个中间的数字，填补变一对的的空缺。
void solve(){
int n=read();
string s;
cin>>s;
s=' '+s;
int minn=0;
for(int i=1;i<=n&&i<=n-i+1;i++){
if(s[i]!=s[n-i+1])minn++;
}
if(n%2==0){
for(int i=0;i<=n;i++){
if(minn<=i&&i<=n-minn&&i%2==minn%2){
cout<<1;
}else cout<<0;
}
}else{
for(int i=0;i<=n;i++){
if(minn<=i&&i<=n-minn){
cout<<1;
}else cout<<0;
}
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(C. Salyg1n and the MEX Game\)
每次加入 \(Mex\) 即可，感觉很显然啊，这样可以一直逼近 \(0\) ，直到不能再 \(move\) 。
如果想要更大的 \(Mex\) 将来不及补缺，不能做到。
int a[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
int cnt=0,op=a[n]+1;
for(int i=1;i<=n;i++){
if(a[i]==cnt)cnt++;
else {
op=cnt;
break;
}
}
while(1){
cout<<op<<endl;
int x;
cin>>x;
if(x==-1)break;
op=x;
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Cyclic Operations\)
对位置和点权建边，跑强连通。
如果一个点位于单链上，分析可知一定可以完成赋值的，因为总存在一个点不需要对其他点负责，而且也可以多次对一个点覆盖。
如果一个点位于强连通分量上，显然要大小等于 \(k\) ，感觉这个没什么好说的。
int cnt,low[N],num[N],dfn,sccno[N],sta[N],top;
int siz[N];
vector<int>G[N];
void dfs(int u){
sta[top++]=u;
low[u]=num[u]=++dfn;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(!num[v]){
dfs(v);
low[u]=min(low[v],low[u]);
}else if(!sccno[v]){
low[u]=min(low[u],num[v]);
}
}
if(low[u]==num[u]){
cnt++;
while(1){
int v=sta[--top];
sccno[v]=cnt;
if(u==v)break;
}
}
}
void Tarjan(int n){
cnt=top=dfn=0;
for(int i=1;i<=n;i++){
if(!num[i]){
dfs(i);
}
}
}
void solve(){
int n=read(),k=read(),ans=1;
for(int i=0;i<=n+100;i++){
G[i].clear();
num[i]=0;
sccno[i]=0;
siz[i]=0;
low[i]=0;
}
for(int i=1;i<=n;i++){
int x=read();
G[i].push_back(x);
}
if(k==1){
int ok=1;
for(int i=1;i<=n;i++){
if(G[i][0]!=i)ok=0;
}
puts(ok>0?"YES":"NO");
return ;
}
Tarjan(n);
for(int i=1;i<=n;i++){
siz[sccno[i]]++;
}
for(int i=1;i<=n;i++){
if((siz[sccno[i]]==1&&G[i][0]==i)||(siz[sccno[i]]!=1&&siz[sccno[i]]!=k))ans=0;
}
puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}