【最后一篇】做题笔记

校内赛的题解还是不公开了。

代码的话……看难度而定。

时间似乎是乱序的。

在退役之前会高强度更新。

Vim 好像不支持自动生成目录，所以麻烦全文查找一下。

【来源未知】排列计数

请统计长为 $n(n\le 10^6)$ 的排列中，有多少组排列有至少 $4$ 个位置满足 $p_i \neq i$，输出答案在 $\operatorname{mod} 998244353$ 意义下的值。

【来源未知】排列计数 解法

正难则反。 考虑不合法的方案。

容易发现原命题的等价命题为 有多少排列有小于等于 n-4 个位置相同，逆命题为 有多少排列有大于 n-4 位相同，这个容易算。

• 恰好有 $n-3$ 位相同的排列：${ {n} \choose {3} }D_3 = 2{ {n} \choose {3} }$。
• 恰好有 $n-2$ 位相同的排列：${ {n} \choose {2} }D_2= { {n} \choose {2} }$。
• 恰好有 $n-1$ 位相同的排列：${ {n} \choose {1} }D_1 = 0$。（因为 $D_1=0$）
• 恰好有 $n$ 位相同的排列：$1$。

所以答案就是 $n! - (2{ {n} \choose {3} } + { {n} \choose {2} } + 1)$。

代码难看。

#include <stdio.h>

const int maxn = 1e6, mod = 998244353;

int n, jn = 1;
const int inv2 = 499122177, inv3 = 332748118;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		jn = 1ll * jn * i % mod;
	printf("%d", ((jn + mod - 2ll * n * (n - 1) % mod * (n - 2) % mod * inv2 % mod * inv3 % mod) % mod + mod - 1ll * n * (n - 1) % mod * inv2 % mod - 1) % mod);
	return 0;
}

CF733E Sleep in class

有一个长度为n的楼梯，每节台阶上有一个字符串

• 为 U 则代表向上走
• 为 D 则代表向下走
• 当走过这个台阶后，台阶上的字符串会从U变为D或从D变成U

求从第$i$个台阶开始要走出这N个台阶需要的步数(即从1号台阶向下，或N号台阶向上）

若出不去则输出 $-1$

CF733E Sleep in class 解法

这个是模拟赛 T1，状况频出的一道题。 数组开小，压行 UB。 开大之后发现倍增空间炸了，然后发现不用倍增，输麻了。

首先我们可以发现被修改的格子一定是连续的，且一定是向左找 R，向右找 L，所以可以写出本题的 $O(n^2)$ 代码。

i64 query(int x)
{
    i64 res = 0;
    int l = x, r = x, st = ops[x];
    while (true)
    {
        if (st == 1)
            do
                r++;
            while (ops[r] == st && r <= n);
        else
            do
                l--;
            while (ops[l] == st && l);

        res += (r - l);
        st ^= 1;

        if (r == n + 1 or l == 0)
            return res;
    }
}

稍微优化一下：

i64 query(int x)
{
    i64 res = 0;
    int l = x, r = x, st = ops[x];
    while (true)
    {
        if (st == 1)
            r = mostrl[r];
        else
            l = mostlr[l];

        res += r;
        res -= l;
        st ^= 1;

        if (r == n + 1 or l == 0)
            return res;
    }
}

预处理这样：

cin >> n;
for (int i = 1; i <= n; i++)
	cin >> ch,
		ops[i] = (ch == 'R');
ops[0] = ('R' == 'R');
ops[n + 1] = ('L' == 'R');

int p = n + 1;
for (int i = n; i; i--)
{
	mostrl[i] = p;
	if (ops[i] == 0)
		p = i;
}
p = 0;
for (int i = 1; i <= n; i++)
{
	mostlr[i] = p;
	if (ops[i] == 1)
		p = i;
}

我们就发现了实际上我们在找这个跳跃次数，然后求和左右端点。

所以我们可以得到跳跃次数，前缀和即可。 然后左右端点求和也是前缀和二分，不能倍增，要是开 256 就炸空间了。

i64 query(int x)
{
    i64 steps[2] = {0, 0};
    i64 res = 0;

    steps[ops[x] ^ 1] = lsum[x + 1]; // getrstep(x);
    steps[ops[x]] = rsum[x - 1];     // getlstep(x);

    if ((ops[x] ^ (steps[0] > steps[1])))
        res -= (n + 1);

    steps[((steps[0] > steps[1]) ^ 1)] = steps[(steps[0] > steps[1])] - ((steps[0] > steps[1]) ^ 1);

    if (ops[x])
        res -= x;
    else
        res += x;

    res -= gmostlrsum(x, steps[ops[x]]) * 2;
    res += gmostrlsum(x, steps[ops[x] ^ 1]) * 2;
    return res;
}

代码：

#include <iostream>
#include <string.h>

using std::cin;
using std::cout;
const char endl = '\n';

typedef long long i64;

const i64 mod = 1;
const int maxn = 5e5;

i64 ops[maxn], lsum[maxn], rsum[maxn];
i64 lisum[maxn], risum[maxn];
int n;
char ch;

int grsumsum(int l, int r) { return rsum[r] - rsum[l - 1]; }
i64 grisumsum(int l, int r) { return risum[r] - risum[l - 1]; }
int glsumsum(int l, int r) { return lsum[l] - lsum[r + 1]; }
i64 glisumsum(int l, int r) { return lisum[l] - lisum[r + 1]; }

i64 gbefksum(int x, int p)
{
    if (p == 0)
        return 0;

    x--;
    int l = 1, r = x;

    if (grsumsum(1, x) < p)
    {
        return grisumsum(1, x);
    }

    while (r - l > 3)
    {
        int mid = (l + r) >> 1;
        if (grsumsum(mid, x) > p)
            l = mid;
        else
            r = mid;
    }

    for (int i = r; i >= l; i--)
        if (grsumsum(i, x) == p)
        {
            return grisumsum(i, x);
        }
    return 0;
}

i64 gaftksum(int x, int p)
{
    if (p == 0)
        return 0;

    x++;
    int l = x, r = n;

    if (glsumsum(x, n) < p)
    {
        return glisumsum(x, n) + (n + 1);
    }

    while (r - l > 3)
    {
        int mid = (l + r) >> 1;
        if (glsumsum(x, mid) > p)
            r = mid;
        else
            l = mid;
    }

    for (int i = l; i <= r; i++)
        if (glsumsum(x, i) == p)
            return glisumsum(x, i);

    return -1;
}

i64 query(int x)
{
    i64 steps[2] = {0, 0};
    i64 res = 0;

    steps[ops[x] ^ 1] = lsum[x + 1]; // getrstep(x);
    steps[ops[x]] = rsum[x - 1];     // getlstep(x);

    if ((ops[x] ^ (steps[0] > steps[1])))
        res -= (n + 1);

    steps[((steps[0] > steps[1]) ^ 1)] = steps[(steps[0] > steps[1])] - ((steps[0] > steps[1]) ^ 1);

    if (ops[x])
        res -= x;
    else
        res += x;

    res -= gbefksum(x, steps[ops[x]]) * 2;
    res += gaftksum(x, steps[ops[x] ^ 1]) * 2;
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> ch,
            ops[i] = (ch == 'U'),
            lsum[i] = (ch == 'D'),
            rsum[i] = (ch == 'U'),
            lisum[i] = (ch == 'D') * i,
            risum[i] = (ch == 'U') * i;
    ops[0] = ('U' == 'U');
    ops[n + 1] = ('D' == 'U');

    rsum[0] = lsum[n + 1] = 1;
    for (int i = 1; i <= n; i++)
        rsum[i] += rsum[i - 1],
            risum[i] += risum[i - 1];
    for (int i = n; i >= 1; i--)
        lsum[i] += lsum[i + 1],
            lisum[i] += lisum[i + 1];

    for (int i = 1; i <= n; i++)
        cout << query(i) << ' ';
    return 0;
}

P6327

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\ldots,a_n$，进行 $m$ 次操作，操作分为两类。

操作 $1$：给出 $l,r,v$，将 $a_l,a_{l+1},\ldots,a_r$ 分别加上 $v$。

操作 $2$：给出 $l,r$，询问 $\sum\limits_{i=l}^{r}\sin(a_i)$。

解法有两种，先给核心公式。

P6327 解法一

题解都是这个写法，不必我多言了吧。

P6327 解法二

这个标记是可以上推的，所以考虑线段树。

具体地，区间乘区间求和。

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

#define mkpair make_pair

typedef long long i64;
typedef std::pair<int, int> pii;
typedef std::pair<i64, i64> pi64;
typedef std::vector<int> vint;
typedef std::vector<i64> vi64;
typedef std::queue<int> qint;
typedef std::queue<i64> qi64;
typedef std::priority_queue<int> pqint;
typedef std::priority_queue<i64> pqi64;

typedef long long i64;
const int maxn = 4.1e5;

typedef complex<double> cd;
cd tree[maxn << 2], lazy[maxn << 2];

inline cd initial(int u) { return cos(u) + 1.i * sin(u); }

int n, m, t, u, v, w;
void build(int index, int l, int r)
{
    lazy[index] = 1.;
    if (l == r)
    {
        cin >> u;
        tree[index] = initial(u);
        // cout << l << " : " << tree[index] << endl;
        return;
    }
    int mid = (l + r) >> 1;
    build(index << 1, l, mid),
        build(index << 1 | 1, mid + 1, r);
    tree[index] = tree[index << 1] + tree[index << 1 | 1];
    // cout << l << " " << r << " : " << tree[index] << endl;
}

void setlazy(int index, int l, int r, cd val) { tree[index] *= val, lazy[index] *= val; }

void pushlazy(int index, int l, int r)
{
    int mid = (l + r) >> 1;
    setlazy(index << 1, l, mid, lazy[index]);
    setlazy(index << 1 | 1, mid + 1, r, lazy[index]);
    lazy[index] = 1.;
}

void modify(int index, int l, int r, int ql, int qr, cd val)
{
    if (ql <= l and r <= qr)
    {
        // cout << "set " << index << " " << val << endl;
        setlazy(index, l, r, val);
        return;
    }

    if (l > qr or r < ql)
        return;

    pushlazy(index, l, r);

    int mid = (l + r) >> 1;

    modify(index << 1, l, mid, ql, qr, val),
        modify(index << 1 | 1, mid + 1, r, ql, qr, val);
    tree[index] = tree[index << 1] + tree[index << 1 | 1];
}

cd query(int index, int l, int r, int ql, int qr)
{
    pushlazy(index, l, r);
    if (ql <= l and r <= qr)
    {
        // cout << "ret " << l << " " << r << endl;
        return tree[index];
    }
    if (l > qr or r < ql)
        return 0;
    int mid = (l + r) >> 1;
    return query(index << 1, l, mid, ql, qr) +
           query(index << 1 | 1, mid + 1, r, ql, qr);
}

int main()
{
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n;
    build(1, 1, n);
    cin >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> t;
        if (t == 1)
        {
            cin >> u >> v >> w;
            // cout << "modify " << u << " " << v << " multiply " << initial(w) << endl;
            modify(1, 1, n, u, v, initial(w));
            // cout << "Not Supported!" << endl;
        }
        else
            // cout << "query" << endl,
            cin >> u >> v,
                // cout << query(1, 1, n, u, v) << endl;
                cout << fixed << setprecision(1) << query(1, 1, n, u, v).imag() << endl;
    }
    // cout << "end" << endl;
    return 0;
}

abc323e Playlist

高桥有一个播放列表，里面有$N$首歌。歌曲$i$ $(1 \leq i \leq N)$持续$T_i$秒。 Takahashi在时间$0$开始随机播放播放列表。

随机播放重复以下内容:以等概率从$N$首歌曲中选择一首歌，播放到最后。在这里，歌曲是连续播放的:一旦一首歌结束，下一首选择的歌曲立即开始。可以连续选择同一首歌。

求歌曲$1$在时间$0$后$(X + 0.5)$秒播放的概率，取$998244353$的模。

abc323e Playlist 解法

看到这个就可以想到期望 dp 加背包了。 定义 $f_i$ 为从第 $i$ 秒开始播放，第 $X+0.5$ 秒播放到第一首歌的概率。

我们便容易得到：

然后题就做完了。

int main()
{
    cin >> n >> x;
    invn = pow(n, mod - 2);

    for (int i = 1; i <= n; i++)
        cin >> v[i];

    if (x < v[1])
    {
        cout << invn;
        return 0;
    }

    for (int i = x; i > x - v[1]; i--)
        f[i] = invn;

    for (int i = x - 1; i >= 0; i--)
        for (int j = 1; j <= n; j++)
            f[i] = (1ll * f[i] + 1ll * f[i + v[j]] * invn) % mod;

    cout << f[0];

    return 0;
}

P4700 Traffic

在平面直角坐标系上有 $n$ 个点，其中第 $i$ 个点的坐标是 $(x_i,y_i)$ ，所有点在一个以 $(0,0)$ 和 $(A,B)$ 为相对顶点的矩形内。

如果 $x_i=0$ ，那么我们称这个点在西侧。如果 $x_i=A$ ，那么我们称这个点在东侧。

这些点之间有 $m$ 条边，每条边可能是有向边也可能是无向边，保证边在交点以外的任何地方不相交。

现在请你求出，对于每一个西侧的点，能够沿着边到达多少东侧的点。

P4700 Traffic 解法

这道题最重要的性质就是：边保证在交点以外的任何地方不相交。

那我们得到如下性质：在去除了图中所有点不能到达的右侧点后，每个点能够到达的右侧点是一个区间。

我们考虑它的证明：假如存在左侧点 $X$，右侧点 $A,B,C$，使得 $A_y>B_y>C_y$，且 $X$ 能够到达 $A,C$，对于每个右侧点，都存在一个左侧点可以到达。

则若有点要到达 $B$，就至少存在一条与 $XA$ 或 $XC$ 交叉的边，而边在交点外是不相交的，所以存在一个 $XA$ 或 $XC$ 路径上的交点，使得交点可以到达 $B$。

由此得到：若一个左侧点能够到达 $y$ 更高和更低的点，则中间的点也能到达。

所以我们只需要维护左侧点最高和最低的 $y$ 值，这个的话缩点建反图然后 DAG dp 即可。

// Problem: P4700 [CEOI2011] Traffic
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4700
// Memory Limit: 125 MB
// Time Limit: 5000 ms

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>

using std::cin;
using std::cout;
using std::max;
using std::min;
using std::vector;
// using std::endl;
const char endl = '\n';

typedef long long i64;
typedef std::pair<int, int> pii;
typedef std::vector<int> vint;
typedef std::queue<int> qint;
typedef std::map<int, int> mpii;
typedef std::stack<int> sint;

typedef long long i64;
const i64 mod = 1;
const int maxn = 4e5;

vint edge[maxn], edge_new_rev[maxn];
int flg[maxn], reach[maxn];
int scclo[maxn], scchi[maxn];

vector<pii> left, right, points;
mpii mping;

int n, m, r, _, u, v, w;

int dfn[maxn], low[maxn], cnt, scc[maxn], scnt, active[maxn], inscc[maxn];
sint st;
void tarjan(int index)
{
    low[index] = dfn[index] = ++cnt;
    st.push(index);

    for (auto u : edge[index])
    {
        if (!dfn[u])
            tarjan(u);
        if (!scc[u])
            low[index] = min(low[u], low[index]);
    }

    if (dfn[index] == low[index])
    {
        ++scnt;
        while (true)
        {
            int u = st.top();
            st.pop();
            scc[u] = scnt;
            if (u == index)
                break;
        }
    }
}

qint q;
const int inf = 1e9;

int main()
{
    cin >> n >> m >> r >> _;
    for (int i = 0; i < n; i++)
    {
        cin >> u >> v;
        points.push_back({u, v});
        if (u == 0)
            left.push_back({-v, i});
    }

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w, u--, v--,
            edge[u].push_back(v);
        if (w == 2)
            edge[v].push_back(u);
    }

    for (auto x : left)
        q.push(x.second);

    sort(left.begin(), left.end());

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (active[u])
            continue;
        active[u] = 1;
        for (auto v : edge[u])
            q.push(v);
    }

    for (int i = 0; i < n; i++)
        if (active[i] and points[i].first == r)
            right.push_back({points[i].second, i});

    sort(right.begin(), right.end());
    for (int i = 0, e = right.size(); i < e; i++)
        mping[right[i].second] = i + 1;

    for (int i = 0; i < n; i++)
        if (!dfn[i])
            tarjan(i);

    for (int u = 0; u < n; u++)
        for (auto v : edge[u])
            if (scc[u] != scc[v])
                edge_new_rev[scc[v]].push_back(scc[u]), inscc[scc[u]]++;

    for (int i = 1; i <= scnt; i++)
        scclo[i] = inf,
        scchi[i] = -inf;

    for (auto i : right)
        scclo[scc[i.second]] = min(scclo[scc[i.second]], mping[i.second]);
    for (auto i : right)
        scchi[scc[i.second]] = max(scchi[scc[i.second]], mping[i.second]);

    for (int i = 1; i <= scnt; i++)
        if (!inscc[i])
            q.push(i);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto x : edge_new_rev[u])
        {
            scclo[x] = min(scclo[u], scclo[x]),
            scchi[x] = max(scchi[u], scchi[x]);
            if (--inscc[x] == 0)
                q.push(x);
        }
    }

    for (auto i : left)
        if (scchi[scc[i.second]] == -inf || scclo[scc[i.second]] == inf)
            cout << 0 << endl;
        else
            cout << scchi[scc[i.second]] - scclo[scc[i.second]] + 1 << endl;

    return 0;
}

P3343 地震后的幻想乡

傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。

这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 $n$ 个地方，那么最快的方法当然是修复 $n-1$ 条道路将这 $n$ 个地方都连接起来。 幻想乡这 $n$ 个地方本来是连通的，一共有 $m$ 条边。现在这 $m$ 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 $i$ 条边所需要的时间为 $e_i$。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 $e_i$ 会是一个 $0$ 到 $1$ 之间均匀分布的随机实数。并且所有 $e_i$ 都是完全独立的。

现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 $n-1$ 条边，同时开始修复，那么修复完成的时间就是这 $n-1$ 条边的 $e_i$ 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 $e_i$ 的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？

P3343 地震后的幻想乡 解法

期望题，其实不需要积分，积分是为了证明最后的性质：

对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,...,x_n$，第 $k$ 小的那个的期望值是 $k/(n+1)$。

这个性质最后来。

我们令 $f_{S,i}$ 代表对于点集 $S$ 的导出子图，在选择了 $i$ 条边后仍然不连通的方案数量。

我们同时定义 $g_{S,i}$ 为在 $f_{S,i}$ 的条件下，图连通的方案数量。

定义 $d(S)$ 为 $S$ 的导出子图中的边数，我们有 $f_{S,i} + g_{S,i} = { {d(S)} \choose {i} }$，这是显然的。

然后我们就得到了本题的核心公式：

这里的 $k$ 并没有被用到，但是为了保证不算重，是必要的，且对于相同的 $S$，应有相同的 $k$。

我们强制 $S$ 的子图 $T$ 连通，然后选择 $j-u$ 条边，这个图一定是不连通的。

然后枚举一下子集应该就完了。

最后的答案是这样的：

参考了这篇题解：题解 P3343 【[ZJOI2015]地震后的幻想乡】 - ButterflyDew 的博客 - 洛谷博客

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string.h>
#include <bitset>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>

using std::cin;
using std::cout;
using std::min;

// using std::endl;
const char endl = '\n';

typedef long long i64;
const int maxn = 11, maxm = 51;

std::vector<int> edge[maxn];

int n, m, u, v;

int lowbit(int set) { return set & (-set); }

i64 f[1 << maxn][maxm], C[maxm][maxm], g[1 << maxn][maxm];
int d[1 << maxn], graph[1 << maxn];

int main()
{
    cin >> n >> m;

    C[0][0] = 1;
    for (int i = 1; i <= m; i++)
        C[i][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

    for (int i = 0; i < m; i++)
        cin >> u >> v, u--, v--,
            graph[(1 << u) | (1 << v)]++;

    for (int S = 1; S < (1 << n); S++)
        for (int T = S; T; T = (T - 1) & S)
            d[S] += graph[T];

    for (int S = 1; S < (1 << n); S++) // enumerate S
        for (int j = 0; j <= d[S]; j++)
        {
            for (int T = (S - 1) & S; T; T = (T - 1) & S) // T \subsetneq S
                if (lowbit(S) & T)                        // k = lowbit(s) \in T
                    for (int u = 0; u <= min(j, d[T]); u++)
                        f[S][j] += g[T][u] * C[d[S ^ T]][j - u];
            g[S][j] = C[d[S]][j] - f[S][j];
        }

    double s = 0;
    for (int i = 0; i <= m; i++)
        s += 1. * f[(1 << n) - 1][i] / C[m][i];

    cout << std::fixed << std::setprecision(6) << (s / (1. + m));
    return 0;
}

P2865 Roadblocks G

贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。

贝茜所在的乡村有 $R(1≤R≤10^5)$ 条双向道路，每条路都连接了所有的 $N(1≤N≤5000)$ 个农场中的某两个。贝茜居住在农场 $1$，她的朋友们居住在农场$N$（即贝茜每次旅行的目的地）。

贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且一条路可以重复走多次。当然第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

P2865 Roadblocks G 解法

考虑答案必定是 u 到 v 的最短路的一条路径更改一条边得到的，所以处理出从 1 开始的最短路，从 n 开始的最短路，最后合并求解即可。

#include<stdio.h>
#include<queue>
#include<vector>

const int maxn = 1e5;

int n,m,u,v,w;
std::vector<std::pair<int,int> > edge[maxn];
std::priority_queue<std::pair<int,int> > q;
std::priority_queue<int> mins;

int dis[maxn],dis2[maxn],vis[maxn],mx;

void rundij(int* arr,int index){
	for(int i=1;i<=n;i++)vis[i]=0,arr[i]=0x3f3f3f3f;
	while(!q.empty())q.pop();
	arr[index]=0,q.push({0,index});

	while(!q.empty()){
		auto u = q.top();q.pop();
		if(vis[u.second])continue;vis[u.second]=1;
		for(auto v:edge[u.second]){
			if(arr[v.first] > arr[u.second] + v.second) arr[v.first] = arr[u.second] + v.second , q.push({-arr[v.first],v.first});
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&u,&v,&w),
			edge[u].push_back({v,w}),
			edge[v].push_back({u,w});

	rundij(dis,1);
	rundij(dis2,n);

	for(int i=1;i<=n;i++)
		for(auto u:edge[i])
		{
			int v = dis[i]+u.second+dis2[u.first];
			if(v > dis[n])
				mins.push(-v);
		}

	printf("%d",-mins.top());

	return 0;
}

P3166 数三角形

给定一个 $N\times M$ 的网格，请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

P3166 数三角形 解法

首先正难则反，考虑用总方案数减去三点共线的方案数。

然后我们发现我们需要求如下的一个东西：

给定两点 $(x_1,y_1),(x_2,y_2)$，假定 $x_1 \le x_2,y_1 \le y_2$，求在这条线段上有多少个整点。

我们这样考虑：

将线段看作向量，那么这个向量可以转化为几个（斜率与原向量相同）向量的和。

起始点和终点都保证是整点，那么如果我们能将 $\overrightarrow{v}$ 变为两个向量 $\overrightarrow{a}$ 和 $\overrightarrow{b}$，且这两个向量的横向分量和纵向分量长度都为整数，则存在一个整点。

$\overrightarrow{v}$ 可以被拆分成多个向量，且拆分的极限应该是 $\gcd(x_2-x_1,y_2-y_1)$ 组，所以在这之中有 $\gcd(x_2-x_1,y_2-y_1)-1$ 个整数点（忽略右侧端点）。

所以我们枚举所有端点对，然后统计中间的端点，然后用总方案数减去即可。

但这样的复杂度是 $O(n^4)$ 的，还会有一些可能会算重的情况，考虑优化。

我们将枚举端点对变为枚举一个端点和 $\Delta x$ 以及 $\Delta y$，尽管复杂度不变，但注意到如下基本事实：所有 $(\Delta x,\Delta y)$ 相同的线段对答案的贡献是相同的，考虑有多少对这样的线段，设想一个 $(\Delta x,\Delta y)$ 的矩形在 $(n+1,m+1)$ 的矩形内移动，会有 $(n+1-\Delta x)\times(m+1-\Delta y)$ 对。

所以我们就得到了本题的 $O(n^2)$ 做法（$n,m$ 同阶）。

#include<stdio.h>
#include<algorithm>

typedef long long i64;

i64 n,m,tot;

i64 C3(i64 x){return x*(x-1)/2ll*(x-2)/3ll;}
i64 intg(i64 dx,i64 dy){return std::__gcd(dx,dy)-1;}

int main(){
	scanf("%lld%lld",&n,&m),n++,m++;

	tot += C3(n*m);

	tot -= n*C3(m) + m*C3(n);

	for(int di=1;di<=n;di++)
		for(int dj=1;dj<=m;dj++)
			tot -= 2ll* intg(di,dj) * (n-di)*(m-dj);

	printf("%lld",tot);
	return 0;
}

然后这道题有一个复杂度更优的做法（莫比乌斯反演）：

上面高亮的式子求的实际上就是：

有如下基本事实成立：$\varphi * 1 = id$，所以我们可以将 $\gcd(i,j)$ 转为 $\sum_{i|\gcd(i,j)}\varphi(i)$。

然后就是漫长枯燥的式子推导：

最后这题就做完了，复杂度是线性的。

#include<stdio.h>
#include<algorithm>

typedef long long i64;

const int maxn = 200000;

int check[maxn],prime[maxn],phi[maxn],cnt;
void ola_prime(){
	phi[1]=1;
	for(int i=2;i<maxn;i++){
		if(!check[i])
			phi[i] = i-1,
			prime[++cnt] = i;
		for(int j=1;j<=cnt and i*prime[j]<maxn;j++){
			check[i*prime[j]]=1;
			if(!(i%prime[j])){
				phi[i*prime[j]] = phi[i]*prime[j];
				break;
			}
			else
				phi[i*prime[j]] = phi[i]*(prime[j]-1);
		}
	}
}

i64 n,m,tot;

i64 C3(i64 x){return x*(x-1)/2ll*(x-2)/3ll;}
i64 intg(i64 dx,i64 dy){return std::__gcd(dx,dy)-1;}
i64 cal(i64 x,i64 d){return (x/d)*x-d*(x/d)*(x/d+1ll)/2ll;}

int main(){
	ola_prime();
	scanf("%lld%lld",&n,&m),n++,m++;

	tot += C3(n*m);

	tot -= n*C3(m) + m*C3(n);

	for(int d=1,e=n<m?n:m;d<=e;d++)
		tot -= 2*phi[d]*cal(n,d)*cal(m,d);

	tot += n*(n-1)*m*(m-1)/2ll;
	printf("%lld",tot);
	return 0;
}

P1129 矩阵游戏

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 $n \times n$ 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

• 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
• 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

P1129 矩阵游戏 解法

二分图匹配，原因在这里：

首先不难证得，交换只会交换行（或列）。

然后考虑匹配，一行能匹配一列当且仅当这一列中，该行所在的位置是黑格。

所以我们给行和列各开虚点，给黑格的行连向列，最后求解二分图匹配即可。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>

#define int long long

const int maxn = 2 * 207 + 5, maxm = 2 * 5000 + 5, inf = 0x3f3f3f3f3f3f3f3f;

int n, m, tot=1, head[maxn], cur[maxn], ter[maxm], nxt[maxm], cap[maxm], dis[maxn];

void add(int u, int v, int w) {ter[++tot] = v, nxt[tot] = head[u], cap[tot] = w, head[u] = tot;}
void addedge(int u, int v, int w) {
	// printf("%d %d %d\n",u,v,w);
	add(u, v, w) , add(v, u, 0);
}

bool bfs(int s,int t) {
	memset(dis, -1 , sizeof(dis));
	std::queue<int> q;
	q.push(s), dis[s] = 0, cur[s] = head[s];
	while(!q.empty()) {
		int fr = q.front(); q.pop();
		for(int i = head[fr] ; i ; i = nxt[i]) {
			int v = ter[i];
			if(cap[i] && dis[v] == -1) {
				dis[v] = dis[fr] + 1;
				q.push(v);
				cur[v] = head[v];
				if(v==t)
					return true;
			}
		}
	}
	return false;
}

int dfs(int u, int t, int flow) {
	if(u == t) return flow;
	int ans = 0;
	for(int &i = cur[u] ; i && ans < flow ; i = nxt[i]) {
		int v = ter[i];
		if(cap[i] && dis[v] == dis[u] + 1) {
			int x = dfs(v, t, std::min(cap[i], flow - ans));
			if(!x) dis[x] = -1;
			cap[i] -= x,cap[i^1] += x, ans += x;
		}
	}
	return ans;
}

int dinic(int s, int t) {
	int ans = 0, x;
	while (bfs(s,t)) {
		while(x = dfs(s,t,inf))
			ans += x;
	}
	return ans;
}

int T, u, v, w, c, s, t;
int point_left(int index) { return n+index;}
int point_up  (int index) { return index;}

signed main() {
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);

		memset(head,0,sizeof head);
		memset(cur,0,sizeof cur);
		memset(ter,0,sizeof ter);
		memset(nxt,0,sizeof nxt);
		memset(cap,0,sizeof cap);
		memset(dis,0,sizeof dis);


		s = 2*n+1,t = 2*n+2;
		tot = 1;
		for(int i=1;i<=n;i++)
			head[i] = 0;

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%lld",&u);
				if(u)
					addedge(point_left(i),point_up(j),1);
			}
		}

		for(int i=1;i<=n;i++)
			addedge(s,point_left(i),1),
			addedge(point_up(i),t,1);

		int ans = dinic(s, t);
		puts(ans == n ? "Yes" : "No");
	}
	return 0;
}

P2120 仓库建设

L 公司有 $n$ 个工厂，由高到低分布在一座山上，工厂 $1$ 在山顶，工厂 $n$ 在山脚。

由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 $i$ 个工厂目前已有成品 $p_i$ 件，在第 $i$ 个工厂位置建立仓库的费用是 $c_i$。

对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 $n$，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，一件产品运送一个单位距离的费用是 $1$。

假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

• 工厂 $i$ 距离工厂 $1$ 的距离 $x_i$（其中 $x_1=0$）。
• 工厂 $i$ 目前已有成品数量 $p_i$。
• 在工厂 $i$ 建立仓库的费用 $c_i$。

请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。

简化题意：

有 $n$ 个点，每个点有一定量（$p_i$）的物资，现在要选择一些点，将所有物资通过向右移动的方式汇集到这些点中，选择点和向右移动单位物资均有代价，求最小代价。

P2120 仓库建设 解法

我们首先想一个 $O(n^2)$ 的 dp 式子。

注意到如下基本事实：若一个点建立了仓库，则前面的没有运输进仓库的点都会运输到这里，所以每个仓库的覆盖范围是一定的。

我们定义 $f_i$ 为前 $i$ 个地点的物品都能被安置，且 $i$ 号点是最后一个仓库时的最小花费。

则我们可以得到（下文中的 $d$ 指的是题目中的 $x$，即距离）：

我们定义 $q_i = \sum_{j \in [1,i]}p_j,r_i = \sum_{j \in [1,i]}d_j\cdot p_j$，则上面的式子就变成了这样：

这个基本就是斜率优化的板子了，我们假定存在 $u,v\in [0,i)$ 且 $u<v$，同时 $v$ 优于 $u$（即选 $v$ 转移 $f$ 比选 $u$ 更大），那么我们就能列出不等式：

于是我们将问题抽象如下：平面上有 $n$ 个点，坐标为 $(q_i,f_i+r_i)$，若对于 $u<v$ 的两点，满足两点的斜率小于 $d_i$，则选择右侧的点是更优的。

这里可以用凸壳维护，因为不在凸壳上的点一定劣于凸壳上的点，下面是具体原因：

我们假设有 $u,v,w$ 三点，满足 $u < v < w$，且 $u,w$ 在凸壳上，$v$ 在凸壳以内。

假如此时 $u$ 优于 $w$，则有 $k_{uw} < k_{u,v},k_{uw} \le di$，结合几何相关知识得 $k_{vw} \le k_{uv}$ 此时 $w$ 优于 $v$，所以 $v$ 对答案没有贡献。

配上一张很丑的图示：

假如此时 $u$ 劣于 $w$，则同样有 $k_{uw} < k_{u,v},k_{uw} \le di,k_{uv} \ge k_{uw}$ 此时 $w$ 劣于 $u$，同时 $v$ 劣于 $u$，$v$ 对答案同样没有贡献。

综上，$v$ 对答案是没有贡献的，所以我们可以维护一个下凸壳，因为凸壳上的斜率单调递增，所以可以在上面二分最优决策点。

但这题有更好的性质：$d_i$ 单调递增，所以我们可以直接维护一个单调队列代表凸壳上边的斜率，在查找时直接弹出队尾斜率不合法的点即可，因为队尾若不合法，接下来也不可能合法。

还有一个要注意的点（hack 数据），就是 $p_i$ 等于 $0$ 的情况，若末尾有连续的 $p_i=0$，取其 $f$ 值的最小值即可。

代码不长，重在理解。

#include<stdio.h>

typedef long long i64;
const int maxn = 1.2e6;

int n;

i64 d[maxn],p[maxn],c[maxn],f[maxn],q[maxn],r[maxn];

i64 min(i64 a,i64 b){ return a<b?a:b;}

i64 decx (int index)   { return q[index];}
i64 decy (int index)   { return f[index]+r[index];}
i64 maked(int i,int u) { return f[u] + d[i] * (q[i] - q[u]) - r[i] + r[u] + c[i];}

// back -> . . . . . . . . . <- front
int que[maxn],vfront,vback;
int  size     ()      { return vfront-vback;}
int  front    ()      { return que[vfront-1];}
int  front2   ()      { return que[vfront-2];}
int  back     ()      { return que[vback];}
int  back2    ()      { return que[vback+1];}
void push     (int v) { que[vfront++]=v;}
void pop_front()      { vfront--;}
void pop_back ()      { vback++;}

int main(){
	scanf("%d",&n);

	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld",d+i,p+i,c+i);

	for(int i=1;i<=n;i++) q[i] = p[i] + q[i-1];
	for(int i=1;i<=n;i++) r[i] = d[i] * p[i] + r[i-1];

	push(0);

	for(int i=1;i<=n;i++){
		while(
			size()>=2 and
			(decy(back2())-decy(back()))
				<= d[i] * (decx(back2())-decx(back()))
		)
			pop_back();
		f[i] = maked(i,back());
		while(
			size()>=2 and
			(decy(front())-decy(front2())) * (decx(i)-decx(front()))
				>= (decy(i)-decy(front())) * (decx(front()) - decx(front2()))
		)
			pop_front();
		push(i);
	}

	i64 ans = f[n];

	int x=n;
	while(p[x]==0)
		x--,ans=min(ans,f[x]);

	printf("%lld",ans);

	return 0;
}