最近懒死了，所以没有更新太多博客。在这里做一个小的集合吧。

「雅礼集训 2017 Day8」共

这题好屌。如果我们要搞一颗这样的树，使得 \(k\) 个点的深度都为奇数，那么我们完全可以放到二分图上去做：二分图中不存在奇环，所以我们可以把深度奇、偶的点放在两部，做一遍这个图的生成树计数即可。那么，「完全二分图」的生成树计数结论是 \(n^{m – 1}m^{n – 1}\)，证明：BZOJ4766: 文艺计算姬（Prufer序列） 题

「雅礼集训 2017 Day8」爷

看题解的时候被震惊到：还真特么是分块题。考虑在 DFS 序上做分块，然后标记维护。对于询问，我们可以二分答案来确定第 \(k\) 小；对于修改，就用分块的基本操作即可。对于查找区间内有多少个数小于等于 \(mid\)，如果用 lower_bound，时间复杂度会来到 \(\Theta(\sqrt{n}n\log n \log \sqrt{n}\)，会超时（比赛的时候我写的是这种，亲测有 70 分）。我们发现 \(len\) 很小，所以我们可以直接开个数组记录，并且定期重构。

「雅礼集训 2017 Day5」珠宝

一道很棒的背包+决策单调性题。单调性：我们发现这个 \(c_i\) 很小，所以我们可以把同代价的物品按价值从大到小排序，然后发现越往后选所带来的价值越小。解决这个问题之后，我们可以把转移进行分类：在模域 \(c_i\) 下，枚举取模后的价值 \(w\)，然后再枚举源位置，也就是使得 \(w’ \bmod c_i \equiv w\) 的所有 \(w’\)。这个过程比较调和级数。具体看代码，我觉得这个模域分类进行批量转移的操作很屌。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_K = 50010;
typedef long long ll;

int n, k, max_price, pos[MAX_K], ptot;
vector<ll> store[330];
ll dp[330][MAX_K];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

void solve(int idx, int l, int r, int LB, int RB)
{
    if (LB > RB)
        return;
    int mid = (LB + RB) >> 1, gpt = l;
    for (int i = max(l, int(mid - store[idx].size())); i <= min(mid, r); i++)
        if (dp[idx][pos[mid]] < dp[idx - 1][pos[i]] + (i == mid ? 0 : store[idx][mid - i - 1]))
            gpt = i, dp[idx][pos[mid]] = dp[idx - 1][pos[i]] + (i == mid ? 0 : store[idx][mid - i - 1]);
    solve(idx, l, gpt, LB, mid - 1), solve(idx, gpt, r, mid + 1, RB);
}

int main()
{
    n = read(), k = read();
    for (int i = 1, c, v; i <= n; i++)
        c = read(), v = read(), store[c].push_back(v), max_price = max(max_price, c);
    for (int i = 1; i <= max_price; i++)
    {
        sort(store[i].begin(), store[i].end());
        reverse(store[i].begin(), store[i].end());
        for (int j = 1, siz = store[i].size(); j < siz; j++)
            store[i][j] += store[i][j - 1];
    }
    for (int price = 1; price <= max_price; price++)
        for (int start_pos = 0; start_pos < price; start_pos++)
        {
            ptot = 0;
            for (int i = start_pos; i <= k; i += price)
                pos[++ptot] = i;
            solve(price, 1, ptot, 1, ptot);
        }
    for (int i = 1; i <= k; i++)
        printf("%lld ", dp[max_price][i]);
    putchar('\n');
    return 0;
}

[CERC2017]Gambling Guide

这题的转移模型比较经典，用最短路算法进行转移的方式。我们设置 \(dp[u]\) 为从点 \(x\) 到点 \(n\) 的期望硬币消耗数。那么，转移：

\[ dp[u] = \sum_{v \in nearby} \frac{\min\{dp[u], dp[v]\}}{deg[u]} + 1 \]

我们可以一开始把最小值设置为自身，然后用 Dijsktra 搞一下转移即可。我们需要记录被转移和、被转移次数，然后进行自身的计算。

// P4745.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 301000;
typedef pair<double, int> pdi;

int head[MAX_N], n, m, current, deg[MAX_N], cnt[MAX_N];
double dist[MAX_N], sum[MAX_N];
bool vis[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void shortest_path()
{
    priority_queue<pdi> pq;
    pq.push(make_pair(0, n));
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (vis[edges[i].to] == false)
            {
                cnt[edges[i].to]++, sum[edges[i].to] += dist[u];
                dist[edges[i].to] = double(sum[edges[i].to] + deg[edges[i].to]) / double(cnt[edges[i].to]);
                pq.push(make_pair(-dist[edges[i].to], edges[i].to));
            }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u), deg[u]++, deg[v]++;
    shortest_path(), printf("%.10lf\n", dist[1]);
    return 0;
}

CF914G Sum the Fibonacci

先看下条件：

• \((s_a | s_b) \& s_c \& (s_d \oplus s_e) = 2^i, s_a \& s_b = 0\)

首先，\(s_a | s_b, s_a \& s_b = 0\) 就是子集卷积，用 FWT_OR 进行展开，\(\Theta(n \log^2 n\) 做完；\(s_c\)不用考虑；\(s_d \oplus s_e\) 用 FWT_XOR 搞一下就行了。接下来这三个部分用 FWT_AND 做就完事了。