2017-03-16

Codeforces Round #404 (Div. 2)

这一场比较水, 然而掉了rating......E题是原题, 连我都知道是原题, 可见多么裸. 但是比赛时只完成2/5, C题FST, E题手抖......而且都是被sqrt这个函数坑了...... 但是我要为出题人点赞. 他的Editorial写得非常详细, 有Hint, 有Tutorial, 还有至少两种语言的实现, 诚意满满. D是道不错的数学题. UPDATE: 经过提醒才发现Editorial为E题给了一种不带log的做法, 后面将会叙述. 题解: 5/5. # A. Anton and Polyhedrons 给出n个字符串, 每个字符串属于集合{"Tetrahedron", "Cube", "Octahedron", "Dodecahedron", "Icosahedron"}. 如果你像我一样一脸懵逼也没有关系, 题面告诉我们它们分别是x面体. 问这n个多面体共有多少面. (1≤n≤200000)

注意到这是#404, A题的Hint写道: > 404 Not Found

#include <bits/stdc++.h>
using namespace std;
int x[300];

int main()
{
	x['T'] = 4;
	x['C'] = 6;
	x['O'] = 8;
	x['D'] = 12;
	x['I'] = 20;
	int n, sum = 0;
	cin >> n;
	while (n--) {
		string s;
		cin >> s;
		sum += x[s[0]];
	}
	cout << sum << endl;
	return 0;
}

B. Anton and Classes

n个chess class的时间段, m个programming class的时间段. 两个时间段(l1,r1),(l2,r2)之间的距离定义为|i-j|的最小值, 其中l1≤i≤r1, l2≤j≤r2. 选取一节chess class和一节programming class, 求最大距离. (1≤n,m≤200000, 1≤l,r≤10^9)

如果找不到不重叠的两节课, 则答案为0. 否则, 重叠一定不是最优解. 分两类: 先上chess class, 先上programming class. 那么, 距离为后上的那节课的开始时刻 - 先上的那节课的结束时刻. 注意到选择互不影响, 贪心即可.

嫌代码不够优美, 改来改去 (结果还是不怎么优美)......喂, 比赛的时候真的有这个必要吗? 清晰即可.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
using namespace std;
const int N = 200000;

int l[2][N], r[2][N];

int main()
{
	int n, m, ans = 0;
	cin >> n;
	Rep (i, 0, n)
		cin >> l[0][i] >> r[0][i];
	cin >> m;
	Rep (i, 0, m)
		cin >> l[1][i] >> r[1][i];
	int mx = *max_element(l[1], l[1] + m), mn = *min_element(r[0], r[0] + n);
	ans = max(ans, mx-mn);
	mx = *max_element(l[0], l[0] + n), mn = *min_element(r[1], r[1] + m);
	ans = max(ans, mx-mn);
	cout << ans << endl;
	return 0;
}

C. Anton and Fairy Tale

谷仓的容量为n, 每天开始时加入m个单位的谷子 (不得超过容量, 多出来的那些就当是消失了), 第i天结束时麻雀吃掉i个单位的谷子, 问第几天结束时谷仓首次变空. 从1开始数数, 第1天开始时谷仓是满的. (1≤n,m≤10^18)

这个数据范围估摸着二分或者用公式直接计算.

如果没有容量限制, 问题还是蛮简单的. 手动模拟一下, 发现开始几天麻雀吃完之后的第二天谷仓又满了. 之后, 加谷子的速度不及吃谷子的速度, 并且可以忽略容量限制. 那么, 转折点具体在哪一天呢? 第i天加入m个单位, 吃掉i个单位. 当i≤m, 第二天谷仓又变满. 当i>m, 第二天加入谷子之后总量仍然减少. 于是:

m-1	m	m+1	m+2	m+3	...	m+t
n	n	n	n-1	n-3	...	n-t(t-1)/2
n-m+1	n-m	n-m-1	n-m-3	n-m-6	...	n-m-t(t+1)/2

当i=m+t>m, 每天结束时, 谷子净减少m+t-m=t, 所以得到上面的公式. 令其不大于0. 然后有两种选择: 解之, 可得t的范围, 或者二分.

注意到这一切建立在n-m>0的前提下. 当n≤m时, 会发生什么呢? 第二天谷仓总是会变满, 第n天结束时谷仓首次变空. n=1包含在这种情况中.

我直接用公式, 心中默念浮点运算你要给力一点啊, 然后FST. 用Python这个计算器检验了一下, 我的答案并没有什么不对啊......这是因为Python的浮点数精度也有限, 整型才是不限长度的. 看了Editorial下面的评论才知道得用decimalmodule, C++里用long double就好.

这是为什么呢? 根据C++ Reference, cmath库里的许多函数都为float, double, long double重载了不同的版本. 先前并没有在意, 这次吃亏活该咯......

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int main()
{
	ll n, m;
	cin >> n >> m;
	if (n <= m)
		cout << n << endl;
	else {
		ll t = ceil(sqrt((ld)2*(n-m) + 0.25) - 0.5);
		cout << m + t << endl;
	}
	return 0;
}

D. Anton and School - 2

长度为n的字符串, 每个字符为(或). 问有多少个子序列是RSBS: - 非空 - 长度为偶数 - 前一半是( - 后一半是) 输出答案对10^9+7取模的结果. (n ≤ 200000)

首先想到一个DP做法: f[i][j] = i位置的)必选, i后面的)可选, 一共选j个, 方案数. (同理. 时间是不允许的. 发现能用组合数直接计算. 预处理一个前缀和. 式子变成了点积. 把其中一个倒过来. 嗯, 卷积, fft......可是我不会在模意义下做fft啊......果断下一题.

比赛结束后看群里的聊天记录, 貌似没考fft啊......转念一想, 组合数的卷积大概也能用组合数表示出来. 所以这应该是一道简单的数学题......

推了一下. Editorial的想法后面讲.

首先需要组合数求和的两个公式. 读者 (如果存在) 可以略过证明.

变成卷积或许容易一些:

$Missing \end{split} \begin{split} \sum_i\binom n i\binom m {m-i} &= \[x^m$ (1+x)^n(1+x)^m \ &= (1+x)^{n+m} \ &= \binom {n+m} m \end{split} \]

这里规定时.

2)
其实是朱世杰恒等式啦......我既忘了等号右边是什么, 又忘了华叔是怎么巧妙证明的, 还忘了我在课堂上是怎么强行证明的. 用生成函数推一推吧.
我们有:
因为前的系数=不定方程自然数解的组数. 转化为正整数解, 再插一插板子. 或者, 前的系数=从(0,0)走到(n+1,i), 每步只能向上或向右走的方案数. 一共走(n+i)步, 必须恰有n步向右, i步向上.
生成函数的前缀和运算很方便:
两种理解方式: 前的系数是与的卷积. 或者, 每个对的前缀和有贡献.
这两个结合起来, 有
因为我们要求生成函数0~m项前系数的和. 暴力一点 (反正是在纸上运算), 把0~i项前系数的和都搞出来, 再取其一.

又回忆了一下, 来一个波哥 & 华叔风格的证明:

这是一个连续的和, 我们要用追逐的差来对付它. 并且注意到下面不动, 上面增加. 二项式系数有什么追逐的差呢?

移项, 把下面一样的放到一边, 并做一些变量代换:

依然规定时, 这样时等式也成立.

然后:

不得不说这种证明更加优美.

上网查了一下, 我们还可以用yy的方式证明.

从

元集{a}中选

个元素, 枚举选取的最后一个元素=

, 则有:

有了背景知识, 导出本题的解法还是比较简单的.

令 = s[0..i) 中(的数目, = s(i..n) 中)的数目 (下标从0开始).

$name is not defined Math input error$

第二行是上面的恒等式1, 第五行是朱世杰恒等式. 第四行基于这样一个事实: 取遍, 且每个数只取一次. 化简的思路是减少记号. 很难继续化简了 (显然答案与字符串具体长什么样有关, 这是难以用的信息表示的), 这样也足够了.

Editorial也是这个思路, 但是不再算算算, 而是yy.

先解决一个简化版的问题: (m+n)个字符, 前m个是(, 后n个是), 有多少个子序列是RSBS. 前面取(的数目和后面取)的数目相等, 当且仅当, 后面取)的数目 + 前面没取的(的数目 = m. 随便指定m个字符就好了, 它们属于哪一部分视自己的位置而定. 所以答案是

枚举最后一个s[i]=(. 共有

个(,

个). 现在, 问题跟简化版相似, 只是规定某个字符不能成为 "前面没取的(". 除了这个限制之外, 随便指定

个字符. 答案是

是不是觉得上面那一堆算式不忍直视呢?

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;
const int N = 200000, MOD = 1e9 + 7;
char s[N+1];
int n, pre[N], suf[N], fac[2][N];

ll fpm(ll x, int n)
{
	ll y = 1;
	while (n) {
		if (n & 1)
			(y *= x) %= MOD;
		(x *= x) %= MOD;
		n >>= 1;
	}
	return y;
}

void init()
{
	fac[0][0] = fac[1][0] = 1;
	Rep (i, 1, n)
		fac[0][i] = (ll)fac[0][i-1] * i % MOD;
	fac[1][n-1] = fpm(fac[0][n-1], MOD - 2);
	Down (i, n-2, 1)
		fac[1][i] = (ll)fac[1][i+1] * (i+1) % MOD;
}

inline int C(int n, int k)
{
	return k > n ? 0 : (ll)fac[0][n] * fac[1][k] % MOD * fac[1][n-k] % MOD;
}

int main()
{
	scanf("%s", s);
	n = strlen(s);
	init();
	Rep (i, 1, n)
		pre[i] = pre[i-1] + (s[i-1] == '(');
	Down (i, n-2, 0)
		suf[i] = suf[i+1] + (s[i+1] == ')');
	int ans = 0;
	Rep (i, 0, n-1)
		if (s[i] == '(') {
			ans += C(pre[i] + suf[i], pre[i] + 1);
			ans -= ans >= MOD ? MOD : 0;
		}
	printf("%d\n", ans);
	return 0;
}

# E. Anton and Permutation 1到n的一个排列, q个操作, 每次交换两个元素 (可以和它本身), 输出每次交换后的逆序数. 初始排列为{1,2,...,n}. (1≤n≤200000, 1≤1≤50000)

[bzoj 2141] 排队

然而40分钟并不够我写出正确的分块. 有三处错误: 设置块的大小没开根号, 查询时中间的整块应是开区间(lb, rb), 块的大小要和1取max, 因为我取的是sqrt(n*log2(n)). 先是TLE, 用随机数据跑了跑, 还真是够慢......加时10min, 终于发现第一个错误, 修正过来, 样例未过, 已无力回天......

UPDATE 2017.3.17 不带log的离线做法 询问分块, 称每块中的询问涉及到的点为动点, 其余为定点. 每块的询问的答案分为三个部分: 1. 定点-定点对于该块的所有询问, 这部分的贡献相同. 用上一块最后一个答案-2,3部分得到. 2. 动点-动点每块至多有个动点. 暴力初始化, 暴力更新, 只用更新跟修改有关的逆序对的情况. 3. 定点-动点不带修改的, 区间小于某数的数的个数的查询. 不妨将查询离线, 再将定点按权值分块. 至此问题解决, 时间复杂度.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#ifdef __WIN32
#define LLFORMAT "I64"
#else
#define LLFORMAT "ll"
#endif

using namespace std;
const int N = 200000;
typedef long long ll;

int n, sz, blk, a[N], b[N];

void build()
{
	sz = max(1.0, ceil(sqrt(n*log2(n))));
	blk = (n + sz - 1)/sz;
	copy(a, a+n, b);
	Rep (i, 0, blk) {
		int j = min(sz, n - i*sz);
		sort(b + i*sz, b + i*sz + j);
	}
}

int query(int l, int r, int x) // [l, r] < x
{
	if (l > r) return 0;
	int ans = 0, lb = l/sz, rb = r/sz, i;
	if (lb == rb) {
		for (i = l; i <= r; ++i)
			ans += a[i] < x;
	} else {
		for (i = l; i < (lb+1)*sz; ++i)
			ans += a[i] < x;
		for (int j = lb+1; j < rb; ++j)
			ans += lower_bound(b + j*sz, b + min(j*sz + sz, n), x) - (b + j*sz);
		for (i = rb*sz; i <= r; ++i)
			ans += a[i] < x;
	}
	return ans;
}

void modify(int pos, int x)
{
	int bx = pos/sz, l = bx*sz, r = min(l+sz, n) - 1, p = find(b + l, b + r + 1, a[pos]) - b;
	a[pos] = x;
	b[p] = x;
	while (p+1 <= r && b[p+1] < b[p]) {
		swap(b[p], b[p+1]);
		++p;
	}
	while (p-1 >= l && b[p-1] > b[p]) {
		swap(b[p], b[p-1]);
		--p;
	}
}		

int main()
{
	scanf("%d", &n);
	Rep (i, 0, n)
		a[i] = i+1;
	build();
	int q;
	ll ans = 0;
	scanf("%d", &q);
	while (q--) {
		int i, j;
		scanf("%d%d", &i, &j);
		--i, --j;
		if (i == j) {
			printf("%" LLFORMAT "d\n", ans);
			continue;
		}
		if (i > j) swap(i, j);
		int len = j-i+1, x = a[i], y = a[j];
		ans += len - 2 * query(i+1, j-1, x);
		ans += 2 * query(i+1, j-1, y) - len;
		ans += (y > x) - (y < x);
		printf("%" LLFORMAT "d\n", ans);
		modify(i, y);
		modify(j, x);
	}
	return 0;
}

总结: 1. 数学题yy的功力有待加强. 生成函数那套理论得深入研究. 2. 浮点运算需谨慎. 3. 设置块的大小表达式要写正确, 考虑是否需要跟1取max. 4. 不熟悉的代码不要凭印象写, 要过脑子. 看到原题不要太兴奋. 5. 码力不足, 有待加强.

这场和yp同学一块打的, 一人挂一题, 但是人家div 1选手不用掉rating. QAQ