2023省选游记
NOIP后
“你只要做出四题应该还是可以进队的”——教练
嗯，我高考考七百多分就可以上清北了市三检没上六百的菜鸡在想什么。
嘛，毕竟NOIP考成那鸟样，虽然可惜，但我的OI生涯就只能如此草草收场了。
之后就没怎么碰OI了，再看时洛谷已经掉到橙名了。
现在是真的什么都不会了。
但毕竟是曾经赋予了大量期望的一场考试，最后还是决定参加一下表示尊重。
教练因为一些原因无法带队，只能自己参加考试，社恐的我一度想放弃考试，所幸没什么报名流程。
Day0
早上上完数学课，中午出发，坐动车赶上了试机，是上次NOIP时就眼馋的win10机房，花了一些时间找键盘的手感（退役之后用的薄膜键盘），研究了一下对拍。
出来之后看官网的公告被上面的NoiLinux搞不会了，自己的虚拟机因为没带移动硬盘而无法使用，吓得我临时弄了个阿里云的云电脑（免费试用），然后才知道FJ不知道在哪又发了个公告改成了win+虚拟机。
Day1
早上六点起来随便看了几个板子luogu国际版是什么鬼？，在酒店吃完早饭（似乎比上次NOIP时要好一些），就去了考场。
似乎是第一个进了考场，提前打完了快读开始摆烂。
与昨天试机时不同，今天dev的debug死活打不开，只能开虚拟机的gdb来调试，键盘也比昨天卡很多。
开了乐虎，罕见地中了奖（“一元乐享”），出考场的时候因为情绪低落随手扔到走廊的垃圾桶里了虽然留着也没啥用。
T1简单到难以置信，以至于我多次误解题目，加上开错了T2的样例（随手开了第一个，输入长得差不多）加深了我的误解，于是白给了近一个小时才发现只是个红题。
T2初看比较毒瘤，无向图划分？有点不知所措，于是开了T3。
T3大概是数据结构一眼DDP，四个月没碰这玩意的我果断放弃了思考，花半小时写了个
再看T2,此时还剩近3个小时。手玩一下发现并喜提MLE，现在我光是搞出边双就快用了一个小时，然后又折腾了大量时间才把计数部分搞出来，最后没调完就结束了。
拿到代码之后发现T2计数写挂了，喜提0pts。
耗费大量时间最后因为某个小错误而付之一炬，这个问题几乎存在于我的每场考试中，我的整个OI生涯也是如此。或许是心态的问题吧就是菜，不过对已经退役的我来说已经无所谓了。
大概
下午已经没有动力了，一直在摸鱼。
Day 2
剑走偏锋，早上起来背多项式的板子就算真出了也写不出来。
T1初看像个很麻烦的图论+构造，果断放弃，直接开T3。
T3题目看到“数组——”又是个计数，还以为早上背的板子要派上用场了，决定先搞它。
于是从8：30玩到了10：00，还是没找到什么这个数列有什么决定性的性质，最后无奈放弃这种题一开始思考就会忘记时间，重新回到T1。
注意到T1数据非常小第一次看竟然没注意到，总共只会有为什么我还记得这种东西，开一个队列，从结束局面倒着搜，如果是P态那能到达它的都是N态，N态的话就检查能到达它的点是否只能到达N态，如果一个点状态确定了，就压入队列，如果到最后都没有确定的话就是平局，N态记录最短路，P态记录最长路，这么看来或许只是蓝题。
但是实际写起来代码长度就到了4K3，写完大概11：30,编译都过不了，又花了20分钟才想起来是y1y2的锅，幸好有sublime可以批量修改。又过不了样例，因为状态过多又写了状态压缩，导致调试起来非常痛苦，只能静态查错，看着时间一分一秒地流逝，心跳开始加速，手也开始抖（出考场的时候感觉舌头都麻了，你可以想象四个月没碰OI的人写出来的大模拟是什么样子。），担心要重蹈FJOI2022D1的覆辙。终于在还有大概15分钟的时候过了小样例（看到那个75就感觉很稳），但是第二个样例就输出了一个“Tie”，又让我不知所措，最后五分钟才意识到快读锅了，把while打成了if，只能读入第一个字符，改完还是只输出了9个点，最后赌一把把read换成scanf（已经差不多忘了这玩意怎么用了，没想到陪伴我整个OI之旅的快读竟然会在这最后一场考试挂掉），成功过了第二个样例，此时还剩两分钟。
T1应该大家都会写吧,这次又要被吊打了。
总觉得这样很多实力没发挥出来不得不结束还是有点意难平就一个小菜鸡有什么实力，不过盛衰之理，虽曰天命，岂非人事哉？或许到底都是学艺不精，经验不够，基础不牢罢了。
祝大家都能有个光明的未来。
有道小图灵：
upd:虽然D2T1被卡常了，卡了5分（编码解码常数太大了），不过D1T2又白送了5分。
总分
附代码 D1T1
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')f=(c!='-'),c=getchar();
while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
if(f)return x;return -x;
}
const int maxn=4e6+10;
//int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*b%mod;a=a*a%mod,b<<=1;}return ans;}
struct range{int l,r;}a[maxn];
int cmp1(range a,range b){return a.l<b.l;}
int cmp2(range a,range b){return a.r>b.r;}
int vis[maxn];
signed main(){
freopen("station.in","r",stdin);
freopen("station.out","w",stdout);
int n=read(),m=read(),x=read();
for(int i=1;i<=m;i++)a[i]={read(),read()};
sort(a+1,a+1+m,cmp1);
for(int i=1,now=x;i<=m;i++){
if(a[i].r<=x)continue;
if(a[i].l<=now)now=max(now,a[i].r),vis[a[i].r]=1;
}
sort(a+1,a+1+m,cmp2);
for(int i=1,now=x;i<=m;i++){
if(a[i].l>=x)continue;
if(a[i].r>=now)now=min(now,a[i].l),vis[a[i].l]=1;
}
for(int i=1;i<=n;i++)if(vis[i])printf("%lld ",i);
return 0;
}
/*
int vis[maxn];
signed main(){
int n=read(),m=read(),x=read();
for(int i=1;i<=m;i++){
int l=read(),r=read();
if(l<=x&&x<=r){
if(x!=l)vis[r]=1;
if(x!=r)vis[l]=1;
}
}
for(int i=1;i<=n;i++)if(vis[i])printf("%lld ",i);
return 0;
}*/
D1T2
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')f=(c!='-'),c=getchar();
while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
if(f)return x;return -x;
}
const int maxn=4e5+10,mod=998244353;
int cut[maxn],n,m,k,K,qp[maxn],ans;
map<pair<int,int>,int> mp;
int head[maxn],ver[maxn],nxt[maxn],wgh[maxn],tot=1;
void add(int a,int b,int c){ver[++tot]=b,nxt[tot]=head[a],head[a]=tot,wgh[tot]=c;}
#define fore(u,i) for(int i=head[u];i;i=nxt[i])
int dfn[maxn],lst[maxn],idx=0;
void tarjan(int u,int in){
dfn[u]=lst[u]=++idx;
fore(u,i)if(!dfn[ver[i]]){
tarjan(ver[i],i);lst[u]=min(lst[u],lst[ver[i]]);
}else lst[u]=min(lst[u],dfn[u]);
if(dfn[u]==lst[u])cut[in]=cut[in^1]=1;
}
int tp[maxn],siz[maxn];
vector<int> S[maxn];
void dfs(int u,int top){tp[u]=top;siz[top]++;S[top].push_back(u);fore(u,i)if(!tp[ver[i]])dfs(ver[i],cut[i]?ver[i]:top);}
int f[maxn],Siz[maxn];
void dp(int x,int fa){
Siz[x]=siz[x],f[x]=1;
for(int u:S[x]){
int W=1,sz=1,tmp=1;
fore(u,i)if(ver[i]!=fa&&cut[i]){dp(ver[i],u);tmp+=Siz[ver[i]]%K,sz+=Siz[ver[i]],W=W*f[ver[i]]%mod;if(Siz[ver[i]]%K)W=W*(qp[wgh[i]]-1)%mod;}
if(x!=u){if(K==tmp)f[x]=f[x]*W%mod;else f[x]=0;}
if(tmp+n-sz==K&&sz!=1){
int cnt=0;
fore(u,i)if(!cut[i])cnt++;
W=W*(qp[cnt]-1)%mod;
ans=(ans+W)%mod;
}
Siz[x]+=sz;
}
}
signed main(){
freopen("cities.in","r",stdin);
freopen("cities.out","w",stdout);
n=read(),m=read(),k=read(),ans=1;
qp[0]=1;for(int i=1;i<=m;i++)qp[i]=qp[i-1]*2%mod;
for(int i=1;i<=m;i++){
int u=read(),v=read();
if(u>v)swap(u,v);
if(!mp.count({u,v}))mp[{u,v}]=1;
else mp[{u,v}]++;
}
for(auto e:mp){
int w=e.second,u=e.first.first,v=e.first.second;
add(u,v,w);add(u,v,w);
}
tarjan(1,1);dfs(1,1);
for(K=2;K<=n;K++)if(n%K==0)dp(1,1);
printf("%lld",ans);
return 0;
}
/*
4 4 0
1 2
2 3
3 4
1 3
*/
D1T3
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')f=(c!='-'),c=getchar();
while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
if(f)return x;return -x;
}
const int maxn=4e5+10;
//int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*b%mod;a=a*a%mod,b<<=1;}return ans;}
typedef priority_queue<int> pq;
pq q[maxn];
pq* p[maxn];
pq* merge(pq* a,pq* b){
if((a->size())<(b->size()))swap(a,b);
while(b->size()){
int tmp=b->top();
a->push(tmp);b->pop();
}
return a;
}
int f[maxn],siz[maxn];
vector<int> son[maxn];
multiset<int> mp[maxn];
void dfs(int u){
while(q[u].size())q[u].pop();
p[u]=&q[u],f[u]=0,siz[u]=1;
for(int v:son[u]){
dfs(v);p[u]=merge(p[u],p[v]);
f[u]+=f[v],siz[u]+=siz[v];
}
for(int x:mp[u])p[u]->push(-x),f[u]+=x;
while(p[u]->size()>siz[u])f[u]+=p[u]->top(),p[u]->pop();
}
void work(){
dfs(1);printf("%lld ",f[1]);
}
int a[maxn],pos[maxn];
signed main(){
freopen("transfer.in","r",stdin);
freopen("transfer.out","w",stdout);
int sid=read();
int n=read(),k=read(),m=read();
for(int i=2;i<=n;i++)son[read()].push_back(i);
for(int i=1;i<=k;i++){int x=read(),v=read();mp[x].insert(v);a[i]=v,pos[i]=x;}
work();for(int i=1;i<=m;i++)if(read()==1){
int x=read(),v=read();a[++k]=v,pos[k]=x;mp[x].insert(v);
work();
}else{
int id=read();auto p=mp[pos[id]].lower_bound(a[id]);mp[pos[id]].erase(p);
work();
}return 0;
}
D2T1（还不清楚为什么当时第二个样例只输出了9个点）
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')f=(c!='-'),c=getchar();
while(c>='0'&&c<='9')x=10*x+c-'0',c=getchar();
if(f)return x;return -x;
}
inline int getc(){char c=getchar();while(c!='.'&&c!='#'&&c!='X'&&c!='O')c=getchar();if(c=='.')return 0;if(c=='#')return 1;if(c=='X')return 2;return 3;}
const int maxn=11*11*11*11*11*11*2,tox[4]={1,-1,0,0},toy[4]={0,0,1,-1},inf=1e9+10;
int G[11][11],n,m,X1,Y1,X2,Y2,X3,Y3,tp,cnt[maxn],f[maxn],d[maxn],qu[maxn];
inline int encode(){return (X1-1)*2e5+(Y1-1)*2e4+(X2-1)*2e3+(Y2-1)*2e2+(X3-1)*2e1+(Y3-1)*2+tp;}
inline void decode(int st){tp=st&1,st>>=1,Y3=st%10+1,st/=10,X3=st%10+1,st/=10,Y2=st%10+1,st/=10,X2=st%10+1,st/=10,Y1=st%10+1,st/=10,X1=st+1;}
int deg(){
int ans=0;
if(tp)for(int t=0;t<4;t++){
X2+=tox[t],Y2+=toy[t];if(1<=X2&&X2<=n&&1<=Y2&&Y2<=m&&!G[X2][Y2]&&(X2!=X3||Y2!=Y3))ans++;X2-=tox[t],Y2-=toy[t];
X3+=tox[t],Y3+=toy[t];if(1<=X3&&X3<=n&&1<=Y3&&Y3<=m&&!G[X3][Y3]&&(X2!=X3||Y2!=Y3))ans++;X3-=tox[t],Y3-=toy[t];
}else for(int t=1;t<4;t++){X1+=tox[t],Y1+=toy[t];if(1<=X1&&X1<=n&&1<=Y1&&Y1<=m&&!G[X1][Y1])ans++;X1-=tox[t],Y1-=toy[t];}
return ans;
}
inline int judge(){
if(G[X1][Y1]||G[X2][Y2]||G[X3][Y3])return 0;
if(X2==X3&&Y2==Y3)return 0;
if(X1==1&&tp==0)return 1;
if(X1==1&&tp==1)return -1;
if(X1==X2&&Y1==Y2)return -1;
if(X1==X3&&Y1==Y3)return -1;
if(deg()==0)return -1;
return 0;
}
signed main(){
freopen("zu.in","r",stdin);
freopen("zu.out","w",stdout);
int ID,TEST;scanf("%lld%lld",&ID,&TEST);
while(TEST--){
scanf("%lld%lld",&n,&m);X2=Y2=0,tp=1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)switch(getc()){
case 0:G[i][j]=0;break;
case 1:G[i][j]=1;break;
case 2:G[i][j]=0,X1=i,Y1=j;break;
case 3:G[i][j]=0;if(!X2)X2=i,Y2=j;else X3=i,Y3=j;
}
int ST=encode();
int l=1,r=0;
for(X1=1;X1<=n;X1++)for(Y1=1;Y1<=m;Y1++)for(X2=1;X2<=n;X2++)for(Y2=1;Y2<=m;Y2++)for(X3=1;X3<=n;X3++)for(Y3=1;Y3<=m;Y3++)for(tp=0;tp<=1;tp++){
int st=encode();f[st]=judge();if(f[st])d[st]=(f[st]==1)?-1:0;else d[st]=inf,cnt[st]=deg();
}
for(X1=1;X1<=n;X1++)for(Y1=1;Y1<=m;Y1++)for(X2=1;X2<=n;X2++)for(Y2=1;Y2<=m;Y2++)for(X3=1;X3<=n;X3++)for(Y3=1;Y3<=m;Y3++)for(tp=0;tp<=1;tp++){
int st=encode();if(d[st]==-1)qu[++r]=st;
}
for(X1=1;X1<=n;X1++)for(Y1=1;Y1<=m;Y1++)for(X2=1;X2<=n;X2++)for(Y2=1;Y2<=m;Y2++)for(X3=1;X3<=n;X3++)for(Y3=1;Y3<=m;Y3++)for(tp=0;tp<=1;tp++){
int st=encode();if(d[st]==0)qu[++r]=st;
}
while(l<=r){
int st=qu[l++];decode(st);tp=!tp;
if(!tp)for(int t=1;t<4;t++){
X1-=tox[t],Y1-=toy[t];
if(1<=X1&&X1<=n&&1<=Y1&&Y1<=m&&!G[X1][Y1]){
int nst=encode();
if(!f[nst]){
if(f[st]==1){if(--cnt[nst]==0)f[qu[++r]=nst]=-1,d[nst]=d[st]+1;}
else f[qu[++r]=nst]=1,d[nst]=d[st]+1;
}
}
X1+=tox[t],Y1+=toy[t];
}else for(int t=0;t<4;t++){
X2-=tox[t],Y2-=toy[t];
if(1<=X2&&X2<=n&&1<=Y2&&Y2<=m&&!G[X2][Y2]&&(X2!=X3||Y2!=Y3)){
int nst=encode();
if(!f[nst]){
if(f[st]==1){if(--cnt[nst]==0)f[qu[++r]=nst]=-1,d[nst]=d[st]+1;}
else f[qu[++r]=nst]=1,d[nst]=d[st]+1;
}
}
X2+=tox[t],Y2+=toy[t];
X3-=tox[t],Y3-=toy[t];
if(1<=X3&&X3<=n&&1<=Y3&&Y3<=m&&!G[X3][Y3]&&(X2!=X3||Y2!=Y3)){
int nst=encode();
if(!f[nst]){
if(f[st]==1){if(--cnt[nst]==0)f[qu[++r]=nst]=-1,d[nst]=d[st]+1;}
else f[qu[++r]=nst]=1,d[nst]=d[st]+1;
}
}
X3+=tox[t],Y3+=toy[t];
}
}
if(f[ST]==1)printf("Red %lld\n",d[ST]);
if(f[ST]==-1)printf("Black %lld\n",d[ST]);
if(f[ST]==0)puts("Tie");
}return 0;
}D2T2
无
D2T3
无