2020河南省第二届CCPC真题解析（附榜单）

骑猪看日落 2022-12-23 03:19 99阅读 0赞

### 这里写目录标题 ###

*  A：班委竞选
 *   *  题目：
     *  分析：
     *  AC代码：
 *  B：广告投放
 *   *  题目：
     *  分析：
     *  AC代码：
 *  C：我得重新集结部队
 *   *  题目：
     *  分析：
     *  AC代码：
 *  D：园艺大师
 *   *  题目：
     *  分析：
     *  AC代码：
 *  E：发通知
 *   *  题目：
     *  分析：
     *  AC代码：
 *  F：旅游胜地
 *   *  题目：
     *  分析：
     *  AC代码：
 *  G：vvvvvvvim
 *   *  题目：
     *  分析：
     *  AC代码：
 *  H：林克与翻转排列
 *   *  题目：
     *  分析：
     *  AC代码：
 *  I：太阳轰炸
 *   *  题目：
     *  分析：
     *  AC代码：
 *  J：二进制与、平方和
 *   *  题目：
     *  分析：
     *  AC代码：
 *  K：子串翻转回文串
 *   *  题目：
     *  分析：
     *  AC代码：
 *  L：送外卖
 *   *  题目：
     *  分析：
     *  AC代码：
 *  榜单：

# A：班委竞选 #

时间限制: 1 Sec 内存限制: 128 MB

## 题目： ##

某班级中有 n 位学生，学号为 1,2,…,n。现在班级中正在举行 m 个班干部职位的竞选，职位用 1,2,…,m 编号。学号为 i 的同学竞选的职位为 ci，获得 ti 票。最终每个职位选择票数最高的同学上任，若存在多个同学票数一致，则选择学号最小的同学上任。  
现在给你唱票结果，请你告诉班主任最终的班干部名单。

输入  
第一行包含两个整数 n, m (1≤n≤51, 1≤m≤12, m≤n)，含义见题目描述。  
接下来 n 行，第 i 行包含两个整数 ci, ti (1≤ci≤m, 1≤ti≤n)，含义见题目描述。  
数据保证每个职位至少有一位同学参与竞选。

输出  
输出一行，包含 m 个整数。第 i 个整数表示担任第 i 个班干部职位的同学学号。

样例输入 Copy  
5 2  
1 2  
2 1  
2 1  
1 1  
2 2  
样例输出 Copy  
1 5  
提示  
样例输入二  
12 8  
8 12  
6 8  
2 6  
1 8  
1 7  
2 9  
3 12  
4 9  
5 1  
6 12  
7 6  
8 8  
样例输出二  
4 6 7 8 9 10 11 1

第一个样例中，第 1 个岗位有学号 1 和学号 4 两个同学竞选，获得的票数分别为 2 和 1，第 1 个岗位由获得票数最多的学号 1 同学来担任；第 2 个岗位有学号 2, 3 和 5 三个同学竞选，获得的票数分别为 1, 1 和 2，第 2 个岗位由获得票数最多的学号 5 同学来担任。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][20201124220455282.png_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    const int N = 5e5 + 10;
     
    struct node
    { 
        int p, id;
        bool operator < (const node &oth)const
        { 
            if (p != oth.p)
                return p > oth.p;
            return id < oth.id;
        }
    };
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        map<int, set<node>>mp;
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        { 
            int c, t;
            cin >> c >> t;
            mp[c].insert({  t, i });
        }
        for (int i = 1; i <= m; i++)
            cout << mp[i].begin()->id << (i == m ? '\n' : ' ');
        return 0;
    }

# B：广告投放 #

## 题目： ##

时间限制: 3 Sec 内存限制: 512 MB

题目描述  
现在有一档综艺节目即将在网络上播出，总共会有 n 集，节目会按顺序逐集播出。节目组决定在某些集节目中投放广告。  
节目最初播出时，会有 m 名观众观看。若第 i 集投放有广告，记此时还剩有 c 名观众观看，则会产生 c⋅pi 的收益；但播出后则会让观众的人数变为c′=⌊c/di⌋，即第 i+1 集只会剩有 c′ 名观众观看。如果在第 i 集没有投放广告，则不会产生收益，观众人数也不会变化。  
请你帮助节目组计算一下各种可能的方案中，最大的收益和。

输入  
第一行，两个整数 n 和 m (1≤n,m≤105)，表示节目集数和首播时的观众数量。  
第二行，共 n 个整数 pi (1≤pi≤106)，表示第 i 集投放广告时每名观众能带来的收益。  
第三行，共 n 个整数 di (1≤di≤m)，表示第 i 集投放广告后，观众数量会变为人数除以 di 并向下取整。

输出  
一个整数，表示可能的最大的收益和。

样例输入 Copy  
5 20  
9 14 10 4 5  
2 7 1 8 10

样例输出 Copy  
335

提示  
样例输入二  
6 5  
5 31 53 58 74 97 5 5 4 5 5 4  
样例输出二  
485

第一个样例中，可以考虑在第 1, 2, 3, 5 集投放广告。这样，在第 1 集时有 2 名观众，投放广告获得收益 2；在第 2 集时有⌊20/2⌋=10 名观众，投放广告获得收益 10×14=140；在第 3 集时有 ⌊10/7⌋=1 名观众，投放广告获得收益 1×10=10；在第 4 集时有 ⌊1/1⌋=1 名观众，但因为没有投放广告，所以没有收益；在第 5 集时有 1 名观众，投放广告获得收益 1×5=5。最终，总收益为 1。这是能够取到最大的收益和的一个方案。  
第二个样例中，可以考虑只在第 6 集投放广告，能获得的总收益为 5×97=485，这是能够取到最大的收益和的一个方案。 换个方案，如果选择在第 5, 6 集投放广告，能获得的总收益为 5×74+⌊5/5⌋×97=467，并不如只在第 6 集投放广告获得的总收益高。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][20201124220435736.png_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    const int N = 1e5 + 10;
     
    int p[N], d[N];
    ll f[N * 10];
    ll g[N * 10];
    int vis[N * 10];
    int val[N];
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            scanf("%d", &p[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &d[i]);
        int cnt = 0;
        vis[m] = 1;
        val[++cnt] = m;
        for (int i = m; i >= 1; i--)
        { 
            if (vis[i])
            { 
                for (int j = 1; j <= i; j++)
                    vis[i / j] = 1;
                val[++cnt] = i;
            }
        }
        for (int i = 1; i <= n; i++)
        { 
            for (int j = 1; j <= cnt; j++)
                f[val[j] / d[i]] = max(f[val[j] / d[i]], g[val[j]] + 1LL * val[j] * p[i]);
            for (int j = 1; j <= cnt; j++)
                g[val[j]] = f[val[j]];
        }
        ll ans = 0;
        for (int i = 0; i <= m; i++)
            ans = max(ans, f[i]);
        cout << ans << endl;
        return 0;
    }

# C：我得重新集结部队 #

## 题目： ##

时间限制: 1 Sec 内存限制: 128 MB

题目描述  
为了保护科普卢星区的和平，大主教阿塔尼斯每时每刻都在指挥部队抗击肆虐的虫群。最近，阿塔尼斯把目光投向了又一颗布满虫群的星球。在这次行动中，阿塔尼斯计划使用狂热者铲除星球上的虫群威胁。  
狂热者是星灵的基本近战兵种，每个狂热者有一个攻击力 atk 和一个攻击范围 r。在狂热者发动攻击时，他会冲向距离最近的异虫，在这只异虫处释放 3 次威力强大的旋风斩。若有多只距离最近的异虫，他会选择最早出现的那只。若当前没有存活的异虫，那么这只狂热者会在原地释放旋风斩。每次旋风斩会对所有与攻击者距离小于等于 r 的异虫进行攻击，对每只异虫造成 atk 的伤害（生命值减少 atk）。  
当然，这些异虫也是不好惹的。每只异虫具有初始生命值 h，当生命值小于等于 0 时，该异虫将会死亡（并离开战场）。但是，在一次攻击中，若一只异虫受到 3 次旋风斩后仍未死亡，那么它将会对进攻的狂热者进行反击，使这个狂热者不得不离开战场。  
在整个战役中，按照时间顺序依次发生了 n 个事件，事件有以下两种：  
异虫出现。一只初始生命值为 h 的异虫单位出现在 (x,y)坐标。  
折跃狂热者。一个狂热者被折跃到了 (x,y) 坐标，冲向距离最近的异虫（若存在）并发动 3 次旋风斩。若此后该狂热者没有受到反击，那么他将会一直留在战场，但是不会继续进行攻击。  
你作为阿塔尼斯的副官，想知道战场的最终情况：每个狂热者是否离开了战场，以及每只异虫是否死亡。

输入  
第一行包含一个整数 n (1≤n≤2×103)，代表事件的数量。  
接下来 n 行，每行给出一种事件，格式为以下两种之一：  
1 x y h，代表一个生命值为 h 的异虫出现在了坐标 (x,y)。  
2 x y atk r，代表一个攻击力为 atk，攻击半径为 r 的狂热者被折跃到了坐标 (x,y)，并立即进行攻击。  
上述所有的x,y,r 均为整数，满足 0≤∣x∣,∣y∣,r≤108；所有的 atk,h 均为整数，满足 1≤atk,h≤108。

输出  
输出 n 行，第 i 行表示第 i 个事件中出现的异虫或狂热者最终是否留在战场。Yes 表示异虫未死亡或狂热者未离开战场，No 表示异虫死亡或狂热者离开战场，大小写不敏感。

样例输入 Copy  
5  
1 0 0 4  
1 0 1 8  
2 1 0 1 1  
2 1 0 1 1  
2 1 0 1 1

样例输出 Copy  
No  
No  
No  
No  
Yes

提示  
在样例中，发生了如下事件：  
事件 1 中，在 (0,0)处出现了一只异虫，其生命值为 4。  
事件 2 中，在 (0,1)处新出现了一只异虫，其生命值为 8。  
事件 3 中，在 (1,0) 处折跃一只攻击力为 1，攻击半径为 1 的狂热者，他移动到坐标 (0,0) 后，发动 3 次旋风斩。异虫 1,2 分别剩余生命值 1,5，随后狂热者受到反击离开战场。  
事件 4 中，在 (1,0) 处折跃一只攻击力为 1，攻击半径为 1 的狂热者，他移动到坐标 (0,0) 后，发动 3 次旋风斩。异虫 1 死亡，异虫 2 剩余生命值 2，随后狂热者受到反击离开战场。  
事件 5 中，在 (1,0) 处折跃一只攻击力为 1，攻击半径为 1 的狂热者，他移动到坐标 (0,1) 后，发动 3 次旋风斩。异虫 2 死亡，狂热者留在战场。  
因而，最终所有异虫死亡，只有狂热者 5 留在战场。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][20201124220604265.png_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e3 + 10;
    const int mod = 1e9 + 7;
    typedef long long ll;
     
    struct node
    { 
        int x, y;
        ll r;
        bool death;
    }insect[N];
    int type[N];
    ll dis(int a, int b, int c, int d)
    { 
        return 1LL * (a - c) * (a - c) + 1LL * (b - d) * (b - d);
    }
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        int n;
        int cnt = 0, tot = 0;
        cin >> n;
        while (n--)
        { 
            ++cnt;
            int op;
            scanf("%d", &op);
            if (op == 1)
                scanf("%d%d%lld", &insect[cnt].x, &insect[cnt].y, &insect[cnt].r), type[cnt] = 1;
            else
            { 
                type[cnt] = 2;
                int x, y, atk, r;
                scanf("%d%d%d%d", &x, &y, &atk, &r);
                int k = 0;
                ll d = 1e18;
                for (int i = 1; i <= cnt; i++)
                { 
                    if (type[i] == 1 && insect[i].r > 0)
                    { 
                        if (d > dis(x, y, insect[i].x, insect[i].y))
                            d = dis(x, y, insect[i].x, insect[i].y), k = i;
                    }
                }
                for (int i = 1; i <= cnt; i++)
                { 
                    if (!insect[i].death && type[i] == 1 && 1LL * (insect[i].x - insect[k].x) * (insect[i].x - insect[k].x) + 1LL * (insect[i].y - insect[k].y) * (insect[i].y - insect[k].y) <= 1LL * r * r)
                    { 
                        insect[i].r -= 3LL * atk;
                        if (insect[i].r <= 0)
                            insect[i].death = 1;
                        else
                            insect[cnt].death = 1;
                    }
                }
            }
        }
        for (int i = 1; i <= cnt; i++)
            puts(!insect[i].death ? "Yes" : "No");
        return 0;
    }

# D：园艺大师 #

## 题目： ##

时间限制: 1 Sec 内存限制: 128 MB

题目描述  
小钾立志成为传说中的园艺大师，因此开始练习修剪技术。  
园林中有 n 株灌木排成一排，且它们的高度都为一个正整数 h。对于每株灌木，小钾可以进行一次修剪，使其高度变成一个小于 h 的任意正整数；或是不进行修剪，使其高度仍为 h。为了保持灌木丛整体的美观，小钾还提出了 n−1 个要求，第 i 个要求为下列的一种：  
第 i 株灌木的高度严格小于第 i+1 株  
第 i 株灌木的高度严格大于第 i+1 株  
我们称两种修剪方案不同，当且仅当存在某株灌木的最终高度在两种方案中不同。当小钾将所有不同的修剪方案都完成时，他就能提升为园艺大师。但是他实在太忙了，因此请你帮他计算所有不同的修剪方案数量对质数109+7 取模后的值。

输入  
第一行包含两个整数 n, h (2≤n≤3×103, 1≤h≤106)，含义见题目描述。  
第二行包含一个长度为 n−1 的字符串，仅由字符 “<” 与 “>”（不包括引号）组成，表示小钾的要求。若第 i 个字符为 “<”，则要求为"第 i 株灌木的高度严格小于第 i+1 株"；若第 i 个字符为 “>”，则要求为"第 i 株灌木的高度严格大于第 i+1 株"。

输出  
输出一行一个整数，表示所有不同的修剪方案数量对质数 109+7 取模后的值。

样例输入 Copy  
3 3  
<>

样例输出 Copy  
5

提示  
样例输入二  
5 12  
<>><  
样例输出二  
16522

第一个样例中，一共有 5 种符合要求的方案：(1,2,1), (1,3,1), (1,3,2), (2,3,1), (2,3,2)。

## 分析： ##

## AC代码： ##

# E：发通知 #

## 题目： ##

时间限制: 5 Sec 内存限制: 512 MB

题目描述  
学院一共有 n 位学生，用 1 编号。每天，学院都会派遣辅导员给学生发送若干通知，以保证各项措施、活动消息得到落实。  
现在，学院要求辅导员发送一条关于光盘行动的通知。对于通知信息，同学们的反应往往各不相同，辅导员预测出第 i 号学生收到通知后会产生 wi 的愉悦度。此外，辅导员还观察到第 i 号学生会在 \[ai,bi\]时间段内实时查阅通知消息，能够收到这段时间内的所有通知；而其他时间将无法收到通知（愉悦度为 0）。  
辅导员会选择在某一时刻发布一次通知消息，他希望在至少有 k 名同学收到通知的前提下，使得同学们的总体愉悦度最大。同学们的总体愉悦度是所有同学愉悦度的异或和。请聪明的你帮助辅导员计算最大的总体愉悦度。

输入  
第一行包含两个整数 n, k (1≤n≤5×105,1≤k≤n)，含义见题目描述。  
接下来 n 行，每行包含三个整数 ai, bi, wi (1≤ai≤bi≤109, 0≤wi≤109)，含义见题目描述。

输出  
输出一行一个整数，即最大的总体愉悦度。若不可能有至少 k 名同学收到通知，输出 −1。

样例输入 Copy  
5 1  
1 5 8  
3 6 2  
7 8 4  
8 9 0  
10 10 1

样例输出 Copy  
10

提示  
样例输入二  
2 2 3 5 8 1 2 4  
样例输出二  
\-1

第一个样例中，辅导员可以选择在时刻 3 发送通知，这样第 1 位和第 2 位同学会收到通知，总体愉悦度可取到最大值，为8⊕2=10。当然，最大的合法方案不止这一种，也可以选择在时刻 5 发送通知，总体愉悦度为 1。  
第二个样例中，无论选取哪一时刻发布通知，都无法让两位同学均接收消息，故输出 −。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][2020112422071265.png_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    const int N = 5e5 + 10;
     
    int d[N * 2];
    int e[N * 2];
    int a[N], b[N], c[N];
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        int n, k;
        cin >> n >> k;
        vector<int>v;
        for (int i = 1; i <= n; i++)
        { 
            scanf("%d%d%d", &a[i], &b[i], &c[i]);
            v.push_back(a[i]), v.push_back(b[i] + 1);
        }
        sort(v.begin(), v.end());
        int cnt = v.erase(unique(v.begin(), v.end()), v.end()) - v.begin();
        for (int i = 1; i <= n; i++)
        { 
            int bg = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
            int ed = lower_bound(v.begin(), v.end(), b[i] + 1) - v.begin() + 1;
            d[bg] ^= c[i], d[ed] ^= c[i];
            e[bg]++, e[ed]--;
        }
        int ans = -1;
        for (int i = 1; i <= cnt; i++)
        { 
            d[i] ^= d[i - 1];
            e[i] += e[i - 1];
            if (e[i] >= k)
                ans = max(ans, d[i]);
        }
        cout << ans << endl;
        return 0;
    }

# F：旅游胜地 #

## 题目： ##

时间限制: 8 Sec 内存限制: 512 MB

题目描述  
有一旅游胜地，可以看做是一个 n 个点、m 条边的连通无向图。每个点都有一个点权，编号为 i 的点的点权为 ai，表示这个点的景观值。  
开发商为了能获取收益，准备选择一些点建设商业区，但是会让这些点的景观值大打折扣。具体地说，如果选择编号为 i 的点建设商业区，则会让该点的景观值变为 bi，其中 bi≤ai。  
不过对于游客来讲，只要游览相邻的两个点时，景观值的差距不要太大就好。即确定好需要建设商业区的点后，记编号为 i 的点最终的点权为 wi，只要所有边 u,v 的 ∣wu−wv∣ 中最大值尽可能小即可。或者说，最小化有边相连的景观值差距的最大值。  
请你帮助开发商计算所有可能的方案中，景观值最大差距的最小值。

输入  
第一行，两个正整数 n,m(2≤n≤105, n−1≤m≤min(n(n−1)/2,105) )，表示图的点数和边数。  
第二行，共 n 个正整数 ai (1≤ai≤109)，表示编号为 i 的点不建设商业区的景观值。  
第三行，共 n 个正整数 bi (1≤bi≤109, bi≤ai)，表示编号为 i 的点建设商业区后的景观值。  
接下来 m 行，每行两个正整数 u,v，表示 u 和 v 有一条边相连。  
数据保证图是连通的，也保证没有重边或自环。

输出  
一个整数，景观值最大差距的最小值。

样例输入 Copy  
4 3  
10 7 5 5  
6 2 1 2  
2 4  
3 2  
2 1

样例输出 Copy  
2

提示  
样例输入二  
6 6  
8 8 7 6 9 9  
7 4 6 3 4 7  
3 1  
4 3  
5 1  
2 4  
1 6  
4 1  
样例输出二  
2

下面两图分别为两个样例的一个方案。点的标记为"编号：景观值"，白色填充为没有建立商业区的点，灰色填充的为建立了商业区的点；边权为所连接的两个点的景观值差距。  
第一个图中，只有点 1 建立了商业区，景观值最大差距为 2；第二个图中，点 1、2、3、6 建立了商业区，景观值最大差距为 2。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]

## 分析： ##

## AC代码： ##

# G：vvvvvvvim #

## 题目： ##

时间限制: 3 Sec 内存限制: 512 MB

题目描述  
一天，心血来潮的 Toxel 对 vim 进行了魔改。他在 vim 中添加了指令 vvvvvvv，该指令可以在一段文本中选取任意一条连续的路径进行操作。Toxel 将这一全新的文本编辑器命名为 vvvvvvvim。  
vvvvvvvim 中的一段文本包含若干行，每行包含若干个从行首开头的字符，与一般的文本编辑器相同。第 i 行左起的第 j 个字符用坐标 (i,j) 表示（i,j 均从 1 开始）。  
vvvvvvv 指令选取的连续路径可定义为从文本中某个存在的字符开始，每次向上、下、左、右移动一个字符，通过有限次移动得到的字符序列。移动的过程中不允许走到不存在字符的位置，但可以重复访问同一位置的字符。  
形式化地说，vvvvvvv 指令选取的路径可表示为 (x1,y1)→(x2,y2)→⋯→(xt,yt)(t≥1)，其中 t 表示路径长度。设 n 表示文本行数，那么要求对于所有的 i(1≤i≤t) 满足 1≤xi≤n,1≤yi≤lenxi。并且对于所有的 i(1≤i<t) 满足 ∣xi−xi+1∣+∣yi−yi+1∣=1。  
为了测试你对 vvvvvvvim 的掌握情况，Toxel 给了你两段文本，它们的行数相同，所有对应行的长度也相同。你需要在第一段文本上使用 vvvvvvvim 指令选取一条路径，将路径上所有字符统一修改成字符 ch（ch 可任选），使得两段文本相同。请判断是否可行。两段文本相同是指行数相同，每行的长度相同，且所有对应位置的字符也相同。

输入  
注意：本题包含多组测试数据。  
第一行包含一个整数 T (1≤T≤5×105)，表示数据组数。接下来依次给出 T 组测试数据。  
每组测试数据的第一行包含一个整数 n，表示两段文本的行数均为 n (1≤n≤5×105)。  
接下来 n 行描述第一段文本的内容。输入的第 i 行包含一个字符串 c1t1c2t2⋯cdtd，表示文本的第 i 行有 d 段，依次为 t1 个 c1，t2 个 c2，以此类推。字符与数字间没有空格，参见样例。保证所有 cj 均为小写字母，tj 为整数且 1≤tj≤109,1≤d≤5×105,∑j=1dtj≤109。  
接下来 n 行描述第二段文本的内容，格式和限制与第一段文本相同。保证两段文本所有对应行的长度相同。  
保证单个测试点中所有测试数据第一段文本的 d 之和不超过 5×105，第二段文本的 d 之和不超过 5×105。

输出  
对于每组测试数据，输出一行一个字符串，Yes 表示可以修改第一段文本使得两段文本相同，No 表示不能，大小写不敏感。

样例输入 Copy  
1  
2  
a2  
a1b1  
b2  
b2

样例输出 Copy  
Yes  
提示

样例输入二  
1  
1  
a1b1a1  
b1a1a1

样例输出二  
No

第一个样例中，第一段文本为：  
aa  
ab  
第二段文本为：  
bb  
bb  
可以选择从第一行的第二个字符开始，走到第一行的第一个字符，再走到第二行的第一个字符。将路径选中的这些字符全部修改为字符 b 后，两段文本就相同了。  
第二个样例则没有办法只使用一次操作来完成目标。

## 分析： ##

## AC代码： ##

# H：林克与翻转排列 #

## 题目： ##

时间限制: 1 Sec 内存限制: 128 MB

题目描述  
林克穿过果彭加沼泽，来到了壶洞窟的门口。但是一道机关挡住了他的去路，机关上的铭牌刻着：“只有解开迷题的人，方可进入洞窟探寻宝物。”  
这个迷题是这样的：机关上有上下两串数字，它们分别是 1∼n 的排列。上方的数字串可以操作，而下方的不行。每次操作可以选取连续的 k 个数字，将它们翻转过来。由于机关有一定的使用寿命，操作至多可以进行 2×105 次，允许不进行任何操作。只有两个序列变得完全相同，门才会开启。  
形式化地说，有两个 1∼n的排列a1,a2,⋯,an 和 b1,b2,⋯,bn，每次操作可以选取一个 l，满足 1≤l≤n−k+1，并将子串 al,al+1,⋯,al+k−1 翻转过来。操作之后，a1,a2,⋯,an 会变成 a1,⋯,al−1,al+k−1,⋯,al+1,al,al+k,⋯,an。你需要用若干次操作使得 a1=b1,a2=b2,⋯,an=bn。  
请你帮助林克破解这道机关。

输入  
第一行包含两个整数 n, k (2≤k≤n≤100, k 为偶数)，含义见题目描述。  
第二行包含 n 个整数，第 i 个为 ai (1≤ai≤n)，表示上方数字串的第 i 个数字。保证所有的 ai 两两不同。  
第三行包含 n 个整数，第 i 个为 bi (1≤bi≤n)，表示下方数字串的第 i 个数字。保证所有的 bi 两两不同。

输出  
如果这道机关无解，输出一行一个整数 −1。  
否则输出一种操作的方案。方案第一行，包含一个整数 c，表示操作的次数。c 应当满足 0≤c≤2×105。  
接下来 c 行，第 i 行包含一个整数 li，表示第 i 步操作翻转了 ali,ali+1,⋯,ali+k−1 这个子串。li 应当满足1≤li≤n−k+1。  
如果有多种方案，输出任意一种即可。可以证明，只要有解，必然存在一种不超过 2×105 次操作的方案。

样例输入 Copy  
4 2  
1 4 2 3  
1 2 3 4

样例输出 Copy  
2  
2  
3  
提示  
样例输入二  
6 4 2 5 4 1 6 3 1 2 3 4 5 6  
样例输出二  
2  
第一个样例，a 的变化为 1,4,2,3→1,2,4,3→1,2,3,4。  
第二个样例无解。

## 分析： ##

## AC代码： ##

# I：太阳轰炸 #

## 题目： ##

时间限制: 2 Sec 内存限制: 128 MB

题目描述  
背景：阿塔尼斯，达拉姆的大主教，在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰：亚顿之矛。作为艾尔星灵数千年来的智慧结晶，亚顿之矛除了搭载了以太阳能碎片为核心的兵工厂之外，还配备了诸如汇聚射线、太阳能射线枪等威力强大的支援武器。而在这些武器中，最负盛名、也最让敌人胆寒的就是太阳轰炸。  
太阳轰炸是一件威力巨大的对星球武器。在太阳轰炸开火时，亚顿之矛将聚集太阳能核心中的太阳能量，向目标坐标发射成百上千枚火焰飞弹。虽然这些火焰飞弹精准度较差，但太阳轰炸的高攻击频率仍然可以让地面上的敌人无法躲避，化为灰烬。  
在这一次的行动中，阿塔尼斯的目标是一枚臭名昭著的虚空碎片。在俯视视角下，虚空碎片的投影是一个半径为 R1 的圆，太阳轰炸的攻击散布范围是一个半径为 R2 的圆。这两个圆的圆心均为原点 (0,0)。太阳轰炸将射出 n 枚火焰飞弹，每一枚火焰飞弹等概率地落在攻击散布范围内每一个点上，所有火焰飞弹的落点相互独立。火焰飞弹的伤害范围是以落点为圆心，半径为 r 的圆。若火焰飞弹的伤害范围和虚空碎片的投影相交，则该枚火焰飞弹命中虚空碎片，造成 a 点伤害。若总伤害大于等于 h，则虚空碎片会被摧毁。  
摧毁这枚虚空碎片对阿塔尼斯的战略部署非常重要，因此阿塔尼斯想要知道一次太阳轰炸能够摧毁这枚虚空碎片的概率。你需要输出答案对质数 109+7 取模的值。

输入  
仅一行，包含六个整数 n, R1, R2, r, a, h (1≤n≤5×106, 1≤R1,R2,r≤108, 1≤a,h≤108)，含义见题目描述。

输出  
一个整数，表示答案。

样例输入 Copy  
3 2 4 1 1 1  
样例输出 Copy  
636962896  
提示  
答案对质数109+7 取模的定义：设 M=109+7，可以证明答案可表示为一个既约分数 p/q，其中 , 均为整数且 q 模 M 不余 0。输出满足 0≤x<M 且x⋅q≡p(mod M) 的整数 x。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]  
上图对应了样例中 R1=2,R2=4,r=1 的情况。其中红色的圆是虚空碎片的投影，蓝色的圆是太阳轰炸的攻击范围。A,B,C 是三个可能的落点，其中 A,C 命中虚空碎片，而 B 没有命中虚空碎片。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][20201124220136146.png_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    const int N = 5e6 + 10;
     
    ll fpow(ll a, int b, int mod) {  ll res = 1; for (; b > 0; b >>= 1) {  if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
    int jc[N], inv[N];
    int fz1[N], fz2[N];
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        jc[0] = 1;
        for (int i = 1; i <= 5e6; i++)
            jc[i] = 1LL * jc[i - 1] * i % mod;
        inv[5000000] = fpow(jc[5000000], mod - 2, mod);
        for (int i = 5e6 - 1; i >= 0; i--)
            inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
        ll n, r1, r2, r, a, h;
        cin >> n >> r1 >> r2 >> r >> a >> h;
        ll fm = 1, x1 = r2 * r2 % mod, x2 = (r1 + r) * (r1 + r) % mod, x3 = (x1 - x2 + mod) % mod;
        fz1[0] = fz2[0] = 1;
        for (int i = 1; i <= n; i++)
        { 
            fm = fm * x1 % mod;
            fz1[i] = 1LL * fz1[i - 1] * x2 % mod;
            fz2[i] = 1LL * fz2[i - 1] * x3 % mod;
        }
        ll res = 0;
        int flag = 0;
        for (int i = 1; i <= n; i++)
        { 
            if (i * a >= h)
            { 
                flag = 1;
                ll f = 1LL * jc[n] * inv[i] % mod * inv[n - i] % mod;
                res = (res + 1LL * f * fz1[i] % mod * fz2[n - i] % mod) % mod;
            }
        }
        if ((r1 + r) >= r2)
        { 
            printf("%d\n", flag);
            exit(0);
        }
        cout << res * fpow(fm, mod - 2, mod) % mod << endl;
        return 0;
    }

# J：二进制与、平方和 #

## 题目： ##

时间限制: 3 Sec 内存限制: 512 MB

题目描述  
请你维护一个长度为 n 的非负整数序列 a1,a2,…,an，支持以下两种操作：  
第一种操作会将序列 al,al+1,…,ar 中的每个元素，修改为各自和 x 的"二进制与"（Bitwise binary AND）的值，其中 l,r,x 在每次操作时会给定；  
第二种操作会询问序列 al,al+1,…,ar 中所有元素的平方和模 998244353的值，即 ∑i=lrai2 模 998244353，其中 l,r在每次操作时会给定。  
总共有 q 次操作，请你在维护序列的过程中，输出第二种操作所询问的答案。注意需要取模。

输入  
第一行，一个整数 n (1≤n≤3×105)，表示序列的长度。  
第二行，共 n 个整数 ai (0≤ai<224)，表示序列。  
第三行，一个整数 q (1≤q≤3×105)，表示询问的数量。  
接下来 q 行，每行表示一个操作，输入有两种格式：  
第一种操作的格式为 “1 l r x”，表示将序列中编号在区间 \[l,r\] 的所有元素，修改为和 x 二进制与操作后的值，其中 1≤l≤r≤n, 0≤x<224；  
第二种操作的格式为 “2 l r”，表示询问序列中编号在区间 \[l,r\] 的所有元素的平方和，模 998244353 的值，其中 1≤l≤r≤n。  
数据保证至少有一个第二种操作，即保证至少询问一次答案。

输出  
每当遇到第二种操作时，输出询问的答案。注意需要取模。

样例输入 Copy  
3  
13 31 28  
4  
2 1 3  
1 3 3 25  
1 1 2 18  
2 2 3

样例输出 Copy  
1914  
900

提示  
样例输入二  
5  
9 11 12 5 1  
7  
2 1 3  
1 3 3 0  
1 1 3 9  
1 4 5 13  
2 1 3  
1 4 5 14  
2 1 5

样例输出二  
346  
162  
178

样例输入三  
4  
16777215 16777215 16777215 16777214  
4  
2 2 2  
1 1 4 16777214  
2 1 4  
2 3 4

样例输出三  
981185168  
795789897  
897017125

“二进制与”（Bitwise binary AND）结果的第 i 个二进制位为 1，当且仅当两个操作数的第 i 位都为 1。

## 分析： ##

## AC代码： ##

# K：子串翻转回文串 #

## 题目： ##

时间限制: 2 Sec 内存限制: 128 MB

题目描述  
给一个串 s=s1s2⋯sn，你可以选定其一个非空子串，然后将该子串翻转。具体来说，若选定的子串区间为 \[l,r\]（1≤l≤r≤n），则翻转后该串变为 s1s2⋯sl−1srsr−1⋯slsr+1⋯sn。  
请你回答仅通过一次上述操作后，s 是否能变成回文串。串 s 是回文串，当且仅当它从左至右读出与从右至左读出完全相同，即 s1s2⋯sn=snsn−1⋯s1

输入  
注意：本题包含多组测试数据。  
第一行包含一个整数 T（1≤T≤5×105），表示数据组数。  
接下来的 T 行，每行包含一个仅由英文小写字母组成的字符串 s，含义见题目描述，且串长 ∣s∣ 满足1≤∣s∣≤5×105。  
保证字符串总长 ∑∣s∣不超过 5×105。

输出  
对于每组测试数据，输出一行一个字符串，若仅通过一次操作后 s 能变成回文串，则输出 Yes，否则输出 No，大小写不敏感。  
样例输入 Copy  
4  
abba  
bacad  
abacbaa  
aabadcdca  
样例输出 Copy  
Yes  
No  
Yes  
Yes  
提示  
第一组数据中，abba 翻转带下划线的子串得到回文串 abba。  
第二组数据中，无论如何翻转子串，都不能得到回文串。  
第三组数据中， abacbaa翻转带下划线的子串得到回文串 aabcbaa。  
第四组数据中， aabadcdca翻转带下划线的子串得到回文串 acdabadca。

## 分析： ##

[原文链接][Link 1].

## AC代码： ##

![在这里插入图片描述][20201124220855185.png_pic_center]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    const int mod = 20000311;
    const int INF = 0x3f3f3f3f;
    const int N = 5e5 + 10;
     
    struct StringHash 
    { 
        ll h[N], w[N], base, mod; 
        void Init(ll b, ll m)
        { 
            h[0] = 0, w[0] = 1, base = b, mod = m;
        }
        void Add(char* s)
        { 
            int len = strlen(s + 1);
            for (int i = 1; i <= len; i++)
                h[i] = (h[i - 1] * base + s[i]) % mod, w[i] = w[i - 1] * base % mod;
        }
        ll Get(int l, int r)
        { 
            return (h[r] - h[l - 1] * w[r - l + 1] % mod + mod) % mod;
        }
    }ha1, ha2;
    char t[N];
    char s[N];
    int n;
    bool check()
    { 
        for (int i = 1; i <= n; i++)
        { 
            if (i <= n - i)
            { 
                if (ha1.Get(1, i) == ha1.Get(n - i + 1, n))
                { 
                    if (ha1.Get(i + 1, n - i) == ha2.Get(i + 1, n - i))
                        return 1;
                }
            }
            else
            { 
                int len = n - i;
                if (ha1.Get(n - 2 * len + 1, n - len) == ha1.Get(n - len + 1, n))
                { 
                    if (ha1.Get(1, n - 2 * len) == ha2.Get(2 * len + 1, n))
                        return 1;
                }
            }
        }
        return 0;
    }
    int main()
    { 
    #ifdef LOCAL
        freopen("E:/input.txt", "r", stdin);
    #endif
        ha1.Init(233, 1e9 + 9);
        ha2.Init(233, 1e9 + 9);
        int T;
        cin >> T;
        while (T--)
        { 
            scanf("%s", t + 1);
            int len = strlen(t + 1);
            n = 0;
            for (int i = 1; i <= len; i++)
            { 
                if (t[i] != t[len - i + 1])
                { 
                    for (int j = i; j <= len - i + 1; j++)
                        s[++n] = t[j];
                    break;
                }
            }
            if (n == 0)
            { 
                puts("Yes");
                continue;
            }
            ha1.Add(s);
            reverse(s + 1, s + n + 1);
            ha2.Add(s);
            int ans = check();
            if (!ans)
            { 
                ha1.Add(s);
                reverse(s + 1, s + n + 1);
                ha2.Add(s);
                ans = check();
            }
            puts(ans ? "Yes" : "No");
        }
        return 0;
    }

# L：送外卖 #

## 题目： ##

时间限制: 8 Sec 内存限制: 512 MB

题目描述  
在智慧岛上，程序员小 Q 每天下班都会在 n 栋公寓之间兼职送外卖。这 n 栋公寓由 m 条双向道路连通，任意两栋公寓可通过这些道路相互到达。第 i 条道路连接公寓 ui,vi，长度为 wi 米。  
精通解梦的小 Q 早已在昨夜梦中知晓今日的所有订单信息：今晚，每栋公寓都恰好订了一份外卖，公寓 i 在 qi 秒下单。小 Q 下班后会从 1 公寓骑上他的小电驴，从 0 秒开始送餐。小 Q 可以以不超过 1 m/s的速度沿道路移动，也可以在任意位置休息不动，到达公寓后的送餐时间可以忽略不计。当然，小 Q 不能在下单前将外卖送达，以免引起客户的恐慌。  
对于一笔订单，小Q在订单发起后的不同时间送达将会产生不同收益。形式化地说，对一笔订单 j，外卖平台会规定 d 个送达时间节点 qj<t1<t2<⋯<td（单位：秒），以及 d+1 个根据时间变化的收益p1, p2, ⋯, pd+1。注意，收益不一定随着送达时间推迟而减少。设小 Q 在 T 秒送达外卖，那么他的收益为

聪明的你能告诉小 Q，今晚送完所有订单最多能挣多少钱吗？

输入  
第一行包含两个整数 n, m (1≤n≤14, n−1≤m≤(n(n−1))/2)，分别表示公寓的数量和道路的数量。  
接下来 m 行，第 i 行包含三个整数 ui,vi,wi (1≤ui,vi≤n, ui≠vi, 1≤wi≤300)，表示第 i 条道路连接公寓 ui,vi，长度为 wi 米。保证无重边。  
接下来一行包含 n 个整数，第 i 个整数为 qi (0≤qi≤200)，表示第 i 栋公寓订单的发起时刻。  
接下来 3n 行，每 3 行依次描述公寓 1,2,⋯,n 订单的收益信息。第一行包含一个整数 d (1≤d≤200)。第二行包含 d 个整数，第 i 个整数为 ti (1≤ti≤200)。第三行包含 d+1 个整数，第 d+1 个整数为 pi (0≤pi≤108)。d,ti,pi的含义见题目描述。  
输出  
输出一行一个整数，表示最大收益。  
样例输入 Copy  
3 2  
1 2 1  
2 3 1  
1 3 3  
1  
2  
5 1  
1  
4  
5 4  
1  
4  
5 1  
样例输出 Copy  
14  
提示  
样例中，小 Q 在第 0 秒时已经在 1 号公寓等候订单；第 1 秒小 Q 完成 1 号订单（不计时间），获得 5 收益，随后动身前往 3 号公寓，并于第 3 秒抵达；第 3 秒小 Q 完成 3 号订单，获得 5 收益，随后动身前往 2 号公寓，并于第 4 秒抵达；第 4 秒小 Q 完成 2 号订单，获得 4 收益，此时全部订单完成，小 Q 获得最大收益 14。

## 分析： ##

## AC代码： ##

欢迎大佬一起进群交流![在这里插入图片描述][20201124221504442.png_pic_center]

![在这里插入图片描述][20201124221402227.png_pic_center]

# 榜单： #

明天更新！  
https://acm.sdut.edu.cn/srk\_ccpc/  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]

[Link 1]: https://blog.csdn.net/weixin_43731933?t=1
[20201124220455282.png_pic_center]: /images/20221120/3153a417ea5e4ab79d3275c7b873461e.png
[20201124220435736.png_pic_center]: /images/20221120/97be79dc2ade4a3db4a4c0a79b9d673e.png
[20201124220604265.png_pic_center]: /images/20221120/5ddb2b094a9246308a4205fc33596a8e.png
[2020112422071265.png_pic_center]: /images/20221120/7ae23ab993db4d56bb8777335ab1a083.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e44961bf15644841933dee6c9617b7c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201124215515214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70#pic_center
[20201124220136146.png_pic_center]: https://img-blog.csdnimg.cn/20201124220136146.png#pic_center
[20201124220855185.png_pic_center]: https://img-blog.csdnimg.cn/20201124220855185.png#pic_center
[20201124221504442.png_pic_center]: https://img-blog.csdnimg.cn/20201124221504442.png#pic_center
[20201124221402227.png_pic_center]: https://img-blog.csdnimg.cn/20201124221402227.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201121212815836.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70#pic_center