20230703测试

A

我不打了，但是考场上没想起来排列 stl 怎么写，所以在下面打 10 遍

next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation

你可以数一下，一共有 11 遍

B

\([1,1000]\)

典，对于这类数字和的题，直接考虑拆位处理，预处理一下就可以了

const int maxN = 1000 + 10;
int n;
string s[maxN];
int a[maxN][maxN];
int pre[maxN];
void solve(){
    cin >> n;
    fp(i, 1, n) cin >> s[i];
    fp(i, 1, n) fp(j, 1, n) a[i][j] = s[i][j - 1] - '0';
    int num = 1;
    pre[0] = 1;
    fp(i, 1, n) {
        (num *= 10) %= mod;
        pre[i] = (pre[i - 1] + num) % mod;
    }
    int ans = 0;
    fp(i, 1, n) {
        fp(j, 1, n) {
            int x = (a[i][j] * pre[n - i]) % mod;
            (x *= i) % mod;
            (ans += x) %= mod;
            x = (a[i][j] * pre[n - j]) % mod;
            (x *= j) % mod;
            (ans += x) %= mod;
        }
    }
    cout << ans << endl;
}

C

\(n\in [1,20]\)

讲个笑话，老师发的代码过不去第一个样例……
还有个笑话，有个写了 D 的人 C 过不去

考场上想贪心想到头疼，正解是 DP ……
所以告诉我们，贪心没有正确性时，可以考虑 DP

一眼状压，但是我们不能直接枚举最终状态，考虑转移

我们目前已经将一些水杯中的水倒到了其他水杯中，然后考虑继续转移，可以将一杯水倒到另一个非空的杯子里进行更新

所以做完了

我是煞笔

const int maxN = 100, N = 1e7;
int n, m;
int f[N];
int c[maxN][maxN];
int popcount(int now) {
    int sum = 0;
    while (now) sum++, now -= (now & -now);
    return sum;
}
void solve(){
    n = rd(), m = rd();
    fp(i, 1, n) fp(j, 1, n) c[i][j] = rd();
    memset(f, 0x3f, sizeof(f));
    if (m == n) {
        cout << 0 << endl;
        return ;
    }
    f[0] = 0;
    int ans = inf;
    fp(i, 1, (1 << n) - 1){  // black is k
        fp(j, 1, n) 
            if (i & (1 << (j - 1)))   // j to k
                fp(k, 1, n) 
                    if (!(i & (1 << (k - 1)))) 
                        f[i] = min(f[i], f[i ^ (1 << (j - 1))] + c[j][k]);
        if (popcount(i) == n - m)
            ans = min(ans, f[i]);
    }
    cout << ans << endl;
}

D

\(1e5\)

不太难

很明显，有重复的只可能出现在投票的组之中，可以对投票的组算一下每个人会有多少对重复的组，然后减出来就可以了

const int maxN = 1e5 + 10;
int n, m;
pii a[maxN],ts[maxN],mat[maxN]c[maxN];
map<pii, int> vis, mp;

inline int lowbit(int x) { return x & -x; }
inline void add(int wh) {for (; wh <= n; wh += lowbit(wh)) c[wh]++;}
inline int query(int x) {
    if (x <= 0) return 0;
    int sum = 0;
    while (x) sum += c[x], x -= lowbit(x);
    return sum;
}
void solve(){
    cin >> n >> m;
    fp(i, 1, n) {
        cin >> a[i].first >> a[i].second;
        ts[a[i].first]++, ts[a[i].second]++;
        mp[a[i]]++;
        mp[{a[i].second, a[i].first}]++;
    }
    fp(i, 1, n) {
        if (vis[a[i]] || vis[{ a[i].second, a[i].first }]) continue;
        vis[a[i]] = 1;
        int x = a[i].first, y = a[i].second;
        if (ts[x] + ts[y] - mp[a[i]] < m)
            if (ts[x] + ts[y] >= m) 
                mat[x]++, mat[y]++;
    }
    fp(i, 1, n) add(ts[i] + 1);
    int p = 0;
    fp(i, 1, n) {
        int sum = ts[i];
        int k = n - query(m - sum);
        if (ts[i] * 2 >= m) k--;
        p += k - mat[i];
    }
    cout << p / 2 << endl;
}