2023 ICPC NANJING

A

数据范围很小,可以每一对跑bfs原因是如果有一个没有掉下去,那就可以回到原来了位置,所以可以暴力去实现这个问题

using namespace std;
#define MAX 1005
int n, m, ans;
char s[MAX + 10];
vector<string> MAP;
int vis[MAX * MAX + 10];
bool flag[MAX * MAX + 10];

int gao(int i, int j, int r, int c) {
    return i * m * n * m + j * n * m + r * m + c;
}

void ungao(int msk, int &i, int &j, int &r, int &c) {
    i = msk / (m * n * m);
    j = msk / (n * m) % m;
    r = msk / m % n;
    c = msk % m;
}

bool fall(int i, int j) {
    return i < 0 || j < 0 || i >= n || j >= m || MAP[i][j] == 'O';
}

short dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void bfs(int S) {
    queue<int> q;
    q.push(S);
    vis[S] = S;
    flag[S] = false;
    while (!q.empty()) {
        int i, j, r, c;
        ungao(q.front(), i, j, r, c);
        q.pop();
        for (int k = 0; k < 4; k++) {
            int ii = i + dir[k][0], jj = j + dir[k][1];
            int rr = r + dir[k][0], cc = c + dir[k][1];
            if (fall(ii, jj)) {
                continue;
            }
            if (fall(rr, cc)) {
                flag[S] = true;
                continue;
            }
            int nxt = gao(ii, jj, rr, cc);
            if (vis[nxt] >= 0) {
                continue;
            }
            q.push(nxt);
            vis[nxt] = S;
        }
    }
}

int check(int i, int j) {
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (MAP[r][c] == '.') {
                if (i == r && j == c) {
                    continue;
                }
                int msk = gao(i, j, r, c);
                if (vis[msk] == -1) {
                    bfs(msk);
                }
                if (!flag[vis[msk]]) {
                    return 0;
                }
            }
        }
    }
    return 1;
}

void solve()
{
    //IOS;
    cin >> n >> m;
    MAP.clear();
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        MAP.push_back(string(s));
    }
    memset(vis, -1, sizeof(int) * (n * m * n * m + 3));
    ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (MAP[i][j] == '.') {
                ans += check(i, j);
            }
        }
    }
    cout << ans << endl;

}

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

C

所有小于等于m的数可以根据与m最长公共前缀的长度分成60种.

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

long long P, m, ans;

// 求 0 <= kP + 1 <= x 的 k 的数量
long long calc(long long x) {
    x--;
    if (x < 0) return 0;
    else return x / P + 1;
}

// 求 L <=> kP + 1 <= R 的 k 的数量
long long calc(long long L, long long R) {
    return calc(R) - calc(L - 1);
}

void solve() {
    scanf("%lld%lld", &P, &m);
    ans = 0;
    // 枚举与 m 的最长公共前缀
    for (int i = 60; i >= 0; i--) if (m >> i & 1) {
        // 计算 kP + 1 的上下界
        long long L = m >> i ^ 1;
        L ^= (P - 1) >> i;
        L <<= i;
        long long R = L + (1LL << i) - 1;
        // 求特定范围内 k 的数量
        ans += calc(L, R);
    }
    // 别忘了 m 本身也要算
    ans += calc(m ^ (P - 1), m ^ (P - 1));
    printf("%lld\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

F

如果交换任意两个相邻元素都无法得到新的合法拓扑序，说明G依赖关系至少是一条从1到n的链,即拓扑序唯一。

所以就好求了

include <bits/stdc++.h>
#define MAXN ((int) 1e5)
#define MAXM ((int) 1e5)
using namespace std;

int n, m;

// last[i]：最后修改位置 i 的操作
int last[MAXM + 10];
// OP[i]：操作 i 改了哪些位置
unordered_set<int> OP[MAXN + 10];
// flag[i]：操作 i - 1 到 i 是否有一条连边
bool flag[MAXN + 10];

void solve() {
    scanf("%d%d", &n, &m);
    memset(last, 0, sizeof(int) * (m + 3));
    for (int i = 1; i <= n; i++) OP[i].clear();
    memset(flag, 0, sizeof(bool) * (n + 3));

    for (int i = 1; i <= n; i++) {
        int p; scanf("%d", &p);
        for (int j = 1; j <= p; j++) {
            int x; scanf("%d", &x);
            last[x] = i;
            OP[i].insert(x);
        }
    }

    // 只有修改每个位置的最后一次操作可能与前面的操作有连边
    // 枚举每个位置，并检查最后一次操作
    for (int i = 1; i <= m; i++) if (last[i] > 1)
        // 如果 last[i] - 1 也改了位置 i，则两个操作之间有连边
        if (OP[last[i] - 1].count(i)) flag[last[i]] = true;

    int ans = 0;
    // 寻找没有与上一个操作连边的操作
    for (int i = 2; i <= n; i++) if (!flag[i]) { ans = i; break; }
    if (ans > 0) {
        printf("Yes\n");
        for (int i = 1; i <= n; i++) {
            if (i == ans - 1) printf("%d", ans);
            else if (i == ans) printf("%d", ans - 1);
            else printf("%d", i);
            printf("%c", "\n "[i < n]);
        }
    } else {
        printf("No\n");
    }
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

G

按重量大小排序,选k个价值最大的,其他的用背包

#include <bits/stdc++.h>
#define MAXN ((int) 1e4)
#define MAXM ((int) 2e4)
#define INF ((long long) 1e18)
using namespace std;
typedef pair<int, int> pii;

int n, m, K;
pii A[MAXN + 10];
long long ans;

// f[i]：计算背包问题的滚动数组
// g[i]：从第 i 个物品开始的后缀免费选出 K 个物品的最大价值之和
long long f[MAXM + 10], g[MAXN + 10];

int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= n; i++) scanf("%d%d", &A[i].first, &A[i].second);
    sort(A + 1, A + n + 1);

    long long sm = 0;
    g[n + 1] = 0;
    // 利用堆算出每个后缀选出免费物品的最大价值之和
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = n; i > 0; i--) {
        pq.push(A[i].second);
        sm += A[i].second;
        if (pq.size() > K) {
            sm -= pq.top();
            pq.pop();
        }
        g[i] = sm;
    }

    for (int i = 0; i <= m; i++) f[i] = -INF;
    f[0] = 0;
    // 答案的初始值：只买免费物品
    ans = g[1];
    // 用滚动数组计算背包问题
    for (int i = 1; i <= n; i++) for (int j = m; j >= A[i].first; j--) {
        f[j] = max(f[j], f[j - A[i].first] + A[i].second);
        // 计算分界点在 i 的情况下的答案
        ans = max(ans, f[j] + g[i + 1]);
    }
    printf("%lld\n", ans);
    return 0;
}

I

纯签到，队友还能wa一发

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

int n;

void solve() {
    scanf("%*d%d", &n);

    // mp[L] 表示 L 是一个清零操作，且从 L + 1 到 mp[L] 都是加一操作
    map<int, int> mp;
    bool failed = false;
    for (int i = 1; i <= n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        // 计数器的值不能比操作数还大
        if (y > x) failed = true;
        // 记录必须是清零操作的位置，以及加一操作的区间
        int &t = mp[x - y];
        t = max(t, x);
    }
    if (failed) { printf("No\n"); return; }

    // R 表示清零操作的“禁区”的最右端
    int R = -1;
    for (auto &p : mp) {
        // 需要在“禁区”里执行清零操作，无解
        if (R >= p.first) { printf("No\n"); return; }
        // 更新“禁区”的最右端
        R = p.second;
    }
    printf("Yes\n");
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

L

可以将2劈成两个1

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n;
long long K, ans;
vector<pii> A;

void solve() {
    scanf("%d%lld", &n, &K);

    A.clear();
    for (int i = 1; i <= n; i++) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        // 把所有大小为 2 的包裹拆成两个大小为 1 的包裹
        A.push_back(pii(-z, x * y));
    }
    // 按楼层从高到低排序
    sort(A.begin(), A.end());

    ans = 0;
    // now：这一趟电梯的最高楼层
    // sm：现在电梯里已经放了多少包裹
    long long now = -A[0].first, sm = 0;
    // 依次处理每种包裹
    for (pii p : A) {
        sm += p.second;
        // 新包裹的加入导致电梯里放了超过 K 个包裹
        if (sm > K) {
            ans += now;
            now = -p.first;
            sm -= K;

            // 用除法快速处理同一种包裹
            // 这里分子是 sm - 1，是为了防止 sm % K == 0 的情况，导致 now 的值出错
            long long t = (sm - 1) / K;
            ans += now * t;
            sm -= t * K;
        }
    }
    ans += now;

    printf("%lld\n", ans);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

不这么做就是铜牌的题目银牌的码量