C、Forsaken City

从后往前贪心， 取最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define int long long

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    int ans = 0;
    for (int i = n - 2; i >= 0; i--) {
        ans = std::max(ans, a[i] - a[i + 1]);
        a[i] = std::min(a[i], a[i + 1]);
    }
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

F、The Correlation

一次操作可以使两个奇偶性相同的两个数相等， 最多执行n - 1 次可以使得最多存在两个不i同的数 x， y， 再取 （x + y）/ 2， 最后所有数的差不会超过 1, 所以答案就是 奇数个数 * 偶数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define int long long
const int MOD = 998244353;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    int ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        if (a[i] & 1) {
            ans1++;
        } else {
            ans2++;
        }
    }
    std::cout << (ans1 * ans2) % MOD << '\n';
}

signed main() {
    int t = 1;
    // std::cin >> t;
    while (t--) solve();
    return 0;
}

G、Nice Doppelgnger

打表找规律， 输出全部素因子个数都为奇数的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define int long long

const int PRIME_N = 1000010;
int st[PRIME_N];
int primes[PRIME_N];
int cnt;
void fun()
{
    for (int i = 2; i < PRIME_N; i++)
    {
        if (!st[i])
        {
            st[i] = i;
            primes[cnt++] = i;
        }
        for (int j = 0; i * primes[j] < PRIME_N; j++)
        {
            st[i * primes[j]] = primes[j];
            if (i % primes[j] == 0)
                break;
        }
    }
}

void solve() {
    int n;
    std::cin >> n;
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        int j = i;
        int cnt = 0;
        while (j > 1) {
            int c = 0;
            int p = st[j];
            while (j % p == 0) {
                c++;
                j /= p;
            }
            cnt += c;
        }
        if (j > 1) cnt++;
        if (cnt & 1) {
            std::cout << i << ' ';
            ans++;
            if (ans == n / 2) {
                break;
            }
        }
    }
    std::cout << '\n';
}   

signed main() {
    fun();
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

J、Ivory

设 b < d， e = gcd(a, c), xe = a， ye = c :

gcd(a^b,c^d) = gcd(x^b * e^b,y^d * e^d) = e^b * gcd(x^b,y^d * e^(d−b))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define int long long
const int MOD = 998244353;

int qui(int a, int b, int MOD = MOD) {
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}

int dfs(int a, int b, int c, int d) {
    int ans = 1;
    int g = std::__gcd(a, c);
    if (g == 1) {
        return 1;
    }
    if (b > d) {
        ans = qui(g % MOD, d);
        int t = c / g;
        if (t == 1) {
            return ans;
        }
        return ans * dfs(a, b - d, t, d) % MOD;
    } else {
        ans = qui(g % MOD, b);
        int t = a / g;
        if (t == 1) {
            return ans;
        }
        return ans * dfs(t, b, c, d - b) % MOD;
    }
}

void solve() {
    int a, b, c, d;
    std::cin >> a >> b >> c >> d;
    int g = std::__gcd(a, c);
    int ans = dfs(a, b, c, d);
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) solve();
    return 0;
}

A、Loopy Laggon

把n * n的矩阵转化为一维数组处理， 顺时针旋转 90度就是 取两个数交换了 12次， 每次交换会使逆序对数量增减 奇数个， 旋转后逆序对奇偶性不变， 逆序对数量一定是偶数。如果被破坏过的一套玩具， 随便放的话， 有 1 / 2 的概率逆序对为奇数个， 所以如果一套玩具逆序对全是偶数个，那这套玩具被破坏的概率是 1 / 1024， 所以只要逆序对数量为 奇数个直接认为是被破坏的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define int long long

bool check(std::vector<int>& a) {
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        for (int j = i + 1; j < a.size(); j++) {
            if (a[i] > a[j]) cnt++;
        }
    }
    return (cnt & 1);
}

void solve() {
    int id, m, k, n;
    std::cin >> id >> m >> k >> n;
    std::vector<std::vector<std::vector<int>>> a(m, std::vector<std::vector<int>>(k, std::vector<int>(n * n)));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < k; j++) {
            for (int z = 0; z < n * n; z++) {
                std::cin >> a[i][j][z];
            }
        } 
    }
    std::string ans;
    for (int i = 0; i < m; i++) {
        int f = 0;
        for (int j = 0; j < k; j++) {
            if (check(a[i][j])) {
                f = 1;
                break;
            }
        }
        if (f) {
            ans += '1';
        } else {
            ans += '0';
        }
    }
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
//     std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}