NOIP2022 游记 & 简要题解

标签：简要 return int 题解 void ch NOIP2022 inline id

游 .寄

\(\text {Day0}\)

由于疫情的原因，原本预定的团建活动鸽了，于是就在机房里放送起来，打了一天的三国杀，身份、国战都打了。中午教练请吃饭，吃到了来一中之后最好的一餐。云了几道 \(atcoder\) 的思维题，很早就回家休息去了。

\(\text {Day1}\)

早上起的比较早， \(7:10\) 到了一中，在大巴车上强迫自己戴上耳机睡觉，平复一下心情。也没有很紧张，想着大不了退役也不是我完全承担不起的后果。

开考了。

\(20min\) 看完了所有的题目，哇靠怎么又是构造题，还有两道数数题，最后一道题是个数据结构题，感觉要凉，构造题和数数题都不是我擅长的类型。

好在 \(\text T1\) 看完就回了，但是当时以为下面那一根必须长于上面那一根，然后直接冲了个树状数组，打了将近 \(100\) 行的代码，然后发现过不了样例 \(2\) ，此时已经开始慌了，又仔细读了几遍题，发现树状数组什么的没屁用，直接统计就行了，赶忙删掉了写的一部分代码，改了改。

然后第一问过了，第二问比答案小到不知道哪里去了，我感觉不太对，明明 \(F\) 的限制比 \(C\) 还会严格一些啊，凭什么答案还比 \(C\) 的大。这个时候已经 \(1.5h\) 左右了，我还没有过 \(\text T1\) 。此时真的感觉直面退役了。去厕所洗了把脸冷静了一下，再次读了一遍题，终于意识漏了到 \(F\) 下面那一截的贡献，改完就过了。

把几个样例拼在一起试了一下多测，感觉没啥能挂的就直接丢了。

此时已经十点多了，必须抓紧时间，看了很久后面三题都不太会正解，但感觉暴力分还行。

最后 \(100+35+45+36=216\) 草草离场，感觉发挥的很差。

\(\text{Day?}\)

出分了，\(\text T2\) 挂了 \(15pts\) ，总分 \(201pts\) 排名 \(25\) 。感觉发挥的真的只能算中规中矩吧，没有什么很突出的地方，相比于别人人均会 \(2-3\) 个正解，我真的就只是用暴力分来掩饰了我的菜。

总结

思维能力一定要多提高， \(\text T2\) 和 \(\text T3\) 都没想到正解，\(\text T4\) 白送的 \(52pts\) 也没有想到，确实反映出我的思维水平明显欠练。以后有 \(Atcoder\) 或者 \(Codeforces\) 的比赛尽量还是看一看，把和自己能力稍高一点的题写了就行，提升思维水平。
以后大考绝对不能再犯看错题这种低级错误，花了近 \(2h\) 才过 \(\text T1\) ，不管怎么说都还是严重影响了考试的发挥的。
打暴力一定要稳，打的暴力敲下的代码尽量要做到不出错，不挂分。

就这样吧，希望自己接下来的比赛可以越打越好。

简要题解

\(\text{T1 plant}\)

记 \(dp_{i,j}\) 表示从 \((i,j)\) 开始向右连续 \(1\) 的数量。预处理出这个。

然后枚举左上角，考虑它正下方每一个点对它的贡献即可。

点击查看代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1005,P=998244353;

int T,id,n,m,c,f,ansc,ansf,dpr[N][N];
char mp[N][N];

inline void inc(int &x,int y) { x+=y-P; x+=(x>>31)&P; }

inline void Init() {
	for(int i=1;i<=n;i++) {
		dpr[i][m+1]=-1;
		for(int j=m;j>=1;j--) {
			dpr[i][j]=(mp[i][j]=='0')?dpr[i][j+1]+1:-1;
		}
	}
}

inline void DP() {
	for(int j=1,lst,tc,tf;j<=m;j++) {
		lst=0; tc=0; tf=0; 
		for(int i=n;i>=1;i--) {
			if(mp[i][j]=='1') { tc=tf=lst=0; continue; }
			else if(!lst) lst=i;
			inc(ansc,1LL*dpr[i][j]*tc%P); inc(ansf,1LL*dpr[i][j]*tf%P);
			if(i+1<=lst && dpr[i+1][j]) inc(tc,dpr[i+1][j]);
			if(i+1<lst && dpr[i+1][j]) inc(tf,1LL*dpr[i+1][j]*(lst-i-1)%P);
		}
	}
}

int main() {
	//freopen("plant.in","r",stdin);
	//freopen("plant.out","w",stdout);
	cin>>T>>id; 
	while(T--) {
		cin>>n>>m>>c>>f;
		for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
		ansc=ansf=0; Init(); DP();
		ansc=1LL*ansc*c%P;
		ansf=1LL*ansf*f%P;
		cout<<ansc<<" "<<ansf<<endl; 
	}
	return 0;
}

\(\text {T2 meow}\)

对于 \(k=2n-2\) 的部分很容易，留一个空栈，其余每个栈负责两种花色，栈顶直接删，栈底依靠空栈去删。

我们考虑怎么推广到 \(k=2n-1\) 的情况。

我们假设此时面临这么一个状态，目前已经有 \(n-1\) 个栈满了（即栈中有两个不同的花色），我们考虑怎么放这第 \(x\) 牌。

首先我们记所有栈底元素中下一次出现的位置的最小值为 \(mn\) ，这张取得最小值的牌为 \(y\) ，\(y\) 的栈顶为 \(z\) 。下一个与 \(x\) 同花色的牌为 \(p\) 。

\(p<mn\) 那么我们直接把 \(x\) 丢到空栈就行，因为下一次要用到空栈的时候，\(x\) 已经被消去了。
\(p>mn\) ，我们记区间 \([x,mn]\) 这个区间内与 \(z\) 花色相同的牌的个数为 \(c\) 。如果 \(c\) 为偶数，我们把 \(x\) 丢到 \(y\) 所在栈中，\([x,mn]\) 中所有与 \(z\) 花色相同的牌也丢到这个栈里，它们会彼此消去，那么到时候将 \(mn\) 丢到空栈里面消去 \(y\) ，\(x\) 所在的栈就只有 \(2\) 个元素了。如果 \(c\) 为奇数，我们把 \(x\) 丢到空栈，\([x,mn]\) 中所有和 \(z\) 花色相同的牌都丢到 \(y\) 所在的栈，这样等 \(mn\) 这张牌出现的时候，栈里就只剩 \(y\) 这一张牌，直接消去即可，这个栈也就成为了新的空栈。

细节巨大多，不太好写。

点击查看代码

#include<bits/stdc++.h>
#define vc vector
#define pb push_back
using namespace std;
const int N=305,M=2e6+5,inf=0x3f3f3f3f;

inline int read() {
    int x=0,w=0; char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
    return w?-x:x;
}

int T,n,m,k,tot,las,stk[N][10],topf[N];
int p[N<<1],s[N<<1],in[N<<1],c[N<<1],o[M];
int op[M<<1],lst[M],suf[N<<1],s1[M<<1],s2[M<<1],idx;
bool used[N];
vc<int> d[M];

inline void Solve();
inline void Push(int,int,int,int);
inline void Del(int,int);
inline void Work(int);
inline bool Istop(int x,int id) { return stk[id][topf[id]]==x; }
inline int Getempty() { for(int i=1;i<=n;i++) if(!topf[i]) return i; return 114514; }
inline int Find() { int p[10]={0,0}; for(int i=n;i>=1;i--) if(!used[i]) p[topf[i]]=i; return p[1]?p[1]:p[0]; }
inline bool check() { int cnt=0; for(int i=1;i<=n;i++) cnt+=topf[i]==2; return cnt==n-1;}

int main() {
    freopen("meow.in","r",stdin);
    freopen("meow.out","w",stdout);
    T=read(); 
    while(T--) {
        n=read(); m=read(); k=read(); idx=tot=las=0;
        for(int i=1;i<=n;i++) topf[i]=0;
        for(int i=1;i<=k;i++) c[i]=inf, p[i]=s[i]=in[i]=0;
        for(int i=1;i<=m;i++) o[i]=read();
        for(int i=m;i>=1;i--) {
            lst[i]=c[o[i]]; c[o[i]]=i;
            suf[o[i]]=i;
        }
        Solve(); 
    }
    return 0;
}

inline void Solve() {
    for(int i=1,em;i<=m;i++) {
        suf[o[i]]=lst[i];
        if(las<i && check() && !in[o[i]]) Work(i);
        else if(p[o[i]]>=i) Push(o[i],s[o[i]],0,0);
        else if(in[o[i]]) {
            if(Istop(o[i],in[o[i]])) Push(o[i],in[o[i]],1,1);
            else em=Getempty(), Push(o[i],em,0,1), Del(in[o[i]],em);
        }
        else Push(o[i],Find(),1,1);
        for(auto &x:d[i]) used[x]=0;
        d[i].clear();
    }
    printf("%d\n",idx);
    for(int i=1;i<=idx;i++) {
        printf("%d %d ",op[i],s1[i]);
        if(op[i]==2) printf("%d ",s2[i]);
        putchar(10);
    }
}

inline void Push(int x,int id,int f,int g) {
    ++idx; op[idx]=1; s1[idx]=id;
    stk[id][++topf[id]]=x;
    if(f) in[x]=id;
    if(topf[id]>1) 
        if(stk[id][topf[id]]==stk[id][topf[id]-1]) {
            if(g) in[x]=0;
            topf[id]-=2;
        }
}

inline void Del(int x,int y) {
    in[stk[x][1]]=in[stk[y][1]]=0;
    if(x>y) swap(x,y);
    ++idx; op[idx]=2; s1[idx]=x; s2[idx]=y;
    for(int i=1;i<topf[x];i++) stk[x][i]=stk[x][i+1];
    for(int i=1;i<topf[y];i++) stk[y][i]=stk[y][i+1];
    --topf[x]; --topf[y]; 
}

inline void Work(int pos) {
    int x=o[pos],cnt=0,mn=inf,id=0,y,it,z,em=Getempty();
    for(int i=1;i<=n;i++) 
        if(topf[i] && suf[stk[i][1]]<mn) 
            mn=suf[stk[i][1]], id=i;
    it=suf[o[pos]];
    y=stk[id][1]; z=stk[id][2]; las=min(mn,it);
    if(mn>it) { Push(x,em,1,1); used[em]=1; d[it].pb(em); return ;}
    else {
        for(int i=pos+1;i<mn;i++) if(o[i]==z) ++cnt;
        if(cnt&1) { Push(x,em,1,1); used[id]=1; d[mn].pb(id); return ; }
        else Push(x,id,1,1), s[z]=id, p[z]=mn;
    }
}

\(\text{T3 barrack}\)

\(f_{i}\) 表示在以 \(i\) 为根的子树中，至少选择一个军营的方案数。

初值 \(f_i=2^{V_i+E_i}\) ，\(Vi\) 为这个边双内的点数，\(E_i\) 为边数。

转移的话枚举每个子树内是否要选择军营。

\[f_x=f_x\cdot(f_y+2^{c_y+1}) \]

其中 \(c_y\) 为以 \(y\) 为根的子树中的边数。

然后 \(f_x\) 需要减去一个都不选的方案 \(2^{sum_x}\) 。

最后考虑 \(f_x\) 对于答案的贡献，子树 \(x\) 之外的边中，除了 \(x\) 到父节点的连边必须不选（这样不会算重），其余的均是可选可不选，所以贡献为 \(f_x\cdot2^{m-sum_x-|fa_x\neq0|}\) 。

点击查看代码

#include<bits/stdc++.h>
#define LL long long
#define vc vector
#define pb push_back
using namespace std;
const int N=5e5+5,M=1e6+5,P=1e9+7;

inline int read() {
    int x=0,w=0; char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
    return w?-x:x;
}

int n,m,u,v,sum,V[N],E[N],f[N],id[N],pw[M<<1],c[N],tot,cnt;
int hd[N],to[M<<1],ne[M<<1],tc=1;
int idx,dfn[N],low[N];
bool bg[M<<1],vis[N];
vc<int> G[N];

inline void inc(int &x,int y) { x+=y-P; x+=x>>31&P; }
inline void Add(int,int);
inline void Tarjan(int,int);
inline void Get(int,int&,int&);
inline void Dfs(int,int);

int main() {
    //freopen("barrack4.in","r",stdin);
    n=read(); m=read();
    pw[0]=1; for(int i=1;i<=n+m+5;i++) pw[i]=2LL*pw[i-1]%P;
    for(int i=1;i<=m;i++) u=read(), v=read(), Add(u,v);
    Tarjan(1,0);
    for(int i=1;i<=n;i++) if(!vis[i]) ++cnt, Get(i,V[cnt]=0,E[cnt]=0), E[cnt]>>=1;
    for(int i=2;i<=tc;i+=2) if(id[to[i]]^id[to[i^1]]) 
        G[id[to[i]]].pb(id[to[i^1]]), G[id[to[i^1]]].pb(id[to[i]]), ++sum;
    Dfs(1,0);
    cout<<tot<<endl;   
    return 0;
}

inline void Add(int x,int y) {
    to[++tc]=y; ne[tc]=hd[x]; hd[x]=tc; 
    to[++tc]=x; ne[tc]=hd[y]; hd[y]=tc; 
}

inline void Tarjan(int x,int in) {
    dfn[x]=low[x]=++idx;
    for(int i=hd[x],y;i;i=ne[i]) if(i!=(in^1)) {
        if(!dfn[y=to[i]]) {
            Tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) bg[i]=bg[i^1]=1;
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

inline void Get(int x,int &v,int &e) {
    if(vis[x]) return ;
    vis[x]=1; id[x]=cnt; v++; 
    for(int i=hd[x],y;i;i=ne[i]) if(!bg[i]) 
        ++e, Get(y=to[i],v,e);
}

inline void Dfs(int x,int fa) {
    f[x]=pw[V[x]+E[x]]; c[x]=E[x];
    for(auto &y:G[x]) if(y!=fa) {
        Dfs(y,x);
        c[x]+=(c[y]+1);
        f[x]=1LL*(f[y]+pw[c[y]+1])%P*f[x]%P;
    }
    inc(f[x],P-pw[c[x]]);
    inc(tot,1LL*f[x]*pw[m-c[x]-(fa!=0)]%P);
}

\(\text {T4 match}\)

首先比较显然的是对于单组询问可以用分治做到 \(o(n\log n)\) 。

考虑跨区间中点的子区间的贡献是，我们对于每个右端点，看它对每个左端点的贡献，维护前缀后缀 \(max\) ，看最大值取值在哪一边即可。

这样做总复杂度是 \(o(q\cdot n\log n)\) ，可以过 \(52pts\) 。

点击查看代码

#include<bits/stdc++.h>
#define ULL unsigned long long
using namespace std;
const int N=2e5+5e4+5;

inline int read() {
    int x=0,w=0; char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
    return w?-x:x;
}

int T,n,q,u,w;
ULL ans,a[N],b[N],al[N],ar[N],bl[N],br[N];
ULL c[N],ca[N],cb[N],cab[N];

#define mid (l+r>>1)
ULL v,va,vb,vab;
inline void Solve(int l,int r) {
    if(l==r) return al[l]=ar[l]=a[l], bl[l]=br[l]=b[l], ans+=a[l]*b[l], void();
    Solve(l,mid); Solve(mid+1,r);
    for(int i=mid+1,pa=mid,pb=mid,p;i<=r;i++) {
        while(pa>=l && ar[pa]<=al[i]) --pa;
        while(pb>=l && br[pb]<=bl[i]) --pb;
        p=max(pa,pb);
        c[mid]+=al[i]*bl[i]; c[p]-=al[i]*bl[i];
        if(pa>pb) ca[pa]+=bl[i], ca[pb]-=bl[i];
        else if(pa<pb) cb[pb]+=al[i], cb[pa]-=al[i];
        p=min(pa,pb);
        cab[p]++; cab[l-1]--;
    }
    v=va=vb=vab=0;
    c[l-1]=ca[l-1]=cb[l-1]=cab[l-1]=0;
    for(int i=mid;i>=l;i--) {
        v+=c[i]; va+=ca[i]; vb+=cb[i]; vab+=cab[i];
        c[i]=ca[i]=cb[i]=cab[i]=0;
        ans+=v; ans+=va*ar[i]; ans+=vb*br[i]; ans+=vab*ar[i]*br[i];
    }
    al[l]=a[l]; bl[l]=b[l]; ar[r]=a[r]; br[r]=b[r];
    for(int i=l+1;i<=r;i++) al[i]=max(al[i-1],a[i]), bl[i]=max(bl[i-1],b[i]);
    for(int i=r-1;i>=l;i--) ar[i]=max(ar[i+1],a[i]), br[i]=max(br[i+1],b[i]);
}

int main() {
    T=read(); n=read(); 
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    q=read();
    while(q--) {
        u=read(); w=read(); ans=0;
        Solve(u,w); printf("%llu\n",ans);
    }
    return 0;
}

考虑对于多组询问怎么处理。
整体分治 ，我们像整体二分一样，把所有询问离线一起分治。

具体的，对于分值的每一个区间 \([l,r]\) 开一个 \(vector\) 记录被包含在这个区间里的询问区间。

具体的，对于当前考虑到的区间 \([l,r]\) ，我们把只在左半边区间和只在右半边区间的直接分治下去处理，跨过区间中点的先拆成两半分治求不挂跨过中点的子区间的答案。

然后再来统计跨过区间中点的答案，我们把每一个询问区间挂到它的右端点上，还是像普通的分治一样，对于右端点，让它去贡献左端点，开 \(4\) 个线段树维护一下就行。

值得注意的一点是，如果一个询问区间它跟当前递归到的这个区间是相等的，我们无需再递归下去，它的答案就是整个区间的答案，这个可以直接在统计答案的时候求出来。这样就保证了每个询问区间最多只会被拆成 \(\log n\) 个区间，总时间复杂度是 \(o(n\log^2n)\) 。

点击查看代码

#include<bits/stdc++.h>
#define ULL unsigned long long
#define mid (l+r>>1)
#define vc vector
#define pb push_back
using namespace std;
const int N=2e5+5e4+5;

inline int read() {
    int x=0,w=0; char ch=getchar();
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
    return w?-x:x;
}

int T,n,q;
ULL ans[N],a[N],b[N],al[N],ar[N],bl[N],br[N];

struct SGT {
    ULL tre[N<<2],f[N<<2],s[N<<2];
    inline void Build(int k,int l,int r,int o) {
        f[k]=tre[k]=0;
        if(l==r) {
            if(o==0) s[k]=1;
            else if(o==1) s[k]=ar[l];
            else if(o==2) s[k]=br[l];
            else s[k]=ar[l]*br[l];
            return ;
        }
        Build(k<<1,l,mid,o); Build(k<<1|1,mid+1,r,o);
        s[k]=s[k<<1]+s[k<<1|1];
    } 
    inline void Down(int k) {
        if(!f[k]) return ;
        f[k<<1]+=f[k]; tre[k<<1]+=f[k]*s[k<<1];
        f[k<<1|1]+=f[k]; tre[k<<1|1]+=f[k]*s[k<<1|1];
        f[k]=0;
    }
    inline void Modify(int k,int l,int r,int L,int R,ULL v) {
        if(L>R) return ;
        if(L<=l && R>=r) return f[k]+=v, tre[k]+=v*s[k], void();
        Down(k); 
        if(L<=mid) Modify(k<<1,l,mid,L,R,v);
        if(R>mid)  Modify(k<<1|1,mid+1,r,L,R,v);
        tre[k]=tre[k<<1]+tre[k<<1|1];
    }
    inline ULL Query(int k,int l,int r,int L,int R) {
        if(L<=l && R>=r) return tre[k];
        Down(k);
        if(R<=mid) return Query(k<<1,l,mid,L,R);
        else if(L>mid) return Query(k<<1|1,mid+1,r,L,R);
        else return Query(k<<1,l,mid,L,R)+Query(k<<1|1,mid+1,r,L,R);
    }
}sgt[4];

struct Qry { int id,l,r; };
vc<Qry> Q,nq,now[N];

inline ULL Solve(int l,int r,vc<Qry> q) {
    ULL sum=0;
    al[l]=a[l]; bl[l]=b[l]; ar[r]=a[r]; br[r]=b[r];
    if(l==r) { for(auto &u:q) ans[u.id]+=a[l]*b[l]; return a[l]*b[l]; }
    nq.clear(); 
    for(auto &u:q) if(u.l<=mid && (u.l!=l || u.r!=r)) 
    	nq.pb(Qry{u.id,u.l,min(u.r,mid)});
    sum+=Solve(l,mid,nq);
    nq.clear(); 
    for(auto &u:q) if(u.r>mid && (u.l!=l || u.r!=r)) 
    	nq.pb(Qry{u.id,max(u.l,mid+1),u.r}); 
    sum+=Solve(mid+1,r,nq);
    for(int i=0;i<4;i++) sgt[i].Build(1,l,mid,i);
    for(int i=mid+1;i<=r;i++) now[i].clear();
    for(auto &u:q) if(u.l<=mid && u.r>mid) now[u.r].pb(u);
    for(int i=mid+1,id,L,A=mid,B=mid;i<=r;i++) {
        while(A>=l && ar[A]<=al[i]) --A;
        while(B>=l && br[B]<=bl[i]) --B;
        sgt[0].Modify(1,l,mid,max(A,B)+1,mid,al[i]*bl[i]);
        if(A>B) sgt[1].Modify(1,l,mid,B+1,A,bl[i]);
        else if(B>A) sgt[2].Modify(1,l,mid,A+1,B,al[i]);
        sgt[3].Modify(1,l,mid,l,min(A,B),1);
        for(auto &u:now[i]) {
            id=u.id; L=u.l;
            if(i==r && L==l) continue;
            for(int j=0;j<4;j++) ans[id]+=sgt[j].Query(1,l,mid,L,mid);
        }
        now[i].clear();
    }
    for(int i=0;i<4;i++) sum+=sgt[i].tre[1];
    for(auto &u:q) if(u.l==l && u.r==r) ans[u.id]+=sum;
    for(int i=l+1;i<=r;i++) al[i]=max(al[i-1],a[i]), bl[i]=max(bl[i-1],b[i]);
    for(int i=r-1;i>=l;i--) ar[i]=max(ar[i+1],a[i]), br[i]=max(br[i+1],b[i]);
    return sum;
}

signed main() {
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    T=read(); n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    q=read(); for(int i=1,u,v;i<=q;i++) u=read(), v=read(), Q.pb(Qry{i,u,v});
    Solve(1,n,Q);
    for(int i=1;i<=q;i++) printf("%llu\n",ans[i]);
    return 0;
}

标签：简要,return,int,题解,void,ch,NOIP2022,inline,id
From： https://www.cnblogs.com/oscaryangzj/p/16992999.html

NOIP2022 游记 & 简要题解

游 .寄

\(\text {Day0}\)

\(\text {Day1}\)

\(\text{Day?}\)

总结

简要题解

\(\text{T1 plant}\)

\(\text {T2 meow}\)

\(\text{T3 barrack}\)

\(\text {T4 match}\)

相关文章

赞助商

阅读排行