2023-10-07发表2023-10-10更新题解44 分钟读完 (大约6640个字)

杂题选做（2023.10.3-2023.10.7）

真就 Atcoder 选做了呗。

CF442D Adam and Tree

题目描述：

树指的是一种无向连通图且满足任意两个点间不存在两条不同的简单路径；

彩色树指的是一种每条边都有一种颜色的树，并且同一种颜色的边集一定形成一条路径。

对于彩色树上的任意一个点 $u$ ，定义其权值 $w(u)$ 为 $u$ 至根节点（即 $1$ 号点）的路径上所有边的颜色种类数。
彩色树会生长，初始时树中仅有根节点 $1$ 号点，每个时刻都会有一个新节点长出来。每个时刻（包括初始时刻），你需要决定每条边的颜色，在满足彩色树的定义的前提下，使这个时刻树中节点权值的最大值最小。

$1 \le n \le 10^6$

题目分析：

感觉上树剖就是一种很优的做法，但是显然不是很对。

一个观察就是对于 $u,v$ ，设 $p$ 为 $lca(u,v)$ ，则将 $u,v$ 之间的路径划分为一种颜色，与将 $u,p$ 和 $v,p$ 之间的路径分别划为不同的颜色对答案造成的影响一样，所以我们只需要考虑将祖先到儿子的链划分为一种颜色即可。

所以显然可以可以使用 $dp$ 解决这个问题，而 $dp$ 的决策就是将哪个儿子的链与这个节点到祖先的链接上，所以一个显然的想法就是设 $dp[i]$ 表示以 $i$ 为根的子树的权值最大值最小是多少，注意这里的权值包含 $i$ 到父亲的边。

设 $i$ 儿子中 $dp$ 值最大为 $mx_1$ 次大为 $mx_2$ ，决策显然就是让 $mx_1$ 与 $i$ 到父亲的链接上，则转移为：

dp[i] = \max(mx_1,mx_2+1)

注意对于 $i=1$ 时因为不存在父亲边所以需要特判。

具体的维护方式就是每加入一个点，就从这个点暴力向上更新，直到更新不下去了就跳出，这样看上去复杂度是 $O(n^2)$ 的。

但是不要忘记了树剖的想法，也就是说我们每个点的答案必然不会超过 $O(\log n)$ ，所以每个点最多被更新 $O(\log n)$ 复杂度就是 $O(n \log n)$ 。

而且通过这道题也可以发现，树剖就基本是一种最优的剖分方式了，因为这个 $dp$ 最终跑出来的复杂度就是 $O(n \log n)$ 。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int mx[N],mx2[N],dp[N],fa[N];
void update(int now,int val){
//	if(val == 0)	val = 1;
	if(val > mx[now])	swap(mx[now],mx2[now]),mx[now] = val;
	else if(val > mx2[now])	mx2[now] = val;
	if(now == 1)	dp[now] = max(mx[now],mx2[now]);
	else	dp[now] = max(mx[now],mx2[now]+1);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;scanf("%d",&n);
	dp[1] = 1;
	for(int i=2; i<=n+1; i++){
		scanf("%d",&fa[i]);
		dp[i] = 1;
		int now = i;
		while(now > 1){
			int tmp = dp[fa[now]];
			update(fa[now],dp[now]);
			if(dp[fa[now]] != tmp)	now = fa[now];
			else{
				now = 0;break;
			}
		}
		printf("%d ",dp[1]);
	}
	return 0;
}

ABC082D FT Robot

题目描述：

现有一个机器人在坐标轴原点处，朝向 $x$ 轴正方向。给定一个命令串 $s$ ， $s$ 内含有两种命令： $F,T$ 。 $F$ 表示向当前朝向前进 $1$ 步， $T$ 表示向左或向右旋转 $90$ 度。请你回答，按照命令串 $s$ 执行，会不会到达 $(x,y)$ 处。（ $x$ 与 $y$ 由题目输入）

$1 \le |s| \le 8\cdot10^3$

题目分析：

首先第一点就是对于一个极长的均为 $F$ 的段，必然只会向一个方向走，所以可以对于每一段缩在一起即可。

注意到一点如果我们当前面向横着的一个方向，则我们下一次既可以选择向上也可以选择向下，也就是对于每一个 $F$ 的段我们可以自由决定到底是向正方向还是负方向走。

所以直接按奇偶分类讨论然后按 $x,y$ 坐标分别 $dp$ 判断是否可以到达即可。

需要特判的就是对于第一个 $T$ 的段因为我们一开始面对 $x$ 正方向所以只能向正方向走。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+4;
vector<int> v[2];
char s[N];
int dp[N],g[N];
bool solve(int opt,int x,int tx){
	memset(dp,0,sizeof(dp));memset(g,0,sizeof(g));
	dp[x+8000] = 1;
	for(auto i : v[opt]){
		for(int j=8000; j>=-8000; j--){
			if(dp[j+8000] && i + j <= 8000 && i + j >= -8000)	g[i+j+8000] = true;
			if(dp[j+8000] && j - i <= 8000 && j - i >= -8000)	g[j-i+8000] = true;
		}
		for(int j=-8000; j<=8000; j++)	dp[j+8000] = g[j+8000],g[j+8000] = 0;
	}
	return dp[tx+8000];
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int tx,ty;
	scanf("%s",s+1);
	scanf("%d%d",&tx,&ty);
	int n = strlen(s+1);
	int x = 0,y = 0;
	for(int i=1; i<=n; i++){
		if(s[i] == 'F')	++x;
		else	break;
	}
	int now = 1;
	for(int i=x+2; i<=n; ){
		int j = i;
		while(j <= n && s[j] == 'F')	++j;
		v[now].push_back(j - i);
		now ^= 1;
		i = j + 1; 
	}
	
	if(solve(0,x,tx) && solve(1,y,ty))	printf("Yes\n");
	else	printf("No\n");
	return 0;
}

ARC157E XXYX Binary Tree

题目描述：

给你一棵有根树，根为 $1$ ，保证对于任意一个点要么有两个儿子，要么没有儿子，你需要把每个点标号为 X，Y 之一，使得对于 $n-1$ 个由父亲和儿子顺序组成的长度为 $2$ 的字符串中：

有 $A$ 个 XX。
有 $B$ 个 XY。
有 $C$ 个 YX。
不存在 YY。

保证 $A+B+C=n-1$ ，而你只需要判断是否有解。

多组数据

$1 \le \sum n \le 10^4$

题目分析：

一个想法就是 $dp$ 解决这个问题。

注意到一点就是不能存在 YY 也就是我们选 Y 的点是一个独立集，而我们每次选择一个 Y 因为其父亲必然选择 X 所以必然会产生一个 XY 的贡献，当然这个东西是除了根节点之外的。

所以我们只需要记录选择了几个 Y 以及有多少个非叶子节点的 Y 就可以解决掉 $B,C$ 限制，而我们通过限制独立集的事情保证了 $D$ 限制的完成，所以 $A$ 限制也自然解决了。

所以直接做的话状态就爆炸了为 $O(n^3)$ 而我们的 $dp$ 值却只是记录了 $01$ 就很亏，所以一个想法就是能不能把 $dp$ 的某个状态扔到值里，所以一个猜测就是当我们选择的 Y 数量固定时，选择非叶子节点的 Y 的数量必然为一段连续的区间，通过打表发现的确如此。

所以我们只需要记录一个最大值以及最小值就好了，直接记录可能就爆了，所以分两次 $dp$ 分别做就好了。

具体的 $dp$ 状态就是记 $dp[i][j][0/1]$ 表示以 $i$ 为根的子树，选择了 $j$ 个 Y，点 $i$ 是不是选择了 Y，的情况下最大/最小的选择非叶子节点 Y 的数量，转移就是树上背包，复杂度 $O(n^2)$ 。

需要注意的一点就是如果 $C$ 是奇数同样也是不合法的，需要特判。

代码：

点击查看代码

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N = 1e4+5;
const int INF = 1e9+5;
int dp[2][N][N],g[2][N];
int sz[N],fa[N];
vector<int> G[N];
void dfs1(int now,int fath){
	if(G[now].size() == 0){
		dp[1][now][1] = 0;
		dp[0][now][0] = 0;
	}
	else{
		dp[1][now][1] = 1;
		dp[0][now][0] = 0;
	}
	sz[now] = 1;
	for(auto to : G[now]){
		if(to == fath)	continue;
		dfs1(to,now);
		for(int i=0; i<=sz[now] + sz[to]; i++)	g[1][i] = g[0][i] = INF;
		for(int i=0; i<=sz[now]; i++){
			for(int j=0; j<=sz[to]; j++){
				g[1][i+j] = min(g[1][i+j],dp[1][now][i] + dp[0][to][j]);
				g[0][i+j] = min(g[0][i+j],dp[0][now][i] + min(dp[1][to][j],dp[0][to][j]));
			}
		}
		for(int i=0; i<=sz[now]+sz[to]; i++)	dp[1][now][i] = g[1][i],dp[0][now][i] = g[0][i];
		sz[now] += sz[to];
	}
}
void dfs2(int now,int fath){
	if(G[now].size() == 0){
		dp[1][now][1] = 0;
		dp[0][now][0] = 0;
	}
	else{
		dp[1][now][1] = 1;
		dp[0][now][0] = 0;
	}
	sz[now] = 1;
	for(auto to : G[now]){
		if(to == fath)	continue;
		dfs2(to,now);
		for(int i=0; i<=sz[now] + sz[to]; i++)	g[1][i] = g[0][i] = -INF;
		for(int i=0; i<=sz[now]; i++){
			for(int j=0; j<=sz[to]; j++){
				g[1][i+j] = max(g[1][i+j],dp[1][now][i] + dp[0][to][j]);
				g[0][i+j] = max(g[0][i+j],dp[0][now][i] + max(dp[1][to][j],dp[0][to][j]));
			}
		}
		for(int i=0; i<=sz[now]+sz[to]; i++)	dp[1][now][i] = g[1][i],dp[0][now][i] = g[0][i];
		sz[now] += sz[to];
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		int n,A,B,C;scanf("%d%d%d%d",&n,&A,&B,&C);
		for(int i=2; i<=n; i++){
			scanf("%d",&fa[i]);
			G[fa[i]].push_back(i);
		}
		
		for(int i=0; i<=n; i++){
			for(int j=0; j<=n; j++){
				dp[0][i][j] = dp[1][i][j] = INF;
			}
		}
		dfs1(1,0);
		int mn = min(dp[1][1][B+1],dp[0][1][B]);
		
		for(int i=0; i<=n; i++){
			for(int j=0; j<=n; j++){
				dp[0][i][j] = dp[1][i][j] = -INF;
			}
		}
		dfs2(1,0);
		int mx = max(dp[1][1][B+1],dp[0][1][B]);
		
		if(mn * 2 <= C && C <= mx * 2 && C % 2 == 0)	printf("Yes\n");
		else	printf("No\n");
		
		for(int i=1; i<=n; i++)	G[i].clear();
	}
	return 0;
}

ARC067F Yakiniku Restaurants

题目描述：

有编号从 $1$ 到 $N$ 的 $N$ 家烧烤店，烧烤店在一条线上按照编号顺序排序，第 $i$ 家烧烤店与第 $i + 1$ 家烧烤店的距离是 $A_i$ 。

你有编号从 $1$ 到 $M$ 的 $M$ 张烧烤券，不管是在哪一家烧烤店都可用烧烤券来吃烧烤，在第 $i$ 家烧烤店用烧烤券 $j$ 可以吃到一顿美味度为 $B_{i,j}$ 的烧烤，每一张烧烤券只能使用一次，但是在一家烧烤店你可以使用任意多张烧烤券。

你想从自己选择的一家烧烤店开始（随意选择一个开始），然后不断地用未使用的烧烤券去另一家烧烤店。你最终的幸福值是所吃所有烧烤的美味度减去所走的总路程。求最大可能的最终幸福值（ $M$ 张券必须用完）。

$2 \leq N \leq 5 \times 10^3$ ， $1 \leq M \leq 200$

题目分析：

假设我们确定了从 $x$ 烧烤店开始，那么我们最优的一种策略显然是一直向左走直到 $l$ 然后从 $l$ 一直向右走直到 $r$ ，或者先向右后向左也是一样的。

但是这样显然不如直接从 $l$ 走到 $r$ 优，所以我们其实只需要对于每一个 $l$ 一步步向右走即可。

直接枚举 $l,r$ 然后再计算答案的复杂度就是 $O(n^2m)$ 不能通过，考虑优化。

因为 $m$ 个烧烤券相互独立所以可以分开考虑，所以下面只考虑对于一种烧烤券如何快速计算。

我们可以枚举一个位置，然后钦定这一张烧烤券在这个位置取得最大值，当我们将一个区间 $[l,r]$ 看作一个二维平面上的点 $(l,r)$ 时，可以发现以这个烧烤券为最大值的区间必然对应二维平面上的一个矩形，所以可以直接二维差分维护，具体的左右端点可以通过单调栈处理出左边/右边第一个大于这个值的位置即可。

因为我们只需要在最后查询一次，也就是说我们只需要做一次二维前缀和，所以复杂度就是 $O(n^2 + nm)$ .

代码:

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3+5;
int s[N][N],b[N][N],a[N],L[N],R[N];
void add(int l1,int r1,int l2,int r2,int val){
	s[l1][l2] += val;
	s[l1][r2+1] -= val;
	s[r1+1][l2] -= val;
	s[r1+1][r2+1] += val;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<n; i++)	scanf("%lld",&a[i]);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%lld",&b[i][j]);
		}
	}
	for(int j=1; j<=m; j++){
		stack<pair<int,int> >st;
		while(!st.empty())	st.pop();  //相等，默认从更靠左的位置统计贡献 
		for(int i=1; i<=n; i++){
			L[i] = 0;
			while(!st.empty() && st.top().first < b[i][j])	st.pop();
			if(!st.empty())	L[i] = st.top().second;
			st.push({b[i][j],i});
		}
		while(!st.empty())	st.pop();
		for(int i=n; i>=1; i--){
			R[i] = n + 1;
			while(!st.empty() && st.top().first <= b[i][j])	st.pop();
			if(!st.empty())	R[i] = st.top().second;
			st.push({b[i][j],i});
		}
		for(int i=1; i<=n; i++){
			add(L[i]+1,i,i,R[i]-1,b[i][j]);
		}
	}
	for(int i=1; i<n; i++)	add(1,i,i+1,n,-a[i]);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]; 
		}
	}
	int ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n; j++){
			ans = max(ans,s[i][j]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

ABC150F Xor Shift

题目描述：

给定两个长度为 $n$ 的序列 $a=\{a_0,a_1,\cdots,a_{n-1}\}$ 和 $b=\{b_0,b_1,\cdots,b_{n-1}\}$ ，输出所有有序数对 $(k,x)$ ，满足：

$0\leq k<n$ 且 $x\geq 0$ 。
序列 $a'=b$ ，其中 $a'_i = a_{i+k\bmod n}\operatorname{xor} x\ (0\leq i<n)$ ，“ $\operatorname{xor}$ ”表示按位异或。

$1\leq n\leq 2\times 10^5$ ， $0\leq a_i,b_i<2^{30}$ 。

题目分析：

注意到异或操作所以我们可以按位来考虑。

对于每一位问题就是相当于两个 $01$ 序列的循环匹配问题，循环同构的问题可以通过二倍长度来解决，也就是将 $a$ 复制一遍接到 $a$ 的后面，这样问题就转化为了两个 $01$ 序列的匹配问题，直接 KMP 就可以解决。

所以只需要对于不同位的 $k$ 相同的数对暴力合并即可。

复杂度看上去是一个高于 $O(n \log^2 A)$ 的复杂度，但是因为合法的数对很少，所以跑得很快。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,m,a[N],b[N],ta[N],tb[N],nxt[N];
vector<int> v[N],tmp[N],p[N];
void solve(int x){
	for(int i=1; i<=n; i++)	a[i+n] = a[i];
	int m = 2 * n - 1;
	nxt[1] = 0;
	for(int i=2,j=0; i<=n; i++){
		while(j && b[i] != b[j+1])	j = nxt[j];
		if(b[i] == b[j+1])	++j;
		nxt[i] = j;
	}
	for(int i=1,j=0; i<=m; i++){
		while(j && a[i] != b[j+1])	j = nxt[j];
		if(a[i] == b[j+1]) ++j;
		if(j == n){
			tmp[i-n].push_back(0);
			j = nxt[j];
		}
	}
	for(int i=1; i<=m; i++)	a[i] ^= x;
	for(int i=1,j=0; i<=m; i++){
		while(j && a[i] != b[j+1])	j = nxt[j];
		if(a[i] == b[j+1]) ++j;
		if(j == n){
			tmp[i-n].push_back(x);
			j = nxt[j];
		}
	}
	if(x == 1){
		for(int i=0; i<=n; i++)	swap(tmp[i],v[i]);
		return;
	}
	for(int i=0; i<=n; i++){
		for(auto t1 : tmp[i]){
			for(auto t2 : v[i]){
				p[i].push_back(t1 + t2);
			}
		}
		swap(v[i],p[i]);
		vector<int> q;q.clear();swap(q,p[i]);
		tmp[i].clear();
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d",&n);
	for(int i=1; i<=n; i++)	scanf("%d",&ta[i]);
	for(int i=1; i<=n; i++)	scanf("%d",&tb[i]);
	for(int i=1; i<(1<<30); i <<= 1){
		for(int j=1; j<=n; j++){
			a[j] = ta[j] & i;
			b[j] = tb[j] & i;
		}
		solve(i);
	}
	for(int i=0; i<=n; i++){
		for(auto p : v[i])	printf("%d %d\n",i,p);
	}
	return 0;
}

AGC017C Snuke and Spells

题目描述：

$N$ 个球排在一起，每个球上有一个数 $a_i$ 。接下来会进行若干轮删除。设现在还有 $k$ 个球，则 $a_i=k$ 的球会被删除。

最终可能球不会被删完，你需要求出最少修改几个球上的数后可以让球全部被删完。

同时还有 $M$ 次修改，每次修改第 $X_i$ 个球的数为 $Y_i$ ，你需要求出每次修改后上述问题的答案。

$1\ \leq\ N\ \leq\ 200000$ ， $1\ \leq\ M\ \leq\ 200000$ ， $1 \le A_i,X_i,Y_i \le N$

题目分析：

比较结论题。

假设 $a_i = k$ 的数有 $cnt_k$ 个，则我们其实可以将这些数看成一条覆盖 $[a_i-cnt_k+1,a_i]$ 的线段，所以下面的操作其实就是将被覆盖到的点移到外面，将没覆盖到的点找一些点移动进去，其实这两个过程是对称的，因为我们必然是将被覆盖到的点移动向没有覆盖的点。

因此我们的操作数本质上就是没有覆盖的点的数量，因为我们每次修改至多会使得 $O(1)$ 条线段长度变化 $1$ ，所以可以暴力维护更新后的答案即可。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int cnt[N],a[N];
map<int,int> s; 
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%d",&a[i]),cnt[a[i]]++;
	for(int i=1; i<=n; i++)	s[i]++,s[i-cnt[i]]--;
	for(int i=n; i>=1; i--)	s[i] += s[i+1];
	int ans = 0;
	for(int i=1; i<=n; i++)	if(!s[i])	++ans;
	while(m--){
		int pos,val;scanf("%d%d",&pos,&val);
		--cnt[a[pos]];
		if(a[pos] - cnt[a[pos]] > 0){
			--s[a[pos] - cnt[a[pos]]];
			if(!s[a[pos]-cnt[a[pos]]])	++ans;
		}
		if(val - cnt[val] > 0){
			if(!s[val - cnt[val]])	--ans;
			++s[val - cnt[val]];
		}
		++cnt[val];
		a[pos] = val;
		printf("%d\n",ans);
	}
	return 0;
}

ABC259G Grid Card Game

题目描述：

芷萱和诺丝正在玩一个有趣的游戏。

有一个 $H \times W$ 的正方形网格， $i$ 行 $j$ 列的点的权值为 $a_{i,j}$ 。

芷萱选择 $H$ 行中的任意几行（可能为 $0$ ），给这些行上的点放上一张红色卡片。
诺丝选择 $W$ 列中的任意几列（可能为 $0$ ），给这些列上的点放上一张蓝色卡片。

他们计算本游戏分数的方式如下：

如果存在一个网格 $(i,j)$ 满足 $a_{i,j}<0$ 且这个点上同时存在两种颜色的卡片，则游戏失败，分数为 $-10^{100}$ 分，否则，分数为所有放了卡片（不管放了几张，不管放了什么颜色）的网格的权值之和。

$1\ \leq\ H,\ W\ \leq\ 100$ ， $-10^9\ \leq\ A_{i,\ j}\ \leq\ 10^9$

题目分析：

做法一：（猜结论）

注意到假设我们当前选择了 $i$ 行选择了 $j$ 列，则我们的最优方案一定是在只考虑行的情况下选择 $i$ 行最优的前提下，选择 $j$ 列最优的。

所以可以直接枚举选多少行，然后每次暴力判断应该选哪些列最优，复杂度 $O(n^3)$ 。

做法二：（正经做法）

这玩意有一种匹配的感觉，所以考虑网络流，其实就是每一个点第一次被匹配的时候贡献 $a_{i,j}$ ，第二次被匹配的时候如果其为正数则贡献 $0$ ，否则贡献为 $-\infty$ 。

这样的话直接网络流建模问题就在于做不到如果选择了一行/一列，则这一行和这一列的所有元素都被选择，所以考虑最小割建模，因为最小割这个东西的限制很简单。

但是最小割的话我们就必须最小化什么东西，显然就是最小化未被选择的权值和，但是因为一个数选择两次权值不一样就很烦人，所以可以考虑先将答案设为元素和的二倍，这样我们不选择一行/一列的代价就是对应的行/列的元素和。

所以建图其实就是 $S$ 向每一行连边，权值为这一行的元素和，每一列向 $T$ 连边，权值为这一列的元素和，行和列之间连边，权值其实就是这一行和这一列同时被选择的代价，也就是如果当前元素大于 $0$ 会被重复计算要删除，代价就是 $a_{i,j}$ ，否则如果小于 $0$ 则不能被选择两次，代价就是 $\infty$ 。

代码：

做法一：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
const int INF = 1e18;
int t[N],a[N][N];
pair<int,int> s[N];
bool flag[N];
bool cmp(pair<int,int> a,pair<int,int> b){
	return a.first > b.first;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%lld",&a[i][j]);
			s[i].first += a[i][j];
		}
		s[i].second = i;
	}
	int ans = 0,res = 0;
	sort(s+1,s+n+1,cmp);
	for(int i=0; i<=n; i++){
		flag[s[i].second] = true;res += s[i].first;
		int tmp = 0;
		for(int j=1; j<=m; j++){
			t[j] = 0;
			for(int k=1; k<=n; k++){
				if(flag[k] && a[k][j] < 0)	t[j] = -INF;
				else if(!flag[k])	t[j] += a[k][j];
			}
		}
		for(int j=1; j<=m; j++)	if(t[j] > 0)	tmp = tmp + t[j];
		ans = max(ans,tmp + res);
	}
	printf("%lld\n",ans);
	return 0;
}

做法二：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 205;
const int INF = 1e18+5;
struct edge{
	int nxt,to,val;
	edge(){}
	edge(int _nxt,int _to,int _val){
		nxt = _nxt,to = _to,val = _val;
	}
}e[5 * N * N];
int cnt = 1,head[N],cur[N],dis[N],S,T;
int a[N][N],s1[N],s2[N];
void add_edge(int from,int to,int val){
	e[++cnt] = edge(head[from],to,val);
	head[from] = cnt;
	e[++cnt] = edge(head[to],from,0);
	head[to] = cnt;
//	printf("%lld %lld %lld\n",from,to,val);
}
bool bfs(){
	memcpy(cur,head,sizeof(head));memset(dis,0x3f,sizeof(dis));
	dis[S] = 1;
	queue<int> q;q.push(S);
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=head[now]; i; i=e[i].nxt){
			int to = e[i].to;
			if(e[i].val && dis[to] > dis[now] + 1){
				dis[to] = dis[now] + 1;
				q.push(to);
			}
		}
	}
	return dis[T] < 100;
}
int dfs(int now,int limit){
	if(now == T)	return limit;
	int flow = 0;
	for(int i=cur[now]; i && flow < limit; i = e[i].nxt){
		cur[now] = i;
		int to = e[i].to;
		if(e[i].val && dis[to] == dis[now] + 1){
			int g = dfs(to,min(e[i].val,limit - flow));
			flow += g;
			e[i].val -= g;e[i^1].val += g;
			if(!g)	dis[to] = INF;
		}
	}
	return flow;
}
int dinic(){
	int ans = 0;
	while(bfs()){
		int flow = dfs(S,INF);
		ans += flow;
	}
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%lld",&a[i][j]);
			s1[i] += a[i][j];
			s2[j] += a[i][j];
		}
	}
	S = n + m + 1,T = n + m + 2;
	int ans = 0;
	for(int i=1; i<=n; i++){
		if(s1[i] > 0)
			ans += s1[i],add_edge(S,i,s1[i]);
	}
	for(int i=1; i<=m; i++){
		if(s2[i] > 0)
			ans += s2[i],add_edge(i+n,T,s2[i]);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(a[i][j] >= 0)	add_edge(i,j+n,a[i][j]);
			else	add_edge(i,j+n,INF);
		}
	}
	ans = ans - dinic();
	printf("%lld\n",ans);
	return 0;
}

ARC117D Miracle Tree

题目描述：

给定一棵 $n$ 个节点的树，要求构造出一个点权序列 $E$ ，满足以下三个条件：

1.所有 $E_i\ge 1(1\le i\le n)$ 。

2.对于任意一组 $(i,j)(1 ≤ i < j ≤ N)$ ，使 $|E_i-E_j|\ge dist(i,j)$ ， $dist$ 即树上两点距离。

3.使 $E$ 中的最大值最小。

$2\ \leq\ N\ \leq\ 200000$

题目分析：

考虑如何构造一组合法解，我们可以从小到大一个个地构造，一个显然的想法就是从某一个点出发，走一遍整棵树，走到某一个点时将走过的路径长度设为这个点的点权，这里认为回溯也会使得路径长度改变。

可以发现这样构造出来的必然是合法的解，因为如果自己手摸一下的话会发现就是点权最大的数会对我们的方案造成极大的不便，而这样就把点权最大的数使得其满足条件了，所以就一定会满足条件了。

所以我们的目标就是最小化总路径长度，因为我们并不要求在最后走回去，所以除了我们钦定最后走的这一条链只被经过一次，其它的边都会被经过两次，因为是一进一出，所以为了让路径长度最小，就是让最后走的这一条的长度最长，那么直接选择直径就好了。

所以最后的解法就是选择直径的一个端点作为我们的起始节点，然后从这个结点开始走一遍整棵树，并且钦定直径上的边最后一个访问也就是不会回溯即可。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,tot,head[N],fa[N],dis[N],id[N];
bool flag[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
void dfs(int now,int fath){
	fa[now] = fath;dis[now] = dis[fath] + 1;
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(to == fath)	continue;
		dfs(to,now);
	}
}
void get_ans(int now,int fath){
	id[now] = tot;
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(flag[to] || to == fath)	continue;
		++tot;
		get_ans(to,now);
		++tot;
	}
	for(int i=head[now]; i; i=e[i].nxt){
		int to = e[i].to;
		if(!flag[to] || to == fath)	continue;
		++tot;
		get_ans(to,now);
		++tot;
	}
}
int main(){
	int n;scanf("%d",&n);
	for(int i=1; i<n; i++){
		int from,to;
		scanf("%d%d",&from,&to);
		add_edge(from,to);add_edge(to,from);
	}
	dfs(1,0);
	int L = 1;
	for(int i=1; i<=n; i++)	if(dis[i] > dis[L]) L = i;
	dfs(L,0);
	int R = 1;
	for(int i=1; i<=n; i++)	if(dis[i] > dis[R])	R = i;
	while(R != L){
		flag[R] = true;
		R = fa[R];
	}
	tot = 1;
	get_ans(L,0);
	for(int i=1; i<=n; i++)	printf("%d ",id[i]);
	return 0;
}

ARC074F Lotus Leaves

题目描述

给定一个 $H×W$ 的网格图，o是可以踩踏的点，.是不可踩踏的点。

现有一人在 S 处，向 T 移动，若此人现在在 $(i,j)$ 上，那么下一步他可以移动到 $(i,k),(k\in[1,W])$ 或 $(k,j),(k\in[1,H])$ 上。

问最少需要将多少个 o 改成 .，可以使这个人无法从 S 到达 T，输出最少需要更改的数目；如果无论如何都不能使这个人无法从 S 到 T，则输出 $-1$ 。

$2 \le H,W \le 100$

题目分析：

不能从 S 走到 T 其实就是把最小割里的边割掉就可以满足条件。

连边就是可以相互到达的点连边即可，以及注意一件事就是我们是割点而非割边，所以要对每一个点拆点，将拆出来的边流量设为 $1$ 其它的设为 $\infty$ 就可以保证我们一定都是割点了。

但是这样边数为 $10^6$ 点数为 $10^4$ ，看上去不能过但是如果对 dinic 有点信仰的的话，交上去发现的确过了。

考虑优化一下复杂度，就是可以相互到达的点必然满足行相同或者列相同，所以可以对于行/列建一个大点，然后从对应的点连向大点，并从大点连向这些点即可。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 6e6+5;
const int INF = 1e9+5;
struct edge{
	int nxt,to,val;
	edge(){}
	edge(int _nxt,int _to,int _val){
		nxt = _nxt,to = _to,val = _val;
	}
}e[2 * N];
int cnt=1,s,t,tot,in[200][200],out[200][200],head[N],dis[N],cur[N];
char mp[200][200];
void add_edge(int from,int to,int val){
	e[++cnt] = edge(head[from],to,val);
	head[from] = cnt;
	e[++cnt] = edge(head[to],from,0);
	head[to] = cnt;
}
bool bfs(){
	memset(dis,0,sizeof(dis));memcpy(cur,head,sizeof(head));
	dis[s] = 1;
	queue<int> q;q.push(s);
	while(!q.empty()){
		int now = q.front();q.pop();
		for(int i=head[now]; i; i=e[i].nxt){
			int to = e[i].to;
			if(e[i].val && !dis[to]){
				dis[to] = dis[now] + 1;
				q.push(to);
			}
		}
	}
	return dis[t] != 0;
}
int dfs(int now,int limit){
	if(now == t)	return limit;
	int flow = 0;
	for(int i=cur[now]; i && flow < limit; i=e[i].nxt){
		cur[now] = i;
		int to = e[i].to;
		if(e[i].val && dis[to] == dis[now] + 1){
			int g = dfs(to,min(e[i].val,limit - flow));
			flow += g;
			e[i].val -= g,e[i^1].val += g;
			if(!g)	dis[to] = INF;
		}
	}
	return flow;
}
int dinic(){
	int ans = 0;
	while(bfs()){
		int flow = dfs(s,INF);
		ans = ans + flow;
	}
	return ans;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)	scanf("%s",mp[i]+1);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			in[i][j] = ++tot;
			out[i][j] = ++tot;
			add_edge(in[i][j],out[i][j],1);
		}
	}
	pair<int,int> S,T;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			for(int k=1; k<=m; k++){
				if(mp[i][j] != '.' && mp[i][k] != '.')
					add_edge(out[i][j],in[i][k],INF);
			}
			for(int k=1; k<=n; k++){
				if(mp[i][j] != '.' && mp[k][j] != '.')
					add_edge(out[i][j],in[k][j],INF);
			}
			if(mp[i][j] == 'S')	S.first = i,S.second = j;
			if(mp[i][j] == 'T')	T.first = i,T.second = j;
		}
	}
	if(S.first == T.first || S.second == T.second){
		printf("-1\n");
		return 0;
	}
	s = out[S.first][S.second],t = in[T.first][T.second];
	printf("%d\n",dinic());
	return 0;
}

杂题选做（2023.10.3-2023.10.7）

http://linyihdfj.github.io/2023/10/07/practice-2023-10-3-2023-10-7/

作者

linyihdfj

发布于

2023-10-07

更新于

2023-10-10

杂题选做（2023.10.3-2023.10.7）

CF442D Adam and Tree

题目描述：

题目分析：

代码：

ABC082D FT Robot

题目描述：

题目分析：

代码：

ARC157E XXYX Binary Tree

题目描述：

题目分析：

代码：

ARC067F Yakiniku Restaurants

题目描述：

题目分析：

代码:

ABC150F Xor Shift

题目描述：

题目分析：

代码：

AGC017C Snuke and Spells

题目描述：

题目分析：

代码：

ABC259G Grid Card Game

题目描述：

题目分析：

代码：

ARC117D Miracle Tree

题目描述：

题目分析：

代码：

ARC074F Lotus Leaves

题目描述

题目分析：

代码：

作者

发布于

更新于

许可协议

目录