2022.11.15 NOIP2022 模拟赛十

炸弹威力

Source：洛谷 P6036。

记 \(f_{i,0/1}\) 表示第 \(i\) 个位置为 \(0/1\) 的答案个数，有 DP 转移：

\[\begin{aligned}
(1-p_i)(f_{i-1,0}+f_{i-1,1}) &\to f_{i,0}\\
\sum_{j=1}^i (\prod_{k=j}^i p_k) ((1-p_{j-1})a^{b(i-j)}\sum_{k=j}^i w_k+ f_{j-1,0}) &\to f_{i,1}
\end{aligned}
\]

下面那一串式子可以递推 \(O(n)\) 解决，故总时间复杂度 \(O(n)\)。

Code

const int N=1e5+5;

db f[N][2],p[N],sp[N],w[N],s[N];

int main() {

	ios::sync_with_stdio(false);

	int n;db a,b;

	cin>>n>>a>>b;a=pow(a,b);

	FOR(i,1,n) cin>>w[i],s[i]=s[i-1]+w[i];

	p[0]=0;

	FOR(i,1,n) cin>>p[i];

	db s1=0,s2=0,s3=0;

	FOR(i,1,n) {

		f[i][0]=(f[i-1][0]+f[i-1][1])*(1-p[i]);

		s1=s1*p[i]*a+(1-p[i-1])*p[i],s2=s2*p[i]*a+(1-p[i-1])*p[i]*s[i-1],s3=s3*p[i]+p[i]*f[i-1][0];

		f[i][1]=s1*s[i]-s2+s3;

	}

	printf("%.3lf\n",f[n][0]+f[n][1]);

}

序列间距

Source：CF1188C

首先排序，排序后贡献是相邻的。

枚举最小值 \(x\)，设 \(f_{i,j}\) 表示前 \(i\) 个取了 \(j\) 个值，并且每次贡献都 \(\ge x\) 的方案数，计算后差分即可。

单次 DP 的复杂度是 \(O(nk)\) 的，但是注意到若某个 \(x\) 满足 \(kx<V\) 可以不做，故只用做 \(O(\frac{V}{k})\) 次，总时间复杂度是 \(O(nV)\)。

Code

const int N=1005,V=1e5,mod=998244353;

int n,K,a[N],b[N],s[N],f[N][N],g[N][N],h[N],pre[N];

int work(int x) {

    if(x!=0&&V/x<K) return 0;

    FOR(i,1,n) f[i][0]=1,g[i][0]=i;

    int ans=0;

    FOR(i,1,n) {

        while(a[i]-a[pre[i]+1]>=x) pre[i]++;

        FOR(k,1,K) f[i][k]=g[pre[i]][k-1],g[i][k]=(g[i-1][k]+f[i][k])%mod;

        ans=(ans+f[i][K])%mod;

    }

    return ans;

}

int main() {

    n=read(),K=read();

    FOR(i,1,n) a[i]=read();

    sort(a+1,a+n+1);

    K--;

    set<int> S;

    FOR(i,1,n) FOR(j,i+1,n) S.insert(a[j]-a[i]);

    vi tmp;

    for(int i:S) tmp.pb(i);

    int ans=0,las=0;

    reverse(tmp.begin(),tmp.end());

    for(int i:tmp) {

        int zz=work(i);

        ans=(ans+1ll*i*((zz-las+mod)%mod)%mod)%mod;

        las=zz;

    }

    printf("%d\n",ans);

}

平衡集合

Source：CF1616H

首先将所有值插入 Trie 树中，记 \(f_u\) 表示 \(u\) 子树内选点并且不冲突的方案数，\(g_{u,v}\) 表示在 \(u,v\) 中分别选点，两子树间的点互不冲突的方案数，对 \(x\) 当前位分类讨论：

为 \(0\)：

\[\begin{aligned}
f_{x_0}+f_{y_0}+1 &\to f_{x}\\
g_{x_0,y_1}+ g_{x_1,y_0}-1+(2^{siz_{x0}}-1)(2^{siz_{x1}}-1)+(2^{siz_{y0}}-1)(2^{siz_{y1}}-1) &\to g_{x,y}
\end{aligned}
\]

为 \(1\)：

\[\begin{aligned}
g_{x0,x1} &\to f_{x}\\
g_{x0,y1}g_{x1,y0} &\to g_{x,y}
\end{aligned}
\]

注意到对于每一个 \(x\)，与其对应的 \(g_{x,y}\) 只有两个，故总时间复杂度为 \(O(n\log V)\)。

Code

const int N=1.5e5+5,B=30,mod=998244353;

int x,ch[N*B][2],f[N*B],g[N*B],siz[N*B],po[N],tot=1;

void insert(int x) {

    int p=1;

    ROF(i,30,0) {

        bool t=x>>i&1;

        if(!ch[p][t]) ch[p][t]=++tot;

        p=ch[p][t],siz[p]++;

    }

}

int dfs(int p,int q,int d) {

    if(!p||!q) return po[siz[p]+siz[q]];

    if(d<0) return po[p^q?siz[p]+siz[q]:siz[p]];

    int lp=ch[p][0],rp=ch[p][1],lq=ch[q][0],rq=ch[q][1];

    if(x>>d&1) {

        if((p^q)==0) return dfs(lp,rp,d-1);

        return 1ll*dfs(lp,rq,d-1)*dfs(rp,lq,d-1)%mod;

    }

    int a=dfs(lp,lq,d-1),b=dfs(rp,rq,d-1),c=(0ll+a+b+mod-1)%mod;

    if((p^q)==0) return c;

    return (0ll+c+1ll*(mod+po[siz[lp]]-1)*(mod+po[siz[rp]]-1)%mod+

                  1ll*(mod+po[siz[lq]]-1)*(mod+po[siz[rq]]-1)%mod)%mod;

}

int main() {

    int n=read();x=read(),po[0]=1;

    FOR(i,1,n) po[i]=2ll*po[i-1]%mod;

    FOR(i,1,n) insert(read());

    printf("%d\n",(mod+dfs(1,1,30)-1)%mod);

}

公交路线

Source：CF475E

首先找出原图的所有边双，边双内的点对一定可以全部计算上贡献。

现在问题变成树，对于原题的答案，我们一定希望整张图是一个类似「X」形态的图，枚举「X」中间的点，枚举向上有多大，就可以快速计算贡献。

总时间复杂度同树形背包，\(O(n^2)\)。

Code

const int N=2005;

int n,m,dfn[N],low[N],dfc,cut[N*N],col[N],siz[N],tsiz[N],scc,f[N],vis[N];

vector<pii> G[N];

vi G2[N];

void dfs(int u,int fa) {

	dfn[u]=low[u]=++dfc;

	for(auto [v,id]:G[u]) if(fa!=v) {

		if(dfn[v]) low[u]=min(low[u],dfn[v]);

		else {

			dfs(v,u),low[u]=min(low[u],low[v]);

			if(low[v]>dfn[u]) cut[id]=1;

		}

	}

}

void dfs1(int u,int fa) {

	col[u]=scc,siz[scc]++;

	for(auto [v,id]:G[u]) if(v!=fa&&!cut[id]&&!col[v]) dfs1(v,u);

}

void dfs2(int u,int fa) {

	vis[u]=1;

	for(int v:G2[u]) if(v!=fa&&!vis[v]) dfs2(v,u),tsiz[u]+=tsiz[v];

}

int main() {

	scanf("%d %d",&n,&m);

	FOR(i,1,m) {

		int x,y;scanf("%d %d",&x,&y);

		G[x].pb(y,i),G[y].pb(x,i);

	}

	dfs(1,0);

	FOR(i,1,n) if(!col[i]) ++scc,dfs1(i,0);

	FOR(u,1,n) for(auto [v,id]:G[u]) if(cut[id]) G2[col[u]].pb(col[v]);

	int ans=0;

	FOR(i,1,scc) {

		int sum=0;

		FOR(j,1,scc) tsiz[j]=siz[j],vis[j]=0;

		dfs2(i,0);

		FOR(j,1,scc) if(i!=j) sum+=tsiz[j]*siz[j];

		FOR(j,1,n) f[j]=0;

		f[0]=1;

		for(int v:G2[i]) ROF(j,n,tsiz[v]) f[j]|=f[j-tsiz[v]];

		FOR(j,0,n) if(f[j]) ans=max(ans,sum+(n-j)*(siz[i]+j));

	}

	printf("%d\n",ans);

}

巴特西

2022.11.15 NOIP2022 模拟赛十

炸弹威力

序列间距

平衡集合

公交路线

最新文章

热门文章