The 2024 ICPC Latin America Championship

Problem - D - Codeforces

题意:给定一个数字N,在N的因子中(包含本身)轮流取因子,Alice先手,当且仅当全部数字取完后,Alice选的数字的gcd不为1,Alice获胜,否则输.

思路:

显而易见,当因子个数为奇数时,先手必输.因为Bob总可以把因子1留给Alice.
再特判一下size==2,size==4.
剩下只有 ve.size()-1个可取的值才能赢,即因子中除了1,求gcd之后,gcd不为1,先手才能赢,即N为x的次幂,并且是奇数次幂.
否则的话,Bob总可以Force Alice去选两个不同集合的因子，他们的gcd为1.

int n;
显而易见,当因子个数为奇数时,先手必输.
再特判一下sz==2,sz==4
剩下只有 ve.size()-1个可取的值才能赢,即因子中除了1,求gcd之后,gcd不为1,先手才能赢,即N为x的次幂,并且是奇数次幂.
https://codeforces.com/gym/105053/problem/D
void solve(){   补D 畏惧数字cin >> n;vector<int>vct;for(int i=1;i<=n/i;i++) if(n%i==0){if(i==n/i) vct.push_back(i);else vct.push_back(i),vct.push_back(n/i);}int sz=vct.size();if(sz==2 || sz==4) {cout << "Y"; return ;}if(sz&1) {cout << "N"; return ;}int gcd0=0;for(auto v:vct){if(v==1) continue;gcd0=gcd(gcd0,v);}if(gcd0==1) {cout << "N"; return ;}else {cout << "Y"; return ;}
}

Problem - E - Codeforces

题意:给定数字的出栈入栈顺序，问是否能把他们编排在两个不同的栈，使得输入的出入栈顺序符合规则。

思路:

这种题模拟+贪心是不行的.
很典型的分组题..而且只要分两个组,那么建图,染两种颜色即可.
当存在2 1 3 -1 -2 -3,那么1和3肯定不在同一个栈,2和3肯定不在同一个栈,那么都把他们建边.
建图之后给每个点染色,只要相邻的点的颜色都不一样,那么就是有解的.
赛时完全没有想到建图染色,还是题写少了.

int n;
vector<int> vct,edge[1003];
bool vis[1003];
char ans[1003];
这种题模拟+贪心是不行的.
很典型的分组题..而且只要分两个组,那么建图,染两种颜色即可.
赛时完全没有想到建图染色,还是题写少了.
https://codeforces.com/gym/105053/problem/E
void solve(){       补E    赛时一直认为是 模拟+贪心..cin>>n;for(int i=1;i<=2*n;i++){if(i<=n) ans[i]='?';string str; cin>>str;int num=stoi(str.substr(1));if(str[0]=='+') vct.emplace_back(num);else{for(auto v:vct){if(v==num) vis[num]=true;if(vis[v]) continue;if(vis[num]) edge[num].emplace_back(v),edge[v].emplace_back(num);}}}queue<int> que;for(int i=1;i<=n;i++){if(ans[i]!='?') continue;que.emplace(i);while((int)que.size()){int from=que.front();que.pop();bool c1=false,c2=false;for(auto e:edge[from]){if(ans[e]=='?') que.emplace(e);if(ans[e]=='G') c1=true;if(ans[e]=='S') c2=true;}if(c1&&c2){ cout<<"*"; return; }if(!c1) ans[from]='G';else ans[from]='S';}}for(int i=1;i<=n;i++) cout<<ans[i];
}

Problem - F - Codeforces

思路:

裴蜀定理+二进制优化多重背包
(ax+by=gcd(x,y),但是题目要求a,b>=1??
并且有2e5组数字,怎么分成两组?)
多重背包,可以处理出所有可能达到的基层高度x,那么abs((sum-x)-x)就是基层的差值
如果两栋楼的基层之差是gcd的倍数,那么必然有解(裴蜀定理).
要注意的是，在裴蜀定理中：a*x0+b*x1+c*x2+d*x3=gcd(x0,x1,x2,x3),系数a,b,c,d的正负号是不影响定理的正确性的.

int n;
int f[200005];//f[i]为基层为i的高度是否可达  //The sum of the heights of the ground floors of all blueprints is at most 2e5
int cnt[200005];
裴蜀定理+二进制优化多重背包
ax+by=gcd(x,y),但是题目要求a,b>=1.
并且有2e5组数字,怎么分成两组?--背包
多重背包,可以处理出所有可能达到的基层高度x,那么abs((sum-x)-x)就是基层的差值
如果两栋楼的基层之差是gcd的倍数,那么必然有解(裴蜀定理).
要注意的是，在裴蜀定理中：a*x0+b*x1+c*x2+d*x3=gcd(x0,x1,x2,x3),系数a,b,c,d的正负号是不影响定理的正确性的.
https://codeforces.com/gym/105053/problem/F
void solve(){           补Fcin>>n;int gSum=0,rGcd=0;unordered_set<int> uSt;for(int i=1;i<=n;i++){int g,r; cin>>g>>r;gSum+=g,rGcd=gcd(rGcd,r);cnt[g]++,uSt.emplace(g);}if(n==1){ cout<<"N"; return; }f[0]=1;  //初始化第0层for(auto s:uSt){  //这里不能是o(n)的int have=cnt[s];这样写二进制压缩是完全错的..还能跑到75..样例75是2e5个g=1,r=1000000000,即基层就已经平均分配了,与gcd无关.
//        for(int j=20;j>=0;j--){ 二进制压缩
//            int get=(1ll<<j);
//            if(get<=have){
//                have-=get;
//                for(int h=gSum;h>=get*s;h--) f[h]|=f[h-(get*s)];  //o(n)
//            }
//        }vector<int> object;多重背包压缩应该从低位向高位压缩.for(int k=1;k<=have;k*=2) have-=k,object.emplace_back(k*s);if(have) object.emplace_back(have*s);for(auto o:object){  //o(logn)for(int h=gSum;h>=o;h--) f[h]|=f[h-o]; //o(n)}}int start=uSt.count(0)^1;  key:如果存在第0层,那么从第0层开始是合法的;否则从第一层开始.for(int i=start;i<=gSum;i++){if(start!=0&&i==gSum) break; key:如果没有0层的,那么gSum的状态是违法的--改了之后从wa7->wa75if(f[i]){if(abs((gSum-i)-i)%rGcd==0){  裴蜀定理cout<<"Y";return;}}}cout<<"N";
}