夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

ARC杂题选讲P1

2020-11-23 17 min read # 题目集合 # 构造 # 动态规划

必然要有啊~~

从101开始吧

AT4350 [ARC101A] Candles

尺取,不难发现如果我们L,R符号相同,则不需要掉头,否则必然掉头,那么我们选择小的一方*2即可

AT4351 [ARC101B] Median of Medians

害,浪费时间一题

期中考试前做的...

首先如何判断一个数和一段数的中位数大小关系?

把小于等于他的数设为1,其他数设为-1

那么对于偶数区间满足区间和为0,奇数区间满足和为1即可

然后我们外面套一个二分,二分一下全局中位数

然后判断所有区间这个是否成为中位数

AT4162 [ARC099C] Independence

显然的是我们把图分成两个完全子图部分相当于把补图所有连通块黑白染色后选出每个连通块选出一个颜色分给一个集合

因为原来在原图中都有相连的子图在这张图中一定不会相连,所以也就是可以分在一起,反而那些不相连的会有连边,也就是说至少他们俩分入两个集合

如果补图不为二分图,无解

然后我们要最小化两个完全子图的边端点数?

不难发现既然我们能把一个连通块内的颜色分入一个集合,就能用背包把所有可能大小情况都求出来

然后所有的case中算个最小值即可

AT4160 [ARC099A] Minimization

答案甚至是固定的,因为我们一定从最小值处开始进行这个操作,而且不难发现我们最少用⌈n−kk−1⌉\lceil \frac {n-k}{k-1} \rceil个区间覆盖所有位置

所以说我们用这些区间按某种顺序进行就是可行解

AT4161 [ARC099B] Snuke Numbers

答案好像有规律,好像没有

但是你会发现我们尽可能在低位放9好像相当优秀

但是说这个东西好像并不普遍....类似1,2,3,这种也是一个可行的解

然后猜想我们最低位是9之后不会再发生变化,因为说最低位变成0这个对于这个式子来说是一个很劣的事情,至少没有最低位都是9优

所以我们可以从低位向高位加1

然鹅还是不好判断这个小于等于号都成立...

于是你猜测一个凸性,第一个大于前面答案的数就是下一个数

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;

int nw = 1, k, ans;

inline double s(int x) {
	int y = x;
	int z = 0;
	while(y) {
		z += y % 10;
		y /= 10;
	}
	return x / (1.0 * z);
}


signed main() {
	scanf("%lld", &k);
	while(k-- > 0) {
		while(s(ans + nw) > s(ans + nw * 10)) {
			nw *= 10;
		}
		ans += nw;
		nw = 1;
		printf("%lld\n", ans);
	}
	return 0;
}

AT4133 [ARC097D] Monochrome Cat

一开始我想了个树形DP

fi,j,kf_{i,j,k}表示点i的子树,最后是否回到i,以及i颜色为j的情况下最小染黑整颗子树的代价

然后统计完一个根的剩下换根即可

题解则更为巧妙好写

首先我们去掉所有颜色为黑色的叶子节点,这样所有叶子都是白色

然后我们发现dfs一遍(并回到出发点)可以得到所有点翻转度数次的颜色状况

设剩下为黑色的点为未标记点,剩下为白色的点为标记点

显然发现我们标记点还要进行一次操作2

但是我们最后可以不回到根,也就是说我们可以选择一条路径少走一遍

假设这条路径上有k个标记点

会发现,每个标记点少翻转了一次,正好成为了标记点

而之前我们是算两次的,所以这个增量是−2k-2k

那么也就是说我们只要求出最多经过标记点的路径即可

时间复杂度O(n)

P3830 [SHOI2012]随机树

经典好题了

抿一次爽一次

第一问

我们要求这个平均深度的期望??

不难发现首先我们转换成深度的期望再进行递推

发现一次操作一定使得叶子数+1

fif_i表示i个叶子的树平均深度

转移

fi∗i=fi−1∗(i−1)−depi+2∗(depi+1)f_i*i=f_{i-1}*(i-1)-dep_i+2*(dep_i+1)

depidep_i显然等于fi−1∗(i−1)f_{i-1}*(i-1)

fi=fi−1+2if_i=f_{i-1}+\frac 2 i

第二问

显然我们能设计出一个dp状态

fi,jf_{i,j}表示i个点的子树深度为j的期望值

转移??枚举左子树深度,右子树深度,左子树大小?钦点哪个子树卡到上界?

又变成方案数了

不如观察一下更强大的性质

LRRRLLLRRR....LRRRLLLRRR....操作序列写出来,然后k为左子树方案

然后我们有(kn)\binom{k}{n}中组合方案

同时每个位置上的数有1,2,3,4,.....共(k)!中可能性

而右边那些也一样,为(i-k)!种可能性

三个数相乘,正好是(n!)(n!)

也就是说这个和左右子树大小无关

而我们算的是期望,不是方案数,可以发现左子树达到i-1+右子树达到i-1-两边都达到i-1(被算了两次)即可

那么直接

fi,j+=(1i−1)fk,j−1+fi−k,j−1−fk,j−1∗fi−k,j−1f_{i,j}+=(\frac 1 {i-1})f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}*f_{i-k,j-1}

AT4118 [ARC096B] Static Sushi

显然路径只有几种类型

  1. 直接顺时针走到他
  2. 直接逆时针走到他
  3. 顺时针走到他拼上逆时针走的一段(两边)
  4. 逆时针走到他拼上顺时针走的一段(两边)

1,2显然是后面的一个子集

那么就是预处理顺时针走两边的代价的一个数组

然后逆时针走一遍代价的一个数组,都是前缀最大值

然后两边统计并拼起来即可

AT4132 [ARC097C] Sorted and Sorted

这个dp....狠毒啊

主要是难以发现是dp

fi,jf_{i,j}表示放入了前i个白球,前j个黑球的最小代价

然后转移考虑放入第i个白球和第j个黑球的取min

fi,j=minfi−1,j+costwi−1,j,fi,j−1+costbi,j−1f_{i,j}=min{f_{i-1,j}+costw_{i-1,j},f_{i,j-1}+costb_{i,j-1}}

这样我们要预处理后面那个数组....

costw?

发现是挺难的....

因为我们要考虑的是所有都排好之后的代价(不会超过n2n^2),显然这里就不能很劣....比方说直接位置相减

因为你想我们dp相当于dp出原序列一个操作顺序,而我们要的就是按照这个操作顺序一定能得到一组合法的构造解

所以说拆成这一步就是

costwi,j=costwi,.j−1+pbj>pwi+1costw_{i,j}=costw_{i,.j-1}+pb_{j}>pw_{i+1}

costbi,j=costwi−1,j+pbj+1<pwicostb_{i,j}=costw_{i-1,j}+pb_{j+1}<pw_{i}

而这样我们初值costwi,0costw_{i,0}怎么搞啊

发现其实就是排序了....求个前i逆序对即可


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2006;
char s[MAXN];
int n, a[MAXN * 2], pw[MAXN * 2], pb[MAXN * 2], N, c[MAXN * 2];
int cost1[MAXN][MAXN], cost2[MAXN][MAXN];
int f[MAXN][MAXN];
inline void init1() {
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j <= n; ++j) {
			cost1[i][0] += (pw[j] < pw[i + 1]);
		}
	}
	for(int j = 0; j < n; ++j) {
		for(int i = j + 1; i <= n; ++i) {
			cost2[0][j] += (pb[j + 1] > pb[i]);
		}
	}
	return;
}

inline void init() {
	init1();
	for(int i = 0; i < n; ++i) {
		for(int j = 1; j <= n; ++j) {
			cost1[i][j] = cost1[i][j - 1] + (pw[i + 1] < pb[j]);
		}
	}
	for(int j = 0; j < n; ++j) {
		for(int i = 1; i <= n; ++i) {
			cost2[i][j] = cost2[i - 1][j] + (pw[i] > pb[j + 1]);
		}
	}
	return ;
}

inline void solve() {
	memset(f, 0x3f3f3f3f, sizeof(f));
	f[0][0] = 0;
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= n; ++j) {
			if(i)
				f[i][j] = min(f[i - 1][j] + cost1[i - 1][j], f[i][j]);
			if(j)
				f[i][j] = min(f[i][j - 1] + cost2[i][j - 1], f[i][j]);
		}
	}
	printf("%d\n", f[n][n]);
	return ;
}

int main() {
	scanf("%d", &n);
	N = 2 * n;
	for(int i = 1; i <= N; ++i) {
		scanf("%s", s);
		c[i] = s[0] == 'B' ? 0 : 1;
		scanf("%d", &a[i]);
		if(c[i] == 0)pb[a[i]] = i;
		else pw[a[i]] = i;
	}
	init();//预处理cost数组
	solve();//dp
	return 0;
}

AT4119 [ARC096C] Everything on It

最后还是鸽鸽咕了题解

考虑容斥,答案为

∑SF(S)(−1)∣S∣\sum_{S}F(S)(-1)^{|S|}

发现集合元素本质相同,也可以写成

∑i(−1)i(in)g(i)\sum_i(-1)^i\binom{i}{n}g(i)

如何计算g?相当于有i个元素只能算0/1次

那么其他只元素的子集可以自由选择*22n−i2^{2^{n-i}}

同时,我们自己内部的方案数?

发现我们既可以x选1又可以y选0,不是很好做哎...

但是说一个子集只能包括一个元素x

所以说可以认为是把每个元素分入一个集合

但是这样没法处理选0个的情况(也不能枚举,否则会TLE)

所以说我们引入一个叫做"垃圾桶"的概念 : 他包括元素0,和元素0分在一起的就是不选的

于是剩下的集合必须选数,(非空),假设有j个集合,我们

\{i+1j+1\}{i+1}\brace{j+1}

qwq!

但是别忘了其他的元素也有分进来的权利,乘上

(2n−i)j(2^{n-i})^j

于是我们最后的式子

∑i(−1)i22n−i(in)∑j\{i+1j+1\}(2n−i)j\sum_i (-1)^i 2^{2^{n-i}} \binom{i}{n} \sum_{j} {{i+1}\brace{j+1}} (2^{n-i})^j

注意指数上取模要欧拉定理!!


#include<bits/stdc++.h>
#define ll long long
const int MAXN = 3006;
int n;
ll P;
int C[MAXN][MAXN], S[MAXN][MAXN];
int cf2[MAXN];

inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}
inline void sub(int &x, int y) {
	x -= y;
	if(x < 0)x += P;
}

inline ll ksm(ll x, ll y, ll P) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}


inline void init() {
	C[0][0] = 1;
	for(int i = 1; i <= n + 1; ++i) {
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j) {
			add(C[i][j], C[i - 1][j]);
			add(C[i][j], C[i - 1][j - 1]);
		}
	}
	S[0][0] = 1;
	for(int i = 1; i <= n + 1; ++i) {
		for(int j = 1; j <= i; ++j) {
			add(S[i][j], 1ll * S[i - 1][j] * j % P);
			add(S[i][j], S[i - 1][j - 1]);
		}
	}
	cf2[0] = 1;
	for(int i = 1; i <= n + 1; ++i) {
		cf2[i] = 1ll * cf2[i - 1] * 2 % P;
	}
	return ;
}

inline void solve() {
	int ans = ksm(2, ksm(2, n, P - 1), P);
	for(int i = 1; i <= n; ++i) {
		ll tmp = ksm(2, ksm(2, n - i, P - 1), P) * C[n][i] % P;
		int qwq = 0;
		ll qaq = 1;
		for(int j = 0; j <= i; ++j) {
			add(qwq, 1ll * S[i + 1][j + 1] * qaq % P);
			qaq = qaq * cf2[n - i] % P;
		}
		tmp = tmp * qwq % P;
		if(i & 1)sub(ans, tmp);
		else add(ans, tmp);
	}
	printf("%d\n", ans);
	return ;
}

signed main() {
	scanf("%d%d", &n, &P);
	init();
	solve();
	return 0;
}

AT4144 [ARC098D] Donation

qwq?

原本以为是青铜,没想到是王者

这类问题一般可以从二分答案下手,但是这个题二分答案之后转判定意义不大

  1. 我们按顺序要删掉每个点

先不考虑连通性

你会发现先i后j和先j后i可以扰动法找找规律

假设a>ba>b,如果小于令a=ba=b

一开始的钱是x,那么x<=bi+ajx<=b_i+a_j

或者x<=bj+aix<=b_j+a_i

那么我们有

bi+aj<=bj+aib_i+a_j<=b_j+a_i,i靠前更优

即bi−ai<=bj−a−jb_i-a_i<=b_j-a-j

但是显然不够,因为我们还要加强结论以解决连通性

ci=max(ai−bi,0)c_i=max(a_i-b_i,0)(此时也可认为钦点了a>b...?)

然后也就是说每个时刻在某个点i一定要有至少cic_i钱(一开始拿上∑bi\sum b_i)

回溯的来看

有这个前提条件就可以发现我们一定要从小到大回溯这个cic_i,要不然我们的钱数不会单调递增,一定不会更优

也就是从大到小访问这个cic_i

于是想想怎么计算,因为要联通...所以说我们可以考虑删去一个点后,图会成为几个联通块

而我们也一定是按照从大到小顺序访问,所以可以类似于建树的方法来做

就是说我们还是从小到大访问,但是我们发现如果能经过i,那么也一定能经过cic_i小于i的所有点

code:



#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 7;
int n, m;

struct rec {
	ll a, b, c;
	bool operator<(const rec &x) const {
		return c < x.c;
	}
} d[MAXN];

int ccnt, home[MAXN], nxt[MAXN], to[MAXN];

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

int cccnt, fst[MAXN], nnxt[MAXN], tto[MAXN], fa[MAXN], vis[MAXN];
ll sum[MAXN];

inline void ct2(int x, int y) {
	cccnt++;
	nnxt[cccnt] = fst[x];
	fst[x] = cccnt;
	tto[cccnt] = y;
}

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

ll g[MAXN];

inline void solve() {
	for(int i = 1; i <= n; ++i)fa[i] = i;
	for(int q = 1; q <= n; ++q) {
		int u = d[q].a;
		vis[u] = 1;
		sum[u] = d[q].b;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = getf(to[i]);
			if(vis[v] && (v ^ getf(u))) {
				ct2(u, v);
				sum[u] += sum[v];
				fa[v] = u;
			}
		}
		g[u] = sum[u] + d[q].c;
		for(int i = fst[u]; i; i = nnxt[i]) {
			int v = tto[i];
			g[u] = min(g[u], max(g[v], d[q].c) + sum[u] - sum[v]);
		}
	}
	printf("%lld\n", g[d[n].a]);
	return ;
}

int	 main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &d[i].a, &d[i].b);
		if(d[i].a < d[i].b)d[i].a = d[i].b;
		d[i].c = d[i].a - d[i].b;
		d[i].a = i;
	}
	sort(d + 1, d + n + 1);
	for(int i = 1, x, y; i <= m; ++i) {
		scanf("%d%d", &x, &y), ct(x, y), ct(y, x);
	}
	solve();
	return 0;
}
Powered by Gridea RSS