大家好，我是本场比赛的出题人 Leonard，这场比赛由我和 jcccc 负责出题，其中的 A、B、C、E、G、H、I、J、K 是我出的，题面较长的 D、F、L 是由 jcccc 出的。很抱歉，题目出现了一些低级失误，对参赛选手造成了不小的影响。同时也要感谢 Kath，Messywind，磊磊困了，莫说啥，Kidding_Ma，q204789594，s7wIn99，XXPC，obss，SQ2547，yxlxszx，joker_ss，paopaooux，pokemon_，xiandan_dd，SugarT，jk1024，YangFan_，supinf，WHH_FZZ，hide_on_dirt 进行验题工作，感谢各位大佬前来捧场。
赛前对题目难度的预计：
easy：A、G
medium-easy：C、E
medium：B、D、L、H
medium-hard：I、K
hard：F、J
A.下一个
对 和 特判，其余字母输出下一个字母。
B.新大陆
设位于第 行第 列的数字为 ，统计 后面最多有多少个与他相等的元素，记个数为 。然后从下往上枚举找是否有符合答案的状态。
因为长不一定和行平行，宽不一定和列平行，所以我们要考虑两种情况：
1.长与行平行，宽与列平行。
2.长与列平行，宽与行平行。
符合答案的状态有：
1.列长度大于等于 且 。
2.列长度大于等于 且 。
C.勇者之塔
一步步走肯定会超时，容易发现，每一层的起点都是 , 走完一层的步数是一定的，所以可以计算出完整走完一层的层数，再算一下在最终层的位置。
D.史莱姆的战术训练
先求出每种粘液的粘度是多少。因为粘液只会粘在粘度比它小的物体上，所以这样将操作按照粘度从大到小的顺序排序，从而当用一种粘液覆盖这个点时发现这个点已经被粘度大的粘液覆盖后，即可以不覆盖在这个点的本次操作。
于是，我们可以用并查集或者set来维护每个点是否已经被粘液覆盖过，如果已经被覆盖过，就不再跳过这个点的本次操作。
注意 和 的数据范围是 ，所以如果 时应要交换 和 。
这题难度并不大，可能是因为题面的缘故导致实际通过人数不多……
E.贴贴
先说结论，符合条件的数之间的距离一定很小。
质数一定是符合条件的数，且质数之间的距离大概是 ln 级别的，距离除以 2 之后并不会太大，而其余符合条件的数的距离会更小(可以打一下表)，甚至直接暴力比筛质数跑还快( 至于证明呢，就交给聪明的你了！
F.时间就是金钱，我的朋友
虚树，选出一个点使其到达给定点的距离之和最小，可以发现其实是选虚树的重心。
G.简单的数学
输出 即可。
H.Leonard的子序列
对于一个数 来说，如果只考虑在序列中比他更靠前的数的话，那么他产生的价值即是在序列中以比他更靠前且更小的数结尾的子序列价值之和 + 在序列中以比他更靠前且更小的数结尾的子序列的个数 + 1(以自己开始的子序列)。
那么即用线段树或树状数组查询小于等于 / 的数的个数和价值，然后把自己也添加进去。
值得注意的是 / = ，不需要特判。
I.秋游
一道很经典的问题，对关键点进行 dijkstra，跑出关键点和其余点的最短路，然后再以已经走过的点作为状态进行状压 dp， 表示走过景点的状态为 ，当前所在点为 ，不要忘了加上返回的距离。
J.串串大师
首先字符串中有一个性质，一个字符串中本质不同的回文串的个数最多是 级别的， 是字符串的长度，回文串的算法回文自动机和马拉车也都是利用了这个性质。这题的做法很多，我说一下其中的两种做法，第一种是回文自动机，如果会回文自动机的话这道题就是一道裸题了，出这道题的时候我还不会回文自动机555，所以我写了第二种做法，马拉车+哈希 对已经处理过的回文串的哈希值记忆化一下它们的贡献，为什么要记忆化呢，还是用到了上面的性质，所以我们需要处理的回文串的个数最多也是 级别的，这种写法的实现难度远高于第一种写法……
K.Leonard的树
诸如此类的子树问题可以考虑用 dfs序做，如果不考虑并集的话，这题就是一个经典的 dfs序建线段树或树状数组的题了。怎么处理并集呢？我们可以发现，存在并集的节点的 dfs序一定是有交集的，所以可以把每个节点的 dfs序看成一个区间，把这些区间合并一下再在线段树或树状数组查询就可以了。
L.奥特曼的时间管理
1.进行模拟。
2.将时间全转化成秒，然后进行差分
std是差分的版本
std：
A.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve() {
char c;
cin >> c;
if(c == 'z' || c == 'Z') cout << "non-existent";
else cout << char(c + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
B.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<ll>> a(n + 10, vector<ll> (m + 10, -1));
vector<vector<int>> b(n + 10, vector<int> (m + 10));
vector<vector<int>> c(n + 10, vector<int> (m + 10));
vector<vector<int>> d(n + 10, vector<int> (m + 10));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 1; j--) {
if(j == m) b[i][j] = 1;
else b[i][j] = (a[i][j] == a[i][j + 1]) ? b[i][j + 1] + 1 : 1;
}
}
int h, w;
cin >> h >> w;
bool res = 0;
for(int i = n; i >= 1; i--) {
for(int j = 1; j <= m; j++) {
if(b[i][j] >= w) {
if(a[i][j] == a[i + 1][j]) c[i][j] = c[i + 1][j] + 1;
else c[i][j] = 1;
}
if(c[i][j] >= h) res = 1;
}
}
for(int i = n; i >= 1; i--) {
for(int j = 1; j <= m; j++) {
if(b[i][j] >= h) {
if(a[i][j] == a[i + 1][j]) d[i][j] = d[i + 1][j] + 1;
else d[i][j] = 1;
}
if(d[i][j] >= w) res = 1;
}
}
cout << (res ? "YES" : "NO");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
C.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve() {
int n, m, q;
cin >> n >> m >> q;
while(q--) {
ll x, y, k;
cin >> x >> y >> k;
if(!k)
cout << "1 1 1\n";
else {
if(!x && !y)
cout << "1 1 1\n";
else if(!x) {
ll cnt = m / y + (m % y != 0);
ll cur = 1;
cur += k / cnt;
k %= cnt;
ll u = 1, v = 1;
v += k * y;
cout << cur << ' ' << u << ' ' << v << '\n';
}
else if(!y) {
ll cnt = n / x + (n % x != 0);
ll cur = 1;
cur += k / cnt;
k %= cnt;
ll u = 1, v = 1;
u += k * x;
cout << cur << ' ' << u << ' ' << v << '\n';
}
else {
ll cnt = min(m / y + (m % y != 0), n / x + (n % x != 0));
ll cur = 1;
cur += k / cnt;
k %= cnt;
ll u = 1, v = 1;
u += k * x, v += k * y;
cout << cur << ' ' << u << ' ' << v << '\n';
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
D.
#include<bits/stdc++.h>
#define PII pair<int,int>
#define PLL pair<long long,long long>
#define fi first
#define se second
#define endl '\n'
#define bug printf("bug\n");
using namespace std;
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
struct Query{
int xa, ya, xb, yb, col;
friend bool operator < (Query w, Query z){
return w.col > z.col;
}
}q[N];
int val[N], res[N], fa[N], s[N];
int n, m, p, c, a, b;
long long cal(long long x){
return a * x + b;
}
int find(int x){
if(fa[x] != x) return fa[x] = find(fa[x]);
return fa[x] = x;
}
void solve(){
cin >> n >> m >> p >> c >> a >> b;
int flag = 0;
if(n > m) swap(n, m), flag = 1;
for(int i = 1; i <= c; i++){
cin >> val[i];
s[val[i]] = i;
val[i] = cal(val[i]);
}
for(int i = 1; i <= p; i++){
if(flag == 0) cin >> q[i].xa >> q[i].ya >> q[i].xb >> q[i].yb >> q[i].col;
else cin >> q[i].ya >> q[i].xa >> q[i].yb >> q[i].xb >> q[i].col;
q[i].col = val[q[i].col];
}
sort(q + 1, q + p + 1);
for(int i = 1; i <= n * m + 5; i++) fa[i] = i;
for(int i = 1; i <= p; i++){
int xa = q[i].xa, ya = q[i].ya, xb = q[i].xb, yb = q[i].yb, col = q[i].col;
if(col <= 0) continue;
for(int j = xa; j <= xb; j++){
for(int k = find(ya + (j - 1) * m); k <= (yb + (j - 1) * m); k = find(k + 1)){
res[k] = col; fa[k] = k + 1;
}
}
}
if(!flag){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(res[j + (i - 1) * m] == 0) cout << 0 << ' ';
else cout << s[(res[j + (i - 1) * m] - b) / a] << ' ';
}
cout << endl;
}
}
else{
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(res[i + (j - 1) * m] == 0) cout << 0 << ' ';
else cout << s[(res[i + (j - 1) * m] - b) / a] << ' ';
}
cout << endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while(t--){
solve();
}
return 0 - 0;
}
E.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e7 + 10;
const int mod = 1e9 + 7;
int m, p[N], np[N];
void get_prime() {
for(int i = 2; i < N; i++) {
if(!np[i])
p[++m] = i;
for(int j = 1; p[j] < N / i && j <= m; j++) {
np[i * p[j]] = p[j];
if(i % p[j] == 0)
break;
}
}
}
void solve() {
get_prime();
ll x;
cin >> x;
array <ll, 2> res;
for(ll i = x; i >= 1; i--) {
ll num = i;
bool nice = 1;
for(int j = 1; j <= m; j++) {
int cnt = 0;
while(num % p[j] == 0)
num /= p[j], cnt++;
if(cnt > 1) {
nice = 0;
break;
}
if(num == 1)
break;
}
if(nice) {
res[0] = i;
break;
}
}
for(ll i = x + 1; i; i++) {
ll num = i;
bool nice = 1;
for(int j = 1; j <= m; j++) {
int cnt = 0;
while(num % p[j] == 0)
num /= p[j], cnt++;
if(cnt > 1) {
nice = 0;
break;
}
if(num == 1)
break;
}
if(nice) {
res[1] = i;
break;
}
}
if(abs(x - res[0]) == abs(x - res[1])) cout << res[0] << '\n' << res[1];
else {
if(abs(x - res[0]) < abs(x - res[1])) cout << res[0];
else cout << res[1];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
F.
#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout << "bug" << endl;
#define endl '\n'
using namespace std;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using ll = long long;
const int N = 3e5 + 10;
const int M = 1e3 + 10;
const int INF= 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
struct Tree{
long long cnt, h[N], ne[N << 1], e[N << 1];
void init(){
cnt = 0;
memset(h, 0, sizeof(h));
}
void add(int u, int v){
e[++cnt] = v;
ne[cnt] = h[u];
h[u] = cnt;
}
}e1, e2;
int n, m, idx;
int st[N], top;
int s[N], deep[N], dfn[N], fa[N][20];
long long minn[N], dp[N];
long long sum, tr_sz, rt;
long long f[N], sz[N], sz2[N];
void dfs(int u, int father){
dfn[u] = ++idx; deep[u] = deep[father] + 1, fa[u][0] = father;
for(int i = 1; i <= 17; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int i = e1.h[u]; i; i = e1.ne[i]){
int v = e1.e[i];
if(v != father){
dfs(v, u);
}
}
}
int LCA(int a, int b){
if(deep[a] < deep[b]) swap(a, b);
for(int i = 17; i >= 0; i--){
if(deep[fa[a][i]] >= deep[b]) a = fa[a][i];
}
if(a == b) return a;
for(int i = 17; i >= 0; i--){
if(fa[a][i] != fa[b][i]){
a = fa[a][i]; b = fa[b][i];
}
}
return fa[a][0];
}
int cmp(int a, int b){
return dfn[a] < dfn[b];
}
void insert(int u){
if(top == 1){
if(u != 1) st[++top] = u, tr_sz++, e2.h[u] = 0, sz2[u]++;
return ;
}
int lca = LCA(u, st[top]);
for(; top > 1 && dfn[st[top - 1]] >= dfn[lca]; top--){
if(st[top - 1] == st[top]) continue;
e2.add(st[top - 1], st[top]);
}
if(st[top] != lca){
if(lca != st[top]) e2.add(lca, st[top]);
st[top] = lca;
}
st[++top] = u; tr_sz++; sz2[u]++;
e2.h[u] = 0;
}
void get_root(int u, int father){
f[u] = 0, sz[u] = sz2[u]; sz2[u] = 0;
for(int i = e2.h[u]; i; i = e2.ne[i]){
int v = e2.e[i];
if(v == father) continue;
get_root(v, u);
f[u] = max(f[u], sz[v]);
sz[u] += sz[v];
}
f[u] = max(f[u], tr_sz - sz[u]);
if(f[u] < f[rt]) rt = u;
e2.h[u] = 0;
}
void solve(){
cin >> n >> m;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
e1.add(u, v); e1.add(v, u);
}
dfs(1, 0);
while(m--){
int k, num; cin >> k >> num;
for(int i = 1; i <= num; i++) cin >> s[i];
sort(s + 1, s + num + 1, cmp);
top = e2.cnt = 0;
tr_sz = 1;
sz2[1]++;
rt = 0;
f[0] = INF;
st[top = 1] = 1;
e2.h[1] = 0;
for(int i = 1; i <= num; i++) insert(s[i]);
for(int i = 1; i < top; i++) e2.add(st[i], st[i + 1]);
get_root(1, 0);
long long res = 0;
for(int i = 1; i <= num; i++){
int lca = LCA(rt, s[i]);
if(lca == rt || lca == s[i]) res = res + abs(deep[rt] - deep[s[i]]);
else res = res + abs(deep[lca] - deep[s[i]]) + abs(deep[lca] - deep[rt]);
}
if(res >= k) cout << "Good game" << endl;
else cout << res << endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0 - 0;
}
G.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
cout << n;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
H.
线段树版本：
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, m;
ll a[N], b[N];
int find(ll x) {
return upper_bound(b + 1, b + 1 + m, x) - b - 1;
}
struct node {
int l, r;
ll cnt, v;
#define lc u << 1
#define rc u << 1 | 1
} tr[N << 2];
void pushup(int u) {
tr[u].v = (tr[lc].v + tr[rc].v) % mod;
tr[u].cnt = (tr[lc].cnt + tr[rc].cnt) % mod;
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if(l == r) {
return ;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(u);
}
ll qry1(int u, int l, int r) {
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
ll sum = 0;
if(l <= mid) sum = (sum + qry1(lc, l, r));
if(r > mid) sum = (sum + qry1(rc, l, r));
return sum;
}
ll qry2(int u, int l, int r) {
if(tr[u].l >= l && tr[u].r <= r) return tr[u].cnt;
int mid = tr[u].l + tr[u].r >> 1;
ll sum = 0;
if(l <= mid) sum = (sum + qry2(lc, l, r));
if(r > mid) sum = (sum + qry2(rc, l, r));
return sum;
}
void modify1(int u, int x, ll v) {
if(tr[u].l == x && tr[u].r == x) tr[u].v = (tr[u].v + v) % mod;
else {
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= x) modify1(lc, x, v);
else modify1(rc, x, v);
pushup(u);
}
}
void modify2(int u, int x, ll v) {
if(tr[u].l == x && tr[u].r == x) tr[u].cnt = (tr[u].cnt + v) % mod;
else {
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= x) modify2(lc, x, v);
else modify2(rc, x, v);
pushup(u);
}
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i], b[i] = a[i];
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
build(1, 1, m);
for(int i = 1; i <= n; i++) {
int pos1 = find(a[i]), pos2 = find(a[i] / 2);
ll cnt = 0, v = 0;
if(pos2) {
v = qry1(1, 1, pos2);
cnt = qry2(1, 1, pos2);
}
cnt = (cnt + 1) % mod;
v = (v + cnt) % mod;
modify1(1, pos1, v);
modify2(1, pos1, cnt);
}
ll res = 0;
for(int i = 1; i <= m; i++) {
res = (res + qry1(1, i, i)) % mod;
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
树状数组版本
#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout << "bug" << endl;
#define endl '\n'
using namespace std;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using ll = long long;
const int N = 2e5 + 10;
const int M = 1e3 + 10;
const int INF= 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
int n;
long long tr1[N], tr2[N], s[N];
long long lowbit(int x){
return x & -x;
}
void add(int nw, long long val, long long tr[]){
while(nw <= n){
tr[nw] += val;
nw += lowbit(nw);
}
}
long long query(int nw, long long tr[]){
long long res = 0;
while(nw > 0){
res = res + tr[nw];
nw -= lowbit(nw);
}
return res;
}
void solve(){
cin >> n;
vector<double>ve;
for(int i = 1; i <= n; i++) cin >> s[i], ve.push_back(s[i] * 1.0);
sort(ve.begin(), ve.end());
int len = unique(ve.begin(), ve.end()) - (ve.begin());
long long res = 0;
for(int i = 1; i <= n; i++){
int ver1 = upper_bound(ve.begin(), ve.begin() + len, s[i] * 1.0 / 2) - ve.begin() + 1;
long long num1 = query(ver1, tr1) % mod;
long long num2 = query(ver1, tr2) % mod;
int ver2 = lower_bound(ve.begin(), ve.begin() + len, s[i] * 1.0) - ve.begin() + 2;
add(ver2, (num1 + num2 + 1) % mod, tr1);
add(ver2, (num2 + 1) % mod, tr2);
res = (res + num1 + num2 + 1) % mod;
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0 - 0;
}
I.
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, x, y, m, a[21];
auto dijkstra(vector<vector<PII>> &g, int s) {
vector<ll> d(n + 1, -1);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
vector<int> st(n + 1);
q.push({0, s});
d[s] = 0;
while(!q.empty()) {
int u = q.top().se;
q.pop();
if(st[u]) continue;
st[u] = 1;
for(auto [v, w] : g[u]) {
if(d[v] == -1 || d[v] > d[u] + w) {
q.push({d[v] = d[u] + w, v});
}
}
}
return d;
}
ll dp[1 << 19][19];
void solve() {
cin >> n >> x >> y;
vector<vector<PII>> g(n + 1);
vector<vector<ll>> d(x + 1, vector<ll> (n + 1));
a[0] = 1;
for(int i = 1; i <= x; i++)
cin >> a[i];
cin >> m;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 0; i <= x; i++) {
d[i] = dijkstra(g, a[i]);
}
memset(dp, 0x3f, sizeof dp);
dp[1][0] = 0;
ll res = 9e18;
for(int i = 1; i < 1 << (x + 1); i += 2) {
int cnt = __builtin_popcount(i);
if(cnt - 1 > y) continue;
for(int j = 0; j < (x + 1); j++) {
if(i >> j & 1) {
if(dp[i][j] <= 1e16) {
for(int k = 1; k < (x + 1); k++) {
if(!(i >> k & 1)) {
dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + d[j][a[k]]);
}
}
}
if(cnt - 1 == y) {
res = min(res, dp[i][j] + d[j][1]);
}
}
}
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
J.
马拉车版本
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 1e5 + 10, M = 1e5 + 10;
const ll MOD = 1e9 + 7;
ll p[2][M], P[2] = {131, 13331}, mod[2] = {1000000007, 998244353};
vector<ll> h[2][N];
vector<int> cnt[N][26];
string s[N];
auto hs(int op, int l, int r) {
array<ll, 2> hs;
hs[0] = (((h[0][op][r] - h[0][op][l - 1] * p[0][r - l + 1] % mod[0]) % mod[0]) + mod[0]) % mod[0];
hs[1] = (((h[1][op][r] - h[1][op][l - 1] * p[1][r - l + 1] % mod[1]) % mod[1]) + mod[1]) % mod[1];
return hs;
}
ll res;
map <array<ll, 2>, int> c;
char b[M * 2];
int pos[M * 2];
int z[M * 2], l;
void init(string &s) {
int k = 1;
b[0] = '$', b[1] = '#';
for(int i = 1; i < (int)s.size(); i++) {
b[++k] = s[i];
pos[k] = i;
b[++k] = '#';
}
b[++k] = '^';
l = k;
}
void manacher(int op) {
int r = 0, mid;
for(int i = 2; i <= l; i++) {
if(i <= r)
z[i] = min(z[mid * 2 - i], r - i + 1);
else
z[i] = 1;
while(b[i - z[i]] == b[i + z[i]]) {
z[i]++;
}
int x = pos[i - z[i] + 2], y = pos[i + z[i] - 2];
int tx = x, ty = y;
int p1 = 0;
if(x > y || !x || !y || x >= s[op].size() || y >= s[op].size()) continue;
while(x <= y) {
array<ll, 2> h = hs(op, x, y);
if(c.count(h)) {
p1 = x;
break;
}
if(x + 1 <= y - 1)
x++, y--;
else
break;
}
if(p1) {
while(x > tx) {
array<ll, 2> h1 = hs(op, x, y);
array<ll, 2> h2 = hs(op, x - 1, y + 1);
ll mul = 1;
for(int j = 0; j < 26; j++) {
int num = cnt[op][j][y + 1] - cnt[op][j][x - 2];
if(num)
mul = mul * num % MOD;
}
c[h2] = (1ll * c[h2] + c[h1]) % MOD;
c[h2] = (1ll * c[h2] + mul) % MOD;
x--;
y++;
}
}
else {
array<ll, 2> h = hs(op, x, y);
ll mul = 1;
for(int j = 0; j < 26; j++) {
int num = cnt[op][j][y] - cnt[op][j][x - 1];
if(num)
mul = mul * num % MOD;
}
c[h] = mul;
while(x > tx) {
array<ll, 2> h1 = hs(op, x, y);
array<ll, 2> h2 = hs(op, x - 1, y + 1);
ll mul = 1;
for(int j = 0; j < 26; j++) {
int num = cnt[op][j][y + 1] - cnt[op][j][x - 2];
if(num)
mul = mul * num % MOD;
}
c[h2] = c[h1];
c[h2] = (1ll * c[h2] + mul) % MOD;
x--;
y++;
}
}
array<ll, 2> h = hs(op, tx, ty);
res = (res + c[h]) % MOD;
if(i + z[i] - 1 > r) {
r = i + z[i] - 1;
mid = i;
}
}
}
void solve() {
int n;
cin >> n;
int len = 0;
for(int i = 1; i <= n; i++)
cin >> s[i], s[i] = ' ' + s[i], len = max(len, (int)s[i].size()), h[0][i].resize(s[i].size()), h[1][i].resize(s[i].size());
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 26; j++)
cnt[i][j].resize(s[i].size());
}
p[0][0] = p[1][0] = 1;
for(int j = 0; j < 2; j++) {
for(int i = 1; i < len; i++)
p[j][i] = p[j][i - 1] * P[j] % mod[j];
}
for(int j = 0; j < 2; j++) {
for(int i = 1; i <= n; i++) {
for(int k = 1; k < (int)s[i].size(); k++) {
h[j][i][k] = (h[j][i][k - 1] * P[j] + s[i][k]) % mod[j];
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j < (int)s[i].size(); j++) {
for(int k = 0; k < 26; k++) {
cnt[i][k][j] = cnt[i][k][j - 1];
}
cnt[i][s[i][j] - 'a'][j]++;
}
}
for(int i = 1; i <= n; i++) {
init(s[i]);
manacher(i);
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
回文自动机版本(来自于kath大佬)
#include <iostream> /// 本质不同公共回文子串数(广义PAM)
#include <cstring>
#include <bitset>
using namespace std;
#define int long long
const int N=300005,mod=1e9+7; // 最多5个串
int pam[N][26],last,pam_cnt,ni; // 树上的每一个节点都代表一个回文串 上一个形成的回文串的代表节点 添加节点的个数 添加字符的个数
int fail[N],cnt[N],num[N],len[N]; // fail:指向最长后缀回文串代表的节点 cnt:节点i表示的本质不同的回文串的数量
char s[N]; // 存放添加的字符 num:以节点i表示的回文串的右端点结尾的回文串的数量 len:以节点i表示的回文串的串长
int mm_cnt[N*26][26];
void init()
{
last=0;
len[1]=-1;
s[0]='?';
fail[0]=fail[1]=1;
}
int get_fail(int x)
{
while(s[ni-len[x]-1]!=s[ni])
x=fail[x];
return x;
}
void add(int c, int idx)
{
int old=get_fail(last); // 找到最长的串 cA 使得可以和 c 拼接成 cAc (A可以是空串)
if(!pam[old][c]) // 出现了一个新的本质不同回文串
{
int now=++pam_cnt;
fail[now]=pam[get_fail(fail[old])][c];
pam[old][c]=now;
len[now]=len[old]+2;
for(int j=0; j<26; j++)
mm_cnt[now][j]=mm_cnt[old][j];
mm_cnt[now][c]++;
if(len[now]!=1)
mm_cnt[now][c]++;
}
last=pam[old][c];
cnt[last]++;
}
void count() // 计算每个本质不同回文串的出现次数
{
for(int i=pam_cnt; i>=2; i--)
(cnt[fail[i]]+=cnt[i])%=mod;
}
signed main()
{
pam_cnt=1;
int k,n;
scanf("%lld", &k);
for(int i=1; i<=k; i++)
{
scanf("%s", s+1);init();
n=strlen(s+1);
for(ni=1; ni<=n; ni++)
add(s[ni]-'a', i);
}
count();
long long ans=0;
for(int i=2; i<=pam_cnt; i++)
{
long long res=1;
for(int j=0; j<26; j++)
if(mm_cnt[i][j])
res=res*mm_cnt[i][j]%mod;
// cout << len[i] << " : " << res << '\n';
ans=(ans+res*cnt[i]%mod)%mod;
}
cout << ans << '\n';
return 0;
}
K.
树状数组版本
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, q;
vector<int> e[N];
int in[N], out[N], cur, c[N];
void dfs(int u, int fa) {
in[u] = ++cur;
for(int v : e[u]) {
if(v == fa) continue;
dfs(v, u);
}
out[u] = cur;
}
int tr[2][11][N];
int lowbit(int x) {
return x & -x;
}
void add(int op, int p, int x) {
for(int i = p; i <= n; i += lowbit(i))
tr[0][op][i] += x, tr[1][op][i] += x * p;
}
int query(int op, int x) {
int res = 0;
for(int i = x; i; i -= lowbit(i)) {
res += (x + 1) * tr[0][op][i] - tr[1][op][i];
}
return res;
}
struct node {
int l, r;
} b[N];
bool cmp(node x, node y) {
if(x.l == y.l)
return x.r < y.r;
else
return x.l < y.l;
}
void solve() {
cin >> n >> q;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].eb(v), e[v].eb(u);
}
dfs(1, 0);
for(int i = 1; i <= n; i++)
cin >> c[i], add(c[i], in[i], 1), add(c[i], in[i] + 1, -1);
while(q--) {
int op;
cin >> op;
if(op == 1) {
int x, y;
cin >> x >> y;
add(c[x], in[x], -1);
add(c[x], in[x] + 1, 1);
c[x] = y;
add(c[x], in[x], 1);
add(c[x], in[x] + 1, -1);
}
else {
int m;
cin >> m;
vector<int> res(11);
for(int i = 1; i <= m; i++) {
int x;
cin >> x;
b[i].l = in[x], b[i].r = out[x];
}
sort(b + 1, b + 1 + m, cmp);
int lst = 0;
for(int i = 1; i <= m; i++) {
if(b[i].r > lst) {
int l = max(lst + 1, b[i].l), r = b[i].r;
for(int j = 1; j <= 10; j++) {
res[j] += query(j, r) - query(j, l - 1);
}
lst = b[i].r;
}
}
for(int i = 1; i <= 10; i++)
cout << res[i] << ' ';
cout << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
t = 1;
while(t--) {
solve();
}
}
L.
#include<bits/stdc++.h>
#define fi first
#define se second
#define bug cout << "bug" << endl;
#define endl '\n'
using namespace std;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using ll = long long;
const int N = 2e7 + 10;
const int M = 1e3 + 10;
const int INF= 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const long long mod = 1e9 + 7;
long long s[N];
void solve(){
long long n, x, y, z, k, val; cin >> n >> x >> y >> z >> k >> val;
for(int i = 1; i <= n; i++){
string sa, sb; cin >> sa >> sb;
long long num1 = ((sa[0] - '0') * 10 + (sa[1] - '0')) * y * z + ((sa[3] - '0') * 10 + (sa[4] - '0')) * z + (sa[6] - '0') * 10 + (sa[7] - '0');
long long num2 = ((sb[0] - '0') * 10 + (sb[1] - '0')) * y * z + ((sb[3] - '0') * 10 + (sb[4] - '0')) * z + (sb[6] - '0') * 10 + (sb[7] - '0');
s[num1]++; s[num2 + 1]--;
}
for(int i = 0; i <= (x - 1) * y * z + (y - 1) * z + (z - 1); i++) s[i] = s[i] + s[i - 1];
long long res = 0, nw = k + 1;
for(int i = 0; i <= (x - 1) * y * z + (y - 1) * z + (z - 1); i++){
if(s[i] != 0) nw = 0, res++;
else{
nw++;
if(nw <= k) res++;
}
}
res = res * val;
cout << res << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0 - 0;
}
京公网安备 11010502036488号