10月20日模拟赛复盘：一次惨烈的“防线压力测试”
一、 战报
分数极其惨淡，T1、T3暴力挂飞，T2因神秘问题彻底爆炸，T4没看。这是一次不折不扣的滑铁卢。
二、 病灶剖析（防守漏洞）
- T2（连锁崩溃）：逻辑极其清晰（对应CF 2300），本该稳拿的题。却因为手抄文件名少了个
s导致报错，自己却以为是逻辑挂了，病急乱投医把初始化挪后并加了continue，直接导致代码结构崩盘。 - T1（实现断层）：看破了
gcd的关键联系，但写不出来，退而求其次的暴力过于拙劣，导致在子任务捆包下爆零。 - T3（暴力不稳）：见过原题，明智地放弃了长数据结构正解，选择打25分暴力，但暴力依然写挂了。
三、 战略收获（阵型重构）
- 思维上限确认：能在赛场上推导出CF 2300的逻辑，证明我的算法直觉和思维高度是够的。我的问题不是“不会”，而是“代码实现的手在发抖”。
- 战术目标明确：放弃对T3、T4正解的执念。死保T1、T2，用最严谨的暴力去薅T3、T4的部分分（拼包）。如果T1T2能焊死，加上不平凡的暴力，复赛依然能冲得很靠前。
四、 封板前的绝对纪律
- 文件名直接复制粘贴，绝不手抄。
- 遇到 RE 或报错，第一反应查文件读写、数组大小、除零和爆栈，绝不乱改核心逻辑。
- 暴力不是“写个大概”，必须覆盖所有边界（n=1，全相同，极值），自己造数据过了才算数。
- 沉下心，不害怕，每天默写模板。
五、 结语
希望犹存。今天这场惨败，是泰拉围城前的一次防线压力测试。被打穿不可怕，可怕的是不去补窟窿。接下来的10天，排雷、筑垒、默写、对拍。
LGP17161 [入门赛 #50] 数论对称差
原题链接：[入门赛 #50] 数论对称差
分析
我在赛后得到了这个trick，就是：
a n s = r a d ( x ) × r a d ( y ) r a d ( gcd ( x , y ) ) 2 ans=\frac{rad(x)\times rad(y)}{rad(\gcd(x,y))^2}ans=rad(gcd(x,y))2rad(x)×rad(y)
其中，我们引用原题中的集合名称P PP，现在，我们有P ( x ) ， P ( y ) P(x)，P(y)P(x)，P(y)，那么，我们来表示r a d ( ) rad()rad()：
r a d ( x ) = ∏ v ∈ P ( x ) v r a d ( y ) = ∏ v ∈ P ( y ) v r a d ( gcd ( x , y ) ) = ∏ v ∈ P ( x ) ∩ P ( y ) v rad(x)=\prod\limits_{v\in P(x)}{v}\\ rad(y)=\prod\limits_{v\in P(y)}{v}\\ rad(\gcd(x,y))=\prod\limits_{v\in P(x)\cap P(y)}{v}rad(x)=v∈P(x)∏vrad(y)=v∈P(y)∏vrad(gcd(x,y))=v∈P(x)∩P(y)∏v
那么，我们只需要预处理出来r a d radrad即可，模拟埃式筛即可。
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=10000005;intT;intrad[N];voidInit(){for(inti=1;i<N;i++)rad[i]=1;for(inti=2;i<N;i++){if(rad[i]==1){for(intj=i;j<N;j+=i)rad[j]*=i;}}}signedmain(){// freopen("factor.in", "r", stdin);// freopen("factor.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;Init();for(intcs=1,x,y;cs<=T;cs++){cin>>x>>y;intg=__gcd(x,y);intans=rad[x]*rad[y]/(rad[g]*rad[g]);cout<<ans<<"\n";}}CF1385G Columns Swaps
原题链接：G. Columns Swaps
分析
这个场上想出来图论建模了，但是，首先文件名写错了，其次，初始化有一部分被continue了，然后写法也比较拙劣，所以，那还说啥，跳了吧。
明确一下思路吧。
场上我想的是对于处于同一行的两个相同的数，我们只需要交换其对应的下面的东西的状物……啊吧啊吧……然后，我认为做完了。
但是D DD老师说这个需要什么把所有路径异或起来。但是看题解里应该是没有的。
不想看了。调整好心态吧。
正解
#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intt,n;inta[N][2],cnt[N];vector<pair<int,int>>e[N];boolvis[N];intdir(intv,intid){returna[id][0]==v?0:1;}signedmain(){// freopen("columns.in", "r", stdin);// freopen("columns.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;for(inti=1;i<=n;i++){cnt[i]=0;e[i].clear();vis[i]=false;}for(intj=0;j<=1;j++){for(inti=1;i<=n;i++){cin>>a[i][j];}}for(inti=1;i<=n;i++){cnt[a[i][0]]++;cnt[a[i][1]]++;}boolflag=true;for(inti=1;i<=n;i++){if(cnt[i]!=2){flag=false;break;}}if(!flag){cout<<-1<<"\n";continue;}for(inti=1;i<=n;i++){intu=a[i][0],v=a[i][1];if(u==v){vis[i]=true;continue;}e[u].push_back({v,i});e[v].push_back({u,i});}vector<int>ans;for(inti=1;i<=n;i++){if(vis[i]){continue;}vector<int>verts,edges;intstartV=a[i][0];intcurV=startV,curE=i;while(true){vis[curE]=true;verts.push_back(curV);edges.push_back(curE);intx=a[curE][0],y=a[curE][1];intnxtV=(x==curV?y:x);if(nxtV==startV){break;}intnxtE=-1;for(autopr:e[nxtV]){if(pr.second!=curE){nxtE=pr.second;break;}}if(nxtE==-1){flag=false;break;}curV=nxtV;curE=nxtE;}if(!flag){break;}intm=edges.size();vector<int>b(m),x(m,0);for(intj=0;j<m;j++){intpre=edges[(j-1+m)%m];intcur=edges[j];intv=verts[j];b[j]=dir(v,pre)^dir(v,cur)^1;}for(intj=1;j<m;j++){x[j]=x[j-1]^b[j];}if((x[m-1]^x[0])!=b[0]){flag=false;break;}intc0=0;for(intj=0;j<m;j++){c0+=x[j];}if(c0<=m-c0){for(intj=0;j<m;j++){if(x[j]){ans.push_back(edges[j]);}}}else{for(intj=0;j<m;j++){if(!x[j]){ans.push_back(edges[j]);}}}}if(!flag){cout<<-1<<"\n";continue;}cout<<ans.size()<<"\n";if(!ans.empty()){for(inti=0;i<(int)ans.size();i++){if(i){cout<<" ";}cout<<ans[i];}cout<<"\n";}}}LGP15482 [CERC2012] Jewel heist
原题链接：[CERC2012] Jewel heist
分析
恰好一个月之前写的这个题。
显然我当时和现在都秒掉了第一步，就是枚举不选的颜色，然后，这些点会延伸出来一些向上的射线，我们所选取的线段要把不与任何相交。那就取中间的不久可以了吗？一共是O ( n ) O(n)O(n)的，所以说，我们再掏出一个线段树或者树状数组之类的东西取max \maxmax即可。
正解
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=200005;intT;intn,k;structnode{intx,y,c;}inp[N];boolcmp(node tmp1,node tmp2){if(tmp1.y==tmp2.y)returntmp1.x<tmp2.x;returntmp1.y<tmp2.y;}inta[N],b[N];intc[N];intlenl,lenr;voidadd(intx,intval){for(inti=x;i<=lenl;i+=i&(-i)){c[i]+=val;}}intquery(intx){intres=0;for(inti=x;i;i-=i&(-i)){res+=c[i];}returnres;}set<int>s[N];voidinit(){memset(c,0,sizeof(c));for(inti=1;i<=k;i++)s[i].clear();}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;for(intcs=1;cs<=T;cs++){init();cin>>n>>k;for(inti=1;i<=n;i++){cin>>inp[i].x>>inp[i].y>>inp[i].c;a[i]=inp[i].x;b[i]=inp[i].y;}sort(a+1,a+n+1);sort(b+1,b+n+1);lenl=unique(a+1,a+n+1)-a-1;lenr=unique(b+1,b+n+1)-b-1;for(inti=1;i<=n;i++){inp[i].x=lower_bound(a+1,a+lenl+1,inp[i].x)-a;inp[i].y=lower_bound(b+1,b+lenr+1,inp[i].y)-b;}sort(inp+1,inp+n+1,cmp);for(inti=1;i<=k;i++){s[i].insert(0);s[i].insert(lenl+1);}intans=0xc0c0c0c0c0c0c0c0c0;multiset<int>t;for(inti=1;i<=n;i++){if(inp[i].y!=inp[i-1].y){for(autov:t)add(v,1);t.clear();}boolflag=s[inp[i].c].find(inp[i].x)!=s[inp[i].c].end();if(!flag){autor=s[inp[i].c].lower_bound(inp[i].x);autol=r;l--;ans=max(ans,query(*r-1)-query(*l));}s[inp[i].c].insert(inp[i].x);t.insert(inp[i].x);}for(autov:t)add(v,1);t.clear();for(intc=1;c<=k;c++){intpos=0;for(autov:s[c]){if(v){ans=max(ans,query(v-1)-query(pos));pos=v;}}}cout<<ans<<'\n';}}LGP7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping
原题链接：[JOI 2018 Final] 毒蛇越狱 / Snake Escaping
