A 寻找最大值

暴力找最大值及其位置

1. 最大值在 1 处 -> ans = 0

2. 最大值不在 1 处 -> ans = 最大值 - a[1] + 1

#include <bits/stdc++.h>
using namespace std;

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int n, maxn, id, a[105];

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        if (a[i] >= maxn)
        {
            id = i;
            maxn = a[i];
        }
    }
    if (id == 1)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << maxn - a[1] + 1 << endl;
    }
    return 0;
}

B 入度判断

暴力判断入度为 0 的位置个数即可

#include <bits/stdc++.h>
using namespace std;

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int ru[100005];

int main()
{
    int n = read(), m = read();
    for (int i = 1; i <= m; i++)
    {
        int a = read(), b = read();
        ru[b]++;
    }
    int ans = 0, id = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ru[i] == 0)
        {
            ans++;
            id = i;
        }
    }
    if (ans == 1)
    {
        cout << id << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

C 平均数问题

设 $sum$ = $\Sigma a_i$

若 $sum$ % $n == 0$

$ans = \Sigma abs(sum / n - a_i)$

若不是

$ans = \Sigma^{n - (sum \mod n)}_{i=1} abs(sum / n - a_i) + $

$\Sigma^{n}_{i = n - (sum \mod n) + 1} abs(sum / n - a_i)$

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int a[1000005];

signed main()
{
    int n = read(), sum = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        sum += a[i];
    }
    int pj = sum / n, ans = 0;
    if (sum % n == 0)
    {
        for (int i = 1; i <= n; i++)
        {
            ans += abs(pj - a[i]);
        }
    }
    else
    {
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n - sum % n; i++)
        {
            ans += abs(pj - a[i]);
        }
        for (int i = n - sum % n + 1; i <= n; i++)
        {
            ans += abs(pj + 1 - a[i]);
        }
    }
    cout << ans / 2 << endl;
    return 0;
}

D 交互+构造+简单动脑筋

先处理出 $(\Sigma^{k - 1}_{i = 1}i)+j$ 的奇偶性（$j$在$[k,n]$中）

再算 $(\Sigma^{k+1}_{i = 1}i)-j$ 的奇偶性（$j$在$[1,k-1]$中）

最后再暴力处理关系即可

#include<bits/stdc++.h>
using namespace std;

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int n, k, p, v[1005], ans, cnt;

int main()
{
    n = read(), k = read();
    for (int i = k; i <= n; i++)
    {
        cout << "? ";
        for (int j = 1; j < k; j++)
        {
            cout << j << " ";
        }
        cout << i << endl;
        p = read();
        v[i] = p;
    }
    for (int i = 1; i < k; i++)
    {
        cout << "? ";
        for (int j = 1; j < i; j++)
        {
            cout << j << " ";
        }
        for (int j = i + 1; j <= k + 1; j++)
        {
            cout << j << " ";
        }
        cout << endl;
        p = read();
        if (p != v[k])
        {
            v[i] = 1 - v[k + 1];
        }
        else
        {
            v[i] = v[k + 1];
        }
    }
    for (int i = 1; i <= k; i++)
    {
        cnt += v[i];
    }
    if (cnt % 2 != v[k])
    {
        ans = 1;
    }
    cout << "! ";
    for (int i = 1; i <= n; i++)
    {
        cout << (v[i] + ans) % 2 << " ";
    }
    return 0;
}

E 简单动脑筋

打着字符串的幌子却啥也不是（三无产品：无思维，无码量，无科技）

1. 不合法情况：存在连续两个不等于 1 的数

2. 若合法，计算每个数的贡献 $sum = (s[i] - '0' - 1) * ans + 1$（$ans$ 一直在变，相当于递推），最后输出 $ans$

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read()
{
    int f = 1, k = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        k = k * 10 + c - '0';
        c = getchar();
    }
    return f * k;
}

int n;

string s;

const int mod = 998244353;

signed main()
{
    n = read();
    cin >> s;
    int len = s.size(), ans = 1;
    for (int i = 1; i < len; i++)
    {
        if (s[i] != '1')
        {
            if (s[i - 1] != '1')
            {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    for (int i = len - 1; i >= 1; i--)
    {
        ans = (ans + (s[i] - '0' - 1) * ans + 1) % mod;
    }
    cout << ans - 1 << endl;
    return 0;
}