光荣爆0
A circle (Unaccepted)
题目大意 ：
- 咕咕
Code
Show Code
B 生成膜咒
题目大意 ： 每在后面添一个字母就求一下每个子串在后缀自动机的parent树上到跟的所有点的深度和，允许离线
- 用后缀自动机求出每新增一个字母的贡献，有个需要从点到根的修改并询问，就把树先建出来，然后树剖维护
Code
Show Code
#include <cstdio>
#include <cstring>
#define ls (rt << 1)
#define rs (rt << 1 | 1)
using namespace std;
const int N = 4e5 + 5, M = 1e9 + 7;
struct Edge {
int n, t;
}e[N];
int h[N], edc;
void Add(int x, int y) {
e[++edc] = (Edge) {h[x], y}; h[x] = edc;
}
int n, fa[N], t[N][26], len[N], lt, trc, ans, sum, a[N];
int sz[N], son[N], tp[N], dep[N], dfn[N], dfc, b[N], s[N], w[N*4], tag[N*4];
char c[N];
void Dfs(int x) {
sz[x] = 1; dep[x] = dep[fa[x]] + 1;
for (int i = h[x], y; i; i = e[i].n) {
Dfs(y = e[i].t); sz[x] += sz[y];
if (sz[y] > sz[son[x]]) son[x] = y;
}
}
void Dfs(int x, int top) {
tp[x] = top; dfn[x] = ++dfc; b[dfc] = x;
if (son[x]) Dfs(son[x], top);
for (int i = h[x], y; i; i = e[i].n)
if ((y = e[i].t) != son[x]) Dfs(y, y);
}
int Cal(int l, int r) {
return (s[r] - s[l-1] + M) % M;
}
int Ask(int rt, int l, int r, int x, int y) {
if (x <= l && r <= y) {
int tmp = w[rt]; tag[rt]++;
if ((w[rt] += Cal(l, r)) >= M) w[rt] -= M;
return tmp;
}
int mid = l + r >> 1, ans = 0;
if (tag[rt]) {
if ((w[ls] += 1ll * Cal(l, mid) * tag[rt] % M) >= M) w[ls] -= M;
if ((w[rs] += 1ll * Cal(mid+1, r) * tag[rt] % M) >= M) w[rs] -= M;
tag[ls] += tag[rt]; tag[rs] += tag[rt]; tag[rt] = 0;
}
if (x <= mid) ans = Ask(ls, l, mid, x, y);
if (y > mid) ans += Ask(rs, mid+1, r, x, y);
if ((w[rt] = w[ls] + w[rs]) >= M) w[rt] -= M;
return ans >= M ? ans - M : ans;
}
int main() {
scanf("%d%s", &n, c + 1);
lt = trc = 1;
for (int i = 1; i <= n; ++i) {
int x = lt, C = c[i] - 'a', y, z;
len[lt = ++trc] = len[x] + 1;
for (; x && !t[x][C]; x = fa[x]) t[x][C] = lt;
if (!x) fa[lt] = 1;
else if (len[y = t[x][C]] == len[x] + 1) fa[lt] = y;
else {
fa[z = ++trc] = fa[y]; len[z] = len[x] + 1;
memcpy(t[z], t[y], sizeof(t[y]));
fa[y] = fa[lt] = z;
for (; x && t[x][C] == y; x = fa[x]) t[x][C] = z;
}
a[i] = lt;
}
for (int i = 2; i <= trc; ++i) Add(fa[i], i);
Dfs(1); Dfs(1, 1);
for (int i = 1; i <= trc; ++i)
if ((s[i] += (1ll * s[i-1] + len[b[i]] - len[fa[b[i]]] + M) % M) >= M) s[i] -= M;
for (int i = 1; i <= n; ++i) {
int x = a[i];
for (; tp[x] != 1; x = fa[tp[x]])
if ((sum += Ask(1, 1, trc, dfn[tp[x]], dfn[x])) >= M) sum -= M;
if (x != 1 && (sum += Ask(1, 1, trc, 2, dfn[x])) >= M) sum -= M;
printf("%d\n", (ans += sum) %= M);
}
return 0;
}
C simulate
题目大意 ： 一个只由0,1,2组成的序列，每次选大于 1 的数，给他减 2，两边的同时加 1，知道所有数都小于 2，问最后序列是什么样的
- 造几个小数据自己模拟一下就可以知道，依次考虑每个数的时候，如果让这个数减 1,那么会造成后面一个数加 1,然后前面最后一个0向右移动一位，然后就模拟这个过程，不过当然不能太暴力
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e7 + 5;
char c[N];
int n, a[N], stk[N], tp;
int main() {
scanf("%s", c + 1);
n = strlen(c + 1);
for (int i = 1; i <= n; ++i)
a[i] = c[i] - '0';
for (int i = 1; i <= n; ++i) {
while (a[i] >= 2) {
if (!tp) stk[++tp] = 0;
if (stk[tp] < i - 1) {
int x = min(i - 1 - stk[tp], a[i] - 1);
stk[tp] += x; a[i] -= x; a[i+1] += x;
}
else tp--, a[i] -= 2, a[i+1]++;
}
if (!a[i]) stk[++tp] = i;
a[i] = 1;
}
while (tp) a[stk[tp--]] = 0;
for (int i = 1; i <= n; ++i)
putchar(a[i] + '0');
return 0;
}