非常好重测，使我 Rank--
Rank
A. 法阵
出题人注：原题 3100，张口放 T1
一眼高难度题，于是果断开始暴力打表，但我的打表程序十分暴力，跑 \(n=6,m=9\) 的点就已经开始硬控了，遂只拿到 30pts。
打表就不用放了吧，等我咕咕正解。
B. 连通块
同[yLCPC2024] F. PANDORA PARADOXXX
真正的 T1。
赛时由于 T1 的搞心态以及极冷的室内环境，让我几乎没有办法去想暴力以外的东西。考虑对于每次询问，对询问的该点进行 bfs，删边的话只需要在建边的时候加个序号记一下就行，可以过 50pts；然后对于链的情况，我直接用线段树维护每个区段所属的连通块序号，以及每个联通块的左右边界，实现了 \(\mathcal{O(1)}\) 查询，\(\mathcal{O(\log n)}\) 修改，再过 10pts。
正解是倒过来做，删边操作变成建边操作，每次建边相当于一次树上启发式合并，维护树上直径信息就行了。
点击查看代码
求 LCA 用的倍增，常数较大，酌情参考。
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=2e5+5;
const int mod=998244353;
int n,m;
int hh[N],to[N<<1],ne[N<<1],cnt;
int dfn[N],dep[N],tot,fx[N][20],ans[N],ttot;
bool yz[N];
struct edge{int u,v;}e[N];
struct OP{int op,x;}p[N];
struct rmm{int fx,l,r,dis;}fa[N];
namespace Wisadel
{
int Wfind(int x)
{
if(x==fa[x].fx) return x;
return fa[x].fx=Wfind(fa[x].fx);
}
void Wadd(int u,int v)
{
to[++cnt]=v;
ne[cnt]=hh[u];
hh[u]=cnt;
}
void Wdfs(int u,int fa)
{
fx[u][0]=fa,dfn[u]=++tot,dep[u]=dep[fa]+1;
fo(i,1,18) fx[u][i]=fx[fx[u][i-1]][i-1];
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==fa) continue;
Wdfs(v,u);
}
}
int Wlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
fu(i,18,0) if((1<<i)<=dep[x]-dep[y]) x=fx[x][i];
if(x==y) return x;
fu(i,18,0) if(fx[x][i]!=fx[y][i]) x=fx[x][i],y=fx[y][i];
return fx[x][0];
}
int Wgdis(int u,int v)
{
if(u==v) return 0;
return dep[u]+dep[v]-2*dep[Wlca(u,v)];
}
void Wmerge(int i)
{
int u=Wfind(e[i].u),v=Wfind(e[i].v);
fa[u].fx=v;
int maxx=max(Wgdis(fa[u].l,fa[v].l),Wgdis(fa[u].l,fa[v].r));
maxx=max(maxx,max(Wgdis(fa[u].r,fa[v].l),Wgdis(fa[u].r,fa[v].r)));
maxx=max(maxx,max(fa[u].dis,fa[v].dis));
if(Wgdis(fa[u].l,fa[v].l)==maxx){
fa[v].dis=Wgdis(fa[u].l,fa[v].l),
fa[v].r=fa[u].l;
return;
}
if(Wgdis(fa[u].r,fa[v].l)==maxx){
fa[v].dis=Wgdis(fa[u].r,fa[v].l),
fa[v].r=fa[u].r;
return;
}
if(Wgdis(fa[u].l,fa[v].r)==maxx){
fa[v].dis=Wgdis(fa[u].l,fa[v].r),
fa[v].l=fa[u].l;
return;
}
if(Wgdis(fa[u].r,fa[v].r)==maxx){
fa[v].dis=Wgdis(fa[u].r,fa[v].r),
fa[v].l=fa[u].r;
return;
}
if(fa[u].dis==maxx){
fa[v].dis=fa[u].dis,
fa[v].l=fa[u].l,fa[v].r=fa[u].r;
return;
}
}
short main()
{
freopen("block.in","r",stdin),freopen("block.out","w",stdout);
n=qr,m=qr;
memset(hh,-1,sizeof hh);
fo(i,1,n)fa[i]={i,i,i,0};
fo(i,1,n-1)
e[i].u=qr,e[i].v=qr,Wadd(e[i].u,e[i].v),Wadd(e[i].v,e[i].u);
Wdfs(1,0);
fo(i,1,m)
{
p[i].op=qr,p[i].x=qr;
if(p[i].op==1) yz[p[i].x]=1;
}
fo(i,1,n-1) if(!yz[i]) Wmerge(i);
fu(i,m,1)
if(p[i].op==1) Wmerge(p[i].x);
else
{
int _=p[i].x,__=Wfind(_);
ans[++ttot]=max(Wgdis(fa[__].l,_),Wgdis(fa[__].r,_));
}
fu(i,ttot,1) printf("%d\n",ans[i]);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 军队
题面挺抽象的。
大概就是划分成两个问题，一是需要 \(\mathcal{O(n)}\) 求出各队的性别情况，要用到扫描线，二是对于询问求最大值，相比而言第二步较简单些。
赛时没想到扫描线，只会 \(\mathcal{O(n^3)}\) 处理性别，遂只打暴力 20pts。
正解咕咕咕。
D. 棋盘
逆天要 4 个栈。
一眼简单，再一眼困难。
可恶啊赛时没想到过河卒（忘得挺彻底的，遂只打暴力 bfs，只过 \(n=2\) 的 10pts。
用过河卒的方法每次清空 dp 数组可以拿到 30pts 的暴力分。
40pts 代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=1e5+5;
const int mod=998244353;
int n,q,to,ans;
int dh[N][22],st=1,ed;
int yz[N][22],f[N][22];
namespace Wistask
{
void Wdfs(int nowh,int nowl)
{
if(nowh==ed)
{
if(nowl==to) ans=(ans+1)%mod;
return;
}
if(nowl==1)
{
if(dh[nowh+2][2]!=1) Wdfs(nowh+2,2);
return;
}
else
{
if(dh[nowh+2][1]!=1) Wdfs(nowh+2,1);
return;
}
}
short main()
{
while(q--)
{
string op,s;cin>>op;
if(op=="Add")
{
cin>>s;ed++;
fo(i,0,n-1) dh[ed][i+1]=(s[i]=='#');
}
else if(op=="Del") st++;
else
{
int a=qr;to=qr;ans=0;
if(st>ed||(ed-st)&1||dh[st][a]==1){printf("0\n");continue;}
Wdfs(st,a);
printf("%d\n",ans);
}
}
return Ratio;
}
}
namespace Wisadel
{
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
freopen("chess.in","r",stdin),freopen("chess.out","w",stdout);
n=qr,q=qr;
// printf("%lf\n",1.0*sizeof(dh)/1024/1024);
if(n==1)
{
while(q--)
{
string op,s;cin>>op;int a,b;
if(op=="Add") cin>>s;
else if(op=="Del") continue;
else a=qr,b=qr,printf("0\n");
}
return Ratio;
}
if(n==2) return Wistask::main();
while(q--)
{
string op,s;cin>>op;
if(op=="Add")
{
cin>>s;ed++;
fo(i,0,n-1) dh[ed][i+1]=(s[i]=='#');
}
else if(op=="Del") st++;
else
{
int a=qr;to=qr;ans=0;
memset(f,0,sizeof f);
if(dh[st][a]!=1) f[st][a]=1;
else {printf("0\n");continue;}
fo(i,st+1,ed) fo(j,1,n)
{
if(dh[i][j]) continue;
if(i-st>=2)
{
if(j>1) f[i][j]=(f[i][j]+f[i-2][j-1])%mod;
if(j+1<=n) f[i][j]=(f[i][j]+f[i-2][j+1])%mod;
}
if(i-st>=1)
{
if(j>2) f[i][j]=(f[i][j]+f[i-1][j-2])%mod;
if(j+2<=n) f[i][j]=(f[i][j]+f[i-1][j+2])%mod;
}
}
printf("%d\n",f[ed][to]);
}
}
return Ratio;
}
}
int main(){return Wisadel::main();}
末
直接从 CSP 模拟晋升到 NOIP 模拟，难度直线上升。
看到 pdf 就觉得不对劲了，不是牛犇外校大佬出题就是逆天私题，果然被薄纱了。
打暴力手法还有欠缺，不过好在今天学到了新（确信 东西——树上连通块转移直径，不算荒了。
越来越冷了，虽然空调不直对着我（要真直对着估计早寄了，感觉这样下去过几天就也感冒发烧了，悲。
完结撒花~
标签：qr,22,ed,st,ch,else,CSP,模拟,op From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18363585