2023-10-17发表2023-10-18更新题解25 分钟读完 (大约3729个字)

杂题选做（2023.10.14-2023.10.16）

杂七杂八的题目。

Atcoder AGC037D Sorting a Grid

题目描述：

给定一个 $n\times m$ 的矩阵 $A$ , 保证 $A$ 内的元素为 $1$ 到 $n\times m$ 的排列.

将 $A$ 每一行的元素任意排列得到 $B$ .

将 $B$ 每一列的元素任意排列得到 $C$ .

将 $C$ 每一行的元素任意排列得到 $D$ .

要求 $D_{i,j}=(i-1)\times m+j$ , 请输出一组合法的 $B, C$ .

$1\leq n,m\leq 100$

题目分析：

感觉上就是一定有解的，所以可以考虑推一推 $B,C$ 都分别有什么限制。

首先因为将 $C$ 的每一行任意排列可以得到 $D$ 也就是说 $C$ 的第 $i$ 行必然完全包含 $[(i-1)m+1,im]$ ，这样才能重排出来。

考虑将 $B$ 的每一列重排可以得到 $C$ 其实就是不存在 $C$ 某一行的元素有超过 $1$ 个在 $B$ 的某一列上，否则就一定可以重排出来。

更形象地说就是，设元素 $i$ 的颜色为 $\lceil \frac{i}{m}\rceil$ ，其实也就是其在 $C$ 中的行数，则对于 $B$ 的每一列，其均不存在颜色相同的点。

如果想一次确定 $B$ 的所有列看上去很难，但是我们可以一列列地确定，因为 $B$ 的每一列都相当于一个行与颜色的完美匹配，而我们是将 $A$ 每一行重排得到 $B$ 的，所以可以对于 $A$ 的每一行向其包含的颜色连边，这样每次求一个完美匹配就当作 $B$ 的一列就行了。

一定有完美匹配的证明就是当我们剩余 $k$ 列的时候，无论是行还是颜色对应的点的度数均为 $k$ ，根据 hall 定理一定有解。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 205+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[N * N];
vector<int> v[105][105];
int n,m,A[105][105],B[105][105],C[105][105],p[105],col[105][105];
int cnt = 1,S,T,head[N],cur[N],dis[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;
}
bool bfs(){
	memcpy(cur,head,sizeof(head));
	memset(dis,0x3f,sizeof(dis));
	queue<int> q;
	dis[S] = 0;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(dis[to] > dis[now] + 1 && e[i].val){
				dis[to] = dis[now] + 1;
				q.push(to);
			}
		}
	}
	return dis[T] <= 10000000;
}
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));
			e[i].val -= g,e[i^1].val += g;
			flow += g;
			if(!g)	dis[to] = INF;
		}
	}
	return flow;
}
void dinic(){
	while(bfs()){
		dfs(S,INF);
	}
}
void get(int id){
	for(int i=head[S]; i; i=e[i].nxt){
		e[i].val = 1,e[i^1].val = 0;
	}
	for(int i=head[T]; i; i=e[i].nxt){
		e[i].val = 0,e[i^1].val = 1;
	}
	dinic();
	for(int i=n+1; i<=n+n; i++){
		for(int j=head[i]; j; j=e[j].nxt){
			int to = e[j].to;
			if(e[j].val && to != T){
				e[j].val = 0;
				B[to][id] = v[to][i-n].back();
				v[to][i-n].pop_back();
			}
		}
	}
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&A[i][j]);
			col[i][j] = (A[i][j] + m - 1) / m;
			v[i][col[i][j]].push_back(A[i][j]);
		}
	}
	S = n * 2 + 1,T = S + 1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			add_edge(i,col[i][j] + n,1);
		}
	}
	for(int i=1; i<=n; i++){
		add_edge(S,i,1);
		add_edge(i+n,T,1);
	}
	for(int i=1; i<=m; i++)	
		get(i);
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			printf("%d ",B[i][j]);
		}
		printf("\n");
	}
	
	for(int i=1; i<=m; i++){
		int sz = 0;
		for(int j=1; j<=n; j++)	p[++sz] = B[j][i];
		sort(p+1,p+sz+1);
		for(int j=1; j<=n; j++)	C[j][i] = p[j];
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			printf("%d ",C[i][j]);
		}
		printf("\n");
	}
	return 0;
}

CF811E Vladik and Entertaining Flags

题目描述：

在一个 $n \times m$ 的网格上每个格子都有颜色， $q$ 次询问，每次询问只保留 $l$ 至 $r$ 列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。

$1 \le n \le 10$ ， $1 \le m,q \le 10^5$

题目分析：

既然每次询问一个区间，考虑使用线段树硬维护这个东西。

所以我们现在的询问就是如何合并区间 $[l_1,r_1]$ 和区间 $[l_2,r_2]$ 。

首先我们要知道的信息就是这个区间内有多少个连通块，然后还要支持合并就是意味着我们要知道左右端点的这两列的联通情况。

合并其实就是暴力枚举一下就好了。

代码：

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node{
	int cnt;
	int l[11],col_l[11];
	int r[11],col_r[11];
}T[4*N];
int n,m,a[11][N],fa[11 * N];
bool vis[11*N];
int num(int i,int j){
	return (i-1)*m+j;
}
int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}
node merge(node a,node b){
	node c;
	c.cnt = a.cnt + b.cnt;
	for(int i=1; i<=n; i++){
		fa[a.r[i]] = a.r[i];fa[a.l[i]] = a.l[i];
		fa[b.l[i]] = b.l[i];fa[b.r[i]] = b.r[i];
	}
	for(int i=1; i<=n; i++){
		if(a.col_r[i] == b.col_l[i]){
			a.r[i] = find(a.r[i]);
			b.l[i] = find(b.l[i]);
			if(a.r[i] != b.l[i])	--c.cnt;
			fa[a.r[i]] = b.l[i];
		}
	}
	for(int i=1; i<=n; i++){
		c.l[i] = find(a.l[i]);c.col_l[i] = a.col_l[i];
		c.r[i] = find(b.r[i]);c.col_r[i] = b.col_r[i];
	}
	return c;
}
node get(int pos){
	node c;
	c.cnt = 0;
	for(int i=1; i<=n; i++)	fa[num(i,pos)]=num(i,pos),vis[num(i,pos)] = false;
	for(int i=2; i<=n; i++){
		if(a[i][pos] == a[i-1][pos])
			fa[find(num(i,pos))] = find(num(i-1,pos));
	}
	for(int i=1; i<=n; i++){
		if(!vis[find(num(i,pos))]){
			c.cnt++;
			vis[find(num(i,pos))] = true;
		}
		c.l[i] = c.r[i] = find(num(i,pos));
		c.col_l[i] = c.col_r[i] = a[i][pos];
	}
	return c;
}
void build(int now,int now_l,int now_r){
	if(now_l == now_r){
		T[now] = get(now_l);
		return;
	}
	int mid = (now_l + now_r) >> 1;
	build(now<<1,now_l,mid);build(now<<1|1,mid+1,now_r);
	T[now] = merge(T[now<<1],T[now<<1|1]);
}
node query(int now,int now_l,int now_r,int l,int r){
	if(l <= now_l && now_r <= r)	return T[now];
	int mid = (now_l + now_r) >> 1;
	if(r <= mid)	return query(now<<1,now_l,mid,l,r);
	if(l > mid)		return query(now<<1|1,mid+1,now_r,l,r);
	return merge(query(now<<1,now_l,mid,l,r),query(now<<1|1,mid+1,now_r,l,r));
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&a[i][j]);
		}
	}
	build(1,1,m);
	while(q--){
		int l,r;scanf("%d%d",&l,&r);
		printf("%d\n",query(1,1,m,l,r).cnt);
	}
	return 0;
}

CF875F Royal Questions

题面描述

皇家难题

在一个中世纪时期的的王国，经济危机正在肆虐。牛奶产量下降，经济指标每天都在恶化，财政部的钱在消失。为了补救这种情况，国王 Charles Sunnyface 决定让他的 $n$ 个儿子（也就是王子）以尽可能大的嫁妆娶新娘。

为了寻找候选人，国王去了邻近的王国，过了一会儿，几个代表团和 $m$ 个未婚公主来到了。接到客人后，Charles 得知第 $i$ 个公主的嫁妆是 $w_i$ 个金币。

虽然这件事发生在中世纪，但进步的思想已在社会上普遍存在。所以任何人都不能强迫公主嫁给一个她不喜欢的王子。因此，每个公主都可以选择两个王子，并且都准备好成为一个妻子。王子们就惨一点，他们在选择新娘时只能听从父亲的意愿。

国王 Charles 知道每一位公主的嫁妆价值和喜好，就想以一种使他的所有儿子从新娘获得的嫁妆越多的方式举行婚礼。所有王子或公主不一定都被娶（嫁）。每个王子只能娶一个公主，反之亦然，每个公主只能嫁给一个王子。

现在你要帮助国王编写一个程序，求出组织他儿子的婚姻的最赚钱方式。

$2 \le n \le 2\cdot 10^5$ ， $1 \le m \le 2\cdot 10^5$

题目分析：

一个显然的贪心策略就是每次找一个嫁妆最多的公主娶，这样贪心就是很对的。

因为我们放弃一个公主最多能空出来一个王子，也就是说我们放弃一个嫁妆多的公主最多能换来一个嫁妆少的公主，这肯定是不优的。

但是关键是我们让这个公主匹配哪个王子，其实匹配哪个可能都有问题因为我们不知道以后哪个王子会有更多的机会，所以这个时候我们就可以直接把两个王子合并成一个，意味着这两个王子以后只能再选择一个匹配，这样就可以了。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
struct edge{
	int a,b,w;
}p[N];
int fa[N];
bool vis[N];
bool cmp(edge a,edge b){
	return a.w > b.w;
}
int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}
signed main(){
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=m; i++)	scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].w);
	for(int i=1; i<=n; i++)	fa[i] = i;
	sort(p+1,p+m+1,cmp);
	int ans = 0;
	for(int i=1; i<=m; i++){
		int u = p[i].a,v = p[i].b;
		u = find(u);v = find(v);
		if(u == v){
			if(!vis[u]){
				vis[u] = true;
				ans += p[i].w;
			}
		}
		else{
			if(vis[u] && vis[v])	continue;
			int tmp = vis[u] || vis[v];
			fa[u] = v;ans += p[i].w;
			vis[v] = tmp;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Atcoder ABC235G Gardens

题目描述：

有三种不同颜色的球，分别有 $A,B,C$ 个。（相同颜色的球之间不区分）

将球放入 $N$ 个不同的盒子中，要求：

每个盒子至少放了一个球
每个盒子不能存在两个相同颜色的球
可以不放完所有的球

求放置方案数对 $998244353$ 取模的结果。

$1\ \leq\ N\ \leq\ 5\ \times\ 10^6$ ， $0\ \leq\ A,B,C\ \leq\ N$

题目分析：

就是第一个条件看上去很难做，直接推应该不大能做，所以考虑容斥。

类似补集关系容斥在这里看上去就不大能做，所以想办法反演能不能反演出来比较好的形式。

不妨先考虑二项式反演，设 $f(i)$ 表示仅有 $i$ 个盒子的原问题的答案，则我们就是要求这样的一个东西：

g(i) = \sum_{j=1}^i \binom{i}{j} f(j)

这个东西的实际意义其实就是：现在有 $i$ 个盒子，其中有小于等于 $i$ 个盒子满足条件的方案数，其实就是 $i$ 个盒子均无第一个限制的方案数。

这个东西就是很好做的：

g(i) = \sum_{a=0}^A \binom{i}{a}\sum_{b=0}^B \binom{i}{b}\sum_{c=0}^C \binom{i}{c}

如果对于每一个 $i$ 都暴力跑一遍复杂度就是 $O(n^2)$ ，优化就是考虑，由 $g(i)$ 到 $g(i+1)$ 这个式子怎么变的，因为有：

\binom{n}{m} = \binom{n-1}{m} + \binom{n-1}{m-1}

所以其实从 $g(i)$ 到 $g(i+1)$ 对于某个求和值的变化就是乘 $2$ 并且减去 $\binom{i}{A/B/C}$ 。

以及注意上面这个递推式可以认为 $\binom{0}{0} = 1$ 是其边界条件，所以初值令 $g(0) = 1$ 即可。

所以最后的答案就是直接套反演：

f(n) = \sum_{i=0}^n (-1)^{n-i}\binom{n}{i}g(i)

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6+5;
const int MOD = 998244353;
int g[N],fac[N],inv[N];
void add(int &a,int b){
	a = (a + b) % MOD;
}
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int binom(int n,int m){
	if(n < m || n < 0 || m < 0)	return 0;
	return fac[n] * inv[m] % MOD * inv[n-m]%MOD;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,a,b,c;scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = fac[i-1] * i % MOD;
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = inv[i+1] * (i+1) % MOD; 
	int A = 1,B = 1,C = 1;
	g[0] = 1;
	for(int i=1; i<=n; i++){
		A = (A * 2 - binom(i-1,a))%MOD;
		B = (B * 2 - binom(i-1,b))%MOD;
		C = (C * 2 - binom(i-1,c))%MOD;
		g[i] = A * B % MOD * C % MOD;
	}
	int ans = 0;
	for(int i=0; i<=n; i++)	add(ans,((n-i) % 2 == 1 ? -1 : 1) * binom(n,i)%MOD * g[i]%MOD);
	ans = (ans % MOD + MOD)%MOD;
	printf("%lld\n",ans);
	return 0;
}

CF348C Subset Sums

题目描述：

给定一个 $n$ 个数的序列 $a$ ， $m$ 个下标集合，记 $S_{k}=\{S_{k,i}\}$ 。

有 $q$ 次操作，分为如下两种操作：

? k 求集合 $S_k$ 所有元素做原数组下标的和
+ k w 给集合 $S_k$ 的所有下标代表的数加 $w$ 。

$1 \le n,m,q,\sum_i|S_i| \le 10^5$

题目分析：

显然线段树什么的数据结构都做不了这个问题，再加上这个数据范围所以考虑根号分治。

设置一个阈值 $B$ ，我们将集合大小大于等于 $B$ 的称为大集合，小于 $B$ 的称为小集合，然后可以分类讨论一下集合之间的贡献怎么做。

对大集合做加法，求小集合的和，可以考虑在大集合的位置打标记，然后对于每一个小集合遍历所有的大集合，根据交集大小判断影响。
对大集合做加法，求大集合的和，也可以同上求大集合的和的时候遍历每一个大集合求影响即可。
对小集合做加法，求小集合的和，对于加法操作直接将对应下标位置的数暴力加，求和的时候暴力访问一遍求和。
对小集合做加法，求大集合的和，可以在做加法的时候暴力访问一遍所有大集合，根据交集大小求影响。

可以直接预处理交集，因为我们只需要知道大集合与其他集合的交集，取 $B = \sqrt{n}$ 所以直接暴力做复杂度就是 $O(n\sqrt{n})$ 。

上述过程总时间复杂度就是 $O(n \sqrt{n})$ 。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int f[305][N],tag[N],val[N],sum[N],a[N],pos[N];
bool vis[N];
vector<int> v[N],small,big;
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m,q;scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	int S = 500;
	for(int i=1; i<=m; i++){
		int k;scanf("%lld",&k);
		for(int j=1; j<=k; j++){
			int p;scanf("%lld",&p);
			v[i].push_back(p);sum[i] += a[p];
		}
		if(k < S)	small.push_back(i);
		else	big.push_back(i);
	}
	for(int i=0; i<big.size(); i++)	pos[big[i]] = i;
	for(int i : big){
		for(int j : v[i])	vis[j] = true;
		for(int j=1; j<=m; j++){
			for(int k : v[j])	f[pos[i]][j] += vis[k];
		}
		for(int j : v[i])	vis[j] = false;
	}
	while(q--){
		char opt[2];scanf("%s",opt+1);
		if(opt[1] == '?'){
			int k;scanf("%lld",&k);
			int tmp = sum[k];
			for(auto i : big)	tmp += f[pos[i]][k] * tag[i];
			if(v[k].size() < S){
				for(auto i : v[k])	tmp += val[i];
			}
			printf("%lld\n",tmp);
		}
		else if(opt[1] == '+'){
			int k,s;scanf("%lld%lld",&k,&s);
			if(v[k].size() >= S){
				tag[k] += s;
			}
			else{
				for(auto i : v[k])	val[i] += s;
				for(auto i : big)	sum[i] += f[pos[i]][k] * s;
			}
		}
	}
	return 0;
}

杂题选做（2023.10.14-2023.10.16）

http://linyihdfj.github.io/2023/10/17/practice-2023-10-14-2023-10-16/

作者

linyihdfj

发布于

2023-10-17

更新于

2023-10-18

杂题选做（2023.10.14-2023.10.16）

Atcoder AGC037D Sorting a Grid

题目描述：

题目分析：

代码：

CF811E Vladik and Entertaining Flags

题目描述：

题目分析：

代码：

CF875F Royal Questions

题面描述

题目分析：

代码：

Atcoder ABC235G Gardens

题目描述：

题目分析：

代码：

CF348C Subset Sums

题目描述：

题目分析：

代码：

作者

发布于

更新于

许可协议

目录