2017-05-25

Codeforces Round #415 (Div. 2)

有段时间没打CF了, 补了最近的一场. 把C题当成了B题, 幸好都不难. QAQ D是交互题, 最后几秒提交, 然而有个地方做除法没把int转成double......失去一次在 rank 两位数留名的机会, 功夫不到家呀...... E题不太会, 学习了一下, 加深了对数位DP的理解. 题解: 5/5 # A. Straight <<A>> n个[1,k]内的整数, 至少新加入多少个[1,k]中的数, 它们的平均值四舍五入得到k? (1≤n,k≤100)

显然可以全部加入k. 枚举即可, 循环次数不会超过2*10^4. O(1)地计算也是可以的.

int main()
{
	int n, k, s = 0;
	scanf("%d%d", &n, &k);
	rep (i, 0, n) {
		int a;
		scanf("%d", &a);
		s += a;
	}
	int m = 0;
	while (int(double(s+m*k)/(m+n) + 0.5) < k) ++m;
	printf("%d\n", m);
	return 0;
}

B. Summer sell-off

n天, 每天ki件商品, li个顾客. 如果还有商品, 则该顾客买走一件, 否则直接离开. 每天多余的商品不留到下一天. 选择f天使ki加倍, 问最多能卖出多少件商品. (1≤n≤10^5, 0≤f≤n, 0≤ki,li≤10^9)

第i天能卖出 max{ ki, li } 件商品. 先算出原来总共卖出多少件, 然后将所有 max{ 2 ki, li } - max{ ki, li } 排序, 取前f大.

const int N = 1e5;

struct Product {
	int k, l, v;
	Product(int k=0, int l=0): k(k), l(l)
	{
		v = min(2*k, l) - min(k, l);
	}
	
	bool operator<(const Product& o) const
	{
		return v < o.v;
	}
} P[N];

int main()
{
	int n, f;
	ll ans = 0;
	scanf("%d%d", &n, &f);
	rep (i, 0, n) {
		int k, l;
		scanf("%d%d", &k, &l);
		P[i] = Product(k, l);
		ans += min(k, l);
	}
	sort(P, P+n);
	per (i, n-1, n-f) ans += P[i].v;
	printf("%"LLFORMAT"d\n", ans);
	return 0;
}

C. Do you want a date?

n个不同的数, 定义, 求.

我的做法: 把所有数从小到大排序, 枚举取到的那对, 它的贡献是. 发现对于同一个, 很多前的系数一正一负抵消掉了. 具体而言, 设, 前的系数是后个数与前个数之差. 这样, 就可以计算了.

Editorial的做法: 把所有数从小到大排序, 可以拆成许多之和. 对于某个, 它在所有满足的集合中出现, 共个.

评论区中看到的做法: 把所有数从小到大排序, 是个集合的最大元素, 个集合的最小元素, 它的系数是.

我觉得做法三最简洁.

const int N = 3e5, MOD = 1e9 + 7;

ll x[N];

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n)
		scanf("%"LLFORMAT"d", x+i);
	sort(x, x+n);
	
	ll pre = 0, suf = 0, p = 1, ans = 0;
	rep (i, 0, n) {
		(pre += x[i]) %= MOD;
		(suf += x[n-1-i]) %= MOD;
		(ans += p * (suf - pre + MOD)) %= MOD;
		(p *= 2) %= MOD;
	}
	printf("%"LLFORMAT"d\n", ans);
	return 0;
}

D. Glad to see you!

n个数, k个被选中, 60次询问机会, 找出任意两个被选中的数. 每次询问提供两个参数x,y, 设所有被选中的数当中, a使|x-a|最小, b使|y-b|最小, 返回|x-a|≤|y-b|的真假. (2≤k≤n≤10^5)

|x-a|≤|y-b|有点像二分时check的条件, 60≈3lg n. 想着x,y各维护一个二分的范围, 不太好搞. 何不先专心找出一个数, 再在它的左右两侧寻找呢?

假设[l,r)中有一个被选中的数, 它一定会落在[l,m)或[m,r)中. 询问(m,m-1)就知道具体落在哪儿了. 使|m-1-a|最小的a和使|m-b|最小的b可能不是一个数, 但这不碍事~ 此时[l,m)和[m,r)中都有被选中的数. 注意(m,m-1)的顺序不可颠倒, 因为[m,r)内整点个数=[l,m)内整点个数 or +1.

找出第二个数之后得检验一下. 找出第一个数后, 我们已经可以判断|x-a|=0的真假.

下面的代码和上面的叙述略有不同, 取的是两个四等分点. 道理是一样的, 但是确切地说明它的正确性好像更麻烦......

inline bool query(int x, int y)
{
	static char s[10];
	printf("1 %d %d\n", x, y);
	fflush(stdout);
	scanf("%s", s);
	return s[0] == 'T'; // |x-a| <= |y-b|
}

int bs(int l, int r)
{
	while (r-l > 1) { // [l, r)
		int m = (l+r)/2;
		double mid = double(l+r-1)/2, d = double(r-l)/4;
		int a = round(mid-d), b = round(mid+d);
		if (query(b, a)) l = m;
		else r = m;
	}
	return l;
}

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	int a = bs(1, n+1), b = a != 1 ? bs(1, a) : bs(a+1, n);
	if (!query(b, a)) b = bs(a+1, n);
	printf("2 %d %d\n", a, b);
	return 0;
}

E. Find a car

10^9*109的矩阵, (x,y)中的数是不出现于(i,y)或(x,j) (1≤i<x, 1≤j<y) 的最小正整数, q个询问, 求某矩形区域中不超过k的数之和, 答案模10^9+7.

这个定义有点像mex, 进而联想到Nim, 异或. 发现转移和两堆的Nim游戏很像, 但这里并不需要把很多两堆Nim组合起来啊 (不是很明白那时的想法). 打了一个50*50的表, 发现一些自递归的现象, 写出递推式, 发现(i,j)处的数正是 (i-1) xor (j-1) + 1.

看了评论区......我为什么不直接对两堆的Nim用SG定理......QAQ

感觉可以二维前缀和, 然后数位DP. 但我对数位DP的理解并没有进行抽象, 一时没想到怎么处理 i, j, i xor j 都有限制的问题. 结合Editorial评论区中tweety的回答, 学习了一番.

长度相等时, 数的比较就是字符串字典序的比较. DP的状态为 (考虑高l位组成的二进制数, i的高l位和x的高l位相等还是小于后者, j的高l位和y的高l位相等还是小于后者, (i xor j)的高l位和k的高l位相等还是小于后者). 1和(i xor j)拆成cnt, sum两部分处理. 枚举i,j的第(l+1)位取什么, 去除i,j,i xor j的高l位大于x,y,k的高l位的情况后, 就可以转移了.

const int MOD = 1e9 + 7;

ll solve(int X, int Y, int k)
{
	static bool A[31], B[31], C[31];
	static ll cnt[32][2][2][2], sum[32][2][2][2];

	if (X <= 0 || Y <= 0) return 0;

	fill_n(***cnt, sizeof(cnt)/sizeof(ll), 0);
	fill_n(***sum, sizeof(sum)/sizeof(ll), 0);

	per (i, 30, 0) {
		A[i] = X & 1;
		B[i] = Y & 1;
		C[i] = k & 1;
		X >>= 1;
		Y >>= 1;
		k >>= 1;
	}

	cnt[0][1][1][1] = 1;
	
	rep (i, 0, 31) rep (a, 0, 2) rep (b, 0, 2) rep (c, 0, 2) rep (x, 0, 2) rep (y, 0, 2) {
		int z = x ^ y;
		if (a && x > A[i] || b && y > B[i] || c && z > C[i]) continue;
		(cnt[i+1][a && A[i] == x][b && B[i] == y][c && C[i] == z] += cnt[i][a][b][c]) %= MOD;
		(sum[i+1][a && A[i] == x][b && B[i] == y][c && C[i] == z] += sum[i][a][b][c] + (z ? cnt[i][a][b][c] << (30-i) : 0)) %= MOD;
	}

	return (cnt[31][0][0][0] + sum[31][0][0][0]) % MOD;
}

int main()
{
	int q;
	scanf("%d", &q);
	while (q--) {
		int x1, y1, x2, y2, k;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &k);
		printf("%"LLFORMAT"d\n", ((solve(x2, y2, k) - solve(x2, y1-1, k) - solve(x1-1, y2, k) + solve(x1-1, y1-1, k)) % MOD + MOD) % MOD);
	}
	return 0;
}