具体集训

xujunlang2011 · 2024-09-23 21:48:23 · 个人记录

9.22-23

T1(set)

给定正整数 n(n\le200)，计算 n 个元素的集合 \{1,2, ⋯ , n\}，所有非空子集和的乘积取模 998 244 353 后的结果。

发现 n 每加一，就会多出 n 与原来 n - 1 个数的集合的所有子集组成的子集，所以我们开一个数组存每个值的指数，用费马小定理处理，最后集中计算。

时间 O(n^3)，空间 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
const long long N = 305, p = 998244353;
long long T, n, t[N * N], ans = 1;
long long _pow(long long a, long long b)
{
    long long sum = 1;
    while (b)
    {
        if (b & 1)
        {
            sum *= a;
            sum %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return sum;
}
int main()
{
    freopen("set.in", "r", stdin);
    freopen("set.out", "w", stdout);
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        for (int j = i * (i + 1) / 2;j >= 1;j--)
        {
            t[j + i] += t[j];
            t[j + i] %= p - 1;
        }
        t[i]++;
        t[i] %= p - 1;
    }
    for (int i = 1;i <= n * (n + 1) / 2;i++)
    {
        ans *= _pow(i, t[i]);
        ans %= p;
    }
    cout << ans;
    return 0;
}

T2(hire)

富萝莉白浅有 n(n\le5\times10^5) 栋楼，编号分别为 1 到 n，每栋楼都有 k(k\le10^9) 个房间以供出租，每个房间只能住一人。对于租户来说，大家都希望租到一些地理位置合适的房间。假设某个人喜好的位置是 x，那么他就只会选择在 x 到 x+d 这些楼中的某一个房间住下（d(d\le5\times10^5) 是本题的给定值）。

现在有 m(m\le5\times10^5) 次询问，每次询问会给出两个数字 x(x\le n-d), y(y\le10^9)，表示现在来了 y 个喜好位置为 x 的人想要租房，如果 y 为负数，则表示离开了 -y 位喜好位置为 x 的租户，保证离开之后喜好位置为 x 的租户数量不为负数。对于每次询问你都需要回答 YES 或 NO 表示目前白浅能否给每个人都分配到理想的房间。

赛时写了个暴力贪心拿了 30pts。

若 [l,r] 区间内无法分配房间，则 \sum\limits_{i=l}^ra_i > k\times(r+d-l+1)。

将 d 提出来，\sum\limits_{i=l}^r(a_i-k) > k\times d。

然后找到小白逛公园。

代码被次掉了。

T3(block)

给定一棵根为 1 的包含 n(n\le10^5) 个点的树，这些点分别被编号为 1 到 n。其中第 i 个点的权值为 a_i，dfs 序为 dfn_i。现在你需要在这棵树上找到一个连通块，连通块需要满足题目给定的 m(m\le21) 个限制，每个限制用两个正整数 u, v 描述。要么 u, v不同时存在于这个连通块中，要么 u, v 在这个连通块上的 dfs 序不相邻。请在这棵树上找到满足题目限制条件的权值之和最大的连通块。

备注 1：一个结点可能有多个孩子结点，这些孩子是有 dfs 的先后顺序的，dfs 顺序就是题目输入的顺序。

备注 2：连通块的 dfs 序的定义：找到连通块在原树上深度最小的点开始 dfs，然后仍然根据题目读入的顺序获取每个点的 dfs 顺序。

不会。

T4(checkers)

白浅妹妹喜欢玩跳棋，她定义唯一合法的跳法是一个棋子 x 跳过一个相邻的棋子 y 到该直线上与 y 相邻的空位。她试图给一个局面能达到的所有局面计数。为了让大家都能做出这道题，所以白浅妹妹给出的是一个 1 \times n(n\le500) 的棋盘。白浅妹妹会告诉你初始每个位置是否有棋子，或者她觉得这个位置无所谓有没有棋子。你需要对于每一种棋盘的可能的初始情况，求出这个局面经过若干步跳跃能达到的局面有多少种。为了减少输出量，你只需要输出每种可能初始情况对应答案之和对 10^9+7 取模的结果。

先考虑没有 ? 的情况。

可以发现 11 可以自由移动。

还发现 11 在 1 的左边还是右边对方案数没影响，所以可以将单独的 1 删除。

现在只剩了 0 和 11，11 可以插入两个 0 或者 11 之间，设有 a 个 0，b 个 11，答案就是 C_{a+b}^b。

每日任务：费马小定理（2/1）

再考虑有问号的。

设 dp_{i,j,k,l} 表示填到第 i 位，有 j 个 0 和 k 个 11 的方案数，l 表示加上一个 1 能不能凑出一个 11。

~~然后发现 O(n^3) 空间爆了。~~

这时我们可以用类似弗洛伊德（Floyd）的方法把 i 这一维滚掉。

转移~~自己推~~到代码里看。

然后没了。

#include<bits/stdc++.h>
using namespace std;
const long long p = 1e9 + 7;
long long T, n, j[1000], dp[2][1000][1000][2], ans;
string s;
long long _pow(long long a, long long b)
{
    long long sum = 1;
    while (b)
    {
        if (b & 1)
        {
            sum *= a;
            sum %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return sum;
}
long long check(int a, int b)
{
    return j[b] * _pow(j[a] * j[b - a] % p, p - 2) % p;
}
int main()
{
    freopen("checkers.in", "r", stdin); 
    freopen("checkers.out", "w", stdout); 
    cin >> n >> s;
    s = " " + s + " ";
    j[0] = dp[0][0][0][0] = 1;
    for (int i = 1;i <= n;i++)
    {
        j[i] = j[i - 1] * i % p;
    }
    for (int i = 1;i <= n;i++)
    {
        for (int j = 0;j <= n;j++)
        {
            for (int k = 0;k <= n;k++)
            {
                dp[i % 2][j][k][0] = dp[i % 2][j][k][1] = 0;
                if (s[i] != '0')
                {
                    if (j)
                    {
                        dp[i % 2][j][k][0] += dp[i % 2 ^ 1][j - 1][k][1];
                    }
                    dp[i % 2][j][k][1] += dp[i % 2 ^ 1][j][k][0];
                }
                if (s[i] != '1')
                {
                    if (k)
                    {
                        dp[i % 2][j][k][0] += dp[i % 2 ^ 1][j][k - 1][0] + dp[i % 2 ^ 1][j][k - 1][1];
                    }
                }
                dp[i % 2][j][k][0] %= p;
                dp[i % 2][j][k][1] %= p;
            }
        }
    }
    for (int i = 0;i <= n;i++)
    {
        for (int j = 0;j <= n;j++)
        {
            ans += (dp[n % 2][i][j][0] + dp[n % 2][i][j][1]) % p * check(i, i + j) % p;
            ans %= p;
        }
    }
    cout << ans;
    return 0;
}

9.24

臭题目（悲）

T1(yiyi)

从前有个寺庙，名为依依寺。寺庙因《诗经·小雅》中的“昔我往矣，杨柳依依。今我来思，雨雪霏霏。” 而得名。

庙里有个老和尚和小和尚。老和尚叫章丘样，小和尚叫章吊痒。老和尚说“从前有个寺庙，名为依依寺。庙里有个老和尚和小和尚。老和尚叫章丘样，小和尚叫章吊痒......”

有一天，老和尚在拨算盘。他脑海中蹦出了这么一道题：

有 n=a+b+c 个数，其中有 a 个 0，b 个 1，c 个 2。我章丘样和你章吊痒轮流取数，我先手。设累计取出来的数总和为 s，若 s 是 3 的倍数，那么这一方输。如果数字取完了游戏还没结束，则没有数可以取的这一方输。

由于 a,b,c 可能很大，两和尚无法手玩得到，所以想让你编程来帮帮他们。

输入格式

第一行，输入数据组数 T，表示有 T 局游戏。

接下来 T 行，每行输入 a,b,c 表示老和尚和小和尚的一局游戏。

输出格式

输出共 T 行，若老和尚（即先手）赢，输出 First，否则输出 Second。

赛时没发现两个人数共用磕了三小时没过样例喜爆零。

赛后被大粪讨恶心。

直接给代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("yiyi.in", "r", stdin);
    freopen("yiyi.out", "w", stdout);
    int T;
    cin >> T;
    for (int i = 1;i <= T;i++)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        if (a % 2 == 1 && (b == 0 && c <= 1 || b - 1 <= c && c <= b + 1) || a % 2 == 0 && (b == 0 && c != 1 || b > 1 && c == 0))
        {
            cout << "Second\n";
        }
        else
        {
            cout << "First\n";
        }
    }
    return 0;
}

T2(wuyi)

从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给，小和尚叫扶弱呱。老和尚说 “从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给，小和尚叫扶弱呱......”

有一天，扶弱给在潜心研究排列。他在脑中随机一个排列的时候，脑海里冒出了这样一个问题：

对于一个排列 p=1,2,\dots,n，记 val(p) 等于最小的 i 满足 i>a ，如不存在则 val(p)=n+1。

可是 val(p) 的期望值是多少呢？显然，扶弱给没学过编程，需要你来帮帮他。

输入格式

一行一个正整数 n。

输出格式

输出 val(p) 的期望值模 998244353 的结果。

赛时推柿子推错了喜爆零。

还是分讨，对每一位计算 i>a_i 的期望。

#include<bits/stdc++.h>
using namespace std;
const long long p = 998244353;
long long n, j = 1, ans;
long long _pow(long long a, long long b)
{
    long long sum = 1;
    while (b)
    {
        if (b & 1)
        {
            sum *= a;
            sum %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return sum;
}
int main()
{
    freopen("wuyi.in", "r", stdin);
    freopen("wuyi.out", "w", stdout);
    cin >> n;
    ans = n + 1;
    for (int i = 1;i <= n;i++)
    {
        j *= i;
        j %= p;
        ans += (n + 1 - i) * j % p * ((_pow(i + 1, n - i) - _pow(i, n - i)) % p + p) % p;
        ans %= p;
    }
    cout << ans * _pow(j, p - 2) % p;
    return 0;
}

T3(yijiu)

传说中，小喵和小矣是一对夫妻，他们关系很和洽。由于两位都是数学系毕业的，所以平日里他们经常一起研究数学。

最近，他们发现，一个数不仅可以被若干个不同的二进制分解，还可以被若干个斐波那契数分解！

这里定义 fib_1 =1,fib_2 =2，对于 n\ge3 有 fib_n =fib_{n−1}+fib_{n−2}。但很快，他们发现分解方式并不唯一，不过只要满足分解成的斐波那契数不相邻，那么就有了唯一分解。

形式化地。设 x=\sum\limits_{i=1}^kfib_{ai}，满足 \forall i\in\left[1,k\right),a_i+1<a_{i+1} ，则此为 x 的唯一分解。

小喵定义 val(x) 表示 \oplus_{i=1}^kfib_{ai}，即分解的斐波那契数的异或和。

例如 x=6，那么 x=fib_4+fib_1，因此 val(x)=fib_4\oplus fib_1=4。

小矣紧接着想知道，如果给定 l,r，那么 \oplus_{i=l}^rval_i 的值是多少呢？

由于小矣脑子里有许多疑惑，所以他会询问你很多次。

输入格式

第一行，输入查询组数 T

接下来 T 行，每行输入两个数 l,r。

输出格式

输出共 T 行，每行输出相应的异或和。

设 S(x)=\oplus_{i=1}^xval_i 则 ans=S(r)-S(l-1)。

首先二分找到第一个小于等于 x 的k=feb_i，

易得 S(x)=S(k - 1)\oplus S(n - k)\oplus\begin{cases}k&n=k\mod2\\0&n\not=k\mod2\end{cases}

然后记搜。

#include<bits/stdc++.h>
using namespace std;
long long T, l, r, f[100], n = 87;
map <long long, long long> dp;
long long S(long long k)
{
    if (k == 0)
    {
        return k; 
    }
    if (dp[k])
    {
        return dp[k];
    }
    int l = 1, r = n, mid;
    while (l < r)
    {
        mid = (l + r + 1) / 2;
        if (f[mid] <= k)
        {
            l = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    return dp[k] = (S(f[l] - 1) ^ S(k - f[l]) ^ (k % 2 == f[l] % 2 ? f[l] : 0));
}
int main()
{
    freopen("yijiu.in", "r", stdin);
    freopen("yijiu.out", "w", stdout);
    f[0] = f[1] = 1;
    for (int i = 2;i <= n;i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }
    cin >> T;
    for (int ti = 1;ti <= T;ti++)
    {
        cin >> l >> r;
        cout << (S(r) ^ S(l - 1)) << "\n";
    }
    return 0;
}

T4(pear)

传说中，早在公元前 114514 年，有个神秘的国家，叫做补幺国。他们当时就已在用一种叫做 “补幺梨” 的货币，其因形状长得像梨子而得名。

补幺人通过“补幺梨”货币来进行交易。具体地，“补幺梨”有 n 种面值，分别为 a_1 ,a_2 ,\dots,a_n。

补幺人认为，在他们的视野里，m 是“补幺梨”基本面值的上限。因此，他们为了尽可能让这些基本的面值能覆盖所有面额，这 n 种面值是在 \left[1,m\right] 内等概率随机的。

补幺国王掌管大权，每种补幺梨他都有 ∞ 枚。但是，即便他拥有再多的硬币，他还是很惊叹竟然有这些补幺梨凑不出的面额！

古人的智商自然是有限的，因此他们只能意识到问题，但不能解决问题。

作为十万年后的我们，古人借助时光机向我们发出求助。你需要帮他们计算出最大的不能被表示的面额。

输入格式

第一行，输入两个数 n,m，表示 “补幺梨” 的面值种数，基本货币的金额上限。

第二行，输入 a_1 ,a_2 ,\dots,a_n，表示 “补幺梨”。

保证 a 随机生成。

输出格式

你需要帮补幺人计算出最大不能被表示的面额。

不难发现，在给定的数据范围下，必定存在不能被表示的面额。

听说是个背包，不会。

9.25 扑克（poker）

全体起立！

鸡尾酒和智乃在玩一个扑克牌游戏。

游戏规则是这样的：

从一幅扑克牌（不含大小王，共 52 张）中，随机发 3 张牌到每个玩家手上，然后，每个玩家可以任意想象自己抽到了这幅扑克牌中的另外两张牌在手，与自己手上的 3 张牌组成恰好 5 张，以构成一幅最大的手牌。

手牌有以下几种种类（按照优先级从大到小排序）：

其中，顺子不能向上越过 A，或向下越过 2。

如果两人的牌型是一致的，那么，按照关键牌组从大到小去比较，例如两人分别是：

♥A ♠A ♠3 ♦3 ♣9, ♠K ♥K ♣3 ♥3 ♠10

则第一个人胜，因为一对 A > 一对 K。

在这个游戏中，A>K>Q>⋯>2。

对于同点数，不同花色的牌，在游戏中视作一样大小的牌，但在输出中，黑桃 > 红桃 > 梅花 > 方块。

如果你想更具体的阅读比较大小的规则，可以看题目最下方的解释。

鸡尾酒为了赢这个游戏，买了一副透视眼镜，可以看到智乃的底牌。为了羞辱智乃，鸡尾酒决定，每次都想象出两张刚刚好可以稳赢智乃的牌，请帮助鸡尾酒计算，想象出的那两张牌分别应该是什么，或者告诉鸡尾酒，他无法获胜。

伟大，无需多言。

#include<bits/stdc++.h>
using namespace std;
int T, c[128], f;
char d[20], e[5];
struct node
{
    char a, b;
}p1[6], p2[6], pp1[6], pp2[6], ppp1[6];
bool cmp (node a, node b)
{
    return c[a.b] > c[b.b] || (c[a.b] == c[b.b] && c[a.a] < c[b.a]);
}
bool cmp_out (node a, node b)
{
    return c[a.b] < c[b.b] || (c[a.b] == c[b.b] && c[a.a] < c[b.a]);
}
bool check1 (int g)
{
    if (g == 1)
    {
        if (p1[1].a == p1[2].a && p1[2].a == p1[3].a && (c[p1[1].b] > c[p2[1].b] || f != g))
        {
            if (c[p1[3].b] - c[p1[1].b] <= 4)
            {
                int u = min(c[p1[1].b] + 4, 14);
                if (u > c[p2[5].b] || f != g)
                {
                    u = min(u, max(c[p2[5].b] + 1, c[p1[3].b]));
                    if (f != g)
                    {
                        u = max(c[p1[3].b], 6);
                    }
                    p1[4].a = p1[5].a = p1[1].a;
                    for (int i = u - 4;i <= u;i++)
                    {
                        p1[i - u + 5].b = d[i];
                    }
                    return 0;
                }
            }
        }
    }
    if (g == 2)
    {
        if (p1[1].b == p1[2].b && p1[2].b == p1[3].b)
        {
            if (c[p1[1].b] > c[p2[1].b] || f != g)
            {
                p1[4].b = p1[1].b;
                for (int i = 1;i <= 4;i++)
                {
                    p1[i].a = e[i];
                }
                p1[5].a = e[4];
                if (p1[1].b == '2')
                {
                    p1[5].b = '3';
                }
                else
                {
                    p1[5].b = '2';
                }
                return 0;
            }
            else if (p1[1].b == p2[1].b && p2[5].b != 'A')
            {
                p1[4].b = p1[1].b;
                for (int i = 1;i <= 4;i++)
                {
                    p1[i].a = e[i];
                }
                p1[5].a = e[4];
                p1[5].b = d[c[p2[5].b] + 1];
                return 0;
            }

        }
        else if (p1[1].b == p1[2].b || p1[2].b == p1[3].b)
        {
            char u;
            if (p1[1].b != p1[2].b)
            {
                p1[5].a = p1[1].a;
                p1[5].b = p1[1].b;
                u = p1[2].b;
            }
            else
            {
                p1[5].a = p1[3].a;
                p1[5].b = p1[3].b;
                u = p1[1].b;
            }
            if (c[u] > c[p2[1].b] || c[u] == c[p2[1].b] && c[p1[5].b] > c[p2[5].b] || f != g)
            {
                for (int i = 1;i <= 4;i++)
                {
                    p1[i].a = e[i];
                    p1[i].b = u;
                }
                return 0;
            }
        }
    }
    if (g == 3)
    {
        if (p1[1].b == p1[2].b && p1[2].b == p1[3].b)
        {
            for (int i = 4;i <= 5;i++)
            {
                p1[i].a = e[i - 1];
            }
            if (p1[1].b == '2')
            {
                for (int i = 4;i <= 5;i++)
                {
                    p1[i].b = '3';
                }
            }
            else
            {
                for (int i = 4;i <= 5;i++)
                {
                    p1[i].b = '2';
                }
            }
            return 0;
        }
        else if (p1[1].b == p1[2].b || p1[2].b == p1[3].b)
        {
            if (p1[1].b != p1[2].b)
            {
                for (int i = 4;i <= 5;i++)
                {
                    p1[i].b = p1[1].b;
                }
                if (p1[1].a == e[1])
                {
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                else
                {
                    p1[1].a = e[2];
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
            }
            else
            {
                for (int i = 4;i <= 5;i++)
                {
                    p1[i].b = p1[i - 2].b;
                }
                if (p1[1].a != e[4] && p1[2].a != e[4])
                {
                    p1[4].a = e[4];
                }
                else if (p1[1].a != e[3] && p1[2].a != e[3])
                {
                    p1[4].a = e[3];
                }
                else
                {
                    p1[4].a = e[2];
                }
                if (p1[3].a != e[4])
                {
                    p1[5].a = e[4];
                }
                else 
                {
                    p1[5].a = e[3];
                }
            }
            return 0;
        }
    }
    if (g == 4)
    {
        if (p1[1].a == p1[2].a && p1[2].a == p1[3].a)
        {
            if (f != g)
            {
                int t[15], u = 2, uu = 0;
                if (c[p1[3].b] - c[p1[1].b] <= 4 && c[p1[3].b] <= 6)
                {
                    uu = 1;
                }
                if (c[p1[1].b] == 4 && c[p1[3].b] == 6)
                {
                    uu = 2;
                }
                for (int i = 2;i <= 14;i++)
                {
                    t[i] = 0;
                }
                t[c[p1[1].b]] = t[c[p1[2].b]] = t[c[p1[3].b]] = 1;
                p1[4].a = p1[5].a = p1[1].a;
                for (int i = 2;i <= 14;i++)
                {
                    if (!t[i])
                    {
                        t[i] = 2;
                        u--;
                    }
                    if (!u)
                    {
                        break;
                    }
                }
                if (uu == 1)
                {
                    for (int i = min(c[p1[1].b] + 4, 14);i >= c[p1[1].b];i--)
                    {
                        if (t[i] == 2 && uu)
                        {
                            t[i] = 0;
                            for (int j = i + 1;j <= 14;j++)
                            {
                                if (!t[j])
                                {
                                    t[j] = 1;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                }
                else if (uu == 2)
                {
                    for (int i = c[p1[1].b] + 1;i >= 2;i--)
                    {
                        if (t[i] == 2 && uu)
                        {
                            t[i] = 0;
                            for (int j = i + 1;j <= 14;j++)
                            {
                                if (!t[j])
                                {
                                    t[j] = 1;
                                    break;
                                }
                            }
                            break;
                        }
                    }
                }
                u = 1;
                for (int i = 2;i <= 14;i++)
                {
                    if (t[i])
                    {
                        p1[u++].b = d[i];
                    }
                }
                return 0;
            }
            else
            {
                p1[4].a = p1[5].a = p1[1].a;
                int t[15];
                for (int i = 2;i <= 14;i++)
                {
                    t[i] = 0;
                }
                t[c[p1[1].b]] = t[c[p1[2].b]] = t[c[p1[3].b]] = 1;
                for (int i = 3;i <= 14;i++) 
                {
                    if (!t[i]) 
                    {
                        for (int j = 2;j < i;j++)
                        {
                            if (!t[j])
                            {
                                p1[4].b = d[i];
                                p1[5].b = d[j];
                                sort(p1 + 1, p1 + 6, cmp);
                                if (c[p1[1].b] - c[p1[5].b] > 4)
                                {
                                    for (int l = 1;l <= 5;l++)
                                    {
                                        if (c[p1[l].b] > c[p2[l].b])
                                        {
                                            return 0;
                                        }
                                        if (c[p2[l].b] > c[p1[l].b])
                                        {
                                            break;
                                        }
                                    }
                                }
                                for (int l = 1;l <= 3;l++)
                                {
                                    p1[l].a = pp1[l].a;
                                    p1[l].b = pp1[l].b;
                                }
                            }
                        }
                    }
                }
                return 1;
            }
        }
    }
    if (g == 5)
    {
        if (c[p1[3].b] - c[p1[1].b] <= 4 && p1[1].b != p1[2].b && p1[2].b != p1[3].b)
        {
            if (p2[1].b == 'A' && f == g)
            {
                return 1;
            }
            int u = min(c[p1[1].b] + 4, 14);
            if (u > c[p2[1].b] || f != g)
            {
                u = min(u, max(c[p2[1].b] + 1, c[p1[3].b]));
                if (f != g)
                {
                    u = max(c[p1[3].b], 6);
                }
                if (c[p1[1].b] >= u - 4 || f != g)
                {
                    p1[4].a = p1[5].a = e[4];
                    if (p1[1].a == p1[2].a && p1[2].a == p1[3].a && p1[3].a == e[4])
                    {
                        p1[4].a = e[3];
                    }
                    int t[15], uu = 4;
                    for (int i = 2;i <= 14;i++)
                    {
                        t[i] = 0;
                    }
                    t[c[p1[1].b]] = t[c[p1[2].b]] = t[c[p1[3].b]] = 1;
                    for (int i = u - 4;i <= u;i++)
                    {
                        if (!t[i])
                        {
                            p1[uu].b = d[i];
                            uu++;
                        }
                    }
                    return 0;
                }
            }
        }
    }
    if (g == 6)
    {
        if (p1[1].b != p1[2].b && p1[2].b != p1[3].b)
        {
            if (c[p1[1].b] > c[p2[3].b] || c[p1[1].b] == c[p2[3].b] && c[p1[3].b] > c[p2[4].b] || c[p1[1].b] == c[p2[3].b] && c[p1[3].b] == c[p2[4].b] && c[p1[2].b] > c[p2[5].b])
            {
                p1[4].b = p1[5].b = p1[1].b;
                if (p1[1].a == e[1])
                {
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                else
                {
                    p1[1].a = e[2];
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                return 0;
            }
            if (c[p1[2].b] > c[p2[3].b] || c[p1[2].b] == c[p2[3].b] && c[p1[3].b] > c[p2[4].b] || c[p1[2].b] == c[p2[3].b] && c[p1[3].b] == c[p2[4].b] && c[p1[1].b] > c[p2[5].b])
            {
                p1[4].b = p1[5].b = p1[2].b;
                if (p1[2].a == e[1])
                {
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                else
                {
                    p1[2].a = e[2];
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                return 0;
            }
            if (c[p1[3].b] > c[p2[3].b] || c[p1[3].b] == c[p2[3].b] && c[p1[2].b] > c[p2[4].b] || c[p1[3].b] == c[p2[3].b] && c[p1[2].b] == c[p2[4].b] && c[p1[1].b] > c[p2[5].b])
            {
                p1[4].b = p1[5].b = p1[3].b;
                if (p1[3].a == e[1])
                {
                    for (int i = 4;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                else
                {
                    p1[3].a = e[2];
                    for (int i = 3;i <= 5;i++)
                    {
                        p1[i].a = e[i - 1];
                    }
                }
                return 0;
            }
        }
        else if (p1[1].b == p1[2].b && p1[2].b == p1[3].b)
        {
            if (c[p1[1].b] > c[p2[1].b])
            {
                p1[4].a = p1[5].a = e[4];
                for (int i = 4;i <= 5;i++)
                {
                    p1[i].b = d[i - 2];
                }
                return 0;
            }
            else if (c[p1[1].b] == c[p2[1].b])
            {
                int t[15];
                for (int i = 2;i <= 14;i++)
                {
                    t[i] = 0;
                }
                t[c[p1[1].b]] = t[c[p1[2].b]] = t[c[p1[3].b]] = 1;
                for (int i = 3;i <= 14;i++) 
                {
                    if (!t[i]) 
                    {
                        for (int j = 2;j < i;j++)
                        {
                            if (!t[j])
                            {
                                p1[4].b = d[i];
                                p1[5].b = d[j];
                                sort(p1 + 4, p1 + 6, cmp);
                                for (int l = 1;l <= 5;l++)
                                {
                                    if (c[p1[l].b] > c[p2[l].b])
                                    {
                                        p1[4].a = p1[5].a = e[4];
                                        return 0;
                                    }
                                    if (c[p2[l].b] > c[p1[l].b])
                                    {
                                        break;
                                    }
                                }
                                for (int l = 1;l <= 3;l++)
                                {
                                    p1[l].b = pp1[l].b;
                                }
                            }
                        }
                    }
                }
            }
        }
        else
        {
            p1[4].b = pp1[4].b = p1[2].b;
            if (p1[1].b == p1[2].b)
            {
                if (p1[1].a != e[4] && p1[2].a != e[4])
                {
                    p1[4].a = pp1[4].a = e[4];
                }
                else if (p1[1].a != e[3] && p1[2].a != e[3])
                {
                    p1[4].a = pp1[4].a = e[3];
                }
                else
                {
                    p1[4].a = pp1[4].a = e[2];
                }
                sort(p1 + 1, p1 + 5, cmp_out);
                sort(pp1 + 1, pp1 + 5, cmp_out);
            }
            else
            {
                if (p1[2].a != e[4] && p1[3].a != e[4])
                {
                    p1[4].a = pp1[4].a = e[4];
                }
                else if (p1[2].a != e[3] && p1[3].a != e[3])
                {
                    p1[4].a = pp1[4].a = e[3];
                }
                else
                {
                    p1[4].a = pp1[4].a = e[2];
                }
                sort(p1 + 1, p1 + 5, cmp);
                sort(pp1 + 1, pp1 + 5, cmp);
            }
            for (int i = 2;i <= 14;i++) 
            {
                if (i != c[p1[1].b] && i != c[p1[4].b]) 
                {
                    p1[5].b = d[i];
                    p1[5].a = e[4];
                    sort(p1 + 4, p1 + 6, cmp);
                    for (int l = 1;l <= 5;l++)
                    {
                        if (c[p1[l].b] > c[p2[l].b])
                        {
                            return 0;
                        }
                        if (c[p2[l].b] > c[p1[l].b])
                        {
                            break;
                        }
                    }
                    p1[4].a = pp1[4].a;
                    p1[4].b = pp1[4].b;
                }
            }
        }
    }
    return 1;
}
bool check2 (int g)
{
    if (g == 1)
    {
        if (p2[1].a == p2[2].a && p2[2].a == p2[3].a)
        {
            if (c[p2[3].b] - c[p2[1].b] <= 4)
            {
                int u = min(c[p2[1].b] + 4, 14);
                p2[4].a = p2[5].a = p2[1].a;
                for (int i = u - 4;i <= u;i++)
                {
                    p2[i - u + 5].b = d[i];
                }
                return 0;
            }
        }
    }
    if (g == 2)
    {
        if (p2[1].b == p2[2].b && p2[2].b == p2[3].b)
        {
            p2[4].b = p2[1].b;
            for (int i = 1;i <= 4;i++)
            {
                p2[i].a = e[i];
            }
            p2[5].a = e[1];
            if (p2[1].b == 'A')
            {
                p2[5].b = 'K';
            }
            else
            {
                p2[5].b = 'A';
            }
            return 0;
        }
        else if (p2[1].b == p2[2].b || p2[2].b == p2[3].b)
        {
            char u;
            if (p2[1].b != p2[2].b)
            {
                p2[5].a = p2[1].a;
                p2[5].b = p2[1].b;
                u = p2[2].b;
            }
            else
            {
                p2[5].a = p2[3].a;
                p2[5].b = p2[3].b;
                u = p2[1].b;
            }
            for (int i = 1;i <= 4;i++)
            {
                p2[i].a = e[i];
                p2[i].b = u;
            }
            return 0;
        }
    }
    if (g == 3)
    {
        if (p2[1].a == p2[2].a && p2[2].a == p2[3].a)
        {
            int t[15], u = 2;
            for (int i = 2;i <= 14;i++)
            {
                t[i] = 0;
            }
            t[c[p2[1].b]] = t[c[p2[2].b]] = t[c[p2[3].b]] = 1;
            p2[4].a = p2[5].a = p2[1].a;
            for (int i = 14;i >= 2;i--)
            {
                if (!t[i])
                {
                    p2[u + 3].b = d[i];
                    u--;
                }
                if (!u)
                {
                    break;
                }
            }
            sort(p2 + 1, p2 + 6, cmp);
            return 0;
        }
    }
    if (g == 4)
    {
        if (c[p2[3].b] - c[p2[1].b] <= 4)
        {
            int t[15], uu = 0, u = min(int(c[p2[1].b] + 4), 14);
            for (int i = u - 4;i <= u;i++)
            {
                t[i] = 0;
            }
            p2[4].a = p2[5].a = e[1];
            t[c[p2[1].b]] = t[c[p2[2].b]] = t[c[p2[3].b]] = 1;
            for (int i = u;i >= u - 4;i--)
            {
                if (!t[i])
                {
                    uu++;
                    p2[uu + 3].b = d[i];
                }
            }
            sort(p2 + 1, p2 + 6, cmp);
            return 0;
        }
    }
    if (g == 5)
    {
        p2[4].b = p2[5].b = p2[3].b;
        if (p2[3].a == 'D')
        {
            for (int i = 4;i <= 5;i++)
            {
                p2[i].a = e[i - 3];
            }
        }
        else
        {
            for (int i = 3;i <= 5;i++)
            {
                p2[i].a = e[i - 2];
            }
        }
        sort(p2 + 1, p2 + 6, cmp);
        return 0;
    }
    return 1;
}
int main()
{
    freopen("poker.in", "r", stdin);
    freopen("poker.out", "w", stdout);
    for (int i = 2;i <= 9;i++)
    {
        c[i + '0'] = i;
        d[i] = i + '0';
    }
    c[int('T')] = 10;
    c[int('J')] = 11;
    c[int('Q')] = 12;
    c[int('K')] = 13;
    c[int('A')] = 14;
    d[10] = 'T';
    d[11] = 'J';
    d[12] = 'Q';
    d[13] = 'K';
    d[14] = 'A';
    c[int('S')] = 1;
    c[int('H')] = 2;
    c[int('C')] = 3;
    c[int('D')] = 4;
    e[1] = 'S';
    e[2] = 'H';
    e[3] = 'C';
    e[4] = 'D';
    cin >> T;
    for (int ti = 1;ti <= T;ti++)
    {
        for (int i = 1;i <= 3;i++)
        {
            cin >> p1[i].a >> p1[i].b;
            ppp1[i].a = pp1[i].a = p1[i].a;
            ppp1[i].b = pp1[i].b = p1[i].b;
        }
        for (int i = 1;i <= 3;i++)
        {
            cin >> p2[i].a >> p2[i].b;
            pp2[i].a = p2[i].a;
            pp2[i].b = p2[i].b;
        }
        int l = 1;
        while (check2(l))
        {
            l++;
        }
        if (l >= 3)
        {
            l++;
        }
        f = l;
        while (check1(l) && l > 0)
        {
            l--;
            for (int i = 1;i <= 3;i++)
            {
                pp1[i].a = ppp1[i].a;
                pp1[i].b = ppp1[i].b;
                p1[i].a = pp1[i].a;
                p1[i].b = pp1[i].b;
            }
        }
        if (l == 0)
        {
            cout << -1 << "\n";
        }
        else
        {
            sort(p1 + 1, p1 + 6, cmp_out);
            for (int i = 1;i <= 5;i++)
            {
                cout << p1[i].a << p1[i].b << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

其实这是 T4。

你猜右侧快速跳转是做什么的（

[自行尝试](https://www.luogu.com.cn/problem/U484624) ## T1(change) 如果数组 $a$ 中有任意一个点 $i$ 满足 $a_{i−1}>a_i$ 且 $a_i<a_{i+1}

，我们则称这个点 i 为“山谷点”。

数组中第一个元素和最后一个元素永远不可能为山谷点。

一个数组的价值是所有山谷点之和。

至多修改 k 次数组，每次修改可以任选一个位置，使得这个位置上的数字变得比原来更小。你希望数组的价值最大，求最大价值。

设 dp_{ij0/1} 为前 i 个，修改 j 次，本次有没有修改。

转移要注意本来是不是山谷。

然后秒了。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
long long n, k, a[N], dp[N][N][2], ans = -1;
int main()
{
    freopen("change.in", "r", stdin);
    freopen("change.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 2;i < n;i++)
    {
        for (int j = 0;j <= k;j++)
        {
            if (a[i - 1] > a[i] && a[i] < a[i + 1])
            {
                dp[i][j][0] = dp[i - 1][j][1];
                dp[i][j][1] = dp[i - 1][j][0] + a[i];
            }
            else
            {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
                if (j != 0)
                {
                    dp[i][j][1] = dp[i - 1][j - 1][0] + min(a[i - 1], a[i + 1]) - 1;
                }
            }
            ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
        }
    }
    cout << ans;
    return 0;
}

10.9

T1(exchange)

有一个 n×m 的矩阵 a，矩阵的每个元素是 1,2,3。可以任意交换两行，问是否经过若干次交换，使得每一列都是单调不减的。

数据只有 100，sort秒了。

#include<bits/stdc++.h>
using namespace std;
int t, n, m, f;
struct node
{
    int w[105];
}h[105];
bool cmp(node a, node b)
{
    for (int i = 1;i <= m;i++)
    {
        if (a.w[i] != b.w[i])
        {
            return a.w[i] < b.w[i];
        }
    }
    return 1;
}
int main()
{
    freopen("exchange.in", "r", stdin);
    freopen("exchange.out", "w", stdout);
    cin >> t;
    for (int ti = 1;ti <= t;ti++)
    {
        cin >> n >> m;
        for (int i = 1;i <= n;i++)
        {
            for (int j = 1;j <= m;j++)
            {
                cin >> h[i].w[j];
            }
        }
        sort(h + 1, h + n + 1, cmp);
        f = 1;
        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j < n;j++)
            {
                if (h[j].w[i] > h[j + 1].w[i])
                {
                    f = 0;
                    break;
                }
            }
            if (!f)
            {
                break;
            }
        }
        if (f)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}

T2（brick）

有一个 n 层的塔，从上往下数的第 i 层有 i 个砖块，由于塔太高了，我们只能看得到最后一层，也就是第 n 层的砖块。

除了最后一层的砖块外，每一个砖块都和下面一层的两个砖块相邻，呈现这样的形状：

塔上面只有红黄蓝三种颜色的砖块，并且有以下规律：

若相邻的两块砖块是相同颜色，那么这两块方砖紧挨的上面的砖块也将会是相同的颜色
若相邻的两块砖块是不同颜色，那么这两块方砖紧挨的上面的砖块将会是没有出现的第三种颜色

现在告诉你最下面一层的 n 个砖块颜色（红黄蓝分别用 A B C 表示），需要你推出塔顶部的颜色。

一个不容易发现的性质，设：

红 ->0

黄 ->1

#include<bits/stdc++.h>
using namespace std;
int t, n, f[128], ans;
char g[3];
string s; 
int c(int x, long long y)
{
    if (x == 0)
    {
        return 1;
    }
    if (x == 1)
    {
        return y % 3;
    }
    if (x == 2)
    {
        return y * (y - 1) / 2 % 3;
    }
    return c(x / 3, y / 3) * c(x % 3, y % 3) % 3;
}
int main()
{
    freopen("brick.in", "r", stdin);
    freopen("brick.out", "w", stdout);
    f['A'] = 0, g[0] = 'A';
    f['B'] = 1, g[1] = 'B';
    f['C'] = 2, g[2] = 'C';
    cin >> t;
    for (int ti = 1;ti <= t;ti++)
    {
        cin >> n >> s;
        for (int i = 0;i < n;i++)
        {
            ans += f[int(s[i])] * c(i, n - 1) % 3;
            ans %= 3;
        }
        cout << g[(ans * (n % 2 * 2 - 1) + 3) % 3] << "\n";
        ans = 0;
    }
    return 0;
}

蓝 ->2

(-1-1)\mod3=1

(-1-3)\mod3=2

于是可以用杨辉三角推出塔尖。

10.10

T1（collect）

Dr.Wang 是一位植物领域的专家。他要给他的学生们上一节课。课堂上需要展示一种植物。众所周知，植物的生长是有阶段的，本着严谨科学的态度，Dr.Wang 希望可以在课堂上给学生们展示该植物的每个生长阶段。

上图为植物“向日葵”的七个生长阶段。

Dr.Wang 要讲授的植物有 n 个阶段，现在他需要弄到该植物每种阶段各一株。他打听到了这种植物每个生长阶段的价格。但由于科研经费不足，有时候直接购买并不是一个好选择，所以他计划用上他的催熟科技。具体的，Dr.Wang 可以进行如下两种操作：

以 a_i 的价格购买一株生长到第 i 个阶段的植物。
花费 k 的代价使用催熟科技，将所有已购买的植物生长阶段增加 1。若一株植物已经到了阶段 n，则返回阶段 1。（可以理解为成熟到只剩种子，然后被重新种下去了）

现在 Dr.Wang 想让你帮忙求出，他最少需要花费多少代价，可以收集到植物的每个生长阶段。

先暴力。枚举催熟几次，这样第 $i$ 个阶段可以由前几个阶段的任意一个阶段转换，所以取最小值，用ST表维护。时间复杂度 $O(n^2)$。不难(?)发现催收次数和答案的关系成一个山谷函数，所以二分（也许是三分）找谷底。时间复杂度 $O(n\log n)$。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; long long n, k, a[N], dp[N][20], x, num, ans = 1e18; void rmq() { for (int i = 1;i <= n;i++) { dp[i][0] = a[i]; } for (int j = 1;(1 << j) <= n;j++) { for (int i = 1;i <= n;i++) { if (i + (1 << j) - 1 > n) { dp[i][j] = 0; } else { dp[i][j] = min(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]); } } } } long long _min(int l, int r) { x = log2(r - l + 1); return min(dp[l][x], dp[r - (1 << x) + 1][x]); } long long check(int i) { num = 0; for (int j = 1;j <= i;j++) { num += min(_min(1, j), _min(n - i + j, n)); } for (int j = i + 1;j <= n;j++) { num += _min(j - i, j); } return num + k * i; } int main() { freopen("collect.in", "r", stdin); freopen("collect.out", "w", stdout); cin >> n >> k; for (int i = 1;i <= n;i++) { cin >> a[i]; } rmq(); int l = 0, r = n - 1, mid; while (l < r) { mid = (l + r + 1) / 2; if (check(mid - 1) > check(mid)) { l = mid; } else { r = mid - 1; } } cout << min(check(l), min(check(0), check(n - 1))); return 0; } ``` ## T4（attack） Dr.Wang 业务宽泛，他正在带他的学生参加网络攻防竞赛。已知对手的网络结构可以抽象成一张 $n$ 个节点和 $m$ 条双向通道的连通图。各个节点之间借助通道通信。Dr.Wang 研制出了强力的干扰代码，植入后可以直接使一条通道瘫痪。但这条代码只能使用至多 $k$ 次，否则会引起对手的警觉。 Dr.Wang 想要保证打击是强力的，即在打击结束之后，对方的服务器必须存在至少两个节点不能够继续通信。那么作为他的学生，你需要求出总共有多少种植入的方案达成目标。两种方案被视为不同，当且仅当它们选择的通道数不同，或者有一条通道在一种方案被瘫痪了，而另一种方案中没有。**由于 Dr.Wang 的对手同样强大，因此干扰代码的使用次数** $k$ **非常小，你可能需要注意其范围。** $1\le n \le 10^5$，$0\le m \le 2\times10^5$，$k\in \{1,2\}

$k=2$ 时，先用 `dfs` 跑一遍生成树。（这里不能用并查集，不然后面会有些麻烦） - 若切断两条非树边。很显然没有答案。 - 若切断一条非树边，一条树边。很显然树边是桥时有解。还有一种情况，我们定义一条非树边 $(a,b)$ 包含一条树边 $(c,d)$ 当且仅当 $a$ 为 $c$ 的祖先且 $d$ 为 $b$ 的祖先，可以用树上差分解决（用 `dfs` 的原因是不会有横跨边，少写个 `LCA`）。假如有一条树边仅被一条非树边包含，则可以切断这两边。 - 若切断两条树边。很显然有至少一条树边是桥时有解，记得去重。如果两条树边被包含的边集相同，则可以切断这两边，使中间一段被孤立，边集用 `map` 维护。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5; map <long long, int> mp; int n, m, k, x, y, cnt, hc[N], f[N], u[N], w, d1[N], sum1[N]; long long ans, d2[N], sum2[N]; struct node { int v, h; bool f; long long r; }a[N * 2]; void add(int x, int y) { a[++cnt].h = hc[x]; hc[x] = cnt; a[cnt].v = y; a[cnt].f = 0; a[cnt].r = 1ll * rand() * rand() * rand() * rand(); } void build(int k) { f[k] = 1; for (int i = hc[k];i;i = a[i].h) { if (!f[a[i].v]) { a[i].f = 1; a[((i + 1) ^ 1) - 1].f = 1; build(a[i].v); } } } void dfs(int k, int fa) { u[k] = 1; for (int i = hc[k];i;i = a[i].h) { if (!a[i].f && !u[a[i].v]) { d1[k]--; d1[a[i].v]++; d2[k] ^= a[i].r; d2[a[i].v] ^= a[i].r; } } sum1[k] = d1[k], sum2[k] = d2[k]; for (int i = hc[k];i;i = a[i].h) { if (a[i].v != fa && a[i].f) { dfs(a[i].v, k); sum1[k] += sum1[a[i].v]; sum2[k] ^= sum2[a[i].v]; } } if (k != 1) { ans += mp[sum2[k]]; mp[sum2[k]]++; if (sum1[k] == 0) { ans += m; w++; } if (sum1[k] == 1) { ans++; } } } int main() { freopen("attack.in", "r", stdin); freopen("attack.out", "w", stdout); srand(time(0)); cin >> n >> m >> k; for (int i = 1;i <= m;i++) { cin >> x >> y; add(x, y); add(y, x); } build(1); dfs(1, 1); if (k == 1) { cout << w; return 0; } cout << ans - w * (w - 1); return 0; } ``` # 10.14 ## T1（char）白浅妹妹的文件系统中有 $𝑚$ 个文件（名字互不相同），但是白浅妹妹想要通过一个字符串查到它们。具体的，白浅妹妹会给出一个字符串 $𝑠$，长度为 $𝑛$，包含小写英文字符和 `∗`。白浅妹妹称，对于一个字符串 $𝑡$，一个替换方案是合法的当且仅当将其中的所有字符`∗`替换成一个任意仅包含小写字符的字符串（可以为空），使得替换后的字符串与上述 $𝑚$ 个文件名之一相同。白浅妹妹又说，她认为一个字符串 $𝑡$ 的美好度，是其合法的替换方案总数。现在她拿着字符串 $𝑠$ ，想知道所有连续的子串的美好度和对 **998244853** 取模的值。 $1 ≤ 𝑛 ≤ 5 × 10^4, 1 ≤ ∑ ∣ 𝑡_𝑖 ∣≤ 1000

设 dp_{ij} 表示考虑完了字符串中的前 𝑖 个点，目前将所有∗替换之后匹配了目标文件前 𝑗 个字符的方案数总和。

dp_{ij}$ 可以由任意的上个状态转移过来 $dp_{ij}=\sum\limits_{k=1}^mdp_{i-1,k}

若 s_i=t_j

dp_{ij}=dp_{i-1,j-1}

还有一个操作，dp_{i,0}=dp_{i,0}+1

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, p = 998244853;
long long n, m, dp[N][1005], sum[N][1005], l, ans;
string s, t[N];
int main()
{
    freopen("char.in", "r", stdin);
    freopen("char.out", "w", stdout);
    cin >> n >> m >> s;
    s = " " + s;
    for (int i = 1;i <= m;i++)
    {
        cin >> t[i];
        t[i] = " " + t[i];
    }
    for (int k = 1;k <= m;k++)
    {
        l = t[k].size() - 1;
        for (int i = 0;i <= n;i++)
        {
            for (int j = 0;j <= l;j++)
            {
                dp[i][j] = sum[i][j] = 0;
            }
        }
        for (int i = 1;i <= n;i++)
        {
            if (s[i] == '*')
            {
                dp[i][0] = dp[i - 1][0] + 1;
                for (int j = 1;j <= l;j++)
                {
                    dp[i][j] = (sum[i - 1][j] + dp[i - 1][0] + 1) % p;
                    sum[i][j] = (sum[i][j - 1] + dp[i][j]) % p;
                }
            }
            else
            {
                for (int j = 1;j <= l;j++)
                {
                    if (s[i] == t[k][j])
                    {
                        dp[i][j] = dp[i - 1][j - 1];
                        if (j == 1)
                        {
                            dp[i][j]++;
                        }
                    }
                    sum[i][j] = (sum[i][j - 1] + dp[i][j]) % p;
                }
            }
            ans += dp[i][l];
            ans %= p;
        }
    }
    cout << ans;
    return 0;
}

T2(tree)

一棵 𝑛 个节点的树，每个点是黑色或者白色。每条边有边权。

设 𝑆 是黑色点的集合，𝑇 是白色点的集合。则树的价值是∑_{𝑢∈𝑆} ∑_{𝑣∈𝑇} 𝑑i𝑠(𝑢, 𝑣)。

简单路径指路径上的顶点都不相同的路径。至多可以改变一个点的颜色，最大化树的价值。 $n$ 是怎么敢只给 $3000$ 的？先算一遍贡献。枚举修改的点，算出贡献的变化。没了，唐。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 3e3 + 5; int n, x, y, z, hc[N], cnt; bool f[N]; long long ans, num, maxx; struct node { int v, h, s; }a[N * 2]; void add(int x, int y, int z) { a[++cnt].v = y; a[cnt].h = hc[x]; hc[x] = cnt; a[cnt].s = z; } void dfs(int k, int fa, int c, int m) { if (f[k] != c) { ans += m; } for (int i = hc[k];i;i = a[i].h) { if (a[i].v != fa) { dfs(a[i].v, k, c, max(m, a[i].s)); } } } void dfs2(int k, int fa, int c, int m) { if (f[k] != c) { num += m; } else { num -= m; } for (int i = hc[k];i;i = a[i].h) { if (a[i].v != fa) { dfs2(a[i].v, k, c, max(m, a[i].s)); } } } int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); cin >> n; for (int i = 1;i <= n;i++) { cin >> f[i]; } for (int i = 1;i < n;i++) { cin >> x >> y >> z; add(x, y, z); add(y, x, z); } for (int i = 1;i <= n;i++) { dfs(i, i, f[i], 0); } ans /= 2; for (int i = 1;i <= n;i++) { num = 0; f[i] ^= 1; dfs2(i, i, f[i], 0); f[i] ^= 1; maxx = max(maxx, num); } cout << ans + maxx; return 0; } ``` ## T3(wooden) 鸡尾酒有一根长度为 $𝑥$ 的木棍，他可以根据这跟初始的木棍变出三根新的木棍，变木棍的规则如下：变出来的三根新的木棍长度必须严格递增，且新木棍的长度 $𝑛ew_𝑥$ 满足 $𝑥 < 𝑛ew_𝑥 ≤ 4 \times 𝑥$。（其中 $𝑥$ 为初始木棍的长度）例如初始木棍长度为 $𝑥 = 2$，那么变出 $[4,5,8]$ 三根木棍，或者 $[4,6,7]$ 三根木棍等方案都是合法的，但是变出 $[3,5,5]$ 是不合法的，因为变出的三根新木棍长度不是严格递增的；$[4,6,9]$ 也是不合法的，因为 $9$ 比 $4 \times 𝑥 = 8$ 要大。进行一次变幻之后，鸡尾酒总共就有四根木棍了。如果变幻结束之后可以从这四根木棍中选出三根（只要有一种方案即可），使其能够作为一个三角形的三条边（即这三根木棍满足任意两根的长度之和均大于另一根），那么称为这次变幻为一次“成功的变幻”。显然鸡尾酒有很多种变幻木棍的方案，那么请问，假设初始的木棍长度为 $𝑥$，鸡尾酒可以有多少种成功的变幻？由于答案可能很大，请输出答案对 $10^9+7$ 求余后的结果。 $1\le x\le10^{14}

抽象数学题。

省流：C_{3x}^3-(sum2(\left\lfloor\tfrac{x}{2}\right\rfloor)+sum2(\left\lfloor\tfrac{x-1}{2}\right\rfloor)+sum(\left\lfloor\tfrac{x-1}{2}\right\rfloor))

我们定义 sum(n)=1+2+\cdots+n，sum2(n)=1^2+2^2+\cdots+n^2，很显然可以 O(\log p) 计算。

接下来手算比较小的几个。

注：以下的 ans 为不合法的方案数，用总方案数减去即可。

x=2,ans=sum(1)

x=4,ans=sum(1)+sum(3)

x=6,ans=sum(1)+sum(3)+sum(5)

所以总结一下

x=2k,ans=\sum\limits_{i=1}^ksum(2i-1)

$x=3,ans=sum(2)

x=5,ans=sum(2)+sum(4)

x=7,ans=sum(2)+sum(4)+sum(6)

x=2k+1,ans=\sum\limits_{i=1}^ksum(2i)

于是我们愉快地……T了。

继续优化，将 sum 拆开。

x=6,ans=sum(1)+sum(3)+sum(5)=\frac{1\times2}{2}+\frac{3\times4}{2}+\frac{5\times6}{2}=1\times1+3\times2+5\times3

画个图看看：

我们可以将它分为 3 个部分。

第一个部分：

很显然是 sum2(3)

第二个部分：

很显然是 sum2(2)

第三个部分：

很显然是 sum(2)

所以 x=6,ans=sum2(3)+sum2(2)+sum(2)

x=2k,ans=sum2(k)+sum2(k - 1)+sum(k - 1)

再考虑奇数：

x=7,ans=sum(2)+sum(4)+sum(6)=\frac{3\times2}{2}+\frac{5\times4}{2}+\frac{7\times6}{2}=3\times1+5\times2+7\times3

再画一个图：

我们也可以将它分为 3 个部分。

第一个部分：

~~其实这是刚才的图~~

很显然是 sum2(3)

第二个部分：

很显然是 sum(3)

第三个部分：

很显然也是 sum2(3)

所以 x=7,ans=sum2(3)\times2+sum(3)

x=2k+1,ans=sum2(k)\times2+sum(k)

把奇数和偶数的式子合并得到：ans=sum2(\left\lfloor\tfrac{x}{2}\right\rfloor)+sum2(\left\lfloor\tfrac{x-1}{2}\right\rfloor)+sum(\left\lfloor\tfrac{x-1}{2}\right\rfloor)

最后的最后，用总方案数减去 ans 得到：

Ans=C_{3x}^3-(sum2(\left\lfloor\tfrac{x}{2}\right\rfloor)+sum2(\left\lfloor\tfrac{x-1}{2}\right\rfloor)+sum(\left\lfloor\tfrac{x-1}{2}\right\rfloor))

#include<bits/stdc++.h>
using namespace std;
const int p = 1e9 + 7;
long long n, m;
long long _pow(long long a, long long b)
{
    long long sum = 1;
    while (b)
    {
        if (b & 1)
        {
            sum *= a;
            sum %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return sum;
}
long long sum(long long k)
{
    k %= p;
    return k * (k + 1) % p * _pow(2, p - 2) % p;
}
long long sum2(long long k)
{
    k %= p; 
    return k * (k + 1) % p * (k * 2 + 1) % p * _pow(6, p - 2) % p;
}
int main()
{
    freopen("wooden.in", "r", stdin);
    freopen("wooden.out", "w", stdout);
    cin >> n;
    m = (n * 3 - 2) % p;
    cout << (m * (m + 1) % p * (m + 2) % p * _pow(6, p - 2) % p - (sum2(n / 2) + sum2((n - 1) / 2) + sum((n - 1) / 2)) % p + p * 2) % p;
    return 0;
}

程序员节

悻猩场。

T1

给定 n 个长方体，求至少被 n−1 个长方体所覆盖的整点数量。

2\le n\le10^5,x_i, -10^6\le y_i, z_i\le10^6

最后开的题，主要是长得太抽象了。

笑点解析：O(1) 单点查询比线段树查询慢，在老爷机上 T 飞。

不难发现，多个长方体组成的体积交长方体由最右边的左面(4声)，最上边的下面……组成。

所以可以维护每个维度的前后缀最值算出 n 个不同的体积交。

然后考虑容斥，发现任意两个体积交的交为所有长方体的体积交，所以算出答案之后减去 n-1 倍的总体积交即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, inf = 1e9;
long long n, a[4][N][3], b[4][N][3], num, ans; 
int main()
{
    freopen("cube.in", "r", stdin);
    freopen("cube.out", "w", stdout);
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[1][i][0] >> a[2][i][0] >> a[3][i][0] >> b[1][i][0] >> b[2][i][0] >> b[3][i][0];
    }
    for (int i = 1;i <= 3;i++)
    {
        a[i][0][1] = -inf;
        b[i][0][1] = inf;
        a[i][n + 1][2] = -inf;
        b[i][n + 1][2] = inf;
        for (int j = 1;j <= n;j++)
        {
            a[i][j][1] = max(a[i][j - 1][1], a[i][j][0]);
            b[i][j][1] = min(b[i][j - 1][1], b[i][j][0]);
        }
        for (int j = n;j >= 1;j--)
        {
            a[i][j][2] = max(a[i][j + 1][2], a[i][j][0]);
            b[i][j][2] = min(b[i][j + 1][2], b[i][j][0]);
        }
    }
    num = (b[1][n][1] - a[1][n][1] + 1) * (b[2][n][1] - a[2][n][1] + 1) * (b[3][n][1] - a[3][n][1] + 1);
    for (int i = 1;i <= n;i++)
    {
        ans += (min(b[1][i - 1][1], b[1][i + 1][2]) - max(a[1][i - 1][1], a[1][i + 1][2]) + 1) * (min(b[2][i - 1][1], b[2][i + 1][2]) - max(a[2][i - 1][1], a[2][i + 1][2]) + 1) * (min(b[3][i - 1][1], b[3][i + 1][2]) - max(a[3][i - 1][1], a[3][i + 1][2]) + 1) - num;
    }
    cout << ans + num;
    return 0;
}

T2

给定一个长为 n 的序列 a，然后进行 q 次询问，每次给定区间 [l, r]，求是否能够在区间中选出三个不同的下标 (i, j, k)，使得以 (a_i, a_j, a_k) 为边长，可以构成三角形。

1 \le n, q \le 10^5, 1 \le a_i \le 10^{18}, 1 \le l \le r \le n

很像数据结构的诈骗题。

可以发现假如出题人想卡你，数列就为斐波那契数列，不超过 100 项，数字就会 >10^{18}，所以长度过长时直接 Yes。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long n, q, a[N], b[N], x, y; 
int main()
{
    freopen("triangle.in", "r", stdin);
    freopen("triangle.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int ti = 1;ti <= q;ti++)
    {
        cin >> x >> y;
        if (y - x > 100)
        {
            cout << "Yes\n";
        }
        else
        {
            for (int i = x;i <= y;i++)
            {
                b[i - x + 1] = a[i];
            }
            sort(b + 1, b + y - x + 2);
            bool f = 0;
            for (int i = 1;i <= y - x - 1;i++)
            {
                if (b[i] + b[i + 1] > b[i + 2])
                {
                    f = 1;
                    break;
                }
            }
            if (f)
            {
                cout << "Yes\n";
            }
            else
            {
                cout << "No\n";
            }
        }
    }
    return 0;
}

T3

给定一个长为 n 的序列 a 和整数 m，然后进行 q 次操作，每次操作由两个整数 o 和 l 表示：

如果 o = 1，对序列 a 中的区间 [l, l + m - 1] 进行翻转。
如果 o = 2，则表示求 a_l。

保证第一种操作中的 l 单调不减，要求对所有第二种操作获取的值求异或和。

1 \le n, q \le 10^6, 1 \le m \le n, 1 \le a_i \le 10^9, 1 \le l \le n - m + 1

使用印有完整 Splay 代码的文化T恤衫，秒了。

笑点解析：平板电视卡过去了。

两个关键的性质：

翻转操作的区间左边界不减。
区间长度是固定的。

可以将问题看成是一个长度为 m 的定长区间由左向右进行滑动，并某些位置执行翻转操作。

一个翻转状态进行标记，如果区间是未翻转状态，则头出尾进，如果是翻转状态，则尾出头进。

使用双端队列维护即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, q, a[N], b[N * 2], o, x, f, cnt = 1, l = N, ans; 
int main()
{
    freopen("section.in", "r", stdin);
    freopen("section.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1;i <= m;i++)
    {
        b[l + i - 1] = a[i];
    }
    for (int ti = 1;ti <= q;ti++)
    {
        cin >> o >> x;
        if (o == 1)
        {
            for (;cnt < x;cnt++)
            {
                if (!f)
                {
                    a[cnt] = b[l];
                    b[l++ + m] = a[cnt + m];
                }
                else
                {
                    a[cnt] = b[--l + m];
                    b[l] = a[cnt + m];
                }
            }
            f ^= 1;
        }
        else
        {
            if (x < cnt || x >= cnt + m)
            {
                ans ^= a[x];
            }
            else
            {
                if (!f)
                {
                    ans ^= b[l - cnt + x];
                }
                else
                {
                    ans ^= b[l + m - 1 + cnt - x];
                }
            }
        }
    }
    cout << ans;
    return 0;
}

T4

给定一张包含 n 个点的图，每个点的权值分别为 a_i，对于任意点对 (i, j)，如果满足 a_i \And a_j = 0，则它们之间有边。

初始时有一个空集合 S，每次可以选择一个不在集合中的点 v 进行如下两种操作之一：

直接将 v 加入集合，价值为 0。
选择一个在集合中且与 v 有边相连的点 u，将 v 加入集合，价值为 a_u。

求可以获得的最大价值和。

1 \le n \le 1000, 1 \le a_i \le 10^9

big胆！竟敢让我 n^2 建图！

但是 n \le1000。

整一个 0 号虚点，操作 1 就变为了操作 2，然后拆点跑一遍最大生成树。

发现寄了。

一个小操作：先减去点权之和，将边权设为相邻两点权值之和，可以防止方案不合法。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
long long n, b[N], f[N], cnt, ans;
struct node
{
    long long u, v, s;
}a[N * N * 2];
void add(int x, int y, int s)
{
    a[++cnt].u = x;
    a[cnt].v = y;
    a[cnt].s = s;
}
bool cmp(node a, node b)
{
    return a.s > b.s;
}
long long find(long long k)
{
    if (f[k] == k)
    {
        return k;
    }
    return f[k] = find(f[k]);
}
int main()
{
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> b[i];
        ans -= b[i];
    }
    for (int i = 1;i <= n;i++)
    {
        f[i] = i;
        add(0, i, b[i]);
        for (int j = i + 1;j <= n;j++)
        {
            if ((b[i] & b[j]) == 0)
            {
                add(i, j, b[i] + b[j]);
            }
        }
    }
    sort(a + 1, a + cnt + 1, cmp);
    for (int i = 1;i <= cnt;i++)
    {
        if (find(a[i].u) != find(a[i].v))
        {
            ans += a[i].s;
            f[find(a[i].u)] = find(a[i].v);
        }
    }
    cout << ans;
    return 0;
}

烂头，烂中，烂尾。