A、九峰与签到题

使用set把过程中全部低于50通过率的题目统计一下就行了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

struct Node {
    ll val;
    int id;
    bool operator < (const Node& opt) const {
        return val < opt.val;
    }
};

ll n, m;
int ac[N], sub[N];
void solve() {
    js;
    cin >> m >> n;
    string s;
    int id;
    set<int> st;
    while (m--) {
        cin >> id >> s;
        if (s == "AC")    ++ac[id];
        ++sub[id];
        if (!st.count(id) and ac[id] < (sub[id] + 1) / 2)    st.insert(id);
    }
    if (st.size() == n)    cout << "-1";
    else {
        rep(i, 1, n) {
            if (st.count(i) == 0)
                cout << i << " ";
        }
    }
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

J、邬澄瑶的公约数

发现我们要找到的全部数的,那么我们把全部的数分解质因数，拿到全部的因子。
我们知道数可以分成
我们使用两个计数器，分别统计在不同中质数的出现次数，以及出现的幂次。那么如果一个质数一共出现 n 次我们才能在中拿到这个质数，并且贡献就是出现幂次最小的哪个。

const int N = 1e4 + 7;
vector<int> prime;
bool vis[N];
void getprime() {
    vis[1] = 1;
    rep(i, 2, N - 1) {
        if (!vis[i])    prime.push_back(i);
        for (auto& it : prime) {
            if (it * i >= N) break;
            vis[it * i] = 1;
            if (i % it == 0)    break;
        }
    }
}

ll n, m;
ll x[N], p[N];
void solve() {
    n = read();
    rep(i, 1, n)    x[i] = read();
    rep(i, 1, n)    p[i] = read();
    map<int, ll> mp1, mp2;
    rep(i, 1, n) {
        ll tmp = x[i];
        for (auto& it : prime) {
            if (it > tmp)    break;
            if (tmp % it == 0) {
                ++mp1[it];
                int cnt = 0;
                while (tmp % it == 0)
                    ++cnt, tmp /= it;
                if (mp2.count(it))  mp2[it] = min(mp2[it], cnt * p[i] % MOD);
                else mp2[it] = cnt * p[i] % MOD;
            }
        }
    }
    ll ans = 1;
    for (auto& it : prime) {
        if (!mp1.count(it)) continue;
        if (mp1[it] != n)   continue;
        ans = ans * qpow(it, mp2[it], MOD) % MOD;
    }
    print(ans);
}

B、武辰延的字符串

字符串匹配我们有hash办法做到。
那么对于给出的字符串S和T，我们枚举他们公共前缀，接下来还需要使用另一个S的前缀拼接到后面和T一致。比如我们看

aaab
aabb

1、我们枚举第一个字符串就选a，那么接下来就要判断第二个字符串除掉a也就是剩下abb
和第一个字符串最长的匹配长度是多少，显然只能是1，因为a+a=a+a,a+aa!=a+ab
2、我们枚举第一个字符串选aa，接下来去找第二个字符串除掉aa剩下的和第一个字符串
的最长公共前缀，显然答案是0，因为只有aa=aa，aa+a!=aa+b
3、我们枚举第一个字符串选aaa，因为第二个字符串aab!=aaa，所以后面都不需要枚举了，直接退出即可

我们发现只需要判断长度，具有单调性，使用二分优化。时间复杂度就可以到。
当然如果你学会了exkmp，你会发现它就是干这个事的，它的next数组就是求得和前面串的最长公共前缀长度，直接累加一下就是答案了，时间复杂度可以优化到。

ll n, m;
char s1[N], s2[N];
ull has1[N], has2[N], p[N], bas = 131;

ull query1(int l, int r) {
    return has1[r] - has1[l - 1] * p[r - l + 1];
}
ull query2(int l, int r) {
    return has2[r] - has2[l - 1] * p[r - l + 1];
}

void solve() {
    scanf("%s %s", s1 + 1, s2 + 1);
    p[0] = 1;
    rep(i, 1, N - 1)    p[i] = p[i - 1] * bas;
    n = strlen(s1 + 1);
    m = strlen(s2 + 1);
    rep(i, 1, n)
        has1[i] = has1[i - 1] * bas + (s1[i] - 'a');
    rep(i, 1, m)
        has2[i] = has2[i - 1] * bas + (s2[i] - 'a');
    ll ans = 0;
    rep(i, 1, n) {
        if (s1[i] != s2[i])    break;
        int l = i + 1, r = m, res = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            ull a = query1(1, mid - i);
            ull b = query2(i + 1, mid);
            if (a == b)    res = mid - i, l = mid + 1;
            else r = mid - 1;
        }
        ans += res;
    }
    print(ans);
}

G、九峰与蛇形填数

发现每次后面的会覆盖前面的，说明前面填的数后面又填了，那么前几次都是无用功。
那么我们从后往前遍历输入的填数顺序，使用一个数组记录答案，一个数组记录位置下一个没填的在什么地方。这样就可以保证每个位置最多遍历一遍。复杂度有

const int N = 2000 + 7;
const int M = 3000 + 7;

ll n, m;
int s[N][N];
int l[N][N];
int p[4][M];

void solve() {
    n = read(), m = read();
    rep(i, 1, m)
        rep(j, 1, 3)    p[j][i] = read();
    repp(i, m, 1) {
        int sti = p[1][i], stj = p[2][i];
        int edi = sti + p[3][i] - 1, edj = stj + p[3][i] - 1;
        rep(j, sti, edi) {
            rep(k, stj, edj) {
                int x;
                if ((j - sti) & 1)    x = (j - sti + 1) * p[3][i] - (k - stj);
                else