Codeforces Round #724 & ABC204 游记

CF 再一次地 PB 了!

而且赛时排名恰好 787787, 所以有了这张封面图。

CF R724

2do5pF.md.png
(Ubuntu 截图的颜色似乎有点问题啊)

2doGyd.png
2doJOA.png

修正排名 619619, 个人最好成绩。

虽然最后的成绩非常不错,但是中间的失误还是有点多的,也险些只做出两道,那样就会很严重的掉分了。

比赛开始 A 题还是做的比较顺利的,然后 B 题就直接翻车了,明明是很简单的一题 WA 了一次又 T 了一次, 可是这题才 1200……, 然后 C 题就直接弄的人很绝望,看着一千多人过了自己却没有一点思路。

幸好 D 题一下子就大概知道了,结果还没有想清楚,WA 了一次,然后换上 vector, 可这玩意儿居然插入速度没有想象中的那么快,换成 list 才过。

2dTTC8.md.png

C

DK 组成的字符串分成 D 个数和 K 个数比值相同的子串,求最多的串个数。

这里的比值的是可以有 00 的,非常讨厌,所以显然先把前面一段只有单个的给处理好去掉。

然后考虑后面怎么做——然后我就没有思路了,一直到最后才突然开窍。

后面比值是正常的,所以可以约分当做正常分数来算。那么很明显的,对 DK 的个数做前缀和,当 DK 成一定比例时,它们前缀和的差一定是成相同比例的,而第一段是从头开始的,所以就变成了前缀和的比例相同,所以定义个 twt 把那些分数记下来用个 map 存就好了。

就这要我想一个小时???

#include <cstdio>
#include <map>
const int N = 500005;
int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}
struct twt {
    int a, b;
    void pro() {
        int g = gcd(a, b);
        a /= g, b /= g;
    }
    bool operator < (twt y) const {
        return a < y.a || (a == y.a && b < y.b);
    }
};
std::map<twt, int> map;
int n, ans[N], T;
char st[N];
int main() {
    scanf("%d", &T);
    while(T--) {
        map.clear();
        scanf("%d%s", &n, st+1);
        int a = 0, b = 0, f = 1;
        for( ; st[f+1] == st[1]; f++);
        for(int i = 1; i <= f; i++) ans[i] = i;
        if(st[1] == 'D') a = f; else b = f;
        for(int i = f+1; i <= n; i++) {
            twt now;
            a += st[i] == 'D';
            b += st[i] == 'K';
            now.a = a, now.b = b;
            now.pro();
            ans[i] = map[now] + 1;
            map[now] ++;
        }
        for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

D

这个感觉很套路,居然也有 20002000 分?显然中位数最多只移动一个,所以把中间的一串记下来,然后看能不能插入,能插就插,能移就移,不行就不行就好了。所以需要数据结构支持快速插入,用 std::list 即可。

#include <cstdio>
#include <list>
std::list<int> que;
int T, n, x;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        que.clear();
        scanf("%d", &x);
        que.push_back(x);
        std::list<int>::iterator p = que.begin();
        bool flag = 0;
        for(int i = 2; i <= n; i++) {
            scanf("%d", &x);
            if(flag) continue;
            if(x < *p) {
                if(p == que.begin() || x > *((--p)++)) p = que.insert(p, x);
                else if(x != *(--p)) flag = 1;
            }
            else if(x > *p) {
                if((++p)-- == que.end() || x < *((++p)--)) p = que.insert(((++p)--), x);
                else if(x != *(++p)) flag = 1;
            }
        }
        if(flag) puts("NO");
        else puts("YES");
    }
    return 0;
}

E

妙妙题啊!

输入一个 0# 组成的矩阵,# 可以任意填数字,求满足相邻两个数相差不超过 11 且若一个数严格大于 00 则必须严格大于其周围的至少一个数的矩阵个数。

其实把 00 的位置都确定下来之后这个图就是确定的。

为什么?
可以先考虑一排只有一个 00 的情况,那么就只能是从 00 开始向周围发散。然后可以把这个继续思考,一个 11 出去之后如果不继续增长的话这一边没有比它大的了就只能指望其它的边,可其它的方向如果要降下去的话不能重新上升了,因为会产生比周围小的。而下降若不到 00 有不行,因为最后一个就四周没有一个比它小的了。

所以每个位置上就只能是到离他最近的 00 的距离,这样的化就只要枚举每个位置是不是 00 就好了。

代码甚至比第一题短。

#include <cstdio>
const int P = 1000000007;
int T, n, m;
char s[2005];
int main() {
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		int an = 0;
		for(int i = 1; i <= n; i++) {
			scanf("%s", s+1);
			for(int j = 1; j <= m; j++) an += s[j] == '#';
		}
		int ans = 1;
		for(int i = 1; i <= an; i++) ans = ans * 2 % P;
		printf("%d\n", (ans - (an == n*m) + P) % P);
	}
	return 0;
}

F

O 和 A 在 nn 个格子组成的环上面游戏,两人轮流放置字母 ab, 不能让相同的字母相邻,若一个人无法放置字母,他就输了。

求两人都按最优策略的方案数。

这个题目阴险啊!他跟你说是说要最优策略的方案数,然后你手玩一下发现不管怎么搞后手都一定赢。证明考虑最终状态是什么样子的,容易得到它必然是 ab 相间的,且可以有一些空格,不过空格不能连续,且空格两边也是黑白相间的。那么 ab 就需要相同的个数,也就是后手必胜。

所以就是要计算所有合法局的方案数。这又是 nottttttthy 最喜欢的组合数学题了。

考虑枚举空了 ii 个点, 那么就要用 ii 个空将 nin-i 个分开,因为空格不能连续,所以方案数是 (nii)n-i \choose i, 因为这个格子是环状的,所以需要考虑第一个格子时空的情况,那么就是在剩下的 ni1n-i-1 里面选 i1i-1 个就可以了。

因为 ab 可以互换,而且顺序可以随意打乱,所以答案还要乘上 2(ni)!2(n-i)!

代码。

#include <cstdio>
#define int long long
const int N = 1000005, P = 1000000007;
int fac[N], inv[N], n, ans;
int Pow(int a, int b) {
	int an = 1;
	while(b) {
		if(b & 1) an = an * a % P;
		a = a * a % P;
		b >>= 1;
	}
	return an;
} 
int C(int n, int m) { return fac[n] * inv[m] % P * inv[n-m] % P; }
signed main() {
	scanf("%lld", &n);
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % P;
	inv[n] = Pow(fac[n], P-2);
	for(int i = n; i >= 1; i--) inv[i-1] = inv[i] * i % P;
	for(int i = n&1; i <= n-i; i += 2) ans = (ans + 2*fac[n-i]*(C(n-i, i)+C(n-i-1,i-1)) % P) % P;
	printf("%lld", ans);
	return 0;
}

ABC 204

E

E 犯了一个重大失误,没有验证过二分性就直接上二分了,导致最后调了很久才发现这个问题并改正,不然肯定会掉很多的分了,那就成悲剧了。

F

主要讲 F。

1×21 \times 21×11 \times 1 的格子覆盖 n×mn \times m 的矩形的方案数。

注意到数据范围 n6n \le 6,那么显然就是要状压掉一列的内容了。

fi,Sf_{i, S} 表示前 ii 行最后一行是 SS (横着叉出去是 11 否则是 00)的方案数。转移的话就是枚举前面一行的状态,然后再枚举一下空的哪些用 $1\times 2 $ 哪些用 1×11 \times 1 的就可以了。

但是一看 mm 的范围是 101210^{12} 这个范围也非常明显的是要让你矩阵乘法快速幂的优化的或者某些神奇的根号算法的。我们注意到 TST \to S 的转移里面枚举的哪些用 1×21 \times 2 得出方案数的答案是固定的。所以可以把转移这样表示 fi,S=fi1,Tc(S,T)f_{i, S} = \sum f_{i-1, T} \cdot c(S, T),后面的那个东西处理出来就是标准的矩阵乘法了。

说起来轻松但是当我自己写的时候还是遇到了很多的问题,大概是我对于矩阵乘法快速幂的理解不够深刻吧。

#include <cstdio>
#include <cstring>
#define int long long
const int P = 998244353;
int n, m;
struct twt {
	int v[1 << 6][1 << 6], n, m;
	int* operator [] (int x) { return v[x]; }
	twt() { memset(v, 0, sizeof v); }
	friend twt operator * (twt a, twt b) {
		twt c;
		c.n = a.n, c.m = b.m;
		for(int i = 0; i < 	c.n; i++)
			for(int j = 0; j < c.m; j++)
				for(int k = 0; k < a.m; k++)
					c[i][j] = (c[i][j] + a[i][k] * b[k][j] % P) % P;
		return c;
	}
} f, c;
twt Pow(twt a, int b) {
	twt an = a; b--;
	while(b) {
		if(b & 1) an = an * a;
		a = a * a;
		b >>= 1;
	}
	return an;
}
signed main() {
	scanf("%lld%lld", &n, &m);
	f.n = 1, f.m = 1 << n;
	f[0][0] = 1;
	c.n = c.m = 1 << n;
	for(int i = 0; i < (1 << n); i++)
		for(int j = 0; j < (1 << n); j++)
			for(int k = 0; k < (1 << n); k++) 
				if((i | j | k | (k << 1)) == i + j + k + (k << 1)
				&& i + j + k + (k << 1) < 1 << n) c[i][j] ++;
	f = f * Pow(c, m);
	printf("%lld", f[0][0]);
	return 0;
}

我遇到的问题大概都是在起始状态和停止状态上。
要记住,矩阵描述的是满足结合律的运算,所以直接把后面变换的那个 cc 矩阵和我们原来的初始状态相乘就可以了。