哈，这个比赛在开了不久之后，不知道为啥卡了差不多20来分钟，后面卡着卡着就想睡觉了。实在是太困了....
题目意思：
Alice做一次操作，删除任意数字a,而Bob做一次操作删除b使得a+b对4取余是3。
获胜条件，有人不能再进行操作，则另一个人获胜。
思路：
A题嘛，直接胆大心细，观察样例给的数据，得出，仅当给出的数是4的倍数的时候Bob获胜。
其他情况下嘛，Alice获胜。
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;//质数while(n--){int x;cin>>x;if(x%4==0){cout<<"Bob"<<endl;}else{cout<<"Alice"<<endl;}}
} 
题目意思：
给定一个数组，a[i]是i选手的战斗力，当剩余选手超过k名的时候：
随机选择两个选手，淘汰实力较低的那一个，如果实力一样的话，随便淘汰一个。
问是否存在一种操作方式，使得j选手可以成为剩下的那k个。
思路：
首先我们对k进行分析，k=1的时候直接特判，此时第j名选手只有最大才能宝珠。
当k>=2的时候，我们给出一个样例：
1 2 3 4 5 6
此时我们对上述数据进行若干次操作后发现，任意数据都能存活。
那么同理，如果有相同数据的话，也可以共存。
#include<bits/stdc++.h>
using namespace std;
inline void solve(){int n,j,k;cin>>n>>j>>k;vector<int>a(n+1);int mi=-1;for(int i=1;i<=n;i++){cin>>a[i];mi=max(a[i],mi);}if(k>=2){//两种情况cout<<"Yes"<<endl;return;}int ans=a[j];//此时要是整个数组里面最大的那一个if(ans==mi&&k==1){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
}
int main(){int n;cin>>n;//质数while(n--){solve();}
}
题目意思：
给定一个数组，可以做一次操作：
1.选择一个前缀a,并替换成最小值
2.选择一个后缀a,并替换成最大值
到最后数组里面只剩下最后一个数字，如果该数字对应第i个字符，则第i个字符为1，否则为0，
输出01字符串。
思路：
用两个数组，一个维护前缀最小值，一个维护后缀最大值，最后判断原数组是否与该两个数组中的任意一个相等即可。
其实他的原理就是根据题目的意思，维护前缀和后缀。
#include <bits/stdc++.h>
using namespace std;inline void solve() {int n;cin>>n;vector<int>a(n+1);vector<int>pre(n+1,8e18),suf(n+2);//pre维护的是前缀//suf维护的是后缀for(int i=1;i<=n;i++){cin>>a[i];pre[i]=min(pre[i-1],a[i]);}for(int i=n;i>=1;i--){suf[i]=max(suf[i+1],a[i]);}for(int i=1;i<=n;i++){cout<<(a[i]==pre[i]||a[i]==suf[i]?1:0);}cout<<endl;}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
题目意思：
给定一个字符串和两个操作：
Alice操作一次，选择任意k个位置将其变成0
Bob操作一次，选择连续k个位置将其变成1
问，在有限的操作次数内，是否能将整个字符串都变成0。
思路：
我们先对
7 4
1011011
这个数据进行分析
此时Alice进行一次操作
0001000
后Bob在进行一次操作（有多个可能性）
1111000
0011110
0001111
此时我们发现在这种情况下，Alice必胜，必胜的条件在于k，k必须是要大于等于n/2+1，此时刚好整个数组被覆盖的时候中间有重叠的部分。
最后在特判一下第一次Alice就能把数组恢复原状的情况即可。
#include <bits/stdc++.h>
using namespace std;inline void solve() {int n,k;cin>>n>>k;string ac;cin>>ac;int answer=n/2+1;int sum=0;ac=' '+ac;for(int i=1;i<=n;i++){if(ac[i]=='1')sum++;}//一遍就能把数组恢复原状if(sum<=k){cout<<"Alice"<<endl;return;}if(k<answer){cout<<"Bob"<<endl;return;}cout<<"Alice"<<endl;return;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}
题目意思：
定义MEX为数组中没有出现的最小非负数，如
MEX([2, 2, 1]) = 0，因为0不在数组中。
计算从a数组中删除k个值之后，MEX可能值的数量。（0<=k<=n）
思路：
首先我们先肯定一个事情k=0，和k=n一定是固定的，一定是1。
其次我们在考虑k等于1的时候可以从k=0考虑，同理后推。
此时我们发现，当存在多个相同的数字的时候，相同数字的数量成为了我们要考虑的一个点，从这个切口出发，我们构造一个差分数组即可。
#include <bits/stdc++.h>
using namespace std;
void solve(){int n;cin >> n;vector<int> a(n), answer(n+1), suf(n+2);map<int, int> p;for(int i=0; i<n; i++){cin >> a[i];p[a[i]]++;//统计各个数字出现的次数}for(int i=0; i<=n; i++){suf[p[i]]++;//统计次数出现的次数,并且往后进行自减suf[n-i+1]--;//差分if(!p[i])//当前数组中没有这个数字的话，直接跳出break;}for(int k=0; k<=n; k++){answer[k] = (k ? answer[k-1] : 0) + suf[k];//和我们之前说的一样，后面的k受前者k的影响cout << answer[k] << (k != n ? ' ' : '\n');}
}int main(){int t;cin >> t;while(t--) solve();
}
题目意思：
我们定义一个好数组，对于所有的i>=2,gcd(i,pi)!=1。
构造一个这样的数组，并使得固定点最少。（固定点：当i=p[i]）
思路：
其实样例已经给我们一些提示了，下标为2的数字，对应的是4，下标是4的数字对应的是2，而质数下的数字对应的是自己本身。(暂且我们只能从样例中看出这么些情况)
随后我们自己再枚举一些比较大的数据发现，质数i对应的可以是i*2，i*3，i*4....而i*2对应的可以是i*3,i*4...此时我们可以发现，这些数字（gcd=i）形成了一个环，每个数字只要对应的找到下一个数字即可满足gcd！=1的情况。
故：
我们只要先对质数进行预处理，再对每一个质数环进行赋值即可。
最后的最后，还有一个点就是如果从小素数开始遍历，小素数的倍数会覆盖更多的数（因为小素数的倍数更密集），导致后续大素数的倍数可能已经被分配到其他循环中。
如果从大素数开始遍历，大素数的倍数更稀疏，可以优先构建较大的循环，而小素数的倍数可以填充剩余的数。
从大的素数开始遍历可以使得固定点更小。
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<bool>cmp(1e5+3);
vector<int>zhi;
const int op=1e5+4;
void init(){// 埃拉托斯特尼筛法预计算素数for(int i=2;i*i<=op;i++){if(!cmp[i]){for(int j=i*i;j<=op;j+=i){cmp[j]=1;}}}for(int i=2;i<=op;i++)if(!cmp[i])zhi.push_back(i);
}
void solve(){int n;cin>>n;vector<int>answer(n+1);//cout<<*zhi.rbegin()<<endl;for(auto it=zhi.rbegin();it<zhi.rend();it++){//只能从后往前vector<int>c;for(int i=*it;i<=n;i+=*it){//在n这个范围内if(!answer[i]){c.push_back(i);}}for(int i=0;i<c.size();i++){answer[c[i]]=c[(i+1)%c.size()];}}/*for(int i=1;i<=n;i++){if(!answer[i]){answer[i]=i;}}*/answer[1]=1;for(int i=1;i<=n;i++){cout<<answer[i]<<(i!=n?' ':'\n');}return;
}
signed main(){init();int n;cin>>n;while(n--)solve();
}
)
