夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

20ZR省选Day4

2021-01-30 22 min read # 搜索 # manacher # 圆方树 # 比赛题 # 构造 # 动态规划

A. [21省选day4]出题人

有毒啊

就是说我们先神仙问题转换一下

显然我们对于n个点连出n条边使得每条边都满足限制的case,一个点能消掉一个环是相当优秀的case,就是不会更劣

所以考虑偶数,他们一定用n/2n/2自选两次干掉

剩下的就是奇数的情况,考虑我们想制作菜肴一样给他们连出一个环.....

等等?怎么感觉要连出n个环啊??

等等?好像我们有一个万金油:0

有了0,其他所有的东西都可以和0成环解决了!

同时?你会发现如果我们b能满足一个性质加起来为a,我们钦定其中一个是0也不是问题啊

所以考虑再转换假如环长为k

ai=bi+bi+1a_i=b_i+b_{i+1},有bk+1=b1b_{k+1}=b_1

那么你会发现无论如何都有

∑ai=2∗∑bi\sum a_i=2*\sum b_i

然后坏了,你会发现这个东西好像很不能做啊,但是说接着发现

2∣k2|k!!!!

这个信息告诉我们:我们一定存在一种排列a的方案,使得a1+a3+a5...=a2+a4+a6...a_1+a_3+a_5...=a_2+a_4+a_6...

因为说你会发现左右两边拆开后都等于∑bi\sum b_i!

也就差不多找到方法了:如果我们能找到大小和权值和相同的两个集合A,B,将他们拿出来错开,钦定b1=0b_1=0,然后根据a1=b1+b2a_1=b_1+b_2,迭代构造即可

然后剩下的,n2n^2枚举可行的组合即可

解决这个找集合可以折半搜索,就是先整个划分开,然后每个元素要么分入1要么分入2要么不分入,对于一个最后的状态,记录∣A∣−∣B∣|A|-|B|以及整个权值和即可qwq

然后右边一样匹配即可

一开始我这个sb写成了O(3n/2∗n/2)O(3^{n/2}*n/2)

但实际上我们可以在过程中记录信息吐了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=123;
const int P=19260817;
const ll B=123450;
const int MAXV=P;

int n,m,mx,qcnt;
int home[P],nxt[MAXV];
ll w[MAXV],flw[MAXV],to[MAXV];
int ccnt,cnt1,cnt2,flg;
ll a[MAXN],b[MAXN],q1[MAXN],q2[MAXN];

inline void ct(int u,ll x,ll y,ll z) {
	ccnt++;
	nxt[ccnt]=home[u];
	to[ccnt]=x;
	w[ccnt]=y;
	flw[ccnt]=z;
	home[u]=ccnt;
}

inline void add(ll Sc,ll cc,ll rc) {
	int x=(Sc*B%P+cc+P)%P;
//	if(qcnt>MAXV) {
//		printf("%d\n",qcnt);
//		exit(0);
//	}
//	assert(rc>=0);
	for(int i=home[x]; i; i=nxt[i]) {
		ll v=to[i], g=w[i];
//		qcnt++;
		if(v==Sc && g==cc) {
			return ;//²»ÐèÒªÔÙ²åÈë
		}
	}
//	qcnt++;
	ct(x,Sc,cc,rc);
	return;
}

inline void trs(ll S1,ll S2) {
	m=0;
//	printf("%d %d\n",S1,S2);
	for(int i=1; i<=n; ++i) {
		if(!(a[i]%2==0))b[++m]=a[i];
	}
	mx=m/2;
	for(int i=0; i<mx; ++i) {
		if((S1 >> (i<<1) &3) ==1)q1[++cnt1]=b[i+1];
		if((S1 >> (i<<1) &3) ==2)q2[++cnt2]=b[i+1];
	}
	for(int i=1; i<=(m+1)/2; ++i) {
		swap(b[i],b[i+mx]);
//		printf("%d ",b[i]);
	}
	mx=(m+1)/2;
	for(int i=0; i<mx; ++i) {
		if((S2 >> (i<<1) &3) ==1) {
			q1[++cnt1]=b[i+1];
//			printf("%d %d\n",i,b[i+1]);
		}
		if((S2 >> (i<<1) &3) ==2) {
			q2[++cnt2]=b[i+1];
//			printf("%d %d\n",i,b[i+1]);
		}
	}
	return ;
}

inline int qry(ll Sc,ll cc,ll rc) {
	int x=(Sc*B%P+cc+P)%P;
	for(int i=home[x]; i; i=nxt[i]) {
		ll v=to[i],g=w[i];
//		qcnt++;
		if(v==Sc && g==cc) {
			if(flw[i]==0 && rc==0)continue;//¿Õ¼¯²éÕÒµ½ÁË¿Õ¼¯£¡
//			printf("%d %d %d %d\n",v,g,Sc,cc);
			trs(flw[i],rc);
			return 1;
		}
	}
	return 0;
}

inline void dfs1(int u,ll S,ll sum,ll cnt) {
	if(u==mx) {//½áÊø£¬Ñ¹Èëhash
//		ll cnt1=0,cnt2=0,sum1=0,sum2=0;
//		for(int i=0; i<mx; ++i) {
//			if(((S>>(i<<1)) &3)==1) {
//				cnt1++;
//				sum1+=b[i+1];
//			}
//			if(((S>>(i<<1)) &3)==2) {
//				cnt2++;
//				sum2+=b[i+1];
//			}
//		}
//		printf("%d %d %d %d %d!!\n",S,sum1,sum2,cnt1,cnt2);
		//¼Ç¼µÚÒ»¸ö¼¯ºÏ-µÚ¶þ¸ö¼¯ºÏµÄÐÅÏ¢qwq
		add(sum,cnt,S);//Ë«¹Ø¼ü×Ö
		return ;
	}
	dfs1(u+1,S,sum,cnt);
	dfs1(u+1,S^(1ll<<(u<<1)),sum+b[u+1],cnt+1);
	dfs1(u+1,S^(2ll<<(u<<1)),sum-b[u+1],cnt-1);
	return;
}


inline void dfs2(int u,ll S,ll sum,ll cnt) {
	if(flg)return;

	if(u==mx) {
//		ll cnt1=0,cnt2=0,sum1=0,sum2=0;
//		for(int i=0; i<mx; ++i) {
//			if(((S>>(i<<1)) & 3)==1) {
//				cnt1++;
//				sum1+=b[i+1];
//			}
//			if(((S>>(i<<1)) & 3)==2) {
//				cnt2++;
//				sum2+=b[i+1];
//			}
//		}
//		printf("%d %d %d %d %d ??\n",S,cnt1,cnt2,sum1,sum2);
		if(qry(sum,cnt,S)) {
			flg=1;
			return;
		}
		return ;
	}
	dfs2(u+1,S,sum,cnt);
	dfs2(u+1,S^(1ll<<(u<<1)),sum-b[u+1],cnt-1);
	dfs2(u+1,S^(2ll<<(u<<1)),sum+b[u+1],cnt+1);
	return;
}

inline void solve1() {
	puts("Yes");
	int rc=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]%2==0) {
			rc=i;
			b[i]=a[i]/2;
			break;
		}
	}
	for(int i=1; i<=n; ++i) {
		printf("%lld ",a[i]-b[rc]);
	}
	puts("");
	for(int i=1; i<=n; ++i)printf("%d %d\n",i,rc);
}

int main() {
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		scanf("%lld",&a[i]);
	}
	for(int i=1; i<=n; ++i) {
		if(!(a[i]%2==0))b[++m]=a[i];
//		printf("%d ?\n",b[i]);
	}
	if(m!=n)return solve1(),0;
	mx=m/2;
	dfs1(0,0,0,0);//¿¼ÂÇÁËÇ°i¸öÎïÆ·£¬È»ºóµ±Ç°ÎïÆ·Ñ¡ÔñµÄ״̬ÊÇS qaq
//	if(n==30) {
//		puts("qwq");
//		return 0;
//	}
	for(int i=1; i<=(m+1)/2; ++i) {
		swap(b[i],b[i+mx]);
//		printf("%d\n",b[i]);
	}
	mx=(m+1)/2;
	flg=0;
	dfs2(0,0,0,0);//ÕÒµ½ÁËÂð£¿
//	printf("%d?\n",qcnt);
	if(!flg)return puts("No"),0;
	//¹¹ÔìÕâ¸öbÊý×é
	b[1]=0;
	assert(cnt1==cnt2);
//	printf("%d %d ??\n",cnt1,cnt2);
	for(int i=1; i<cnt1+cnt2; ++i) {
//		printf("%d %d %d %d\n",q1[(i+1)/2],q2[(i)/2],b[i],i);
		if(i&1) {
			b[i+1]=q1[(i+1)/2]-b[i];
		} else {
			b[i+1]=q2[i/2]-b[i];
		}
	}
	for(int j=1; j<=n; ++j) {
		bool flg=1;
		for(int i=1; i<=cnt1; ++i) {
			if((a[j]==q1[i]) || (a[j]==q2[i])) {
				flg=0;
				break;
			}
		}
//		printf("%d %d %d\n",j,a[j],flg);
		if(flg) {
			cnt2++;
//			printf("%d %d\n",cnt1,cnt2);
			b[cnt1+cnt2]=a[j];
		}
	}
//	for(int i=1; i<=n; ++i)printf("%d ",a[i]);
	puts("Yes");
	for(int i=1; i<=n; ++i)printf("%lld ",b[i]);
	puts("");
	for(int i=1; i<=n; ++i) {
		bool flg=1;
		for(int j=1; j<=n; ++j) {
			for(int k=1; k<=n; ++k) {
				if(b[j]+b[k]==a[i]) {
					printf("%d %d",j,k);
					flg=0;
					break;
				}
			}
			if(!flg)break;
		}
		puts("");
	}
	return 0;
}
/*
30
1 -21 33 -45 57 -69 79 -89 99
111 111 121 131 141 151 161 171 181 191
2019 2117 2215 2313 2411 2511 2611 2711 2811 2911 3011
*/

B. [21省选day4]彩色挂饰

一开始没看见所有挂饰无色...qaq

考虑树形dp推广开,就是建立圆方树

然后对于一个方点,他的父亲一定是一个圆点,而且是割点

fu,cf_{u,c}就表示圆点u的颜色为c或者方点u的父亲颜色为c的时候的最小连通块数是什么

然后转移对于圆点你会发现他的儿子都是方点,那么直接

fu,c=1+∑v(fv,c−1)f_{u,c}=1+\sum_{v} (f_{v,c}-1)

因为我们会减少一个点的代价啊qwq

然后对于方点的转移QAQ我们要对于这个点双状压了,首先设他代表的点双是v0...vmv_0...v_m,v0v_0是他在圆方树上的父亲

那么你会发现我们可以预处理每个方点的他的vv那些是相互联通的,具体的,枚举一个集合S

如果S>=2S>=2,压位表示出AxA_x表示点x的相邻的在一个点双内的点是哪些,然后转移直接枚举最小编号的那个除掉再&这个点的AxA_x即可qwq

$C(S) = ⋁ x∈S (C(S / {x}) ∧ (S ∩ Ax ≠ ∅)) $

于是能够得到一个连通块染一种颜色的最小代价G,枚举一个颜色c,就是minc(1+∑i∈(fi,c−1))min_c(1+\sum i\in (f_{i,c}-1))

然后对于不连通的S,显然就是正无穷啊

最后考虑dp出整个的方案数,用子集卷积h(S)h(S)表示一个S连通块染的最小代价

h(S)=min⁡G(T)+h(S/T)h(S)=\min G(T)+h(S/T)

fu,c=min(gT,c+H(mS/T),v0∈T)f_{u,c}=min(g_{T,c}+H(mS/T),v_0 \in T)

g数组是我们这个连通块染上颜色c的代价,显然,mSmS是全集

DP不清空辅助数组爆零两行泪

然后小心我们如果是菊花图,他的方点的父亲每次枚举一遍复杂度是不对的

所以保证每个点只在父亲处被枚举一次即可

#include<bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
#define lowbit(x) (x&(-x))
const int MAXN=1e6+2e5+7;
const int inf=1e9+7;
const int MAXK=22;
int n,m,mK,mS,a[MAXN],ccnt;
int nxt[MAXN],to[MAXN],home[MAXN];

inline  void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}

vector<int> G[MAXN];
int dfn[MAXN],low[MAXN],dep,st[MAXN],tp,cnt;

inline void tarjan(int u) {
	low[u]=dfn[u]=++dep;
	st[++tp]=u;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u]) {
				++cnt;
				for(int x=0; x!=v; --tp) {
					x=st[tp];
					G[cnt].pb(x);
					G[x].pb(cnt);
				}
				G[u].pb(cnt);
				G[cnt].pb(u);
			}
		} else low[u]=min(low[u],dfn[v]);
	}
	return;
}
const int MAXS=4505;
int f[MAXN][MAXK],g[MAXS][MAXK],H[MAXN],Gh[MAXN],A[MAXN],avi[MAXN];
int tot,vis[MAXN],vis2[MAXN],q[MAXN],p,rc;

inline void init(int x) {
	tot=0;
	for(int v : G[x]) {
		vis[v]=tot;
		vis2[tot]=v;
		++tot;
	}
	for(int v : G[x]) {
		if(v==rc)continue;
		for(int i=home[v]; i; i=nxt[i]) {
			int q=to[i];
			if(~vis[q]) {
				A[v]|=(1<<vis[q]);
				A[q]|=(1<<vis[v]);
			}
		}
	}//init lin yu
	return ;
}

inline void getG() {
	int ML=(1<<tot)-1;
	for(int S=0; S<=ML; ++S) {
		p=0;
		if(S-lowbit(S)==0)avi[S]=1;
		else {
			avi[S]=0;
			for(int i=0; i<tot; ++i)if(S>>i&1)avi[S]|=(avi[S^(1<<i)]&((S&A[vis2[i]])!=0));
		}
		for(int i=0; i<tot; ++i)if(S>>i&1)q[++p]=vis2[i];
		Gh[S]=inf;
		if(avi[S]) {
			for(int i=1; i<=mK; ++i) {
				g[S][i]=1;
				for(int j=1; j<=p; ++j) {
					g[S][i]+=f[q[j]][i]-1;
				}
				Gh[S]=min(Gh[S],g[S][i]);
			}
		} else for(int i=1; i<=mK; ++i)g[S][i]=inf;
	}
	return ;
}

inline void out(int S) {
	for(int i=0; i<tot; ++i) {
		if(S>>i&1)printf("%lld ",vis2[i]);
	}
	puts("");
}

inline void getH() {
	H[0]=0;
	int ML=(1<<tot)-1;
	for(int S=1; S<=ML; ++S) {
		H[S]=inf;
		for(int T=S; T!=-1; T=(T-1)&S) {
			H[S]=min(H[S],H[T]+Gh[S^T]);
			if(T==0)break;
		}
	}
	return ;
}

inline void getf(int u) {
	int ML=(1<<tot)-1;
	for(int i=1; i<=mK; ++i) {
		f[u][i]=inf;
		for(int S=0; S<=ML; ++S)if(S>>vis[rc]&1)f[u][i]=min(H[ML^S]+g[S][i],f[u][i]);
	}
	return;
}

inline void getclear(int u) {
	int ML=(1<<tot)-1;
	for(int S=0; S<=ML; ++S) {
		H[S]=Gh[S]=avi[S]=vis2[S]=0;
		for(int k=1; k<=mK; ++k)
			g[S][k]=0;
	}
	for(auto v : G[u]) {
		vis[v]=-1;
		A[v]=0;//我他妈的
	}
}

inline void dfs(int u,int F) {
	if(u<=n) {
		for(int k=1; k<=mK; ++k) {
			if(k!=a[u] && a[u])f[u][k]=inf;
			else f[u][k]=1;
		}
		for(auto v : G[u]) {
			if(v==F)continue;
			dfs(v,u);
		}
		for(auto v : G[u]) {
			if(v==F)continue;
			for(int k=1; k<=mK; ++k)
				f[u][k]+=f[v][k]-1;
		}
	} else {
		for(auto v : G[u]) {
			if(v==F)continue;
			dfs(v,u);
		}
		rc=F;
		init(u);//init v message
		getG();
		getH();
		getf(u);
		getclear(u);
	}
	return;
}

signed main() {
	scanf("%lld%lld%lld%lld",&n,&m,&mK,&mS);
	for(int i=1; i<=n; ++i) {
		scanf("%lld",&a[i]);
	}
	cnt=n;
	for(int i=1,x,y; i<=m; ++i) {
		scanf("%lld%lld",&x,&y);
		ct(x,y);
		ct(y,x);
	}
	for(int i=1; i<=n; ++i)if(!dfn[i])tarjan(i);
	memset(vis,-1,sizeof(vis));
	dfs(1,0);
	int ans=inf;
	for(int i=1; i<=mK; ++i)ans=min(ans,f[1][i]);
	printf("%lld\n",ans);
	return 0;
}

没压行前又是4kb吐了

C. [21省选day4]逆转函数

首先对于暴力我们可以枚举回文中心然后枚举回文半径这样子

正解怎么做?

观察m=2的部分分我们可以知道这个和每个位置的回文中心最长回文半径有关系!

考虑manacher qwq

首先将问题转换的具有回文串性质

首先合法串的定义是没有发生冲突的串

发现我们可以知道,如果[l,r][l,r]要成为一个合法串的话,[l+1,r−1][l+1,r-1]至少要满足是一个合法串吧qwq

然后对于l和r位置,至少l对应的位置是r,那么l之后最近的一个位置(假设为nlnl),他对应的字符也应该是r

然后有数学归纳可知这样一直是成立的

如果nl>rnl>r,此时不难发现l是新出现的字符,不需要管

知道这个性质我们同样可以计算对于一个串,有多少位置是已经固定映射多少位置没有

当加入的nl,nr为新字符(前驱后继在区间外的话)就让这个值减少

然后同样的,我们也能很轻易的在扩展字符串的时候维护整个回文串的答案了!

再看看manacher套上去

对于md为最长回文中心的情况,如果i>mx,此时我们是暴力扩展这个i的回文串,显然可以得到那个答案

然后如果i<mx,而且可以直接复制i的对应点j的半径(就是j−radj>=lj-rad_j>=l)就直接复制

否则,你会发现我们可以暴力缩短这个j的回文半径来得到新的串的答案qwq

此时我们要保证复杂度正确啊QAQ

你会发现如果我们每次做不改变回文中心的话,同时无法向后方扩展的话,下一次又双叒叕要跳一次就TLE了QAQ

那么每次我们让回文中心向后移动,你就会发现即使我们花掉了mx−mdmx-md的代价,但是我们又让这个距离减少了O(mx−md)O(mx-md),所以均摊向右还是O(n)O(n)次qwq

先咕着

//By dawn light
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 7e5 + 7;
const int P = 998244353;
int n, m, a[MAXN], N, b[MAXN], nv[MAXN];
int pre[MAXN], suf[MAXN], tmpv[MAXN], rad[MAXN];
ll f[MAXN];
inline void init() {
	f[0] = 1;
	for(int i = 1; i <= m; ++i)f[i] = f[i - 1] * m % P;
	for(int i = 1; i <= n; ++i)b[i * 2 - 1] = a[i];
	N = 2 * n - 1;
	for(int i = 1; i <= N; ++i) {
		if(!(i & 1)) {
			b[i] = 1234567;
			pre[i] = -1;
			suf[i] = N + 1;
		}
	}
	for(int i = 1; i <= N; i += 2) {
		pre[i] = tmpv[b[i]];
		tmpv[b[i]] = i;
	}
	for(int i = 1; i <= n; ++i)tmpv[a[i]] = N + 1;
	for(int i = N; i >= 1; i -= 2) {
		suf[i] = tmpv[b[i]];
		tmpv[b[i]] = i;
	}
	return ;
}

ll ans, sum[MAXN];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	init();

	for(int i = 1, mx = 0, md = -1; i <= N; ++i) {
		int l, r;
		if(i < mx) {
			int dyi = 2 * md - i;
			l = dyi - rad[dyi];
			r = dyi + rad[dyi];
			sum[i] = sum[dyi];
			nv[i] = nv[dyi];
			while(r - l + 1 > 2 * (mx - i) + 1) {//你这个长度不太行啊
				if(b[l] != 1234567 && b[r] != 1234567) {
					sum[i] = (sum[i] - f[m - nv[i]] + P) % P;
					nv[i] -= (suf[l] > r);
					nv[i] -= (pre[r] <= l); //记右不记左
				}
				l++;
				r--;
			}
			int qwq = (r - l + 1) / 2;
			r = i + qwq;
			l = i - qwq;
		} else {//i>mx
			l = i;
			r = i;
			if(i & 1) {
				sum[i] = f[m - 1];
				nv[i] = 1;
			}//如果是偶数位置,根本就不算贡献
		}
		while(l > 1 && r < N && (suf[l - 1] > r + 1 || b[r + 1] == b[l + r - suf[l - 1]]) && (pre[r + 1] < l - 1 || b[l - 1] == b[l + r - pre[r + 1]])) {
			l--;
			r++;
			if(b[l] != 1234567 && b[r] != 1234567) {
				nv[i] += (suf[l] > r);
				nv[i] += (pre[r] <= l);
				sum[i] = (sum[i] + f[m - nv[i]]) % P;
			}
		}
		sum[i] = (sum[i] % P + P) % P;
		ans = (ans + sum[i]) % P;
		rad[i] = r - i;
		if(r >= mx) {
			mx = r;
			md = i;
		}
	}
	ans = (ans % P + P) % P;
	printf("%lld\n", ans);
	return 0;
}
Powered by Gridea RSS