ARC杂题选讲P2

咋做啊

AT4120 [ARC096D] Sweet Alchemy

还是相当毒瘤的一道题

首先要一个经典的转换,就是变成树上问题

然后我们一个点选的次数不能超过他所有祖先d次,同时要小于他所有儿子,等价于我们树上差分之后每个点选择的次数小于等于d

也就是说我们选择一颗子树,代价为 $\sumM_i$ ,权值为 $siz$ ,最多能进行 $d$ 次的最优权值和,但是1没有这个限制

显然这个东西是多重背包,但是不能直接上,因为代价太高,达到 $1e9$ 级别

所以说我们可以考虑 $f_i$ 表示权值为i的最小代价是什么

然后我们还是能最多d次怎么办呢?就是说现在做了转换依然没法转移

我们有一个错误的贪心就是按照性价比排序能选就选

什么时候不错呢?当物品个数都足够多的时候,即可以选择大于n个的时候

此时你会发现无论如何那个性价比更劣的都已经比第一个劣了

比如

$w_j/v_j > w_i/v_i$

当 $n>v_j,v_i$ 时,大于的部分显然满足贪心性质

实现的时候二进制分组,然后我们最后匹配的时候注意每个数最多在额外选择 $d-min(n,d)$ 个

因为我们在之前已经完全背包了min个啊....

AT4111 [ARC095A] Many Medians

这个可以直接做吧?

把数列排序,然后第一个到第 $\frac l 2$ 删掉中位数都是 $\frac l 2+1$

然后之后的删掉都是 $\frac l 2$

qwq

AT4112 [ARC095B] Binomial Coefficients

选出最大的作为第一个数

选出和 $n/2$ 差最小的作为第二个

AT4114 [ARC095D] Permutation Tree

显然树的形态只可能是毛毛虫

因为但凡存在一条侧链,满足u->v,而w->u

那有 $v<u<w$ ,同时v在u之后(因为是侧链)

所以说只能是毛毛虫

判断合法就是找出那条最长的链即可

构造合法解?找到直径的一个端点,然后在直径上走,每个点的权值为前面所有点的点数和

然后直径外的点就是加入点i周围的点,随便赋为点i的权值 $+x$

AT2301 [ARC068D] Solitaire

这种题就不能直接计数啊,首先题目中的删除序列是指删除的数字构成的序列

所以说枚举1在单调队列哪个位置,以及剩下的怎么排列的形态都是不可的,会算重

我们考虑观察并设计dp,因为双端队列这东西保证序列的形态是从一开始向两端递增?..

所以说我们可以发现,删除的形态也是这样的

就是说是分三段

黑色的一段下降,且包括最低点1

黄色的一段下降,且满足最小值大于第三段红色

而且黄色+黑色的长度,红色段的长度为n-k

我们就不妨设 $f_{i,j}$ 表示前i个数,第一个序列(黑色)的最小值为j的方案数

那么前i个数分成的两类,第一个(黑色)的最小值为j,另一个(h)的最小值为minx

我们要有minx大于剩下所有元素的最大值

然后我们要分入一个到A,B序列中

如果下一个数满足 $x<j$ ,那么我们就插入A末尾,仍满足所有条件, $f_{i,j}->f_{i+1,<j}$

而如果大于等于j

加入A,A就不单调递减了

我们只能加入B,而且满足限制二这个值一定是另外的集合中最大的元素

同时,我们要保证这个值大于j,否则我们必然算重....

加入之后仍然满足条件,即向 $f_{i+1,j}$

而这个构造显然我们可以统计出所有黑色和黄色部分答案,剩下红色的长度为n-k-1,方案数为 $2^{n-k-1}$ qaq

从大到小dp即可,转移可以优化,就是下图类型优化

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e3 + 7;
const int P = 1e9 + 7;
int f[MAXN][MAXN];
int n, k;

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

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

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 2; i <= n; ++i)f[1][i] = 1;//分入一个,另你一个为空
	for(int i = 1; i < k - 1; ++i) {
		f[i + 1][n - i + 1] = f[i][n - i + 1];//放入直接转移的
		for(int j = n - i; j >= 2; --j) {
			add(f[i + 1][j], f[i][j]);
			add(f[i + 1][j], f[i + 1][j + 1]);
		}
	}
	int ans = 0;
	for(int i = 2; i <= n - k + 2; ++i) {
		add(ans, f[k - 1][i]);
	}
	if(k == 1)ans = 1;
	ans = 1ll * ans * ksm(2, n - k - 1) % P;
	printf("%d\n", ans);
	return 0;
}

实现的时候要注意我们因为从大到小放入权值,所以第i个位置放入的是n-i+1,而且我们一开始的时候放入n,所以所有方案初值都为1

注意当kn的时候,我们相当于只需要满足之前的限制,红色那段么得了,最后不需要乘上2的次幂,k1的时候我们不需要DP

AT4113 [ARC095C] Symmetric Grid

你会发现行列无关,也就是操作顺序可以先行后列

那我们直接搜搜行的决策,之后列只能直接做匹配

能匹配我们就匹配,丢到一起

然后如果有一个没法匹配就自闭,重新下一个行搜索

看上去我们有 $n!*nm^2$ 巨量计算量

但是那个列匹配能删掉很多计算量

再优化一下做行的过程,就是说我们直接找每一行和那个匹配,就确定了行行的位置

可以优化掉一个没有的 $n!$ ,剩下的状态数/计算量就很合法了!

AT4106 [ARC094B] Worst Case

用手画画几个pair就能找到一点点规律

我们选择的人的组合一定是如下样子:

$(1,AB),(AB,1)$

$(2,AB/2),(AB/2,2)$

$(3,AB/3),(AB/3,3)$

....

其中所有除法都是下取整,总共AB开根号对pair

也就是说,我们一个粗略的答案上界是 $2*\sqrt {AB}$

然鹅,首先你会发现其中一定有一个是原来的人(A,B),答案-1

然后如果说这个AB是完全平方数的话,我们还会多算两遍,答案-2

同时如果说虽然不是完全平方数,但是开根后得到的数字x和 $\lfloor \frac AB x \rfloor$ 是一个数的话,我们直接乘2也会算重

eg:50 -> 7*7<50

满足上述三点后精细实现一下即可

时间复杂度 $O(T)$

code:


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

signed  main() {
	scanf("%lld", &t);
	while(t-- > 0) {
		scanf("%lld%lld", &A, &B);
		int u = sqrt(1ll * A * B);
		int v = A * B / u;
		if(u * v == A * B && v > u)--v;
		if(A > B)swap(A, B);
		int ans = 0;
		if(u == A && v == B)
			ans--;
		else if(u * v == A * B)
			ans -= 2;
		else if(v == u)
			ans--;
		ans += u * 2 - 1;
		printf("%lld\n", ans);
	}
	return 0;
}

AT4107 [ARC094C] Tozan and Gezan

不难发现,如果A数组有位置i的值小于B数组位置j的值,那那个位置最后一定会被Tozan减成0

因为至少当大于0的时候,二者的差在一轮中可以不发生变化,T能进行一次,G在相同位置进行一次

答案至少加上所有 $A<B$ 位置的值和

然后再来看看 $A>B$ 的位置

你会发现无论如何T都最后都能把他们消到只剩一个非0

因为只需要保留那个A>B且大于0位置的数,然后其他位置的数排着消除即可,一定不会中途突然 $A=B$ ,至少有一个位置不同

那之后,我们只需要判断留下哪个位置最优

发现其实就是对应位置A,B差最大的那个

因为G一定可以类似于截击T在操作最后非0位置时---操作其他位置而使其他位置都相同,非0位置不变

又因为两数组和相同,所以我们G也一定能做到

夏晓光(loveJY)的博客

省选模拟赛 7