NOIP2022 暴毙记

· · 个人记录

创业未半而中道崩殂

这大概就是我的最后一场比赛了，
长达两年的OI生涯在今天惨淡收场。 ——2022.11.26

Day -? 1

在CSP-S2022一轮中拿到了本弱市的rk1（87.5），自然在FJ获得了参加NOIP2022的资格。

Day -? 2

“没进队线就回来好好搞whk”他这么说。
我能怎么办，尽人事听天命，两周胡了百来道题，打印用了数百张纸，whk完全没听。

Day 0

靖城突然有了疫情（这鬼地方都能有疫情的吗），手机来不了了。
自驾去福州考试大概是弱校的特权吧。
考场在时代中学，但是5点才开放，先到附中看一下，见到了传说中的Win10考场。
在门口等了好久才进考场，出来的时候天都黑了。
这个键盘感觉要凉。
晚上补了一道点双，但是不小心写成了边双（RP都用在这上面了），拍了好久才发现问题。

Day1

早上起来默了一堆不可能考的板子。

键盘很卡，不习惯。
五分钟打完缺省源，开始看题。

T1题面看起来有点乱，手画了一下发现是裸的前缀和，30分钟才打完(最后一个样例有点意思)。
T2玩了半小时只玩出前30分，放弃先看T3
T3一眼边双后dp，有了昨天的经验10分钟就把点缩好了。计数的时候总是漏东漏西的，前前后后搞了1小时才过大样例。
继续玩T2，玩到了12：30，出来一堆没用的结论，感觉危，赶紧打了个贪心，最后一分钟过了编译。

结束了。
出来之后经提醒才发现T2没输出操作数，30分都没。
估记：100+0+100+0=200
听说一堆200+，没救了。
或许能成为本校第一个NOIP省一？（学校不认CSP-S）
没练过构造，总觉得T2是个纸老虎，但自己就是冲不出来，也因此一直没看T4。
感觉和自己的实力不大匹配，但练得少是这样的，也没什么好说的。
就这样结束了，之后没多少机会搞OI了。
如果有机会省选的话可能还会诈一下尸？不过没啥希望。

完蛋了,T3内存开了610M,200->100,这下连省一都没了。

upd:附代码
T1

#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=1050,mod=998244353;
int dn[maxn][maxn],rt[maxn][maxn],up[maxn][maxn],G[maxn][maxn];
int get(){
    char c=getchar();
    while(c!='0'&&c!='1')c=getchar();
    return c=='1';
}
int n,m,c,f,ans1,ans2;
signed main(){
    //freopen("plant.in","r",stdin);
    //freopen("plant.out","w",stdout);
    int T=read(),id=read();while(T--){
        n=read(),m=read(),c=read(),f=read(),ans1=0,ans2=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)G[i][j]=get();
        for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--)if(!G[i][j]){
                if(j!=m&&!G[i][j+1])rt[i][j]=rt[i][j+1]+1;
                else rt[i][j]=0;
            }
        }
        for(int j=1;j<=m;j++){
            for(int i=1;i<=n;i++)if(!G[i][j]){
                up[i][j]=rt[i][j];
                if(i!=1&&!G[i-1][j])up[i][j]+=up[i-1][j];
            }
        }
        for(int j=1;j<=m;j++){
            for(int i=n;i>=1;i--)if(!G[i][j]){
                if(i!=n&&!G[i+1][j])dn[i][j]=dn[i+1][j]+1;
                else dn[i][j]=0;
            }
        }
        for(int i=3;i<=n;i++)for(int j=1;j<=m;j++)if(!G[i][j]){
            if(G[i-1][j]||G[i-2][j])continue;
            ans1=(ans1+up[i-2][j]*rt[i][j]%mod)%mod;
            ans2=(ans2+up[i-2][j]*rt[i][j]%mod*dn[i][j]%mod)%mod;
        }
        printf("%lld %lld\n",ans1*c%mod,ans2*f%mod);
    }return 0;
}

T3 (数组开大抱零了，luogu可过)

#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=5e6+10,mod=1e9+7;
int n,m,qp[maxn];
//int qpow(int a,int x){int ans=1;while(x){if(x&1)ans=ans*a%mod;a=a*a%mod,x>>=1;}return ans;}
int cut[maxn],c[maxn],ans=1,sum=0,siz[maxn],cnt;
namespace TREE{
    int head[maxn],ver[maxn],nxt[maxn],tot;
    void add(int a,int b){ver[++tot]=b,nxt[tot]=head[a],head[a]=tot;}
    #define fore(u,i) for(int i=head[u];i;i=nxt[i])
    int f[maxn],g[maxn],son[maxn];
    void dfs(int u,int fa){
        f[u]=qp[siz[u]],g[u]=qp[siz[u]],son[u]=1;
        fore(u,i)if(ver[i]!=fa){
            dfs(ver[i],u);son[u]+=son[ver[i]];
            f[u]=(__int128)f[u]*(g[ver[i]]+qp[son[ver[i]]])%mod;
            g[u]=((__int128)g[u]*(g[ver[i]]+qp[son[ver[i]]])%mod)%mod;
        }
        fore(u,i)if(ver[i]!=fa)f[u]=(f[u]-(__int128)g[ver[i]]*qp[son[u]-son[ver[i]]-1]%mod+mod)%mod;f[u]=(f[u]-qp[son[u]-1]+mod)%mod;
        g[u]=(g[u]-qp[son[u]-1]+mod)%mod;
        sum=(sum+(__int128)f[u]*qp[cnt-son[u]]%mod)%mod;
    }
    void work(){dfs(1,1);ans=(__int128)ans*sum%mod;}
}
namespace GRA{
    int head[maxn],ver[maxn],nxt[maxn],tot=1;
    void add(int a,int b){ver[++tot]=b,nxt[tot]=head[a],head[a]=tot;}
    void link(int a,int b){add(a,b);add(b,a);}
    #define fore(u,i) for(int i=head[u];i;i=nxt[i])
    int dfn[maxn],low[maxn],idx;
    void tarjan(int u,int edge){
        dfn[u]=low[u]=++idx;
        fore(u,i)if(i!=edge)if(!dfn[ver[i]]){
            tarjan(ver[i],i^1);low[u]=min(low[u],low[ver[i]]);
            if(low[ver[i]]>dfn[u])cut[i]=cut[i^1]=1;
        }else low[u]=min(low[u],dfn[ver[i]]);
    }
    int vis[maxn];
    void dfs(int u,int cc){c[u]=cc;vis[u]=1;fore(u,i)if(!cut[i]&&!vis[ver[i]])dfs(ver[i],cc);}
    void build(){
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
        for(int i=1;i<=n;i++)if(!vis[i])dfs(i,++cnt);
        for(int u=1;u<=n;u++){siz[c[u]]++;fore(u,i)if(cut[i])TREE::add(c[u],c[ver[i]]);}
        for(int i=2;i<=tot;i+=2)if(!cut[i])ans=ans*2%mod;
    }
}
signed main(){
    freopen("barrack.in","r",stdin);
    freopen("barrack.out","w",stdout);
  while(1);
    n=read(),m=read();for(int i=1;i<=m;i++)GRA::link(read(),read());
    qp[0]=1;for(int i=1;i<=m;i++)qp[i]=qp[i-1]*2%mod;
    GRA::build();TREE::work();
    return printf("%lld",(long long)ans),0;
}