A. Three Decks
#1.由于最后三個數會相等，提前算出來和，%3判斷，再判前兩個數是否大于
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int a,b,c;cin>>a>>b>>c;if((a+b+c)%3==0){int tmp=(a+b+c)/3;if((a<=tmp)&&(b<=tmp))cout<<"YES"<<endl;else cout<<"NO"<<endl;}else cout<<"NO"<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}B. Move to the End
我們每次要從數組末尾拿1,2,3...一直到n?個數，對于每次取，我都可以拿一個數到數組末尾。
#1.為此我們可以取一個前綴max數組，討論從后向前的k個元素的前綴max是否大于這個元素
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n;cin>>n;vector<ll>a(n+1);vector<ll>pre(n+1,0);for(int i=1;i<=n;i++){cin>>a[i];pre[i]=max(pre[i-1],a[i]);}ll sum=0;for(int i=n;i>=1;i--){sum+=a[i];if(pre[i-1]>a[i])cout<<sum-a[i]+pre[i-1]<<" ";else cout<<sum<<" ";}cout<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}C. Card Game
有n張卡，編號大的克制編號小的，特別的1克制n，每回合Alice先出，Bob后手，如Alice克制Bob則得Alice得這兩張牌，反之Bob
#1.注意到由于Alice先手，只有無論Alice出任何牌Bob都能克制她時，Bob勝，其余情況Alice勝
#2.可以用vector存Alice的牌，set存Bob的牌，二分＋特判
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n;cin>>n;string s;cin>>s;vector<int>a;s="#"+s;set<int>st;bool tag=true;for(int i=1;i<=n;i++){if(s[i]=='A')a.push_back(i);else st.insert(i);}int l=a.size();for(int i=0;i<l;i++){if(a[i]==n){if(!(st.count(1)))tag=false;}else{auto it=st.upper_bound(a[i]);if(a[i]==1){if(*it==n)tag=false;}else{if(*it<a[i])tag=false;}}}if(tag)cout<<"Bob"<<endl;else cout<<"Alice"<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}D. Array and GCD
給一個長為n的數組a，可以讓數組中的任一元素減1，另一元素加1，也可只減不加，最后問最少刪幾個元素能讓數組任意兩個元素之間互質，(刪元素要在操作之前)，并且要保證操作后的數組中任意元素都是>=2的
#1. 要讓任意兩個元素之間互素，當數組中都是素數即可
#2.再來考慮操作，我能讓數組中任意元素變化，但數組的總和只能是不變或變小的，假設剩了x個元素，它最小應該是前x個素數相加。
#3.到這只需用歐拉篩篩到1e7(大概6e5個素數)，在對素數做前綴和，即為保留i個元素，i個元素的總和至少為多少
#4.保持貪心性質，刪數只刪最小的
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e7 + 10;
const int M=1e6+4;
bool vis[N];
vector<int>primes;
ll pre[M];
void init(int x)
{vis[0]=vis[1]=true;for(int i=2;i<=x;i++){if(!vis[i])primes.push_back(i);int l=primes.size();for(int j=0;j<l&&primes[j]*i<=x;j++){vis[i*primes[j]]=true;if(i%primes[j]==0)break;}}
}
void solve()
{int n;cin>>n;vector<int>a(n+1);ll sum=0;for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];sort(a.begin()+1,a.end(),greater<int>());if(n<2){cout<<0<<endl;return;}for(int i=n;i>=2;i--){if(sum>=pre[i]){cout<<n-i<<endl;return;}sum-=a[i];}cout<<n-1<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;init(1e7);int l=primes.size();//cout<<l<<endl;for(int i=0;i<l;i++){pre[i+1]=pre[i]+primes[i];}while (t--){solve();}return 0;
}E. Unpleasant Strings
給一個長為n的字符串s，其中只能出現26個字母前k個字母，q次詢問，每次詢問給一個字符串，對于每次詢問給出至少添加幾個字母能使它不為s的子序列。
#1.對于本就不是它的子序列的字符串，添加0個。那就需要判斷以一個字符串是否為另一個字符串的子序列。k很小，可以將每種字符用vector存起來，在判斷時，只需要遍歷要判斷的字符串，二分對于這個字符出現序列中第一個大于上一個位置的位置
#2.通過上述方法可以找到這個字符串作為子序列第一個末尾，對于后續元素至少要添加的元素數量，我們可以采用后綴和提前預處理出答案，后綴和是從后向前遍歷，將k個元素都出現的一段視作1，再做后綴和
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int l,q,k;cin>>l>>k;string s;cin>>s;string str;vector<vector<int>>dp(k+1,vector<int>());vector<ll>suf(l+3,0);s="#"+s;for(int i=1;i<=l;i++){dp[s[i]-'a'+1].push_back(i);}suf[l]=0;int cnt=0;vector<bool>vis(k+1,false);for(int i=l-1;i>=0;i--){if(!vis[s[i+1]-'a'+1])cnt++,vis[s[i+1]-'a'+1]=true;suf[i]=suf[i+1]+(cnt==k);if(cnt==k){fill(vis.begin(),vis.end(),false);cnt=0;}}cin>>q;while(q--){cin>>str;int len=str.length();int pos=-1;bool tag=true;for(int i=0;i<len;i++){int x=str[i]-'a'+1;auto tmp=upper_bound(dp[x].begin(),dp[x].end(),pos);//cout<<tmp<<endl;if(tmp==dp[x].end()){tag=false;break;}pos=*tmp;//cout<<pos<<endl;}if(!tag){cout<<0<<endl;continue;}//cout<<pos<<endl;cout<<suf[pos]+1<<endl;}return 0;
}
