2023 年 9 月做题笔记

未分類 0 Comments

升天，都高一了还在刷普及组题目是不是已经可以原地退役了啊。

「一本通 1676」手机游戏

一个简单二分，时间复杂度低于 O(n^2\log \text{(a big number)})，不是很正确但不好卡，能过就行（

一本通全过，校内数据最劣的点被卡到了 ~900ms 但是出数据的同学已经卡不动了（校内评测机神机！）

i64 life[100005]; // 怪物生命
i64 damage[100005]; // 怪物受到的伤害
inline bool check(const i64 each)
{
    memset(damage, 0, sizeof(i64) * (n + 1));
    int ball = 0;
    for (int i = n; i >= 1; i--) {
        if (damage[i] > life[i]) continue;
        int ball_thisround = (life[i] - damage[i]) / each + 1;
        ball += ball_thisround;
        if (ball > k) return false;
        if (ball_thisround == 0) continue;
        for (int j = i - 1; each - (i - j) * (i - j) > 0 && j >= 1; j--)
            damage[j] += ball_thisround * (each - (i - j) * (i - j));
    }
    return true;
}

void solve()
{
    i64 l = 1, r = 1e15;
    while (l < r) {
        i64 mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << '\n';
}

「APIO2009」抢掠计划

（洛谷 P3627）

跑一遍强连通分量缩个点然后 SPFA 跑最长路。不会 DAG 上 DP，大家都写就我不会。

i64 nw[500005]; // 缩点后点权和
char nb[500005]; // 缩点后这个点是否有出口

inline auto spfa()
{
    queue<int> q;
    fill(dis, dis + SCC_cnt + 1, 0x3f3f3f3f);
    q.push(scc[s]);
    // 确保点 p 是路径最长的出口点
    int p = (nb[scc[s]] ? scc[s] : 0);
    vis[scc[s]] = 1;
    dis[scc[s]] = nw[scc[s]];
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : ng[u]) {
            if (dis[v] > dis[u] + nw[v]) {
                dis[v] = dis[u] + nw[v];
                if (nb[v] && dis[v] < dis[p]) p = v;
                if (!vis[v]) vis[v] = 1, q.push(v);
            }
        }
        vis[u] = 0;
    }
    return dis[p];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        cin >> ow[i];
    cin >> s >> p;
    for (int i = 1; i <= p; i++) {
        cin >> u;
        bar[u] = 1;
    }
    // 跑强连通分量，不放板子了
    // 处理新点权
    for (int i = 1; i <= SCC_cnt; i++) {
        i64 sum = 0;
        bool flag = 0;
        for (int j : SCCs[i])
            sum += ow[j], flag |= bar[j];
        nw[i] = -sum;
        nb[i] = flag;
    }
    // 建边
    for (int u = 1; u <= n; u++) {
        for (auto v : g[u]) {
            if (scc[u] != scc[v])
                ng[scc[u]].push_back(scc[v]);
        }
    }
    fill(vis, vis + n + 1, 0);
    cout << -spfa() << '\n';
}

「CF1605D」Treelabeling

这个超有意思！

两个人在一棵树上做一个游戏，先手选择一个点 u，后手必须选择一个相邻且未被选择过的点 v 满足 u\oplus v \le \min(u,v)（这里 u 和 v 都是点的编号），两人轮流选择，选不了的对手获胜。

先手希望重新排列这棵树上的节点使得她可以选择尽可能多的点一步就获胜。

从 u\oplus v \le \min(u,v) 可以看出一个性质，只有 u 和 v 的二进制表示的最高位相同的情况下才可以选择。

那么只需要让相邻的点二进制最高位不一样就行。因为这是一棵树，因此考虑对树分层然后贪心构造；更近一步地，从根（钦定一个）出发，用 0 / 1 对树节点按层染色，那么只用保证不同颜色的节点编号最高位不一样就可以啦～

constexpr int lg(const int x) { return 31 - __builtin_clz(x); }

void dfs(int u, int fa)
{
    for (const auto& v : G[u]) {
        if (v == fa) continue;
        color[v] = color[u] ^ 1;
        dfs(v, u);
    }
}

inline void solve()
{
    int n, u, v;
    cin >> n;

    G = vector<vector<int>>(n + 1);
    vector<vector<int>> leg(lg(n) + 2);
    color = vector<int>(n + 1, 0);
    vector<int> ans(n + 1, -1);

    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        leg[lg(i)].push_back(i);

    dfs(1, 1);
    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i <= n; i++)
        if (color[i]) cnt1++;
        else cnt0++;
    for (int i = 1, j = 1, k = lg(n); k >= 0; k--) {
        if (cnt1 > cnt0)
            for (auto re : leg[k]) {
                while (color[i] == 0) i++;
                ans[i++] = re; cnt1--;
            }
        else
            for (auto re : leg[k]) {
                while (color[j] == 1) j++;
                ans[j++] = re; cnt0--;
            }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}

「BalticOI 2011 Day1」Treasures and Vikings

（洛谷 P4668）

不知道为啥能评到蓝

跑两次广搜，第一次处理出贼船到每个点的最短距离，然后处理每个点最早可以被贼船干掉的时间，第二次广搜处理出你到藏宝点的最短距离（如果到这个点的最短距离 大于等于 贼船最早干掉这个点的距离就相当于障碍）。

char mp[701][701];
int dis[701][701], fdis[701][701], shoot[705][701];
int n, m;

int delta_x[] = { 0, 0, 1, -1 };
int delta_y[] = { 1, -1, 0, 0 };

int tx, ty;

queue<pair<int, int>> q, fq;

int main()
{
    memset(dis, 0x3f, sizeof(dis));
    memset(fdis, 0x3f, sizeof(fdis));
    memset(shoot, 0x3f, sizeof(shoot));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 'V')
                q.push({ i, j }), dis[i][j] = 1;
            else if (mp[i][j] == 'Y')
                fq.push({ i, j }), fdis[i][j] = 1;
            else if (mp[i][j] == 'T')
                tx = i, ty = j;
        }
    }
    while (!q.empty()) {
        pair<int, int> p = q.front(); q.pop();
        int x = p.first, y = p.second;
        for (int t = 0; t < 4; t++) {
            int new_x = x + delta_x[t], new_y = y + delta_y[t];
            if (mp[new_x][new_y] == 'I' || dis[new_x][new_y] != 0x3f3f3f3f) continue;
            if (new_x < 1 || new_x > n || new_y < 1 || new_y > m) continue;
            dis[new_x][new_y] = dis[x][y] + 1;
            q.push({ new_x, new_y });
        }
    }

    for (int i = 1; i <= n; i++) {
        int last_j = 1, minn = INT_MAX;
        for (int j = 1; j <= m; j++) {
            minn = min(minn, dis[i][j]);
            if (mp[i][j] == 'I') {
                for (int k = last_j; k < j; k++)
                    shoot[i][k] = minn;
                minn = INT_MAX;
                last_j = j + 1;
            }
        }
        for (int j = last_j; j <= m; j++)
            shoot[i][j] = min(shoot[i][j], minn);
        minn = INT_MAX;
    }
    for (int j = 1; j <= m; j++) {
        int last_i = 1, minn = INT_MAX;
        for (int i = 1; i <= n; i++) {
            minn = min(minn, dis[i][j]);
            if (mp[i][j] == 'I') {
                for (int k = last_i; k < i; k++)
                    shoot[k][j] = min(shoot[k][j], minn);
                minn = INT_MAX;
                last_i = i + 1;
            }
        }
        for (int i = last_i; i <= n; i++)
            shoot[i][j] = min(shoot[i][j], minn);
    }

    while (!fq.empty()) {
        pair<int, int> p = fq.front(); fq.pop();
        int x = p.first, y = p.second, dist = fdis[x][y];
        for (int t = 0; t < 4; t++) {
            int new_x = x + delta_x[t], new_y = y + delta_y[t];
            if (mp[new_x][new_y] == 'I' || fdis[new_x][new_y] != 0x3f3f3f3f) continue;
            if (new_x < 1 || new_x > n || new_y < 1 || new_y > m) continue;
            if (shoot[new_x][new_y] <= dist + 1) continue;
            fdis[new_x][new_y] = dist + 1;
            fq.push({ new_x, new_y });
        }
    }
    if (fdis[tx][ty] == 0x3f3f3f3f)
        cout << "NO";
    else
        cout << "YES";
}

「洛谷 P5142」区间方差

单点改，区间查方差。

方差的式子动手脚：

\begin{aligned}
sum &= \sum_{i=1}^n a_i \\
s &= \frac{sum}{n} \\
\end{aligned}

\begin{aligned}
d &= \frac{1}{n} \sum_{i=1}^n (s – a_i)^2 \\
&= \frac{1}{n} \sum_{i=1}^n (s^2 + {a_i}^2 – 2s\cdot a_i) \\
&= \frac{1}{n}\times n\times s^2 + \frac{1}{n} \left(\sum_{i=1}^n {a_i}^2\right) – 2s\times\frac{1}{n} \left(\sum_{i=1}^n a_i\right) \\
&= s^2 – 2s\times \frac{sum}{n} – \frac{1}{n} \left(\sum_{i=1}^n {a_i}^2\right) \\
&= s^2 – 2s^2 + \frac{{\rm square_sum}(a)}{n} \\
&= -s^2 + \frac{{\rm square_sum}(a)}{n}
\end{aligned}

就会发现只用线段树维护区间和以及区间平方和就可以了。

「洛谷 P1471」方差

区间加，区间查方差/平均数。

怎样维护区间平方和呢？

\begin{aligned}
\sum_{i=l}^r (a_i + \Delta)^2
&= \sum_{i=l}^r ({a_i}^2 + \Delta^2 + 2a_i\Delta) \\
&= \sum_{i=l}^r {a_i}^2 + 2\Delta\sum_{i=l}^r a_i + (r – l + 1)\Delta^2
\end{aligned}

所以线段树的 pushdown 可以这么写：

inline void updlz(int p, double v)
{
    nd[p].lz += v;
    // cannot change order of operations
    nd[p].squaresum += (nd[p].rb - nd[p].lb + 1) * v * v + 2 * nd[p].sum * v;
    nd[p].sum += (nd[p].rb - nd[p].lb + 1) * v;
}

inline void pushdown(int p)
{
    if (nd[p].lz) {
        updlz(p << 1, nd[p].lz);
        updlz(p << 1 | 1, nd[p].lz);
        nd[p].lz = 0;
    }
}

注意一下这个题输入是实数，不是整数。

然后就做完了。

「ZJOI2009」狼和羊的故事

网络流题。

  • 源点 \to 狼，流量 \infty；
  • 羊 \to 汇点，流量 \infty；
  • 所有点向四周连边，流量 1。

然后跑最小割，狼和羊之间的边都被割掉了等价于修栅栏。

inline int nid(int x, int y) { return (x - 1) * m + y + 5; }
int vnd;

int main()
{
    cin >> n >> m;
    s = 0, t = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> w;
            switch (w) {
            case 1:
                addedge(s, nid(i, j), INT_MAX);
                break;
            case 2:
                addedge(nid(i, j), t, INT_MAX);
                break;
            }
            if (i > 1) addedge(nid(i, j), nid(i - 1, j), 1);
            if (i < n) addedge(nid(i, j), nid(i + 1, j), 1);
            if (j > 1) addedge(nid(i, j), nid(i, j - 1), 1);
            if (j < m) addedge(nid(i, j), nid(i, j + 1), 1);
        }
    }
    cout << maxflow() << "\n";
    return 0;
}

「洛谷 P1283」平板涂色

预处理出每个方格染色时上方所依赖的方格。

然后深搜，剪枝。最优化剪枝，答案超了当前最优就剪掉。

inline bool check(int x)
{
    for (auto x : up[x]) if (!vis[x]) return false;
    return true;
}

void dfs(int cnt, int sum, int u)
{
    if (cnt == n) {
        ans = min(ans, sum);
        return;
    }
    if (sum >= ans) return;
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && check(i)) {
            vis[i] = 1;
            dfs(cnt + 1, sum + (gd[u].color != gd[i].color), i);
            vis[i] = 0;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> gd[i].x1 >> gd[i].y1 >> gd[i].x2 >> gd[i].y2 >> gd[i].color;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && gd[i].x1 == gd[j].x2 && (gd[i].y2 >= gd[j].y1 && gd[i].y1 <= gd[j].y2))
                up[i].push_back(j);
        }
    }
    dfs(0, 0, 0);
    cout << ans << '\n';
}

「USACO11OPEN」Mowing the Lawn G

（洛谷 P2627）

今年第三次在赛时遇到这个原题了 搬题人有没有新意 就是个 DP + 单调队列优化……

for (int i = 1; i <= n; i++) {
    cin >> bore[i];
    pf[i] = pf[i - 1] + bore[i];
}
deque<int> q;
for (int i = 1; i <= n; i++) {
    // 原 DP 方程
    // for (int j = i - k; j <= i; j++) {
    //  dp[i] = max(dp[i], dp[j - 1] + sum(j + 1, i));
    // }
    dt[i] = dp[i - 1] - sum(1, i);
    if (i <= k) {
        dp[i] = sum(1, i);
        while (!q.empty() && dt[q.back()] < dt[i])
            q.pop_back();
        q.push_back(i);
        continue;
    }
    while (!q.empty() && q.front() < i - k)
        q.pop_front();
    while (!q.empty() && dt[q.back()] < dt[i])
        q.pop_back();
    q.push_back(i);
    dp[i] = dt[q.front()] + sum(1, i);
}
cout << *max_element(dp + 1, dp + n + 1) << endl;

「CF1878A」How Much Does Daytona Cost?

  • 确定 k 且 k 出现次数最多的子段是否存在。
  • 子段长度可以为 1 因此只要在原数组中出现 k 即可满足条件。
  • 判一下 k 有没有在原数组中出现过就行。

「CF1878B」Aleksa and Stack

构造题。有好几个结论，我的结论是首项 1 公差 3 的等差序列一定满足条件。

「CF1878C」Vasilije in Cacak

  • 给定 n, k, x，确定能否选择 [1, n] 中的 k 个数加和为 x。
  • 不难发现，如果 x\ge \sum_{i=1}^k i 且 x\le \sum_{i=n-k+1}^n i 那么必然可以选择 k 个数字加和为 x。
  • 用等差数列进行特判即可。

「CF1878D」Reverse Madness

二分出 x 对应的 l_i, r_i 然后用文艺平衡树维护区间翻转。

cin >> x;
int c = upper_bound(l.begin(), l.end(), x) - l.begin() - 1;
splay.reverse(min(r[c] + l[c] - x, x), max(r[c] + l[c] - x, x));

「CF1878E」Iva & Pav

给定序列 a，和 q 次查询，每次查询包含 l, k，要求找到一个最小的 r 使得 [l, r] 的区间按位与的结果不小于 k。

写一棵线段树处理区间按位与的结果，注意到按位与运算对答案的贡献是单调不下降的，因此可以二分出对应的 r。

时间复杂度 O(n\log^2 n) 可以通过本题的 5 秒时限。

cin >> p >> k;
int l = p, r = n;
if (segt.query(l, l) < k) {
    cout << "-1 ";
    continue;
}
while (r - l > 3) {
    int mid = (l + r) >> 1;
    if (segt.query(p, mid) >= k) {
        l = mid;
    else
        r = mid - 1;
}
// 我恨二分边界
for (int res = r; res >= l; res--) {
    if (segt.query(p, res) >= k) {
        cout << res << ' ';
        break;
    }
}