A 猜拳游戏

分析略。

#include<cstdio>
int main(){
    char s[15];
    scanf("%s", s + 1);
    printf("%s\n", s + 1);
}

B Kevin喜欢一

前期肯定是全力复制，最后一把复制一部分 1 即可。

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int main(){
	int T = init();
    while (T--) {
        int x = 1, n = init(), ans = 0;
        while (x < n) x <<= 1, ++ans;
        print(ans), putchar('\n');
    }
}

C A加B,A模B

简单解一下方程组就会发现，若想满足 $a\mathrm{m}\mathrm{o}\mathrm{d}b=ma\backslash mod\; b=m$ 最好办法就是让 $aa$ 恰好等于 $mm$ 且 $bb$ 尽可能大

此时就得到了 $a=m,b=n-ma=m,b=n-m$ 的结局

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int main(){
	int T = init();
    while (T--) {
        int n = init(), m = init();
        int b = n - m, a = m;
        if (b < 1 || a % b != m) print(-1), putchar('\n');
        else print(a), putchar(' '), print(b), putchar('\n');
    }
}

D MoonLight的运算问题

细节很多。主要思想就是如果大数和大数那就是乘法，$\le 1\backslash le1$ 的数用加法不劣于乘法。

#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int Mod = 998244353;
int mx(int x, int y){
    return x > y ? x : y;
}
signed main(){
	int T = init();
    while (T--) {
        int n = init(), x = 0, max = 0;
        for (int i = 1; i <= n; ++i) {
            int a = init();
            if (max <= 1 || a <= 1) x += a;
            else x *= a;
            max = mx(max, x); x %= Mod;
        }
        print(x), putchar('\n');
    }
}

用一个变量 $maxmax$ 是为了方便出现了 $\times 998244353\backslash times998244353$ 导致 $x\le 1x\backslash le1$ 的问题

E 括号序列操作专家

模板题。不知道怎么审核的，把一道远古题原模原样搬了过来作为了 E 题。

#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 2e5 + 5;
char s[N];
signed main(){
	int T = init();
    while (T--) {
        int n = init();
        scanf("%s", s + 1);
        int cnt = 0, tnt = 0, ans = 0;
        // 目前多出来左 / 右括号个数，下一个左括号摆放位置，交换次数
        int x = 0, y = 0;
        for (int i = 1; i <= n; ++i)
            if (s[i] == '(') {
                ++x;
                if (tnt) {
                    ans += tnt;
                    --tnt;
                }
                else ++cnt;
            }
            else {
                ++y;
                if (cnt) --cnt;
                else ++tnt;
            }
        if (x != y) print(-1), putchar('\n');
        else print(ans), putchar('\n');
    }
}

F Kevin的矩阵

一道有趣的题。

主要在于算法的复杂度证明。

考虑分块：

• 当 $m\le \sqrt{N}m\backslash le\backslash sqrt\{N\}$ 的时候，可以先用 $\sqrt{N}\backslash sqrt\{N\}$ 步调整到 $m\leftarrow \sqrt{N}m\backslash leftarrow\backslash sqrt\{N\}$，然后至多 $\sqrt{N}\backslash sqrt\{N\}$ 步把某一列所有数字全部调整好。

• 当 $m>\sqrt{N}m>\backslash sqrt\{N\}$ 的时候，至多只有 ${\displaystyle \frac{N}{m}}\le \sqrt{N}\backslash dfrac\{N\}\{m\}\backslash le\backslash sqrt\{N\}$ 行，此时也是至多 $\sqrt{N}\backslash sqrt\{N\}$ 步把某一列所有数字全部调整好。

因此最多的步数就是

所以可以考虑枚举一个偏移值，令 $ii$ 表示偏移值，不断地把偏移值放大，进而更新答案（答案初始值设为 $10001000$）

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 2e5 + 5;
int n, m, k, ans, a[N];
int mn(int x, int y){
    return x < y ? x : y;
}
int ab(int x){
    return x < 0 ? -x : x;
}
void check(int step){
    for (int st = 1; st <= step; ++st) {
        int cnt = 0;
        for (int j = st; j <= n; j += step)
            cnt += (a[j] != k);
        ans = mn(ans, ab(step - m) + cnt);
    }
}
int main(){
	int T = init();
    while (T--) {
        n = init(), m = init(), k = init(), ans = 1000;
        for (int i = 1; i <= n; ++i)
            a[i] = init();
        for (int i = 0; i <= ans; ++i) {
            // 枚举偏移值
            if (m - i >= 1) check(m - i);
            check(m + i);
        }
        print(ans), putchar('\n');
    }
}

G Kevin逛超市

二分的模板题。

考虑任何一个长度为 $N(>2)N(>2)$ 的块，无论何时贡献的方式都相同，因此可以用递归+记忆化搜索的形式处理。

#include<cstdio>
#include<cstring>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e7 + 5, Mod = 998244353;
int mp[N];
int calc(int x){
    if (x < N && mp[x] != -1) return mp[x];
    int mid = (1 + x) >> 1;
    int ans = x;
    if (mid == 1) ans += 0;
    else ans = (ans + calc(mid)) % Mod;
    if (x - mid == 1) ans = (ans + 1) % Mod;
    else ans = (ans + calc(x - mid)) % Mod;
    if (x < N) mp[x] = ans;
    return ans;
}
int quick_mod(int a, int b){
    int s = 1;
    while (b) {
        if (b & 1) s = s * a % Mod;
        a = a * a % Mod; b >>= 1;
    }
    return s;
}
signed main(){
    memset(mp, -1, sizeof(mp));
    int T = init();
    while (T--) {
        int n = init();
        if (n == 1) print(1), putchar('\n');
        else print(calc(n) * quick_mod(n, Mod - 2) % Mod), putchar('\n');
    }
}