Codeforces Round #439 (Div. 2) 题解

比赛链接：http://codeforces.com/contest/869

A. The Artful Expedient

题意：给你一个n,分别输入两组n个数字，，如果这两组数字两两异或的结果与两组数字中的某一个数字相等，那么就有1个pair满足要求，如果最后结果是偶数个pair，那么就是Karen赢，否则是KOYOMI赢

解法：暴力。实际上，这个题是不可能出现奇数对的情况的，直接输出"Karen"就可以了。

#include <bits/stdc++.h>
using namespace std;
int a[2010], b[2010];
bool vis[2000010];
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), vis[a[i]]=1;
    for(int i=1; i<=n; i++) scanf("%d", &b[i]), vis[b[i]]=1;
    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(vis[a[i]^a[j]]){
                if(i==j)ans++;
                else ans+=2;
            }
        }
    }
    if(ans%2==0){
        puts("Karen");
    }
    else{
        puts("Koyomi");
    }
    return 0;
}

B. The Eternal Immortality

题意：计算b!/a!的最后一个数字。

解法：实际上就是从a+1算到b,但是没必要真的算到b，我们算到a+20肯定会出现末尾0的情况，所以就for一遍就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
	LL a, b;
	cin >> a >> b;
	LL sum = 1;
	for (LL i = a + 1; i <= min(b, a + 20); i++)
	{
		LL t = i % 10;
		sum *= t;
		sum %= 10;
	}
	printf("%lld\n", sum);
	return 0;
}

C. The Intriguing Obsession

题意：有3种不同颜色的点分别有a,b,c个。要求我们连边，任意相同的点要么不能直接连边，要么它们的距离大于等于3。

解法：根据样例，大概可以猜测是a,b之间的方案数，b,c之间的方案数，a,c之间的方案数的乘积。关键是如何计算a,b之间的方案数，考虑从a,b里面选i个出来，那么i最多到min(a,b)，有C(i,a)*C(i,b)，这i个可以任意排列，所以有i!种方案，因此一共有sigma(i!*C(i,a)*C(i,b))种方案。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5005;
const int mod = 998244353;
LL c[maxn][maxn];
LL fac[maxn];

LL cal(int n, int m)
{
	if (n < m) swap(n, m);
	LL ret = 0;
	for (int i = 0; i <= m; i++)
	{
		ret += fac[i] * c[n][i] % mod * c[m][i] % mod;
		ret %= mod;
	}
	return ret;
}

int main()
{
	c[0][0] = 1;
	for (int i = 1; i <= 5000; i++)
	{
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}
	fac[0] = 1LL;
	fac[1] = 1LL;
	for (LL i = 2; i <= 5000; i++) fac[i] = fac[i - 1] * i % mod;
	LL x, y, z;
	cin >> x >> y >> z;
	LL ans = 1;
	ans = ans * cal(x, y) % mod;
	ans = ans * cal(x, z) % mod;
	ans = ans * cal(z, y) % mod;
	printf("%lld\n", ans);
	return 0;
}

D：还没补。

E. The Untended Antiquity

题意：二维平面上，我们有3种操作，加矩形栅栏，删除矩形栅栏，询问2个点是否连通。

解法：二维树状数组维护一下矩形的和，最后通过对查询点的左上方求和，加和删就对应树状数组的更新。发现和相同就是Yes，否则就是No，但是坑点是这题给每个矩形加1个值的时候，这个值要随机生成，不然会被轻易卡WA。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2520;
LL c[maxn][maxn];
map<pair<pair<int, int>, pair<int, int> >, LL> mp;
int n, m, q;

int lowbit(LL x)
{
	return x & -x;
}

void add(int x, int y, LL z)
{
	for (int i = x; i <= n; i += lowbit(i))
		for (int j = y; j <= m; j += lowbit(j))
			c[i][j] += z;
}

LL sum(int x, int y)
{
	LL ret = 0;
	for (int i = x; i > 0; i -= lowbit(i))
		for (int j = y; j > 0; j -= lowbit(j))
			ret += c[i][j];
	return ret;
}


LL rnd()
{
	return ((LL)rand() << 48) | ((LL)rand() << 32) | ((LL)rand() <<16) | (LL)rand();
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	srand(time(NULL));
	for (int i = 0; i < q; i++)
	{
		int op, x1, y1, x2, y2;
		scanf("%d%d%d%d%d", &op, &x1, &y1, &x2, &y2);
		if (op == 1)
		{
			LL u = rnd();
			mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))] = u;
			add(x1, y1, u);
			add(x1, y2 + 1, -u);
			add(x2 + 1, y1, -u);
			add(x2 + 1, y2 + 1, u);
		}
		else if (op == 2)
		{
			LL u = mp[make_pair(make_pair(x1, y1), make_pair(x2, y2))];
			add(x1, y1, -u);
			add(x1, y2 + 1, u);
			add(x2 + 1, y1, u);
			add(x2 + 1, y2 + 1, -u);
		}
		else
		{
			LL a = sum(x1, y1);
			LL b = sum(x2, y2);
			if (a == b) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}