AGC028 解题记录

### A Two Abbreviations
签到题，就不翻译了
找两个串一段长度的$gcd$，判一判对应位置一不一样就可以了。

### B Removing Blocks
题意：给你一个长度为$N$的序列，将$N$个数依次删掉。每一次删掉一个数的代价是这个数当前所在连通块的数的总和(包括自己)。问所有$N!$种方案的代价和之和。$N\le 10^5$

题解：简单组合计数，对每一个$K$连续子段考虑恰好出现这一段作为贡献的情况，充要条件是：先是左右两边都被删，然后删掉段内的一个数。而且不难发现对于每一个处于整体中间的长度相同的段，它们的贡献是一样的，那么我们时刻维护中间部分的和，对左右端点两个情况进行讨论即可。

code
```
#include<cstdio>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int a[maxn], sum[maxn], n, nsum, tot, ans;
int step[maxn], inv[maxn], side_sum;
void Add(int &x, const int &a) {
	x += a;
	if(x >= mod) x -= mod;
}
int mul(const int &a, const int &b) {
	return 1ll * a * b % mod;
}
int dec(const int &a, const int &b) {
	return a - b < 0 ? a - b + mod : a - b;
}
int fpow(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = mul(ans, a);
		b >>= 1, a = mul(a, a);
	}
	return ans;
}
void pre(int n) {
	step[0] = inv[0] = 1;
	for(register int i = 1; i <= n; ++i)
		step[i] = mul(step[i - 1], i);
	inv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i)
		inv[i] = mul(inv[i + 1], (i + 1));
}
int C(int n, int m) {
	return mul(mul(step[n], inv[n - m]), inv[m]);
}
int main() {
	scanf("%d", &n), pre(n + 3);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &a[i]), sum[i] = sum[i - 1], Add(sum[i], a[i]);
	for(register int i = 1; i < n; ++i) {
		Add(nsum, dec(sum[n - i], sum[i]));
		Add(side_sum, a[n - i + 1]);
		Add(side_sum, a[i]);
		Add(ans, mul(mul(side_sum, step[i]), mul(C(n, i + 1), step[n - i - 1])));
		Add(ans, mul(mul(nsum, mul(2, step[i])), mul(C(n, i + 2), step[n - i - 2])));
	}
	Add(ans, mul(sum[n], step[n]));
	printf("%d", ans);
	return 0;
} 
```

### C Min Cost Cycle
题意：一个$n$个点的完全图，每个点有点权$A_i,B_i$，你需要找到一个经过每一个点恰好一次的有向环，使得权值最小。一个边被定向为$u\to v$后，权值是$min(A_u,B_v)$。$N\le 10^5$

题解：取最小值求最小，看到就本来应该去讨论的结果想了半天图论算法，又跪了……
首先我们可以大胆猜想为什么不一定能拿出$A/B$种前$n$小的。我们将前$n$小的$A/B$标记，那么点一定按照$A/B$被标记的状态分为$4$种。
我们用一个二位二进制数来表示，比如$10$就表示$A$被标记$B$没标记。
当我们有$00/11$至少一对的时候(注意00的数量永远等于11的数量，因为总数是$n$不变)因为有 $被标记为的数\le 无标记的数$ 恒成立，我们可以这样构造：
$$10\to ...\to 10\to(10的循环)\\
00\to 11\to ... \to 00\to 11(多余的00/11)\\ 
00\to \\
01\to ...\to 01\to(01的循环)\\
11\to$$
发现如果没有一对$00/11$必然分为两个环。
特别的，当全部是$01/10$时也可以成为一个环。
那么特判特殊情况，如果有$00/11$直接输出前$n$小的和，否则贪心换出一个$00/11$来。

### D Chords

题意：圆上$2N$个均匀分布的点。要把他们两两配对连线。我们称两个点连通为两个点可以通过连线到达。(可以通过连线之间的交点从一个连线到达另一个连线)。在出题人已经帮你连了一些线的情况下问所有方案的连通块个数和。

题解：首先用上次和ccosi出题的那个结论——这样带标号连线判相交的题断环为链不影响答案。
一开始想偏了，发现如果把一个连通块的下标最大/最小的点看作左右括号，那么一定是一个合法的括号序列。想着去硬$DP$，发现复杂度不对。
实际上用$B$的思路就很对，既然如此，我们可以直接设$f(i,j)$ 表示只考虑$[i,j]$的连线，存在$[i,j]$这样的连通块的方案数。最后的答案只需要乘上一个$n-(i-j + 1)$个点乱连的方案数就好了，设$2n$个点乱连的方案数为$g_n=\prod^{n}_{i=1}(2i-1)$。
直接转显然没法转的，但是我们可以参考连通图计数，用总的减去不合法的。
$$f(i,j)=g_{j-i+1}-\sum^{j-1}_{k=i}f(i,k)g_{j-k}$$
然后对于给定的条件，我们只考虑空出的部分，给定条件就相当于定死一些地方一定连通。大概就行了吧。

### E High Elements

题意：有一个排列$P$，给一个$0/1$字符串$s$，从左到右按顺序依次构造$A/B$两个序列：如果$s_i=0$，将$P_i$放在$A$末尾，否则放在$B$末尾。对于一个序列，定义$i$是好的，当且仅当$i$位置的数等于$i$的前缀最大值。要你在$A/B$好位置个数相同的前提下找到字典序最小的$s$。

要贪心肯定能放$A$就全都放$A$。
问题是什么时候不能放$A$。
首先有个结论，如果存在一种合法方案，那么必定存在$A/B$之间至少有一个的好位置都是原来序列的好位置，设原序列好位置数为$p$。
那么我们分$A/B$全是原有好位置讨论，以$A$为例。
如果$P_x$能放，那么：
假设$A$有了$a$个好位置，$B$有了$b$个好位置，不难发现最后要能补齐$B$的空缺首先肯定要满足补的齐$B$的空，其次还要满足能把$A/B$填平。
那么有：
$$a+p-B的原好位置数=b+B的原好位置数+B的新好位置数$$
那么相当于问后面有没有一个上升序列，其中选一个原好位置贡献$2$，新好位置贡献$1$，使得贡献值恰好为查询值。
因为$c$可以凑出，那么$c+2$也可以凑出。
我们倒着用线段树做一遍$DP$，然后分奇偶性记录$c$的最大值，然后贪心选就好了。

### F Reachable Cells

~~啊我死了~~

Rockdu's Blog

导航

最近发表

大佬们的友链