Codeforces Round #685 (Div. 2)

Codeforces Round #685 (Div. 2)

A Subtract or Divide

思路：对于偶数直接除 (2) 再减 (1) ，奇数先减 (1) ，然后和偶数相同，小一点的数要特判

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int a[maxn], n;
int main(int argc, char const *argv[])
{
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		if(n == 1) {
			printf("0
");
		} else if(n == 2){
			printf("1
");
		} else if(n == 3){
			printf("2
");
		} else if(n % 2 == 0){
			printf("2
");
		} else {
			printf("3
");
		}
	}    
    return 0;
}

B Non-Substring Subsequence

思路：其实只用看 (le) 的左边有没有和 (s_{le}) 相同的或者 (ri) 的右边有没有和 (s_{ri}) 相同的，有一个成立就是 (YES)

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int a[maxn], n, q;
char s[maxn];
int sum[maxn];
int main(int argc, char const *argv[])
{
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &n, &q);
		scanf("%s", s + 1);
		rep(i, 1, n){
			sum[i] = sum[i - 1];
			if(s[i] == '1') sum[i]++;
		}
		while(q--){
			int le, ri;
			scanf("%d%d", &le, &ri);
			if(s[le] == '1' && sum[le - 1]){
				printf("YES
");
				continue;
			}
			if(s[le] == '0' && sum[le - 1] != le - 1){
				printf("YES
");
				continue;
			}
			if(s[ri] == '0' && sum[n] - sum[ri] != n - ri){
				printf("YES
");
				continue;
			}
			if(s[ri] == '1' && sum[n] - sum[ri]){
				printf("YES
");
				continue;
			}
			printf("NO
");
		}
	}    
    return 0;
}

C String Equality

思路：统计串 (s) 和 (t) 中 (a) 到 (z) 的个数，然后从 (a) 开始枚举， 如果 (nums[i] < numt[i]) ，答案就是 (No) ，如果 (nums[i] >= numt[i]) ，那么判断 (nums[i] - numt[i]) 能不能整除 (k) ，若不能，答案就是 (No) ，否则 (nums[i + 1] = nums[i] - numt[i]) 。

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int a[maxn], n, q;
char s[maxn], t[maxn];
int nums[maxn], numt[maxn];
int main(int argc, char const *argv[])
{
	int tt;
	scanf("%d", &tt);
	while(tt--){
		scanf("%d%d", &n, &q);
		scanf("%s", s + 1);
		scanf("%s", t + 1);
		sort(s + 1, s + n + 1);
		rep(i, 0, 25) nums[i] = numt[i] = 0;
		rep(i, 1, n) nums[s[i] - 'a']++;
		rep(i, 1, n) numt[t[i] - 'a']++;
		int flag = 1;
		rep(i, 0, 25){
			if(numt[i] > nums[i]){
				flag = 0;
				break;
			}
			int res = nums[i] - numt[i];
			if(res % q){
				flag = 0;
				break;
			}
			nums[i + 1] += res;
		}
		if(flag) printf("YES
");
		else printf("NO
");
	}    	
    return 0;
}

D Circle Game

思路：我们首先找到最大的 (z) 使得 (zk * zk * 2 <= d^{2}) ，然后判断 ((k*(z + 1)) * (k*(z + 1)) + zk * zk leq d^{2}) ，满不满足，若满足，则先手赢，否则后手赢。

证明:

((k*(z + 1)) * (k*(z + 1)) + zk * zk leq d^{2}) 成立 ：容易看出，无论后手玩家如何移动，先手玩家总有方法使得当前坐标的 (|x - y| == k) ，所以先手必胜

((k*(z + 1)) * (k*(z + 1)) + zk * zk leq d^{2}) 不成立：容易看出，无论先手玩家如何移动，后手玩家总能使当前坐标 (|x == y|)

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int a[maxn], n, q;
char s[maxn], t[maxn];
int nums[maxn], numt[maxn];
int main(int argc, char const *argv[])
{
	int tt;
	scanf("%d", &tt);
	while(tt--){
		LL d, k;
		scanf("%I64d%I64d", &d, &k);
		LL cnt = 1;
		for(LL i = k; i <= d; i += k){
			if(i * i * 2LL <= d * d){
				cnt = i / k * 2;
				if((i + k) * (i + k) + i * i <= d * d){
					cnt++;
				}
			}
		}
		if(cnt % 2){
			printf("Ashish
");
		} else {
			printf("Utkarsh
");
		}
	}    	
    return 0;
}

E1 E2 Bitwise Queries

由于直接看的 (E2) 所以直接讲最优解

思路：我们先得到 (a_1) 和 (a_2) 到 (a_n) 所有数异或后的值 (b_2, b_3, b_4, b_5 .... b_n) ，容易想到只要确定一个数的值，就可以确定其他所有数，然后分两种情况讨论

一、存在相同的数，那么一定存在某两个 (i, j) 使得 (b_i == b_j) 或者 存在一个 (i) 使得 (b_i == 0) ，前者可以的得出 (a_i == a_j) ，后者可以得出 (a_1 == a_i)

​ 然后我们将这两个相同的数 (AND) 后的值就是这两个数的值了

二、不存在相同的数，根据题目中 (n) 一定是 (2) 的次幂，并且 (0leq a[i] leq n - 1) 的条件，可以得出 (a) 是 (0) 到 (n - 1) 的一个排列， 那么就一定存在一个 (i) 使得 (b_i)

​ 等于 (n - 1) ，这样的 (a_1) 和 (a_i) 有一个性质，对于二进制上任意一位，如果 (a_1) 的值为 (0) ，那么 (a_i) 一定为 (1) ，为 (1) 同理，那么我们只要找到任意一个 (j) ，

​ 让 (a_j) 和 (a_1, a_i) 分别 (AND) 后得到值 (c_1, c_i) ，那么 (c_1 | c_i) 的值就是 (a_j) 的值了

自己手推一下比较好理解

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int n;
int res[maxn], ans[maxn];
map<int, int> mp;
int main(int argc, char const *argv[])
{
    scanf("%d", &n);
    int flag = 1;
    int id1 = -1, id2 = -1;
    for(int i = 2; i <= n; i++){
        printf("XOR 1 %d
", i);
        fflush(stdout);
        scanf("%d", &res[i]);
        if(res[i] == 0){
            flag = 0;
            id1 = 1, id2 = i;
        }
        if(mp.count(res[i]) && id1 == -1) {
            id1 = mp[res[i]], id2 = i;
            flag = 0;
        }
        mp[res[i]] = i;
    }
    if(flag == 0){
        printf("AND %d %d
", id1, id2);
        fflush(stdout);
        int x;
        scanf("%d", &x);
        ans[id1] = ans[id2] = x;
        if(id1 != 1){
            ans[1] = x ^ res[id1];
        }
        printf("! %d ", ans[1]);
        rep(i, 2, n){
            ans[i] = ans[1] ^ res[i];
            printf("%d ", ans[i]);
        }
    } else {
        id1 = id2 = -1;
        for(int i = 2; i <= n; i++){
            if(res[i] == n - 1){
                id1 = 1, id2 = i;
                break;
            }
        }
        int id;
        if(id2 == 2) id = 3;
        else id = 2;
        int b1, b2;
        printf("AND %d %d
", id1, id);
        fflush(stdout);
        scanf("%d", &b1);
        printf("AND %d %d
", id2, id);
        fflush(stdout);
        scanf("%d", &b2);
        ans[id] = b1 | b2;
        ans[1] = ans[id] ^ res[id];
        printf("! %d ", ans[1]);
        rep(i, 2, n){
            ans[i] = ans[1] ^ res[i];
            printf("%d ", ans[i]);
        }
    }
    return 0;
}

F Nullify The Matrix

思路：我们定义 (f(x)) 为 (a[i_1][j_1] igoplus a[i_2][j_2] .... igoplus a[i_k][j_k]) 的值，其中 (i_k + j_k == x) ，也就是某一条斜对角线的异或和，如果存在 (f(x)) 不为 (0) ，那么先手赢，否则后手赢， 具体证明请看官方题解，我也是赛后补的题（菜鸡落泪

#include <bits/stdc++.h>
using namespace std;
#define lc (rt << 1)
#define rc ((rt << 1) | 1)
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define PE(i, u) for (int i = head[u]; i != -1; i = edge[i].next)
typedef long long LL;
const int maxn = 1e6 + 20;
const int mod = 1e9 + 7;
int a[105][105];
int n, m;
int main(int argc, char const *argv[])
{
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        rep(i, 1, n){
            rep(j, 1, m){
                scanf("%d", &a[i][j]);
            }
        }
        int flag = 0;
        rep(sum, 2, n + m){
            int res = 0;
            rep(i, 1, sum - 1){
                if(!(i >= 1 && i <= n && sum - i >= 1 && sum - i <= m)) continue;
                res ^= a[i][sum - i];
            }
            if(res) {
                flag = 1;
                break;
            }
        }
        if(flag) printf("Ashish
");
        else printf("Jeel
");
    }   
    return 0;
}