20210826 Lighthouse,Miner,Lyk Love painting,Revive

考场

T1 这不裸的容斥

T2 这不裸的欧拉路，先从奇数度点开始走，走不了就传送

T3 什么玩意，暴力都不会

T4 点分树？？？

仔细想了一波，发现 T1 T2 都好做，T3 二分答案后可以暴力贪心，但不知道复杂度是啥，T4 点分治+暴力修改有 69pts

8.00 开 T1，先打了个暴力确定是简单环，然后开始写，一直 WA，写到 9.20 过了小样例，但大样例差 \(3\)，仔细看了看是把一个 * inv2 写成了 / 2，改完开拍。然后开始修锅，补丁摞补丁，终于在 9.50 过拍，感觉很稳。

发现只剩 1.5h 了，迅速 rush 完 T2，又想了想 T3 还是不会，输出样例走人。10.20 开 T4，到 11.00 写完了点分治，斟酌了一下决定冲 sub3,11.10 过了小样例，但大样例 RE 了，原因不明。

11.15 开始交题，正好测完所有样例。

res

rk7 17+39+0+47

T1 还有一个地方是 / 2，小数据下没有取模，大样例模完是恰好偶数。

rk1 szs 100+7+80+87

rk2 ycx 61+30+0+26

rk8 陈天宇 29+40+0+13

总结

一个老问题：没想清楚就着急写，结果浪费了很多时间 debug+打补丁，而且还有可能打不全或发现算法假了。

T1 代码不难写，但考场上最开始写的漏洞百出，面向数据编程了好久；T4 从昨天下午 4 点改到今早 9 点（今天重构代码了），就是思路不清晰，算法都是假的，还一直调试。

这一点上 ycx 做到很好，他几乎没写过假做法，而且每次写题前都在草稿纸上列好了，不会出现写到一半发现有 bug 的情况，这就是为什么一起开始改，他昨晚 8 点就 A 了。

以后一定一定要想清楚，确定做法没错再写。

还有重构代码这件事，其实昨晚就有着想法了，因为看网上的题解和我写的非常不一样，但我本身非常排斥。我记得上一次重构还是在去年写一道单调队列的题，但事实上如果需要打补丁的地方很多，真的不如重构。一方面写过一遍，写第二遍不会很浪费时间，而且实现会更好；另一方面重写可以让整个思路/代码是连续且独立的，而不是在原来的思路/代码上改，容易受影响。

不管重不重构，果断一点，不要犹犹豫豫地浪费时间。

至于 T1 挂分，确实是活该。前面干过不少挤占检查时间 rush 题的事（交题前检查时间：20min->15min->5min->0），最后 20min 开始写线段树几乎是家常便饭，今天算是遭报应了。

T1 过了大样例的时候我还很高兴，感觉前天的组合没白学，现在看来是脑子和眼睛白长了。

T2 的欧拉路确实是不会，当时只记住了实现，没搞懂原理，只能是不断查漏补缺了。（怎么感觉这话以前写过）

最后一件事，思维太僵化。

通常情况下 DS 我都写的比较好，但这是基于背板和手速的。一旦遇上需要根据改动，代码不长但难调的题就爆毙了。暂时没什么好办法，只能多做题，积累经验了。

T4 的式子只想到暴力展开，没能从实际意义的角度去分析。

sol

这套题比较卡常，且 T1 T2 代码都是在考场代码上改的，比较难看。

T2 T3 T4 有不同的实现/做法，可以看这篇。

Lighthouse

一张完全图不同 \(n\) 元环的数量为 \(\frac{(n-1)!}2\)

暴力枚举选的边容斥。注意细节：一个点度数 \(\neq2\) 就不合法；有环就不合法，但 \(n\) 元环合法；点不分前后，但链有。

code

const int N = 1e7+5, M = 25, mod = 1e9+7, inv2 = 5e8+4;

int n,m;

PII e[M];

int all,id[N],deg[N],fa[N];

LL ans,fac[N];

LL Pow(LL x,LL y=mod-2)

	{ LL res=1; for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod; return res; }

void ckadd(LL &x,LL y) { x+=y; if(x>=mod)x-=mod; else if(x<0)x+=mod; }

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

int count(int s) { int res=0; for(;s;s-=s&-s)++res; return res; }

bool cir(int s) {

	if( count(s) != n ) return 0;

	int res = 0;

	For(i,0,m) if( (s >> i) & 1 )

		fa[find(e[i].fi)] = find(e[i].se), ++deg[e[i].fi], ++deg[e[i].se];

	For(i,1,n) {

		res += fa[i]==i;

		if( deg[i] != 2 ) res = N;

	}

	For(i,1,n) fa[i] = i, deg[i] = 0;

	return res==1;

}

LL calc(int s) {

	if( cir(s) ) return 1;

	int n1 = 0, res = 0, cnt = 0;

	For(i,0,m) if( (s >> i) & 1 ) {

		id[++n1] = e[i].fi, id[++n1] = e[i].se;

		++deg[e[i].fi], ++deg[e[i].se];

		if( find(e[i].fi) == find(e[i].se) ) res = N;

		fa[find(e[i].fi)] = find(e[i].se);

	}

	sort(id+1,id+n1+1), n1 = unique(id+1,id+n1+1)-id-1;

	For(i,1,n1) ckmax(res,deg[id[i]]), cnt += fa[id[i]]==id[i];

	For(i,1,n1) deg[id[i]] = 0, fa[id[i]] = id[i];

	LL ans = res<=2 ? fac[n-n1+cnt-1]*inv2%mod*Pow(2,cnt)%mod : 0;

	return ans;

}

signed main() {

	read(n,m); all = (1 << m--) - 1;

	fac[0] = 1; For(i,1,n) fac[i] = fac[i-1] * i %mod;

	For(i,1,n) fa[i] = i;

	For(i,0,m) read(e[i].fi,e[i].se);

	For(s,0,all) ckadd(ans,(count(s)&1?-1:1)*calc(s));

	write(ans);

	return iocl();

}

Miner

由于欧拉路的算法只能在合法的图上跑，因此需要先手动连边。

注意每个联通块有欧拉路就行了，因此可以有 \(\le2\) 个奇数度点。

code

const int N = 1e5+5;

int n,m,mm=1,head[N],to[N*4],w[N*4],nxt[N*4];

int s,n1,deg[N],fa[N],id[N];

bool vis[N*4];

int tp,rea,ans1; PII stk[N*4],ans[N*4];

void adde(int x,int y,int z)

	{ to[++mm] = y, w[mm] = z, nxt[mm] = head[x], head[x] = mm; }

void link(int x,int y,int z) { adde(x,y,z), adde(y,x,z), ++deg[x], ++deg[y]; }

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }

void dfs(int u,int x=1) {

	static int top; top=0; static PII stack[N*4];

	stack[++top] = MP(x,u);

	while( top ) {

		u = stack[top].se; int i = head[u];

		while( i && vis[i] ) i = nxt[i];

		if( i ) {

			head[u] = nxt[i], vis[i] = vis[i^1] = 1, --deg[u], --deg[to[i]];

			stack[++top] = MP(w[i],to[i]);

		} else {

			if( ~stack[top].fi ) stk[++tp] = stack[top];

			--top;

		}

	}

}

void print() { while( tp ) ans1 += stk[tp].fi, ans[++rea] = stk[tp--]; }

signed main() {

	read(n,m);

	For(i,1,n) fa[i] = i;

	For(i,1,m) {

		int x,y; read(x,y);

		link(x,y,0), fa[find(x)] = find(y);

	}

	For(i,1,n) if( deg[i] & 1 ) id[++n1] = i;

	sort(id+1,id+n1+1,[](const int &x,const int &y){return find(x)<find(y);});

	for(int i = 1, cnt = 1; i <= n1; ++i) {

		if( find(id[i]) == find(id[i-1]) ) {

			++cnt;

			if( cnt > 2 && !(cnt & 1) ) link(id[i],id[i-1],1);

		} else cnt = 1;

	}

	For(i,1,n) if( deg[i] & 1 ) {

		if( !s ) s = i, dfs(s,-1);

		else dfs(i);

		print();

	}

	For(i,1,n) if( deg[i] ) {

		if( !s ) s = i, dfs(s,-1);

		else dfs(i);

		print();

	}

	write(ans1), write(s);

	For(i,1,rea) write(ans[i].fi,' '), write(ans[i].se);

	return iocl();

}

Lyk Love painting

二分答案后 DP 检验，分画所占行数转移，sol 讲的比较清楚了

code

const int N = 1e5+5;

int n,m,a[2][N];

int lst[3][N],f[N];

LL l,r,mid,s[3][N];

bool check() {

	For(k,0,2) for(int i = 0, j = 1; j <= n; ++j) {

		while( s[k][j]-s[k][i] > mid ) ++i;

		lst[k][j] = i;

	}

	f[0] = 0;

	For(i,1,n) {

		f[i] = f[lst[2][i]] + 1;

		int j = i, k = i, s = 0;

		while( s < m && (j || k) ) {

			if( j > k ) j = lst[0][j];

			else k = lst[1][k];

			++s;

			ckmin(f[i],f[max(j,k)]+s);

		}

		if( f[i] > m ) return 0;

	}

	return 1;

}

signed main() {

	read(n,m);

	For(i,0,1) For(j,1,n) {

		read(a[i][j]), s[i][j] = s[i][j-1] + a[i][j];

		ckmax(l,(LL)a[i][j]), r += a[i][j];

	}

	For(i,1,n) s[2][i] = s[2][i-1] + a[0][i] + a[1][i];

	while( l < r ) {

		mid = l+r>>1;

		check() ? r=mid : l=mid+1;

	}

	write(l);

	return iocl();

}

Revive

设 \(P(u,v)\) 为 \(u\) 到 \(v\) 路径上的边集，答案就是

\[\sum_{1\le u<v\le n}(\sum_{e\in P(u,v)}w_e)%2
\]

拆开得到

\[\sum_{e\in E}w_e^2\times经过e的路径数+2\sum_{e_1,e_2\in E,e_1<e_2}w_{e_1}\times w_{e_2}\times同时经过e_1,e_2的路径数
\]

前一部分很好统计，后一部分可以在点分治时记录每个子树的 \(\sum siz\times w\) 计算，具体细节可以自己推移下。

实现上，这题与普通点分治有些不同。为了避免特判，分治中心与其子树的连边并不在分治中心出计算贡献，而是在其子树中；修改需要记录分治时每一层的信息，但权值在边上，因此把信息记录在边上更方便。

另外，二维数组把大的一维开在前面内存访问更连续（否则最后一个 sub 会 T）

code

const int N = 1e6+5, mod = 1e9+7;

int SUB,n,q,fa[N];

LL w[N];

int mm=3,rt,rtmx,head[N],to[N*2],nxt[N*2],siz0[N*2],

	siz[N],siz1[N][17],f[N],g[N][17],top[N][17];

bool vis[N];

LL ans,sum[N],sub[N][17];

LL pw2(LL x) { return x*x%mod; }

void ckadd(LL &x,LL y) { x+=y; if(x>=mod)x-=mod; else if(x<0)x+=mod; }

void adde(int x,int y) { to[++mm] = y, nxt[mm] = head[x], head[x] = mm; }

int dfs0(int u) {

	int sz = 1;

	for(int i = head[u], v; v = to[i], i; i = nxt[i]) if( v != fa[u] ) {

		siz0[i] = dfs0(v), siz0[i^1] = n-siz0[i], sz += siz0[i];

		ckadd(ans,pw2(w[v])*siz0[i]%mod*siz0[i^1]%mod);

	}

	return sz;

}

void findrt(int u,int fa) {

	int mx = 0; siz[u] = 1;

	for(int i = head[u], v; v = to[i], i; i = nxt[i]) if( !vis[v] && v != fa )

		findrt(v,u), siz[u] += siz[v], ckmax(mx,siz[v]);

	ckmax(mx,siz[0]-siz[u]);

	if( mx < rtmx ) rtmx = mx, rt = u;

}

void dfs(int u,int pre,int d,int t) {

	int e = pre>>1;

	f[e] = d, g[e][d] = rt, top[e][d] = t, siz1[e][d] = siz0[pre];

	ckadd(sub[t][d],siz1[e][d]*w[e]%mod);

	if( vis[u] ) return;

	siz[u] = 1;

	for(int i = head[u], v; v = to[i], i; i = nxt[i]) if( (i ^ pre^1) ) {

		dfs(v,i,d,t);

		if( !vis[v] ) siz[u] += siz[v];

	}

}

void work(int u,int d) {

	vis[u] = 1;

	for(int i = head[u], v; v = to[i], i; i = nxt[i])

		dfs(v,i,d,i>>1),

		ckadd(ans,2*sub[i>>1][d]*sum[u]%mod), ckadd(sum[u],sub[i>>1][d]);

	for(int i = head[u], v; v = to[i], i; i = nxt[i]) if( !vis[v] )

		siz[rt=0] = rtmx = siz[v], findrt(v,u), work(rt,d+1);

}

signed main() {

	read(SUB,n,q);

	For(i,2,n) { read(fa[i],w[i]); adde(fa[i],i), adde(i,fa[i]); }

	dfs0(1);

	siz[0] = rtmx = n, findrt(1,0), work(rt,1);

	write(ans);

	while( q-- ) {

		int u; LL x; read(u,x);

		rFor(i,f[u],1) {

			rt = g[u][i]; LL del = siz1[u][i] * x %mod;

			ckadd(ans,2*(sum[rt]-sub[top[u][i]][i])*del%mod);

			ckadd(sub[top[u][i]][i],del), ckadd(sum[rt],del);

		}

		ckadd(ans,(2*w[u]*x+pw2(x))%mod*siz0[u<<1]%mod*siz0[u<<1|1]%mod);

		ckadd(w[u],x);

		write(ans);

	}

	return iocl();

}

巴特西

20210826 Lighthouse,Miner,Lyk Love painting,Revive

考场

res

总结

sol

Lighthouse

Miner

Lyk Love painting

Revive

最新文章

热门文章