【解题报告】小白 76

猜拳游戏

https://ac.nowcoder.com/acm/contest/63419/A

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\mod b=m$ 最好办法就是让 $a$ 恰好等于 $m$ 且 $b$ 尽可能大

此时就得到了 $a = 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的运算问题

细节很多。主要思想就是如果大数和大数那就是乘法， $\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');
    }
}

用一个变量 $m a x$ 是为了方便出现了 $\times998244353$ 导致 $x\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}$ 的时候，可以先用 $\sqrt{N}$ 步调整到 $m\leftarrow\sqrt{N}$ ，然后至多 $\sqrt{N}$ 步把某一列所有数字全部调整好。
当 $m>\sqrt{N}$ 的时候，至多只有 $\dfrac{N}{m}\le\sqrt{N}$ 行，此时也是至多 $\sqrt{N}$ 步把某一列所有数字全部调整好。

因此最多的步数就是 $2\times\sqrt{N}<1000$

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

#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)$ 的块，无论何时贡献的方式都相同，因此可以用递归+记忆化搜索的形式处理。

#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');
    }
}