Skip to content

【最后一篇】做题笔记

Posted on:2023年11月5日 at 17:00

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

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

时间似乎是乱序的。

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

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


【来源未知】排列计数

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

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

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

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

所以答案就是 n!(2(n3)+(n2)+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的楼梯,每节台阶上有一个字符串

求从第ii个台阶开始要走出这N个台阶需要的步数(即从1号台阶向下,或N号台阶向上)

若出不去则输出 1-1

CF733E Sleep in class 解法

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

首先我们可以发现被修改的格子一定是连续的,且一定是向左找 R,向右找 L,所以可以写出本题的 O(n2)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

给出一个长度为 nn 的整数序列 a1,a2,,ana_1,a_2,\ldots,a_n,进行 mm 次操作,操作分为两类。

操作 11:给出 l,r,vl,r,v,将 al,al+1,,ara_l,a_{l+1},\ldots,a_r 分别加上 vv

操作 22:给出 l,rl,r,询问 i=lrsin(ai)\sum\limits_{i=l}^{r}\sin(a_i)

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

P6327 解法一

sin(a+x)=sinacosx+cosasinxcos(a+x)=cosacosxsinasinx\begin{aligned} \sin(a+x) &= \sin a \cos x + \cos a \sin x \\ \cos(a+x) &= \cos a \cos x - \sin a \sin x\end{aligned}
sin(ai+x)=sin(ai)cosx+cos(ai)sinxcos(ai+x)=cos(ai)cosxsin(ai)sinx\begin{aligned}\sum\sin(a_i+x) &= \sum \sin(a_i)\cos x + \sum\cos(a_i) \sin x \\ \sum\cos(a_i+x) &= \sum \cos(a_i) \cos x - \sum \sin(a_i) \sin x \end{aligned}

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

P6327 解法二

cos(a+x)+isin(a+x)=(cos(a)+isin(x))×(cos(x)+isin(a))\begin{aligned}\cos(a+x) + i \sin(a+x) = (\cos(a) + i\sin(x)) \times (\cos(x) + i \sin (a)) \end{aligned}

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

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

#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

高桥有一个播放列表,里面有NN首歌。歌曲ii (1iN)(1 \leq i \leq N)持续TiT_i秒。 Takahashi在时间00开始随机播放播放列表。

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

求歌曲11在时间00(X+0.5)(X + 0.5)秒播放的概率,取998244353998244353的模。

abc323e Playlist 解法

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

我们便容易得到:

fi{1n(i(xv1,x])jvfi+jnotherwisef_i\begin{cases}\dfrac{1}{n} & (i \in (x-v_1,x]) \\ \dfrac{\sum_{j \in v} f_{i+j}}{n} &\operatorname{otherwise}\end{cases}

然后题就做完了。

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

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

如果 xi=0x_i=0 ,那么我们称这个点在西侧。如果 xi=Ax_i=A ,那么我们称这个点在东侧。

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

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

P4700 Traffic 解法

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

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

我们考虑它的证明:假如存在左侧点 XX,右侧点 A,B,CA,B,C,使得 Ay>By>CyA_y>B_y>C_y,且 XX 能够到达 A,CA,C,对于每个右侧点,都存在一个左侧点可以到达。

则若有点要到达 BB,就至少存在一条与 XAXAXCXC 交叉的边,而边在交点外是不相交的,所以存在一个 XAXAXCXC 路径上的交点,使得交点可以到达 BB

由此得到:若一个左侧点能够到达 yy 更高和更低的点,则中间的点也能到达。

所以我们只需要维护左侧点最高和最低的 yy 值,这个的话缩点建反图然后 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 地震后的幻想乡

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

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

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

P3343 地震后的幻想乡 解法

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

对于 nn[0,1][0,1] 之间的随机变量 x1,x2,...,xnx_1,x_2,...,x_n,第 kk 小的那个的期望值是 k/(n+1)k/(n+1)

这个性质最后来。

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

我们同时定义 gS,ig_{S,i} 为在 fS,if_{S,i} 的条件下,图连通的方案数量。

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

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

fS,j=kTS,ugT,u(d(ST)ju)f_{S,j} = \sum_{k \in T \subsetneq S,\forall u}g_{T,u} { {d(S-T)} \choose {j-u} }

这里的 kk 并没有被用到,但是为了保证不算重,是必要的,且对于相同的 SS,应有相同的 kk

我们强制 SS 的子图 TT 连通,然后选择 juj-u 条边,这个图一定是不连通的。

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

最后的答案是这样的:

k[n1,m]km+1fU,kfU,k1(mk)\sum_{k\in [n-1,m]}\dfrac{k}{m+1}\dfrac{f_{U,k}-f_{U,k-1}}{ { {m} \choose {k} } }

参考了这篇题解:题解 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(1R105)R(1≤R≤10^5) 条双向道路,每条路都连接了所有的 N(1N5000)N(1≤N≤5000) 个农场中的某两个。贝茜居住在农场 11,她的朋友们居住在农场NN(即贝茜每次旅行的目的地)。

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

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×MN\times M 的网格,请计算三点都在格点上的三角形共有多少个。注意三角形的三点不能共线。

P3166 数三角形 解法

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

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

给定两点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2),假定 x1x2,y1y2x_1 \le x_2,y_1 \le y_2,求在这条线段上有多少个整点。

我们这样考虑:

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

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

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

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

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

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

所以我们就得到了本题的 O(n2)O(n^2) 做法(n,mn,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;
}

然后这道题有一个复杂度更优的做法(莫比乌斯反演):

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

2i=1nj=1m(gcd(i,j)1)(ni)(nj)2\sum_{i=1}^n\sum_{j=1}^m(\gcd(i,j)-1)(n-i)(n-j)

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

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

2i=1nj=1m(gcd(i,j)1)(ni)(mj)= 2i=1nj=1mdgcd(i,j)φ(d)(ni)(mj)2i=0n1j=0m1ij= 2dφ(d)i=1nj=1m[di][dj](ni)(mj)nm(n1)(m1)2= 2dφ(d)i=1[di](ni)j=1[dj](mj)nm(n1)(m1)2= 2d=1φ(d)i=1nd(ndi)j=1md(mdj)nm(n1)(m1)2= 2d=0min(n,m)φ(d)(nd×ndnd(nd+1)2)(md×mdmd(md+1)2)\begin{aligned}& 2\sum_{i=1}^n\sum_{j=1}^m(\gcd(i,j)-1)(n-i)(m-j) \\ =\space & 2\sum_{i=1}^n\sum_{j=1}^m\sum_{d|\gcd(i,j)}\varphi(d)(n-i)(m-j) -2 \sum_{i=0}^{n-1}\sum_{j=0}^{m-1}i\cdot j \\ =\space & 2\sum_{d}\varphi(d)\sum_{i=1}^n\sum_{j=1}^m[d|i][d|j](n-i)(m-j) - \dfrac{nm(n-1)(m-1)}{2} \\ =\space & 2\sum_{d}\varphi(d)\sum_{i=1}[d|i](n-i)\sum_{j=1}[d|j](m-j) - \dfrac{nm(n-1)(m-1)}{2} \\ =\space & 2\sum_{d=1}\varphi(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}(n-di)\sum_{j=1}^{\frac{m}{d}}(m-dj) - \dfrac{nm(n-1)(m-1)}{2} \\ =\space & 2\sum_{d=0}^{\min(n,m)}\varphi(d)(\lfloor \frac{n}{d} \rfloor\times n-d\dfrac{\lfloor \frac{n}{d} \rfloor(\lfloor \frac{n}{d} \rfloor+1)}{2})(\lfloor \frac{m}{d} \rfloor\times m-d\dfrac{\lfloor \frac{m}{d} \rfloor(\lfloor \frac{m}{d} \rfloor+1)}{2}) \end{aligned}

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

#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×nn \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 公司有 nn 个工厂,由高到低分布在一座山上,工厂 11 在山顶,工厂 nn 在山脚。

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

由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第 ii 个工厂目前已有成品 pip_i 件,在第 ii 个工厂位置建立仓库的费用是 cic_i

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

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

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

简化题意:

nn 个点,每个点有一定量(pip_i)的物资,现在要选择一些点,将所有物资通过向右移动的方式汇集到这些点中,选择点和向右移动单位物资均有代价,求最小代价。

P2120 仓库建设 解法

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

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

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

则我们可以得到(下文中的 dd 指的是题目中的 xx,即距离):

fi=minj[0,i){fj+ci+k[j+1,i)pk(didk)}=minj[0,i){fj+ci+dik[j+1,i)pkk[j+1,i)pkdk}\begin{aligned}f_i &= \min_{j\in[0,i)}\{f_j+c_i+\sum_{k\in[j+1,i)}p_k(d_i-d_k)\} \\ &= \min_{j\in[0,i)}\{f_j+c_i+d_i\sum_{k\in[j+1,i)}p_k-\sum_{k\in[j+1,i)}p_k\cdot d_k\}\end{aligned}

我们定义 qi=j[1,i]pj,ri=j[1,i]djpjq_i = \sum_{j \in [1,i]}p_j,r_i = \sum_{j \in [1,i]}d_j\cdot p_j,则上面的式子就变成了这样:

fi=minj[0,i){fj+ci+di(qiqj)ri+rj}\begin{aligned}f_i &= \min_{j\in[0,i)}\{f_j+c_i+d_i(q_i-q_j)-r_i+r_j\}\end{aligned}

这个基本就是斜率优化的板子了,我们假定存在 u,v[0,i)u,v\in [0,i)u<vu<v,同时 vv 优于 uu(即选 vv 转移 ff 比选 uu 更大),那么我们就能列出不等式:

fu+ci+di(qiqu)ri+rufv+ci+di(qiqv)ri+rvfu+ci+diqidiquri+rufv+ci+diqidiqvri+rvfu+diqidiqu+rufv+diqidiqv+rv(furu)(fvrv)(quqv)di(furu)(fvrv)quqvdi(fvrv)(furu)qvqudi\begin{aligned}f_u+c_i+d_i(q_i-q_u)-r_i+r_u &\le f_v+c_i+d_i(q_i-q_v)-r_i+r_v \\ f_u+c_i+d_iq_i-d_iq_u-r_i+r_u &\le f_v+c_i+d_iq_i-d_iq_v-r_i+r_v \\ f_u+d_iq_i-d_iq_u+r_u &\le f_v+d_iq_i-d_iq_v+r_v \\ (f_u-r_u) - (f_v-r_v) &\le (q_u-q_v)d_i \\ \dfrac{(f_u-r_u) - (f_v-r_v)}{q_u-q_v} &\le d_i \\ \dfrac{(f_v-r_v) - (f_u-r_u)}{q_v-q_u} &\le d_i\end{aligned}

于是我们将问题抽象如下:平面上有 nn 个点,坐标为 (qi,fi+ri)(q_i,f_i+r_i),若对于 u<vu<v 的两点,满足两点的斜率小于 did_i,则选择右侧的点是更优的。

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

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

假如此时 uu 优于 ww,则有 kuw<ku,v,kuwdik_{uw} < k_{u,v},k_{uw} \le di,结合几何相关知识得 kvwkuvk_{vw} \le k_{uv} 此时 ww 优于 vv,所以 vv 对答案没有贡献。

配上一张很丑的图示:

假如此时 uu 劣于 ww,则同样有 kuw<ku,v,kuwdi,kuvkuwk_{uw} < k_{u,v},k_{uw} \le di,k_{uv} \ge k_{uw} 此时 ww 劣于 uu,同时 vv 劣于 uuvv 对答案同样没有贡献。

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

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

还有一个要注意的点(hack 数据),就是 pip_i 等于 00 的情况,若末尾有连续的 pi=0p_i=0,取其 ff 值的最小值即可。

代码不长,重在理解。

#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;
}

U121015 区间

(我小改了下题面)

给定 n,l,rn,l,rnn 个数 a1,a2,a3,,ana_1,a_2,a_3,\cdots ,a_n,求随机选择一段区间,区间的平均值在 llrr 之间的期望在 mod998244353\operatorname{mod} 998244353 意义下的值。

U121015 区间 解法

首先将期望转化为方案数除总方案数,这步不用说。

我们发现如下性质:

l[1,n]r[l,n][k[l,r]akrl+1[l,r]]= l[1,n]r[l,n][k[l,r]akrl+1r]l[1,n]r[l,n][k[l,r]akrl+1<l]= l[1,n]r[l,n][k[l,r]akr×(rl+1)]l[1,n]r[l,n][k[l,r]ak<l×(rl+1)]= l[1,n]r[l,n][k[l,r]akr×(rl+1)0]l[1,n]r[l,n][k[l,r]akl×(rl+1)<0]= l[1,n]r[l,n][k[l,r](akr)0]l[1,n]r[l,n][k[l,r](akl)<0]\begin{aligned} &\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\dfrac{\sum_{k \in [l,r]}a_k}{r-l+1} \in [l,r]\right] \\ =\space &\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\dfrac{\sum_{k \in [l,r]}a_k}{r-l+1} \le r\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\dfrac{\sum_{k \in [l,r]}a_k}{r-l+1} <l\right] \\ =\space &\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}a_k \le r\times(r-l+1)\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}a_k <l\times(r-l+1)\right] \\ = \space & \sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}a_k - r\times(r-l+1) \le 0\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}a_k -l\times(r-l+1) < 0\right] \\ = \space & \sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}(a_k-r) \le 0\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[\sum_{k \in [l,r]}(a_k-l) < 0\right]\end{aligned}

定义 fi=j[1,i](ajr)f_i = \sum_{j\in[1,i]}(a_j-r)gi=j[1,i](ajl)g_i=\sum_{j\in[1,i]}(a_j-l),则上面的式子就可以转化为:

= l[1,n]r[l,n][frfl10]l[1,n]r[l,n][grgl1<0]= l[1,n]r[l,n][frfl10]l[1,n]r[l,n][grgl1<0]= l[1,n]r[l,n][frfl1]l[1,n]r[l,n][gr<gl1]= r[l,n]l[0,r)[frfl]r[l,n]l[0,r)[gr<gl1]\begin{aligned}= \space & \sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[f_r-f_{l-1} \le 0\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[g_r-g_{l-1} < 0\right] \\ =\space& \sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[f_r-f_{l-1} \le 0\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[g_r-g_{l-1} < 0\right] \\ =\space& \sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[f_r \le f_{l-1}\right] -\sum_{l\in[1,n]}\sum_{r \in [l,n]}\left[g_r < g_{l-1}\right] \\ =\space& \sum_{r \in [l,n]}\sum_{l\in[0,r)}\left[f_r \le f_{l}\right] -\sum_{r \in [l,n]}\sum_{l\in[0,r)}\left[g_r < g_{l-1}\right]\end{aligned}

就变成了一个逆序对问题,所以使用树状数组或逆序对即可。

P7453 大魔法师

大魔法师小 L 制作了 nn 个魔力水晶球,每个水晶球有水、火、土三个属性的能量值。小 L 把这 nn 个水晶球在地上从前向后排成一行,然后开始今天的魔法表演。

我们用 Ai,Bi,CiA_i,B_i,C_i 分别表示从前向后第 ii 个水晶球(下标从 11 开始)的水、火、土的能量值。

小 L 计划施展 mm 次魔法。每次,他会选择一个区间 [l,r][l,r],然后施展以下 33 大类、77 种魔法之一:

  1. 魔力激发:令区间里每个水晶球中特定属性的能量爆发,从而使另一个特定属性的能量增强。具体来说,有以下三种可能的表现形式:

    • 火元素激发水元素能量:令 Ai=Ai+BiA_i=A_i+B_i
    • 土元素激发火元素能量:令 Bi=Bi+CiB_i=B_i+C_i
    • 水元素激发土元素能量:令 Ci=Ci+AiC_i=C_i+A_i

    需要注意的是,增强一种属性的能量并不会改变另一种属性的能量,例如 Ai=Ai+BiA_i=A_i+B_i 并不会使 BiB_i 增加或减少。

  2. 魔力增强:小 L 挥舞法杖,消耗自身 vv 点法力值,来改变区间里每个水晶球的特定属性的能量。具体来说,有以下三种可能的表现形式:

    • 火元素能量定值增强:令 Ai=Ai+vA_i=A_i+v
    • 水元素能量翻倍增强:令 Bi=Bi×vB_i=B_i\times v
    • 土元素能量吸收融合:令 Ci=vC_i=v
  3. 魔力释放:小L将区间里所有水晶球的能量聚集在一起,融合成一个新的水晶球,然后送给场外观众。生成的水晶球每种属性的能量值等于区间内所有水晶球对应能量值的代数和。需要注意的是,魔力释放的过程不会真正改变区间内水晶球的能量。

值得一提的是,小 L 制造和融合的水晶球的原材料都是定制版的 OI 工厂水晶,所以这些水晶球有一个能量阈值 998244353998244353。当水晶球中某种属性的能量值大于等于这个阈值时,能量值会自动对阈值取模,从而避免水晶球爆炸。

小 W 为小 L(唯一的)观众,围观了整个表演,并且收到了小 L 在表演中融合的每个水晶球。小 W 想知道,这些水晶球蕴涵的三种属性的能量值分别是多少。

P7453 大魔法师 解法

考虑将这些都写成矩阵变换的形式,然后区间乘,维护区间和即可。

代码为线段树,通过展开矩阵乘法加速(不卡过不去,我常数太大了)。

// Problem: P7453 [THUSCH2017] 大魔法师
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7453
// Memory Limit: 500 MB
// Time Limit: 5000 ms

#include<stdio.h>
#include<ctype.h>

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

const int mod = 998244353;
const int maxl = 4;
struct matrix{
	int data[maxl][maxl];
	int* operator[](int index){return data[index];}
	matrix() { for(int i=0;i<maxl;i++)for(int j=0;j<maxl;j++)data[i][j] = 0;}
};

bool operator==(matrix a,matrix b){
	for(int i=0;i<maxl;i++)
		for(int j=0;j<maxl;j++)
			if(a[i][j] != b[i][j])
				return false;
	return true;
}
matrix operator+(matrix a,matrix b){
	matrix res;
	for(int i=0;i<maxl;i++)
		for(int j=0;j<maxl;j++)
			res[i][j] = (a[i][j]+b[i][j])>=mod ? (a[i][j]+b[i][j]-mod) : (a[i][j]+b[i][j]);
	return res;
}
matrix operator*(matrix a,matrix b){
	matrix res;
	res[0][0] = (1ll * a[0][1] * b[1][0] + 1ll * a[0][0] * b[0][0] + 1ll * a[0][2] * b[2][0] + 1ll * a[0][3] * b[3][0]) % mod;
	res[0][1] = (1ll * a[0][0] * b[0][1] + 1ll * a[0][2] * b[2][1] + 1ll * a[0][1] * b[1][1] + 1ll * a[0][3] * b[3][1]) % mod;
	res[0][2] = (1ll * a[0][0] * b[0][2] + 1ll * a[0][1] * b[1][2] + 1ll * a[0][2] * b[2][2] + 1ll * a[0][3] * b[3][2]) % mod;
	res[0][3] = (1ll * a[0][0] * b[0][3] + 1ll * a[0][1] * b[1][3] + 1ll * a[0][2] * b[2][3] + 1ll * a[0][3] * b[3][3]) % mod;
	res[1][0] = (1ll * a[1][0] * b[0][0] + 1ll * a[1][1] * b[1][0] + 1ll * a[1][2] * b[2][0] + 1ll * a[1][3] * b[3][0]) % mod;
	res[1][1] = (1ll * a[1][0] * b[0][1] + 1ll * a[1][1] * b[1][1] + 1ll * a[1][2] * b[2][1] + 1ll * a[1][3] * b[3][1]) % mod;
	res[1][2] = (1ll * a[1][0] * b[0][2] + 1ll * a[1][1] * b[1][2] + 1ll * a[1][2] * b[2][2] + 1ll * a[1][3] * b[3][2]) % mod;
	res[1][3] = (1ll * a[1][0] * b[0][3] + 1ll * a[1][1] * b[1][3] + 1ll * a[1][2] * b[2][3] + 1ll * a[1][3] * b[3][3]) % mod;
	res[2][0] = (1ll * a[2][0] * b[0][0] + 1ll * a[2][1] * b[1][0] + 1ll * a[2][2] * b[2][0] + 1ll * a[2][3] * b[3][0]) % mod;
	res[2][1] = (1ll * a[2][0] * b[0][1] + 1ll * a[2][1] * b[1][1] + 1ll * a[2][2] * b[2][1] + 1ll * a[2][3] * b[3][1]) % mod;
	res[2][2] = (1ll * a[2][0] * b[0][2] + 1ll * a[2][1] * b[1][2] + 1ll * a[2][2] * b[2][2] + 1ll * a[2][3] * b[3][2]) % mod;
	res[2][3] = (1ll * a[2][0] * b[0][3] + 1ll * a[2][1] * b[1][3] + 1ll * a[2][2] * b[2][3] + 1ll * a[2][3] * b[3][3]) % mod;
	res[3][0] = (1ll * a[3][0] * b[0][0] + 1ll * a[3][1] * b[1][0] + 1ll * a[3][2] * b[2][0] + 1ll * a[3][3] * b[3][0]) % mod;
	res[3][1] = (1ll * a[3][0] * b[0][1] + 1ll * a[3][1] * b[1][1] + 1ll * a[3][2] * b[2][1] + 1ll * a[3][3] * b[3][1]) % mod;
	res[3][2] = (1ll * a[3][0] * b[0][2] + 1ll * a[3][1] * b[1][2] + 1ll * a[3][2] * b[2][2] + 1ll * a[3][3] * b[3][2]) % mod;
	res[3][3] = (1ll * a[3][0] * b[0][3] + 1ll * a[3][1] * b[1][3] + 1ll * a[3][2] * b[2][3] + 1ll * a[3][3] * b[3][3]) % mod;
	return res;
}

namespace typed{
	matrix add_unit,mul_unit,fire_splash,soil_splash,water_splash;
	inline void init_matrix(){
		mul_unit[0][0] = mul_unit[1][1] = mul_unit[2][2] = mul_unit[3][3] =
		fire_splash[0][0] = fire_splash[0][1] = fire_splash[1][1] = fire_splash[2][2] = fire_splash[3][3] =
		soil_splash[0][0] = soil_splash[1][1] = soil_splash[1][2] = soil_splash[2][2] = soil_splash[3][3] =
		water_splash[0][0] = water_splash[1][1] = water_splash[2][0] = water_splash[2][2] = water_splash[3][3] = 1;
	}
	inline matrix ball(int a,int b,int c){
		matrix res;
		res[0][0] = a, res[1][0] = b, res[2][0] = c, res[3][0] = 1;
		return res;
	}
	inline matrix fire_enchant(int v){
		matrix res;
		res[0][0] = res[1][1] = res[2][2] = res[3][3] = 1, res[0][3] = v;
		return res;
	}
	inline matrix water_enchant(int v){
		matrix res;
		res[1][1] = v;
		res[0][0] = res[2][2] = res[3][3] = 1;
		return res;
	}
	inline matrix soil_enchant(int v){
		matrix res;
		res[2][3] = v;
		res[0][0] = res[1][1] = res[3][3] = 1;
		return res;
	}
}

namespace segtree{
	const int maxn = 1.1e6;
	int a,b,c;
	matrix data[maxn],lazy[maxn];
	inline void init(int index,int l,int r){
		lazy[index] = typed::mul_unit;
		if(l==r){
			a=read(),b=read(),c=read();
			data[index] = typed::ball(a,b,c);
			return;
		}
		int mid = (l+r)>>1;
		init(index<<1,l,mid),init(index<<1|1,mid+1,r);
		data[index] = data[index<<1] + data[index<<1|1];
	}
	inline void setlazy(int index,matrix v){
		data[index] = v * data[index];
		lazy[index] = v * lazy[index];
	}
	inline void pushdown(int index){
		if(lazy[index] == typed::mul_unit)
			return;
		setlazy(index<<1,lazy[index]),setlazy(index<<1|1,lazy[index]);
		lazy[index] = typed::mul_unit;
	}
	inline void mul(int index,int l,int r,int ql,int qr,matrix val){
		pushdown(index);
		if(ql <= l and r <= qr){
			setlazy(index,val);
			return;
		}
		if(l>qr or r<ql)
			return;
		int mid = (l+r)>>1;
		mul(index<<1,l,mid,ql,qr,val),mul(index<<1|1,mid+1,r,ql,qr,val);
		data[index] = data[index<<1] + data[index<<1|1];
	}
	inline matrix query(int index,int l,int r,int ql,int qr){
		pushdown(index);
		if(ql <= l and r <= qr)
			return data[index];
		if(l>qr or r<ql)
			return typed::add_unit;
		int mid = (l+r)>>1;
		return query(index<<1,l,mid,ql,qr)+query(index<<1|1,mid+1,r,ql,qr);
	}
}
using segtree::init;
using segtree::mul;
using segtree::query;

int n,m,u,v,w,c;

int main(){
	typed::init_matrix();

	n=read();
	init(1,1,n);
	m=read();
	for(int i=1;i<=m;i++){
		u=read();
		if(u==1)
			v=read(),w=read(),
			mul(1,1,n,v,w,typed::fire_splash);
		else if(u==2)
			v=read(),w=read(),
			mul(1,1,n,v,w,typed::soil_splash);
		else if(u==3)
			v=read(),w=read(),
			mul(1,1,n,v,w,typed::water_splash);
		else if(u==4)
			v=read(),w=read(),c=read(),
			mul(1,1,n,v,w,typed::fire_enchant(c));
		else if(u==5)
			v=read(),w=read(),c=read(),
			mul(1,1,n,v,w,typed::water_enchant(c));
		else if(u==6)
			v=read(),w=read(),c=read(),
			mul(1,1,n,v,w,typed::soil_enchant(c));
		else if(u==7){
			v=read(),w=read();
			matrix res = query(1,1,n,v,w);
			printf("%d %d %d\n",res[0][0],res[1][0],res[2][0]);
		}
	}
	return 0;
}

P2922 Secret Message

贝茜正在领导奶牛们逃跑.为了联络,奶牛们互相发送秘密信息.

信息是二进制的,共有 MM1M500001 \le M \le 50000)条,反间谍能力很强的约翰已经部分拦截了这些信息,知道了第 ii 条二进制信息的前 bib_i1bi100001 \le b_i \le 10000)位,他同时知道,奶牛使用 NN1N500001 \le N \le 50000)条暗号.但是,他仅仅知道第 jj 条暗号的前 cjc_j1cj100001 \le c_j \le 10000)位。

对于每条暗号 jj,他想知道有多少截得的信息能够和它匹配。也就是说,有多少信息和这条暗号有着相同的前缀。当然,这个前缀长度必须等于暗号和那条信息长度的较小者。

在输入文件中,位的总数(即 bi+ci\sum b_i + \sum c_i)不会超过 500000500000

P2922 Secret Message 解法

看到这题就应该拍一个字典树上去,有两种情况存在:

无脑开树,路径上查询有多少个结尾,最后查询子树和即可。

// Problem: P2922 [USACO08DEC] Secret Message G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2922
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<stdio.h>

const int maxn = 1.2*500000;

int sons[maxn][2],cnt=1,tag[maxn],sum[maxn];

void build(){
	int size,val,index=1;
	scanf("%d",&size);
	for(int i=0;i<size;i++){
		scanf("%d",&val);
		if(!sons[index][val])
			// printf("create %d\n",cnt+1),
			sons[index][val] = ++cnt;
		index = sons[index][val];
		sum[index]++;
	}
	tag[index]++;
	sum[index]--;
}

int query(){
	int size=0,val=0,index=1,res=0;
	scanf("%d",&size);
	for(int i=0;i<size;i++){
		scanf("%d",&val);
		// printf("add tag_%d\n",index);
		index = sons[index][val];
		res += tag[index];
	}
	// res += sum[sons[index][0]] + sum[sons[index][1]];
	return res + sum[index];
}

int n,m;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		build();
	for(int i=1;i<=m;i++)
		printf("%d\n",query());
	return 0;
}

P4824 Censoring S

Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志,因此他们在谷仓等待挤奶期间,可以有足够的文章可供阅读。不幸的是,最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章,FJ不愿让他的奶牛们看到这些内容。

FJ已经根据杂志的所有文字,创建了一个字符串 SS ( SS 的长度保证不超过 10610^6 ),他想删除其中的子串 TT ,他将删去 SS 中第一次出现的子串 TT ,然后不断重复这一过程,直到 SS 中不存在子串 TT

注意:每次删除一个子串后,可能会出现一个新的子串 TT (说白了就是删除之后,两端的字符串有可能会拼接出来一个新的子串 TT )。

P4824 Censoring S 解法

之前就认为是神题的神题。

考虑 KMP 匹配,主要去考虑删除怎么做。

在删除之后,如果我们要继续匹配,那么就需要将匹配恢复到之前的状态。

现在关键就在于这个记录状态和删除状态的过程。

我们不能回退指针,这样会让复杂度假掉,考虑记录 kmp 的匹配栈,在匹配到时弹掉。

匹配栈应该是用于记录第二指针的位置的。

然后维护第二个栈用于存放答案,找到就在两个栈中弹出匹配到的部分,这题就做完了,但是用STL记得判空

// Problem: P4824 [USACO15FEB] Censoring S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4824
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<stdio.h>
#include<string.h>
#include<stack>

const int maxn = 3e6;

char str[maxn],fnd[maxn];
int nxt[maxn];
int sl,fl,ps,pf;
std::stack<int> matches;
std::stack<char> result,re2;

int main(){
	scanf("%s%s",str,fnd);
	sl = strlen(str);
	fl = strlen(fnd);

	ps=0,pf=-1;
	nxt[0]=-1;
	while(ps<fl){
		if(pf==-1 or fnd[ps] == fnd[pf])
			nxt[++ps] = ++pf;
		else
			pf = nxt[pf];
	}

	ps=0,pf=0;
	while(ps<sl){
		if(pf==-1 or str[ps] == fnd[pf])
			result.push(str[ps]),matches.push(++pf),ps++;
		else
			pf = nxt[pf];
		if(pf == fl){
			for(int i=0;i<fl;i++) matches.pop(),result.pop();
			if(!matches.empty())
				pf = matches.top();
			else
				pf = 0;
		}
	}

	while(!result.empty())
		re2.push(result.top()),
		result.pop();

	while(!re2.empty())
		putchar(re2.top()),
		re2.pop();

	return 0;
}

CF 1883E

给定长度为 nn 的序列 aa,你可以进行以下操作。

选取一个 ii 满足 1in1\le i\le n,使 aia_i 变为原来的 22 倍。

求最少需要几次操作使得 aa 为一个不下降的序列。

CF 1883E 解法

最优的策略一定是从左到右扫,但是乘可能一定会炸存储范围。

那这里我们可以用一个好玩的 trick,忘了哪里看到的了。

有如下基本事实成立:

log22x=log22+log2x=1+log2x\begin{aligned}\log_22x &= \log_22 + \log_2x \\ &= 1+\log_2 x\end{aligned}

所以你可以把所有数 log\log 了再做,但直接做的话会被卡精度,然后我卡不过去。

所以这里你开一个分数类将数字拆成相对大小和零头,比如 log215=3+log2158\log_215 = 3 + \log_2\dfrac{15}{8},然后再做就很简单了(对数到底数大于 11 实数的映射也是单增的),注意零头带来的边界条件。

struct frac{
    i64 a, b;
    void simplize(){
        i64 g = std::__gcd(a, b);
        a/=g, b/=g;
    }
    frac(i64 a_ = 0, i64 b_ = 1) : a(a_), b(b_) { simplize(); }
    bool m2() { return a < 2*b; }
    void d2() { b *= 2; }
};

bool operator== (frac a, frac b) {
    return a.a * b.b == a.b * b.a;
}
bool operator> (frac a, frac b) { return a.a * b.b > a.b * b.a; }

const int maxn = 3e5;

int n;
vint ve, re;
frac fs[maxn];

double mx;
long long ans = 0;

typedef long long i64;

void solve(){
    ans = 0;
    cin >>n;

    in_vec(ve, n);
    to_siz(re, n);

    array(ve);

    for(int i=0;i<ve.size();i++){
        fs[i] = frac(ve[i]);
        while(not fs[i].m2()) { fs[i].d2();re[i]++; }
        fs[i].simplize();
        if(i==0)
            continue;

        if(re[i-1] >= re[i]){
            int delta = (re[i-1] - re[i]) + (fs[i-1] > fs[i]);
            re[i] += delta;
            ans += delta;
        }
    }
    cout << ans << endl;
}

CF1883F You Are So Beautiful

给定数列 aa,定义一个子序列 SS 是合法的当且仅当从 aa 中有且仅有一种选法能选出子序列 SS(选法相同定义为最终选出的位置集合相同)。

求其有多少非空合法子序列,满足它占据了 aa 中一端连续的区间。

n105n\leq 10^5

CF1883F You Are So Beautiful 解法

有如下基本事实成立:

若选择一段区间,第一个数在原数列是第一次出现,最后一个数在原数列是最后一次出现,则这段区间在原数列唯一。

所以开桶扫一扫就行了。

int n;
vint li, fr, ls;
std::map<int,int> las;

void solve(){
    las.clear();
    cin >> n;
    in_vec(li,n);
    to_siz(fr,n);
    to_siz(ls,n);
    for(int i=0;i<n;i++)
        fr[i] = !las.count(li[i]),
        las[li[i]]=i;
    for(int i=0;i<n;i++)
        ls[i] = (las[li[i]] == i);
    for(int i=1;i<n;i++)
        fr[i] += fr[i-1];
    i64 ans=0;
    for(int i=n-1;i>=0;i--)
        ans += fr[i]*ls[i];
    cout << ans << endl;
    // array(fr);
    // array(ls);
}

CF 1883G1 Dances (Easy version)

CF 1883G1 Dances (Easy version) 解法

我的思路是尺取,正解是二分答案,那就两个都讲。 两个解法基于一个相同的假定:排序数组,删除一定删 AA 的最大值和 BB 的最小值,这样一定是不劣的。

CF 1883G1 Dances (Easy version) 解法1 尺取

考虑数列处于如下一个情况:i[1,l]Ai<Bi\forall i \in [1,l] A_i < B_i,这个情况是可以放缩的,也就是说 i[1,l]Ai<Bi+1\forall i \in [1,l] A_i < B_{i+1} 成立。

所以双指针一下,细节说不清楚,结合 A=[1,1,1,2,2,3,3,4],B=[1,1,1,1,3,3,3,3]A = [1,1,1,2,2,3,3,4],B = [1,1,1,1,3,3,3,3],答案为 44 模拟一下即可。

vint a, b;
int n, m;

void solve(){
    cin >> n >> m;
    in_vec(a, n-1);
    a.push_back(m);
    in_vec(b, n);

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    array(a); array(b);

    int la=0, ra=n-1, lb=0, rb=n-1, ans = 0;
    while(la <= ra){
        if(a[ra] >= b[rb]){
            ans ++;
            if(rb+1<n)
                rb++;
            else
                ra--,lb++;
        }
        else
            ra--,rb--;
    }

    cout << ans << endl;
}

CF 1883G1 Dances (Easy version) 解法2 二分答案

二分删几个然后 O(n)O(n) 检验即可。

int n, m;
vint i1, v1, v2;

bool check(int l1, int l2, int siz){
    for(int i=0;i<siz;i++)
        if(v1[l1+i] >= v2[l2+i])
            return false;
    return true;
}

int solve(int m){
    to_siz(v1, n);
    copy(i1.begin(), i1.end(), v1.begin());
    v1[n-1] = m;
    sort(v1.begin(), v1.end());
    array(v1);
    array(v2);

    int l=0, r=n;
    while(r-l>1){
        int mid = (l+r)>>1;
        if(check(0,mid,n-mid))
            r = mid;
        else
            l = mid+1;
    }

    for(int i=l;i<=r;i++)
        if(check(0,i,n-i)){
            return i;
        }
}

void solve(){
    cin >> n >> m;
    in_vec(i1, n-1);
    in_vec(v2, n);
    sort(v2.begin(), v2.end());
    cout << solve(1) << endl;
}

CF1883G2 Dances (Hard Version)

对于每组数据,给定 nnmm 与数组 aa 的第 22nn 项和数组 bb 的第 11nn 项。你需要根据 aa 数组求出 mmcc 数组的值,具体地:

对于每一个独立的 c[i]c[i] 数组与互不影响的 bb ,你可以将 bbc[i]c[i] 数组中的数字随意排序,再随意删除 c[i]c[i]bb 中的 kk 个数,对于每一个 c[i]c[i] 数组,求最小的 k[i]k[i] 使得1jn,c[i]_jbj \forall 1\le j \le n, c[i]\_j \le b_j ,输出所有 c[i]c[i] 的删除数 k[i]k[i] 的和

CF1883G2 Dances (Hard Version) 解法

你现在已经会 1883G1 了。

然后你需要处理多组询问。

这个很简单的,假设答案关于第一个数字 mm 的函数是 f(m)f(m),那么容易证明 f(1)=f(2)=f(3)==f(x)=f(x+1)+1=f(x+2)+1=f(x+3)+1==f(m)+1f(1) = f(2) = f(3) = \cdots = f(x) = f(x+1)+1 = f(x+2)+1 = f(x+3)+1 = \cdots = f(m)+1

说人话就是,第一个数对答案的影响至多有 11,然后你二分求得 xx 即可。

如果用我尺取的思路似乎比正解快一个 log\log

int n, m;
vint v1, a, b;

int solve_ans(int spec){
    to_siz(a, n);
    copy(v1.begin(), v1.end(), a.begin());
    a[n-1] = spec;
    sort(a.begin(), a.end());
    int la=0, ra=n-1, lb=0, rb=n-1, ans = 0;
    while(la <= ra){
        if(a[ra] >= b[rb]){
            ans ++;
            if(rb+1<n)
                rb++;
            else
                ra--,lb++;
        }
        else
            ra--,rb--;
    }
    return ans;
}

void solve(){
    cin >> n >> m;
    in_vec(v1, n-1);
    in_vec(b, n);
    sort(b.begin(), b.end());
    int l=0, r=m; // find max l when f = 0

    int initial = solve_ans(1);
    while(r-l>1){
        int mid = (l+r)>>1;
        if(solve_ans(mid) - initial)
            r = mid-1;
        else
            l = mid;
    }

    long long ans = 1ll * initial * m;
    for(int i=r;i>=l;i--)
        if(solve_ans(i) - initial == 0){
            if(i>=m){
                cout << ans << endl;
                return;
            }
            ans = ans + m-i;
            cout << ans << endl;
            return;
        }
}
int n, m;
vint i1, v1, v2;

bool check(int l1, int l2, int siz){
    for(int i=0;i<siz;i++)
        if(v1[l1+i] >= v2[l2+i])
            return false;
    return true;
}

int solve_ans(int m){
    to_siz(v1, n);
    copy(i1.begin(), i1.end(), v1.begin());
    v1[n-1] = m;
    sort(v1.begin(), v1.end());
    array(v1);
    array(v2);

    int l=0, r=n;
    while(r-l>1){
        int mid = (l+r)>>1;
        if(check(0,mid,n-mid))
            r = mid;
        else
            l = mid+1;
    }

    for(int i=l;i<=r;i++)
        if(check(0,i,n-i)){
            return i;
        }
}

void solve(){
    cin >> n >> m;
    in_vec(i1, n-1);
    in_vec(v2, n);
    sort(v2.begin(), v2.end());
    int l=0, r=m; // find max l when f = 0

    int initial = solve_ans(1);
    while(r-l>1){
        int mid = (l+r)>>1;
        if(solve_ans(mid) - initial)
            r = mid-1;
        else
            l = mid;
    }

    long long ans = 1ll * initial * m;
    for(int i=r;i>=l;i--)
        if(solve_ans(i) - initial == 0){
            if(i>=m){
                cout << ans << endl;
                return;
            }
            ans = ans + m-i;
            cout << ans << endl;
            return;
        }
}

P5018 对称二叉树

一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:

  1. 二叉树;
  2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

下图中节点内的数字为权值,节点外的 idid 表示节点编号。

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数 最多。请输出这棵子树的节点数。

注意:只有树根的树也是对称二叉树。本题中约定,以节点 TT 为子树根的一棵“子 树”指的是:节点TT 和它的全部后代节点构成的二叉树。

CF1883G2 Dances (Hard Version) 解法

乱搞做法。

hash 子树是肯定的。

考虑如下基本事实:矩阵乘法不满足交换律,所以用它来确定树的形态。

具体地,设定两个不同的矩阵 L,RL, R,然后如下规定:

最后就秒掉了。

// Problem: P5018 [NOIP2018 普及组] 对称二叉树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5018
// Memory Limit: 256 MB
// Time Limit: 1000 ms

#include<stdio.h>
#include<memory.h>

const int mod1 = 998244353, mod2 = 998244853;
const int maxl = 2, maxn = 1000007;

struct matrix{
    int data1[maxl][maxl], data2[maxl][maxl];
    matrix() { memset(data1,0,sizeof data1), memset(data2,0,sizeof data2); }
};

bool operator==(matrix a, matrix b){
    for(int i=0;i<maxl;i++)
        for(int j=0;j<maxl;j++)
            if(a.data1[i][j] != b.data1[i][j] or a.data2[i][j] != b.data2[i][j])
                return false;
    return true;
}

matrix operator*(matrix a, matrix b){
    matrix res;
    for(int i=0;i<maxl;i++)
        for(int j=0;j<maxl;j++)
            for(int k=0;k<maxl;k++)
                res.data1[i][j] = (1ll*res.data1[i][j] + 1ll*a.data1[i][k]*b.data1[k][j] )%mod1,
                res.data2[i][j] = (1ll*res.data2[i][j] + 1ll*a.data2[i][k]*b.data2[k][j] )%mod2;
    return res;
}

matrix operator+(matrix a, matrix b){
    matrix res;
    for(int i=0;i<maxl;i++)
        for(int j=0;j<maxl;j++)
            res.data1[i][j] = (res.data1[i][j] + a.data1[i][j] + b.data1[i][j]) %mod1,
            res.data2[i][j] = (res.data2[i][j] + a.data2[i][j] + b.data2[i][j]) %mod2;
    return res;
}

namespace typed{
    matrix L,R,I;
    void prework(){
        L.data1[0][0] = L.data2[0][0] = 331;
        L.data1[1][1] = L.data2[1][1] = 821;
        L.data1[1][0] = L.data2[1][0] = 711;
        L.data1[0][1] = L.data2[0][1] = 961;

        R.data1[0][0] = R.data2[0][0] = 169;
        R.data1[1][0] = R.data2[1][0] = 117;
        R.data1[0][1] = R.data2[0][1] = 128;
        R.data1[1][1] = R.data2[1][1] = 133;

        I.data1[0][0] = I.data1[1][1] = I.data2[0][0] = I.data2[1][1] = 1;
    }
}

matrix f[maxn],fr[maxn];
int ls[maxn], rs[maxn], v[maxn], size[maxn];
int npos = -1;

int n,mx;

void dfs(int index){
    if(index == npos)
        return;
    size[index] = 1;
    dfs(ls[index]);
    dfs(rs[index]);

    if(ls[index] != -1)
        size[index] += size[ls[index]];
    if(rs[index] != -1)
        size[index] += size[rs[index]];

    f [index].data1[0][0] = f [index].data1[1][1] = f [index].data2[0][0] = f [index].data2[1][1] = v[index];
    fr[index].data1[0][0] = fr[index].data1[1][1] = fr[index].data2[0][0] = fr[index].data2[1][1] = v[index];

    if(ls[index] != -1)
        f [index] = f [index] + typed::L * f[ls[index]],
        fr[index] = fr[index] + typed::R * fr[ls[index]];

    if(rs[index] != -1)
        f [index] = f [index] + typed::R * f[rs[index]],
        fr[index] = fr[index] + typed::L * fr[rs[index]];

    if(f[index] == fr[index]) mx = size[index] > mx ? size[index] : mx;
}

int main(){
    typed::prework();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",v+i);
    for(int i=1;i<=n;i++)
        scanf("%d%d",ls+i,rs+i);
    dfs(1);
    printf("%d",mx);
    return 0;
}

P8085 KRIPTOGRAM

现有一段明文和一部分密文。明文和密文都由英文单词组成,且密文中的一个单词必然对应着明文中的一个单词。

求给出的密文在明文中可能出现的最早位置。

P8085 KRIPTOGRAM 解法

考虑“相同的内容相同,不同的内容不同”这条约束。

考虑一段区间,每个点的值都是距离自己最近的上一个相同串的距离,则可以解决这个问题。

然后就滑动窗口维护这个区间的 hash 即可。

烦人,快速幂写错了。

// Problem: P8085 [COCI2011-2012#4] KRIPTOGRAM
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8085
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include <algorithm>
#include <stdio.h>
#include <random>
#include <vector>
#include <queue>
#include <map>

const int mod1 = 998244353,
          mod2 = 1000000007;
const int maxn = 1.2e6;

std::mt19937 gen(387961);
int lucky1[maxn], lucky2[maxn];
const int p1 = 387, p2 = 961;
const int g1 = 385, g2 = 633;

int pow1(int x,int p){ int res = 1; while(p){ if(p&1) res = 1ll * res * x % mod1; x = 1ll * x * x % mod1; p>>=1; } return res; }
int pow2(int x,int p){ int res = 1; while(p){ if(p&1) res = 1ll * res * x % mod2; x = 1ll * x * x % mod2; p>>=1; } return res; }

void ins(std::vector<std::pair<int,int>>& v){
    int val1 = 0, val2 = 0;
    char ch;
    while(true){
        ch = getchar();
        if(ch == '\n' or ch == '\r')
            continue;
        if(ch == '$')
            return;
        else if(ch == ' ')
            v.push_back({val1, val2}), val1 = 0, val2 = 0;
        else
            val1 = (1ll * val1 * p1 + lucky1[ch-'a']) % mod1,
            val2 = (1ll * val2 * p2 + lucky2[ch-'a']) % mod2;
    }
}

std::vector<std::pair<int,int>> v1, v2;
std::vector<int> l1, l2;
std::vector<int> fr1, fr2;
std::map<std::pair<int,int>, int> bucket;

int h11, h12, h21, h22;
void hash_initial(const std::vector<int>& ve, int lenn, int &h1, int& h2){
    h1 = 0, h2 = 0;
    for(int i=0; i<lenn; i++)
        h1 = (1ll * h1 * g1 + mod1 + ve[i]) % mod1,
        h2 = (1ll * h2 * g2 + mod2 + ve[i]) % mod2;
}

int main(){
    for(int i=0;i<maxn;i++) lucky1[i] = gen() % mod1, lucky2[i] = gen() % mod2;

    ins(v1), ins(v2);
    bucket.clear(); for(int i=v1.size()-1; i>=0       ; i--) l1 .push_back(bucket.count(v1[i])?(bucket[v1[i]]-i):-1), bucket[v1[i]]=i; std::reverse(l1.begin(), l1.end());
    bucket.clear(); for(int i=v2.size()-1; i>=0       ; i--) l2 .push_back(bucket.count(v2[i])?(bucket[v2[i]]-i):-1), bucket[v2[i]]=i; std::reverse(l2.begin(), l2.end());
    bucket.clear(); for(int i=0          ; i<v1.size(); i++) fr1.push_back(bucket.count(v1[i])?(i-bucket[v1[i]]):-1), bucket[v1[i]]=i;
    bucket.clear(); for(int i=0          ; i<v2.size(); i++) fr2.push_back(bucket.count(v2[i])?(i-bucket[v2[i]]):-1), bucket[v2[i]]=i;

    hash_initial(fr1, fr2.size(), h11, h12);
    hash_initial(fr2, fr2.size(), h21, h22);

    for(int l=0, r=fr2.size(); r<fr1.size(); l++,r++){
        if(h11 == h21 and h12 == h22) {
            printf("%d\n", l+1);
            return 0;
        }
        h11 = 1ll * h11 * g1 % mod1, h12 = 1ll * h12 * g2 % mod2;

        if(l1[l]!=-1){
            if(r-l-l1[l] >= 0)
                h11 = (1ll * h11 + mod1 - 1ll * (fr1[l+l1[l]]+1) * pow1(g1, r-l-l1[l]) %mod1) % mod1,
                h12 = (1ll * h12 + mod2 - 1ll * (fr1[l+l1[l]]+1) * pow2(g2, r-l-l1[l]) %mod2) % mod2;
            fr1[l+l1[l]]=-1;
        }
        h11 = (1ll * h11 + 1ll * mod1 + 1ll * -fr1[l] * pow1(g1, r-l) %mod1) % mod1,
        h12 = (1ll * h12 + 1ll * mod2 + 1ll * -fr1[l] * pow2(g2, r-l) %mod2) % mod2;
        fr1[l]=0;
        h11 = (1ll * h11 + mod1 + fr1[r]) % mod1,
        h12 = (1ll * h12 + mod2 + fr1[r]) % mod2;
    }

    printf("no such match.\n");
    return 0;
}

校内模拟赛 【数据删除】

原题不说,因为这道题太太太好玩了就放上来了!

你需要维护一个数据结构,见下。

校内模拟赛 【数据删除】 解法

权值线段树。

【数据删除】

【数据删除】

这个是一个小清新 ds(确切地,线段树)题,相当于要维护这些:

首先我们来看二阶前缀和的式子(FF 为二阶前缀和数组,AA 为原数组):

因为我们要用线段树(确切地,权值线段树)维护,那么我们需要考虑二维前缀和应该如何合并。

Fn=i[1,n]j[1,i]Ai=i[1,k]j[1,i]Ai+i[k+1,n]j[1,i]Ai=i[1,k]j[1,i]Ai+i[k+1,n](j[1,k]Ai+j[k+1,n]Ai)=i[1,k]j[1,i]Ai+i[k+1,n](j[1,k]Ai+j[k+1,n]Ai)=i[1,k]j[1,i]Ai+i[k+1,n]j[1,k]Ai+(nk)j[k+1,n]Ai\begin{aligned}F_n &= \sum_{i\in[1,n]}\sum_{j\in[1,i]}A_i \\ &= \sum_{i\in[1,k]}\sum_{j\in[1,i]}A_i + \sum_{i\in[k+1,n]}\sum_{j\in[1,i]}A_i \\ &= \sum_{i\in[1,k]}\sum_{j\in[1,i]}A_i + \sum_{i\in[k+1,n]}(\sum_{j\in[1,k]}A_i+\sum_{j\in[k+1,n]}A_i) \\ &= \sum_{i\in[1,k]}\sum_{j\in[1,i]}A_i + \sum_{i\in[k+1,n]}(\sum_{j\in[1,k]}A_i+\sum_{j\in[k+1,n]}A_i) \\ &= \sum_{i\in[1,k]}\sum_{j\in[1,i]}A_i + \sum_{i\in[k+1,n]}\sum_{j\in[1,k]}A_i+(n-k)\sum_{j\in[k+1,n]}A_i\end{aligned}

也就是说,一个数列的二阶前缀和就是左半边的二阶前缀和加上右半边的二阶前缀和,最后加上右侧区间的长度乘上左侧的一阶前缀和。

struct Node {
    int f1;
    i64 f2;
    int sons[2];
    Node() {
        f1 = f2 = 0;
        sons[0] = sons[1] = 0;
    }
} tree[maxn];
inline void update(int index, int l, int r) {
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    int rlen = r - mid;
    tree[index].f1 = (tree[tree[index].sons[0]].f1) + (tree[tree[index].sons[1]].f1);
    tree[index].f2 = (tree[tree[index].sons[0]].f2) + (tree[tree[index].sons[1]].f2) +
                     1ll * rlen * tree[tree[index].sons[0]].f1;
}

请结合类型定义理解。

然后我们要反转这个玩意,有点复杂,具体地,将 0 反转成 1 实际上就是把左边的一段区间赋值为 1,反之亦然。

那我们其实是要找到从左边开始的包含 k 个 0 的连续区间,那就考虑权值线段树上二分。

什么,n109n \le 10^9 空间不行?动态开点就是了,空间复杂度是 O(qlogn)O(q \log n) 量级的。

这个写法比可能留下来的另一种线段树做法好想,不需要 lazy,还少存点东西。

这个是线段树上二分的板子:

// fill left ks 0 to 1
void fill0to1(int index, int l, int r, int