夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

ARC杂题选讲P3

2020-12-02 19 min read # 题目集合 # 计数题 # 构造 # 动态规划

最后的狂欢

AT3978 [ARC093A] Traveling Plan

不去一个点...其实不会影响太多吧?

直接走即可吧...

AT3979 [ARC093B] Grid Components

给出一种构造方案

黑7白8


$#$##
#$#$#
$#$##
#$#$#

黑6白7


$#$#$#$
#$#$#$#
#$#$###
#$#$###

黑9白7


#$#$#$#$#$#$#$#$###########
##########################
$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$#$#$#$#$#$#$

就是中间分割卡,然后两边直接暴力拼凑!

AT3981 [ARC093D] Dark Horse

毒瘤啊

DP....

看上去和剪刀石头布那个题很相近,但是我还是假啊

显然我们只需要求出p1=1p_1=1的方案数再乘上2n2^n

做法是容斥,因为这个限制相当于Gi={sth∣∣Gi∣=2i−1,minGi!=Ax}G_i=\{sth||G_i|={2^i-1},minG_i!=A_x\}

每个集合的最小值??太难了,不如求每个集合的最小值都是A里面的容容斥

那么就是说我们要直接DP,fi,Sf_{i,S}表示从大到小考虑了前i个能打败的人,这N个集合有S已经选满了的方案数

然后转移相当于枚举一下下个人,然后看看他干满哪个集合

注意这里这个集合是放满,也就是说我们要用大于当前人i的所有人中2k−12^k-1个,所以要乘一个组合数

然后最后里面的人还可以随便选择,乘上一个fac[1<<k]fac[1<<k]表示我们选入的那些人内部还可以随便排列

同样的,最后计数的时候外面的人可以随便选择,乘上一个fac[1<<n−S−1]fac[1<<n-S-1]即可,为啥是-S呢?因为你就算统计每个二进制位得到的也是-S.....qwq?

做完啦!!

注意我们千万不能减多了...我一开始把1剪掉了...还以为标号是从0~n-1....

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 1e9 + 7;
const int MAXN = 17;
const int MAXS = (1 << 17);
int n, m, a[MAXN];
int f[MAXS], g[MAXS];//滚动数组/se
int fac[MAXS], ifac[MAXS];
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 ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

inline ll C(int x, int y) {
	if(y > x)return 0;
	return 1ll * fac[x] * ifac[y] % P * ifac[x - y] % P;
}

inline void init() {
	fac[0] = ifac[0] = 1;
	int N = (1 << n);
	for(int i = 1; i <= N; ++i)fac[i] = 1ll * fac[i - 1] * i % P;
	ifac[N] = ksm(fac[N], P - 2);
	for(int i = N - 1; i >= 1; --i)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
	return;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i)scanf("%d", &a[i]);
	sort(a + 1, a + m + 1);
	reverse(a + 1, a + m + 1);
	init();
	int mS = (1 << n) - 1;
	f[0] = 1;
	for(int i = 1; i <= m; ++i) {
		for(int S = 0; S <= mS; ++S) {
			add(g[S], f[S]);//放弃这个人?
			for(int k = 0; k < n; ++k) {
				if(S >> k & 1)continue;
				add(g[S ^ (1 << k)], 1ll * f[S] * fac[1 << k] % P * C(mS - S - a[i] + 1, (1 << k) - 1) % P);
			}
		}
		for(int S = 0; S <= mS; ++S) {
			// printf("%d %d %d %d?\n", i, a[i], S, g[S]);
			f[S] = g[S];
			g[S] = 0;
		}
	}
	int ans = 0;
	for(int S = 0; S <= mS; ++S) {
		int cnt = 0;
		for(int i = 0; i < n; ++i)if(S >> i & 1)++cnt;
		if(cnt & 1)sub(ans, 1ll * f[S] * fac[mS - S] % P);
		else add(ans, 1ll * f[S] * fac[mS - S] % P);
	}
	printf("%lld\n", 1ll * ans * (1 << n) % P);
	return 0;
}

AT3980 [ARC093C] Bichrome Spanning Tree

怎么计算?先找一个性质,就是图中的最小生成树

如果她是大于x的,显然此时再怎么染都是0

如果小于x

那T的颜色一定要染成一种颜色,否则T就成最小生成树了...

然后枚举一条边i,强制选上i后的最小生成树是tansitans_i

如果tansi<xtans_i<x,则我们这个东西也要和之前的T同色,因为这个方案可以有之前的T删去一条边加上一条边构造而来

tansi>xtans_i>x那么这个边可以成为异色的,因为不管怎么染都不影响最小异色生成树

tansi==xtans_i==x,这个生成树可以成为最小异色生成树......

依次枚举这些边然后强制选择某种颜色的边数为cntcnt,cntcnt是tansi=xtans_i=x个数

首先强制枚举到边j为黑色,没有被强制染色的边随便染色,贡献为2m−cnt−1−c2^{m-cnt-1-c},然后cnt++,j变成白色

枚举下一条边

会发现这样最终方案数为2∗(2cnt−1)∗2m−n−c2*(2^{cnt}-1)*2^{m-n-c},c为tansitans_itansitans_i等于x的边数

(其实就是相当于按某种顺序计算所有的贡献!)

推导要等比数列求和:

首先T是黑白有2种

2m−n+1−1−c∗22^{m-n+1-1-c}*2=2m−n−c∗22^{m-n-c}*2

2m−n−x∗22^{m-n-x}*2

2m−n+1−x∗22^{m-n+1-x}*2

2m−n+2−x∗22^{m-n+2-x}*2

公比为2,首相为2m−n−x∗22^{m-n-x}*2

1−2cnt1−22m−n−x∗2\frac {1-2^{cnt}} {1-2} 2^{m-n-x}*2

显然cnt+x最后是c..qwq

若ans=xans=x

那么我们先计算T为最小异色生成树的答案,(随便选,减去全一个颜色的)(2n−1−2)∗2m−n+1(2^{n-1}-2)*2^{m-n+1}

强制T同色

计算上面的贡献转换为ans<xans<x

接着套用上面的做法,但是注意到这个c要减去n−1n-1哦...

AT3943 [ARC092B] Two Sequences

这个OJ不行啊这都没有题解?

P3760 [TJOI2017]异或和

这个题还是减法都能两只log/cy

就是枚举算这一位k的答案

变成sumi−sumjsum_i-sum_j,看看有多少j满足

然后分类讨论,如果小于j的位数构成的数sumi<sumjsum_i<sum_j的时候因为进位所以k一定是1

那么对应的就是i这一位和j这一位都是0或者都是1

否则的话,sumi>sumjsum_i>sum_j这一位都是0/1或者1/0

显然可以树状数组实现数点

对于这道题也是一样的,二进制运算加法也满足这个奇妙性质

两个数小于i的所有位和如果大于1<<i1<<i,那么加和也一定这一位为1qwq,否则一定为0

剩下的就是个分类讨论,懒得我就不写了

AT3944 [ARC092C] Both Sides Merger

一开始我看到第三个样例傻掉了,让后才发现这个题是替换不是求和....

注意到如果我们两个数中间夹了奇数个数就一定能合二为一

eg:12213可以凑出4,操作方法是选择中间的那个2一直用

而这个性质其实告诉了我们可以dp(输出方案(雾))

但是我们又有可能存在一些毒瘤的端点删除操作

发现他还是不能改变奇偶性(转移这一回事,只能改变我们dp到最后统计答案时的操作

所以本题做完了

dp的时候要小心这个负数qaq.....

但是这个输出方案输出头的时候一定要只点1不能点其他的.....



#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e3 + 7;
int a[MAXN], n, pre[MAXN], que[MAXN], tot;
ll  f[MAXN], ans, id;

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	memset(f, -0x3f, sizeof(f));
	f[0] = 0;
	for(int i = 1; i <= n; ++i) {
		f[i] = a[i];
		for(int j = 0; j < i; ++j) {
			if((i - j + 1) & 1) {
				if(f[j] + a[i] > f[i]) {
					f[i] = f[j] + a[i];
					pre[i] = j;
				}
			}
		}
	}
	ans = -1e9;
	for(int i = n; i >= 1; --i) {
		if(f[i] > ans) {
			ans = f[i];
			id = i;
		}
	}
	printf("%lld\n", ans);
	for(int i = n; i >= id + 1; --i)que[++tot] = i;
	for(int i = id; i; i = pre[i]) {
		int u = pre[i];
		if(pre[i] == 0) {
			for(int j = 1; j < i; ++j)que[++tot] = 1;
			break;
		}
		int x = i;
		while(x - u) {
			que[++tot] = (x + u) / 2;
			x -= 2;
		}
	}
	printf("%d\n", tot);
	for(int i = 1; i <= tot; ++i)printf("%d\n", que[i]);
	return 0;
}

AT3937 [ARC091B] Remainder Reminder

对于这道题来说分类讨论是唯一的出路?

amodb>=Ka mod b >= K

  1. a<ba<b

那么a>k才行

这个方案数相当于在之后某段区间尺取,两端点不能相同

应该是(n−K)∗(n−K−1)2\frac {(n-K)*(n-K-1)} 2

紧接着我们再看

  1. a>ba>b

那么b>k才行

并且对于一个给定的b,我们有一些A才能对应

eg:K=5,b=6,a=5,11,17

K=3,b=6,a=4,5,10,11,16,17都是可以的

也就是从一段开始向后跳一些步数,直到超过N为止...

枚举那个b,然后O(1)计数a吧?


//Dawn Light
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, k;
int main() {
	scanf("%d%d", &n, &k);
	ll ans = 1ll * (n - k) * (n - k + 1) / 2; //eg : n=5,K=4,a=4,b=5
	if(k != 0)
		for(int i = k + 1; i <= n; ++i) {
			ll tmp = n / i - 1;
			if(tmp < 0)break;
			if(n % i >= k)ans = ans + tmp * (i - k) + (n % i - k + 1);
			else ans = ans + tmp * (i - k);
		} else ans = 1ll * n * n;
	printf("%lld\n", ans);
	return 0;
}

AT3945 [ARC092D] Two Faced Edges

嗯嗯额!

首先我尝试加权,然后得到了一个神奇的数组g,g[i][j]g[i][j]表示从i到j的所有必须边异或和

然后发现我萎住了

我们再深入思考一下翻转这条边(u,v)(u,v)对于图的影响

  1. 存在一条v−>uv->u的路径
  2. 存在一条u−>vu->v但是没有经过这个边的路径

发现如果二者有且仅有一个成立则成功了

因为说分类讨论

二者都不满足,那么一定u,v翻前翻后都是两个联通分量的

二者都满足,那么u,v一定满足翻前翻后都是一个连通分量的

满足1不满足2,之前我们u,v是一个连通分量的(v->u,而u->v),但是之后就不行了,u走不到v

满足2不满足1,之前我们u,v不是一个连通分量的,但是之后就行了,v走的到u

怎么维护条件2?

发现我们本质上就是判断(u,v)这条边是不是u−>vu->v必经边

也就是说我们要判断删掉这条边后能否到达v

显然不太行QAQ

但是说我们对于每个点遍历一遍图的复杂度还是能承受的

所以说如果我们翻转u的所有出边顺序

然后再dfs一遍!

然后判断u的所有出点v到达的时候这个点的编号是否发生变化即可

如果是必经边,那么我们到达这个v的时候一定不会发生变化(不存在第二条不走这条边的路径)

时间复杂度不变吧,用bitset优化一下下

AT3936 [ARC091A] Flip,Flip, and Flip......

  1. 四个顶点会被翻转偶数次
  2. 四个边界会被翻转偶数次
  3. 中间全是奇数次

所以除掉这些点即可

答案为nm-2n-2*m+4

小心当n=1或者m=1的情况

AT3881 [ARC090A] Candies

胡闹,我会做n*m<=1e7的版本

AT3882 [ARC090B] People on a Line

不难发现我们一个人可能和一群人产生一些关系,然后形成一个相对顺序固定的块!

于是再仔细观察数据范围,这个x是01e9,而这个d只有01e4??哦,这个n是0~1e5

也就是说,只要我们不出现冲突的情况,随便摆一定摆的开.....

什么是冲突呢?就是说关系形成了一个环,但是推导之后却能推出一个点在另一个点的两侧

这个直接dfs一下即可....就是建双向边,边权互为相反数这样子

然后我们钦定一个0,得到一组连通块解,然后得到里面可能的最大值,设置成1e9即可

因为极限情况下也一定摆的开(每个点都是前面的点的+1e4距离)所以下一个连通块最大值直接选取上一个连通块最小值即可!

(麻蛋这个还允许多个人在一个点.....)

AT3884 [ARC090D] Number of Digits

好像直接根据那个S不大做不太行,我们观察一点函数的性质

9个1

90个2

900个3

9000个4

90000个5.....

哎?S多大?1e8?

所以说我们实际上可以枚举那个函数本质不同的取值,然后每个计数一下

单独用1->用1,2->单独用2->用2,3->单独用3->用3,4->单独用4

然后我们会发现,对于case1,如果我们使用的数小于k个而且能整除,则有k-sth+1个合法

对于case2,i和i+1一定互质,则要么有一种,要么有0种(不定方程解就一个)

怎么判断呢?其实只要看0种的情况,就是是不是一边都是就好...这尼玛怎么判断啊?

发现对于i,i+1,我们尽量用i+1后,有一个mod i+1意义下的值,而我们通过替换i+1为i可以使其减小,这个值显然小于一开始的i.....

另外当S小于a∗b−a−ba*b-a-b范围的时候,我们要看有无解还挺毒瘤....

发现到我们实际上是x∗a+(x+1)∗b=kx*a+(x+1)*b=k

(a+b)x=k−b(a+b)x=k-b

k−bx=(a+b)\frac {k-b} x=(a+b)

这个正整数a,b解的数量应该是⌊k−1x⌋\lfloor \frac{k-1}{x} \rfloor-⌊kx+1⌋\lfloor \frac {k} {x+1} \rfloor

我直接傻掉?首先这个上界相当于说我们a超级大,即b=1的时候,此时直接移项即可

下界相当于我们b超级大,即当a=1的时候,这个我还真没推出来....

首先假定这个a=0,所以说b=y−b/xb=y-b/x

然后我们有b=k−xx+1b=\frac{k-x}{x+1}

然后回代右边的式子即可,得出k+1x+1\frac{k+1}{x+1}

但是完蛋了,他不太对,我们发现是下取整,那很对了????

不懂,正整数a+b应该是在⌊kx−1⌋\lfloor \frac{k}{x}-1 \rfloor~⌊k−1x⌋\lfloor \frac {k-1} {x} \rfloor

还有第三种情况,就是什么fr−fl>1f_r-f_l>1,这种情况显然不会很多,经检验这个可以直接尺取,因为fl<=7f_{l}<=7

???

AT3938 [ARC091C] LISDL

小清新构造题

首先我们可以通过给出一个长度为A的上升序列满足要求

然后会发现,如果我们使用B个首元素递减的上升序列接在后面,就能得出长度为B的下降序列

证明也很简单,就是我们每次任何元素都不能使用上个上升序列的两个元素作为递减序列的元素

所以说如果构造出来就有解,否则无解

AT3883 [ARC090C] Avoiding Collision

我彻底傻掉

不算复杂度,我们可以考虑一条边是哪些最短路的经过且是中点之边,然后有哪些是不经过这个边的最短轮方案

那不拿发现就是经过他为中点的最短路*不经过他的最短路

怎么算2?删掉这条边,跑最短路计数

怎么算1?正着跑一遍反着跑一遍,然后发现这条边一定处于两个点(u,v)满足disu+len>middis_{u}+len>mid且disv+len>middis_v+len>mid

而必须经过他的最短路就是左边到u的最短路方案和右边从v走到T的最短路方案

于是我们想怎么加速2啊

相当于总方案减去不合法的方案?

/se!

题解的做法是直接补集转换,计算某个点/边相遇的情况,总方案角去

你会发现其实和我们没有什么区别......

最短路计数用dij即可实现(转换为最短路DAG计数)

然鹅,我们要小心一点细节,就是总的减去不合法的时候,要用两边积的平方

因为说我们一开始也是相当于两条路径是一个方案,而两边积对应了一条路径,所以要平方!

完结撒花!

Powered by Gridea RSS