哈，這個比賽在開了不久之后，不知道為啥卡了差不多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();
}
)
