庆祝上分！
Div.3 果然是信心赛！

A

找到若干个数中与众不同的一个

水题。

记个数或者排个序都可以。

B

输入一个图形，标记了矩形的其中两个端点，求剩下俩端点。

分类讨论补全，注意细节。

C

输入一个字符串，用 1 或 0 填充 ?, 使回文且恰好 $a$ 个 0, $b$ 个 1

注意得先把确定的都填完，然后能填哪个就填哪个就可以了。

开始没注意要先把确定的都填完， WA 了两次。

代码。

#include <cstdio>
#include <cstring>
const int N = 200005;
int T, a, b;
char st[N];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &b, &a);
        scanf("%s", st+1);
        int n = strlen(st+1);
        for(int i = 1; i <= n; i++)
            if(st[i] == '1') a--;
            else if(st[i] == '0') b--;
        bool flag = 0;
        // printf("%d %d %d\n", b, a, flag);
        for(int i = 1; i <= n/2; i++) {
            if(st[i] != '?' && st[n-i+1] != '?') {
                if(st[i] != st[n-i+1]) {
                    flag = 1;
                    break;
                }
                else continue;
            }
            if(st[i] == '1') a -= 1, st[n-i+1] = '1';
            else if(st[n-i+1] == '1') a -= 1, st[i] = '1';
            else if(st[i] == '0') b -= 1, st[n-i+1] = '0';
            else if(st[n-i+1] == '0') b -= 1, st[i] = '0';
        }
        for(int i = 1; i <= n/2; i++) {
            if(st[i] == '?' && st[n-i+1] == '?') {
                if(a > 1) a -= 2, st[i] = st[n-i+1] = '1';
                else b -= 2, st[i] = st[n-i+1] = '0';
            }
        }
        if(n % 2 == 1 && st[n/2+1] == '?')     
            if(a) a--, st[n/2+1] = '1';
            else st[n/2+1] = '0', b--;
        if(flag || a != 0 || b != 0) puts("-1");
        else printf("%s\n", st+1);
    }
    return 0;
}

D

不告诉你 $A$, 只知道有 $B$, 前 $n$ 个 $b_i = a_i$, 最后俩一个是前面数的和，另一个是随便写的，求一个可能的 $a$。

和肯定是最大的嘛！所以记一个最大和次大就好了。

E

求出一个 $n$ 的排列使 $\sum_{i=l}^r p_i = s$

那么只要求出 $r-l+1$ 个小于等于 $n$ 的不同数恰好为 $s$, 然后随便填就可以了。

拼只需要让前 $r-l$ 个是 $1\rightarrow (r-l)$, 然后慢慢调整就可以了。

具体地：

1. 排完后若最后一个数比 $n$ 小那直接上。
2. 否则，前面 $r-l$ 个能统一加的就加
3. 加完 1 的还有剩下就从 $r-l$ 个开始往前一个个加。
4. 若有冲突就不成立。

这样的做法保证了倒数俩的距离尽可能大，同时满足条件，如果还得冲突，那肯定不行。

同样要注意细节，以及 $r = l$ 时要特殊处理。

代码。

#include <cstdio>
#include <cstring>
int T, n, l, r, s, flag[505], a[505];
int main() {
    scanf("%d", &T);
    while(T--) {
        memset(flag, 0, sizeof flag);
        scanf("%d%d%d%d", &n, &l, &r, &s);
        int len = r - l + 1;
        if(s < (1+len) * len / 2 || (n-len+1+n) * len / 2 < s) { 
            puts("-1");
            continue;
        }
        bool twt = 0;
        if(len != 1) {
            int sum = 0;
            for(int i = 1; i < len; i++) a[i] = i, sum += i;
            sum = s - sum - n;
            // printf("%d\n", sum);
            int delta = sum / (len - 1);
            if(sum > 0) {
                for(int i = 1; i < len; i++) a[i] += delta;
                sum -= sum / (len-1) * (len-1);
            }
            for(int i = len-1; i >= 1 && sum > 0; i--, sum--) a[i] ++;
            a[len] = n;
            if(sum < 0) {
                while(sum < 0) a[len]--, sum++;
            }
            for(int i = 1; i <= len; i++) flag[a[i]] ++;
        }
        else if(s > n) twt = 1;
        else flag[s] = 1, a[1] = s;
        for(int i = 1; i <= n; i++)         
            if(flag[i] > 1) twt = 1;
        if(twt) {
            puts("-1");
            continue;
        }
        int now = 1;
        for(int i = 1; i < l; i++) {
            while(flag[now]) now++;
            printf("%d ", now);
            now ++;
        }
        for(int i = 1; i <= len; i++) printf("%d ", a[i]);
        for(int i = r+1; i <= n; i++) {
            while(flag[now]) now++;
            printf("%d ", now);
            now ++;
        }
        puts("");
    }
    return 0;
}

F

开始有 $0$ 元，有 $n$ 级，第 $i$ 级每天可领取 $a_i$ 元或花费 $b_i$ 升级， $A$ 单调递增。最少几天总钱数大于等于 $c$

那要升级肯定是早升更好，所以直接枚举最后到哪级，算出答案取 $\min$ 就好了。

#include <cstdio>
#include <algorithm>
#define int long long
const int N = 200005;
int T, n, c, a[N], b[N], ans;
signed main() {
    scanf("%lld", &T);
    while(T--) {
        scanf("%lld%lld", &n, &c);
        ans = 0x3f3f3f3f3f3f3f3fll;
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for(int i = 1; i < n; i++) scanf("%lld", &b[i]);
        int now = 0, nd = 0;
        for(int i = 1; i <= n; i++) {
            ans = std::min(ans, nd + (c - now + a[i]-1) / a[i]);
            int d = (b[i] - now + a[i]-1) / a[i];
            // printf("*%lld %lld %lld %lld\n", ans, d, now, nd);
            now = now + d * a[i] - b[i], nd += d+1; // 注意升级也要天数。
        }
        printf("%lld\n", ans);
    }
}

G

唯一有真正难度的一题。

数论题。

$d(n) = \sum_{k|n} k$ 求最小 $n$ 使 $d(n) = c$

这玩意儿居然有积性。

欧拉筛一遍二分即可。

但赛场上没时间也想不到。

好好看 《初等数论》 吧。