竞赛讨论区 > 牛客练习赛 108 题解
头像
可爱小萌妹
编辑于 2023-02-17 07:15 河南
+ 关注

牛客练习赛 108 题解

六道题目的出题人都是我,希望大家玩的开心!

UPD:赛时 E 题数据出了一些问题,赛后我们更换了新的数据并重测了本题的所有提交。

出题人在这里谢罪。非常抱歉!!>_<

A. 惊鸿

显然位或之后只会变大,因此答案为 4×(a1 or a2 or a3 or a4)4\times (a_1\text{ or }a_2\text{ or }a_3\text{ or }a_4)

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

signed main(void){

	int tt=read();while(tt--){
		int a=read(),b=read(),c=read(),d=read();
		cout<<((a|b|c|d)<<2)<<endl;
	}

	return 0;
}

B. 风间

有解必须要 i,aibi(mod2)\forall i,a_i\equiv b_i\pmod2,且 i=1nai=i=1nbi\sum_{i=1}^na_i=\sum_{i=1}^nb_i

那么首先判掉无解,如果有解,记 fi=jiaj,gi=jibjf_i=\sum_{j\le i}a_j,g_i=\sum_{j\le i}b_j,答案就是 i=1nfigi2\sum_{i=1}^n\frac{|f_i-g_i|}{2}

略证:考虑每个 1i<n1\le i<n,算出 i,i+1i,i+1 之间转移了多少次。当 fi>gif_i>g_i 时,左侧有 figif_i-g_i 这么多值要转到右边去,每次最多转移 22,因此贡献至少为 figi2\frac{f_i-g_i}{2}fi<gif_i<g_i 时同理。显然可以构造出方案。

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int N=2e5+5;
int a[N],b[N],n;
void solve(){
	n=read();int ans=0,A=0,B=0;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	for(int i=1;i<=n;i++){
		if(a[i]%2!=b[i]%2){puts("-1");return ;}
		A+=a[i],B+=b[i],ans+=(max(A,B)-min(A,B))>>1;
	}
	if(A!=B){puts("-1");return ;}
	cout<<ans<<endl;
}

signed main(void){

	int tt=read();
	while(tt--)solve();

	return 0;
}

C. 梦迹

考虑开一个桶,记 cic_i 为满足 ax=ia_x=ixx 的个数,再设其前缀和 fi=j=1icjf_i=\sum_{j=1}^ic_j

如果不考虑 iji\le j 的限制,那么答案就是

i=0WcifWi(1)\sum_{i=0}^Wc_if_{W-i}\tag{1}

一次修改相当于将某个 cxcx+1,cycy1c_x\leftarrow c_x+1,c_y\leftarrow c_y-1。考虑 cxcx+1c_x\leftarrow c_x+1 对答案的影响。

分两种情况讨论:

  • 2x>W2x>W:这种情况比较简单,(1)(1) 式的第 0,1,,Wx0,1,\cdots,W-x 项与第 xx 项发生了改变。对于 iWxi\le W-xcifWic_if_{W-i} 变为了 ci(fWi+1)c_i(f_{W-i}+1),增加了 cic_i;对于第 xx 项,cxfWxc_xf_{W-x} 变为 (cx+1)fWx(c_x+1)f_{W-x},增加了 fWxf_{W-x}。因此只需将答案加上 fWx+iWxci=2fWxf_{W-x}+\sum_{i\le W-x}c_i=2f_{W-x},再处理对应的 c,fc,f 的改动即可。
  • 2xW2x\le W:此时 (1)(1) 式的第 0,1,,Wx0,1,\cdots,W-x 项发生改变,但第 xx 项的改变不同。对于 iWxi\le W-xixi\neq x,这一项的增加仍为 cic_i;但对于第 xx 项,由 cxfWxc_xf_{W-x} 变成了 (cx+1)(fWx+1)(c_x+1)(f_{W-x}+1),增加了 cx+fWx+1c_x+f_{W-x}+1,因此总的增幅为 2fWx+12f_{W-x}+1

使用树状数组维护单点加与前缀和,复杂度 O((n+q)logV)O((n+q)\log V),其中 V=3×105V=3\times 10^5 为值域。

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int N=3e5+5;
int n,q,W,a[N],cnt,ans;
struct BIT{
	int c[N];
	int lowbit(int x){return x&(-x);}
	void add(int x,int k){x++;for(int i=x;i<=W+1;i+=lowbit(i))c[i]+=k;}
	int sum(int x,int res=0){x++;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
}T;

void Modify(int x,int k){
	cnt+=k*(x+x<=W);
	if(x+x>W)ans+=k*2*T.sum(W-x),T.add(x,k);
	else ans+=k*2*T.sum(W-x)+1,T.add(x,k);
}

signed main(void){

	n=read(),q=read(),W=read();
	for(int i=1;i<=n;i++)a[i]=read(),Modify(a[i],1);
	for(int i=1;i<=q;i++){
		int p=read(),x=read();Modify(a[p],-1),Modify(x,1),a[p]=x;
		cout<<(ans+cnt)/2<<endl;
	}

	return 0;
}

D. Small Cloud Sugar Candy

BV1Uy4y137SA

对每条限制连边,那么得到一张无向图。考虑每个连通块,

  • 若存在奇环,那么奇环上的点权都可以直接确定,进而确定整个连通块,看看是否有矛盾即可。具体来说,如果我们找到了一个奇环,设其上的边权分别为 w1,w2,,wkw_1,w_2,\cdots,w_k,其中 wiw_i1i<k1\le i<k) 连接 ai,ai+1a_i,a_{i+1}wkw_k 连接 ak,a1a_k,a_1,那么 ax=w1w2+,wk1+wk2a_x=\frac{w_1-w_2+\cdots,-w_{k-1}+w_k}{2}
  • 否则,我们随便钦定一个点,让它的权值为 00(或者任意数),那么整个连通块的值都可以确定。确定后看是否有矛盾即可。

时间复杂度 O(n+m)O(n+m)。显然构造出的序列每一项都在 [1018,1018][-10^{18},10^{18}] 中。

Bonus:

  • 实际上我们也可以构造出满足 aia_i 仍然在 [0,109][0,10^9] 内的解
  • 并且能构造字典序最小的解,还能输出方案数。
#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int N=5e5+5;

struct Edge{
	int cost,to;
	Edge(int T,int C):to(T),cost(C){}
	Edge(){}
};
vector<Edge>G[N];
int dep[N],fa[N],val[N],a[N],fir;
bool chk=0,vis[N],calc[N];
bool Ans=1;

void dfs1(int u){
	vis[u]=1;
	for(auto t:G[u]){
		int v=t.to,w=t.cost;
		if(v==fa[u])continue;
		else if(!vis[v]){dep[v]=dep[u]+1,fa[v]=u,val[v]=w,dfs1(v);continue;}
		if((!chk)&&(dep[u]-dep[v]+1)%2==1){
			int p=u,now=1,sum=w;
			while(p!=v)sum+=val[p]*now,now=-now,p=fa[p];
			if(sum%2!=0)Ans=0;
			a[u]=sum/2,fir=u,chk=1,calc[u]=1;
		}
	}
}

void dfs2(int u){
	calc[u]=1;
	for(auto t:G[u]){
		int v=t.to,w=t.cost;
		if(!calc[v])a[v]=w-a[u],dfs2(v);
		else if(calc[v]&&a[u]+a[v]!=w)Ans=0;
	}
}

int n,m,fr[N],to[N],we[N];
void solve(){
	n=read(),m=read();Ans=1;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();fr[i]=u,to[i]=v,we[i]=w;
		G[u].push_back(Edge(v,w)),G[v].push_back(Edge(u,w));
	}

	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		chk=0,fir=i,dfs1(i),dfs2(fir);
	}

	if(!Ans)puts("-1");
	else{for(int i=1;i<=n;i++)cout<<a[i]<<" ";puts("");}
	
	for(int i=1;i<=n;i++)dep[i]=fa[i]=val[i]=a[i]=calc[i]=vis[i]=0;fir=chk=0;
	for(int i=1;i<=n;i++)G[i].clear();
} 

signed main(void){
	
	int tt=read();while(tt--)solve();

	return 0;
}

E. 琉焰

对于每次询问,设 kk 为此时连通块数量,mm 为此时的边数,那么答案就是 2mn+k12^{m-n+k}-1

为什么呢,首先可以对每个连通块单独考虑。随便拎出来一个生成树,那么合法的方案与非树边的非空子集一一对应。一个大致的证明如下:

  • 对于任意一个非树边的非空子集,我们考虑这样构造方案:对于这个子集中的每条边 (u,v)(u,v),将森林中 uvu\to v 的路径上的所有边以及 (u,v)(u,v) 这条边覆盖一次,那么最终我们选取的边集就是所有覆盖次数为奇数的边组成的集合。不难验证这个生成子图确实符合条件。

  • 考虑一个符合条件的生成子图,那么图中的每个连通块都存在一条欧拉回路。欧拉回路一定可以被拆分成若干个环的并,而在上面的构造方式中,每个环的刻画方式是唯一的。因此两边就一一对应了。

一个连通块的非树边数量是 边数 - 点数 +1,当有 kk 个连通块时,方案数就是 2mn+k12^{m-n+k}-1,减一是减去空集。

考虑线段树分治,把 (u,v)(u,v) 的存在区间拆成 O(logn)O(\log n) 个小区间插入线段树,然后 DFS 整棵树并处理对应的修改即可。

使用可撤销并查集维护连通块个数,时间复杂度不会超过 O((n+m)2(n+m))O((n+m)\log ^2(n+m))

//我是宵宫小姐的狗

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
int randint(int l,int r){return rand()*rand()%(r-l+1)+l;}

#define fi first
#define se second
#define mk make_pair

const int N=2e5+5;
int n,m;
map<pair<int,int>,int>Map;

int fa[N],sz[N],top=0,cnt=0,P[N];
pair<int,int>stk[N];
int find(int x){return x==fa[x]?x:find(fa[x]);}
void adde(int x,int y){
	x=find(x),y=find(y);
	if(x==y)return ;
	if(sz[x]>sz[y])swap(x,y);
	sz[y]+=sz[x],fa[x]=y,stk[++top]=mk(x,y),cnt--;
}
void undo(int id){
	int x=stk[id].fi,y=stk[id].se;
	sz[y]-=sz[x],fa[x]=x,cnt++;
}

#define ls(p) (p<<1)
#define rs(p) (p<<1|1)

vector<pair<int,int> >vec[N<<2];
void add(int l,int r,pair<int,int>k,int ql,int qr,int p){
	if(l<=ql&&qr<=r){vec[p].emplace_back(k);return ;}
	int mid=(ql+qr)>>1;
	if(l<=mid)add(l,r,k,ql,mid,ls(p));
	if(r>mid)add(l,r,k,mid+1,qr,rs(p));
}

int Ans[N],cur[N];
void dfs(int ql,int qr,int p){
	int now=top;for(auto t:vec[p])adde(t.fi,t.se);
	if(ql==qr){Ans[ql]=P[cur[ql]-n+cnt]-1;while(top>now)undo(top--);return ;}
	int mid=(ql+qr)>>1;dfs(ql,mid,ls(p)),dfs(mid+1,qr,rs(p));
	while(top>now)undo(top--);
}

int st[N],ed[N],fr[N],to[N]; 
signed main(void){
	
	n=read(),m=read();int tot=0;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();auto it=Map.find(mk(u,v));
		if(it==Map.end())Map[mk(u,v)]=i,cur[i]=cur[i-1]+1;
		else st[++tot]=it->se,ed[tot]=i-1,fr[tot]=u,to[tot]=v,Map.erase(it),cur[i]=cur[i-1]-1;
	}
	for(auto it:Map)st[++tot]=it.se,ed[tot]=m,fr[tot]=it.fi.fi,to[tot]=it.fi.se;
	P[0]=1;for(int i=1;i<=m;i++)P[i]=(P[i-1]<<1)%mod;
	for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1;cnt=n;
	for(int i=1;i<=tot;i++)add(st[i],ed[i],mk(fr[i],to[i]),1,m,1);
	dfs(1,m,1);for(int i=1;i<=m;i++)cout<<Ans[i]<<'\n';
	
	return 0;
}

//外星日记 地球纪年2023.2.16
//今天又用陷阱捕获了不少人类。但当我看到一个叫宵宫的人的时候我愣住了。捕获了那么多人类,还是第一次被人类捕获了。

F. wavedash.ppt

首先我们把平方拆开,有

f(S)=V(P)S,V(Q)SW(P)W(Q)f(S)=\sum_{V(P)\subseteq S,V(Q)\subseteq S}W(P)W(Q)

考虑交换求和顺序,枚举 P,QP,Q,有

S{1,2,,n}f(S)=P,Q2nV(P)V(Q)W(P)W(Q)=2nP,Q2V(P)V(Q)W(P)W(Q)\begin{aligned}\sum_{S\subseteq \{1,2,\cdots,n\}}f(S)&=\sum_{P,Q}2^{n-|V(P)\cup V(Q)|}W(P)W(Q)\\&=2^n\sum_{P,Q}2^{-|V(P)\cup V(Q)|}W(P)W(Q)\end{aligned}

注意到 AB=A+BAB|A\cup B|=|A|+|B|-|A\cap B|,因此上式即

2nP,Q2V(P)V(Q)×2V(P)W(P)×2V(Q)W(Q)2^n\sum_{P,Q}2^{|V(P)\cap V(Q)|}\times 2^{-|V(P)|}W(P)\times 2^{-|V(Q)|}W(Q)

我们定义 W(P)=2V(P)W(P)W'(P)=2^{-|V(P)|}W(P),则只需要求

P,Q2V(P)V(Q)W(P)W(Q)=P,Q(T[T(V(P)V(Q))])W(P)W(Q)=TTV(P),TV(Q)W(P)W(Q)\begin{aligned}\sum_{P,Q}2^{|V(P)\cap V(Q)|}W'(P)W'(Q)&=\sum_{P,Q}\left(\sum_{T}[T\subseteq \big(V(P)\cap V(Q)\big)]\right)W'(P)W'(Q)\\&=\sum_{T}\sum_{T\subseteq V(P),T\subseteq V(Q)}W'(P)W'(Q)\end{aligned}

考虑设 g(u)g(u) 表示 TT 中拓扑序最小的点为 uu(这里认为存在连边 uvu\to vuu 的拓扑序小于 vv),且只计入从 uu 开始的路径 P,QP,Q,但不计入 uu 的贡献,此时的所有 (T,P,Q)(T,P,Q) 的贡献之和;同时预处理 s(u,v)s(u,v) 表示所有从 uu 开始到 vv 结束的路径 PP,但不计入 uu 的贡献的 W(P)W'(P) 之和,那么有转移

g(u)g(v)×s(u,v)2g(u)\leftarrow g(v)\times s(u,v)^2

同时定义

s(0,v)=nu1wu2×s(u,v),s(v,n+1)=1uns(v,u)(1vn)s(0,n+1)=1u,vns(u,v)×wu2s(0,v)=\sum_{n\ge u\ge 1}\frac{w_u}{2}\times s(u,v),s(v,n+1)=\sum_{1\le u\le n}s(v,u)\quad(1\le v\le n)\\ s(0,n+1)=\sum_{1\le u,v\le n}s(u,v)\times \frac{w_u}{2}

并类似地定义 g(0)g(0),则初值为 g(n+1)=1g(n+1)=1,答案即为 g(0)g(0)

拓扑排序后 DP 即可。时间复杂度为 O(n2+nm)O(n^2+nm)

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
int randint(int l,int r){return rand()*rand()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}

const int N=4005;
const int iv=inv(2);
int f[N][N],g[N],n,m,w[N],ind[N];
vector<int>G[N],tp;
queue<int>q;

bool topo(){
	for(int i=1;i<=n;i++)if(!ind[i])q.push(i);
	while(q.size()){
		int x=q.front();q.pop();tp.emplace_back(x);
		for(int v:G[x])if(--ind[v]==0)q.push(v);
	}
	return (tp.size()==n+1);
}

signed main(void){

	n=read(),m=read();
	for(int i=1;i<=n;i++)w[i]=read()*iv%mod;
	for(int i=1;i<=m;i++){int u=read(),v=read();G[u].emplace_back(v),ind[v]++;}
	
	tp.emplace_back(0);assert(topo());tp.emplace_back(n+1);
	for(int i=1;i<=n;i++){
		int u=tp[i];f[u][u]=1;
		for(int j=i;j<=n;j++){
			int v=tp[j];for(int x:G[v])add(f[u][x],f[u][v]*w[x]%mod);
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(f[0][i],f[j][i]*w[j]%mod),add(f[i][n+1],f[i][j]);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)add(f[0][n+1],f[i][j]*w[i]%mod);

	g[n+1]=1;for(int i=n;i>=0;i--){
		for(int j=i+1;j<=n+1;j++)add(g[tp[i]],g[tp[j]]*f[tp[i]][tp[j]]%mod*f[tp[i]][tp[j]]%mod);
	}
	cout<<g[0]*ksm(2,n)%mod<<'\n';
	
	return 0;
}

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐