A 选择
题目大意 : 无向图,每次删边或询问两点间是否有两条边不相交的路径
-
没有强制在线就时光倒流一下,把删边转为加边
-
对于判断x到y是否有两条边不相交的路径的话,可以把图建一颗生成树,然后找树边和非树边两条路径就行
-
所以每出现一条非树边,就把两点间树边都标记一下,表示从这条边两个端点都在一个边双里,这样询问的时候就看路径中如果全被标记就存在题目要求的路径、
-
好不容易和正解思路一模一样,但之前没写过LCT维护值的,所以Update写错了,T_T
Code
Show Code
#include <cstdio>
#include <algorithm>
#define ls(x) t[x].c[0]
#define rs(x) t[x].c[1]
#define Get(x) (t[t[x].f].c[1] == x)
#define Nroot(x) (t[t[x].f].c[Get(x)] == x)
using namespace std;
const int N = 1e5 + 5, M = 1 << 18;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
bool ans[N];
int n, m, Q, stk[M], tp, cnt;
struct Side {
int x, y;
}a[N];
struct Ques {
char od; int x, y;
}q[N];
struct Hash {
int n, x, y;
}h[M];
int head[M], hac;
void Add(int x, int y) {
int u = (1ll * x * N + y) % M;
h[++hac] = (Hash) {head[u], x, y}; head[u] = hac;
}
bool Find(int x, int y) {
int u = (1ll * x * N + y) % M;
for (int i = head[u]; i; i = h[i].n)
if (h[i].x == x && h[i].y == y) return 1;
return 0;
}
struct Tree {
int f, c[2], s, sz; bool w, tr, t1;
}t[M];
void Pushup(int x) {
t[x].sz = t[ls(x)].sz + t[rs(x)].sz + 1;
t[x].s = t[ls(x)].s + t[rs(x)].s + t[x].w;
}
void Rotate(int x) {
int y = t[x].f, z = t[y].f, k = Get(x), B = t[x].c[k^1];
if (Nroot(y)) t[z].c[Get(y)] = x; t[x].f = z;
t[x].c[k^1] = y; t[y].f = x;
t[y].c[k] = B; t[B].f = y;
Pushup(y); Pushup(x);
}
void Update(int x) {
t[x].w = t[x].t1 = 1; t[x].s = t[x].sz;
}
void Pushdown(int x) {
if (t[x].tr) {
swap(ls(x), rs(x)); t[x].tr = 0;
t[ls(x)].tr ^= 1; t[rs(x)].tr ^= 1;
}
if (t[x].t1) t[x].t1 = 0, Update(ls(x)), Update(rs(x));
}
void Splay(int x) {
for (int p = x; p; p = Nroot(p) ? t[p].f : 0) stk[++tp] = p;
while (tp) Pushdown(stk[tp--]);
while (Nroot(x)) {
int y = t[x].f;
if (Nroot(y)) Get(x) == Get(y) ? Rotate(y) : Rotate(x);
Rotate(x);
}
}
void Access(int x) {
for (int y = 0; x; y = x, x = t[x].f)
Splay(x), t[x].c[1] = y, Pushup(x);
}
int Froot(int x) {
Access(x); Splay(x);
while (t[x].c[0]) x = t[x].c[0];
return Splay(x), x;
}
void Mroot(int x) {
Access(x); Splay(x); t[x].tr ^= 1;
}
void Split(int x, int y) {
Mroot(x); Access(y); Splay(y);
}
void Link(int x, int y) {
Mroot(x); t[x].f = y;
}
int main() {
cnt = n = read(); m = read(); Q = read();
for (int i = 1; i <= m; ++i)
a[i] = (Side) {read(), read()};
for (int i = 1; i <= Q; ++i) {
char od; scanf(" %c", &od);
int x = read(), y = read();
q[i] = (Ques) {od, x, y};
if (od == 'Z') Add(x, y), Add(y, x);
}
for (int i = 1; i <= m; ++i) {
int x = a[i].x, y = a[i].y;
if (Find(x, y)) continue;
if (Froot(x) == Froot(y)) Split(x, y), Update(y);
else ++cnt, Link(cnt, x), Link(cnt, y);
}
for (int i = Q; i >= 1; --i) {
char od = q[i].od; int x = q[i].x, y = q[i].y;
if (od == 'P') ans[i] = (Froot(x) == Froot(y) && (Split(x, y), t[y].sz == t[y].s));
else if (Froot(x) == Froot(y)) Split(x, y), Update(y);
else ++cnt, Link(cnt, x), Link(cnt, y);
}
for (int i = 1; i <= Q; ++i)
if (q[i].od == 'P') puts(ans[i] ? "Yes" : "No");
return 0;
}
B 三元组
题目大意 : 所有相邻的回文串最左端和最右端乘积的和
-
很容易想到枚举两个回文串的间隙(x,x+1)在哪,然后求出以x为结尾的回文串的左端点的和跟以x+1为开头的回文串右端点的和,然后乘起来,但是这两个东西不好求
-
i可以拆成x-len0+1, k可以拆成x+len1,要求出所有的i的和跟k的和,只要求出以一个点为结尾的字符串的个数和长度和就行,用回文自动机可以做到
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e6 + 5, M = 1e9 + 7;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
char c[N];
int n, fail[N], t[N][26], len[N], s[N], dep[N], sl[N], sr[N], cl[N], cr[N], trc;
int Find(int x, int y) {
while (c[y-len[x]-1] != c[y]) x = fail[x];
return x;
}
void Pam(int *S, int *C) {
memset(t, 0, sizeof(t[0]) * (trc + 1));
int x = trc = 1;
for (int i = 1; i <= n; ++i) {
int y = c[i] - 'a'; x = Find(x, i);
if (!t[x][y]) {
++trc;
len[trc] = len[x] + 2;
fail[trc] = t[Find(fail[x], i)][y];
s[trc] = (s[fail[trc]] + len[trc]) % M;
dep[trc] = dep[fail[trc]] + 1;
t[x][y] = trc;
}
x = t[x][y];
S[i] = s[x]; C[i] = dep[x];
}
}
signed main() {
int T = read();
fail[0] = 1; c[0] = len[1] = -1;
while (T--) {
scanf("%s", c + 1);
n = strlen(c + 1);
Pam(sr, cr);
reverse(c + 1, c + n + 1);
Pam(sl, cl);
reverse(sl + 1, sl + n + 1);
reverse(cl + 1, cl + n + 1);
int ans = 0;
for (int i = 1; i < n; ++i) {
int r = (1ll * cr[i] * (i + 1) % M - sr[i] + M) % M;
//cr[i] 是以 i 为结尾的回文串个数,sr[i] 是 以 i 为结尾的回文串长度和
int l = (1ll * cl[i+1] * i % M + sl[i+1]) % M;
//cl[i] 是以 i 为开头的回文串个数,sl[i] 是 以 i 为开头的回文串长度和
if ((ans += 1ll * r * l % M) >= M) ans -= M;
}
printf("%lld
", ans);
}
}
C 最有价值
题目大意 : 对于题中定义的价值,让选出一个子序列使得价值最大
-
最大权闭合图
-
对于 (w_{i,j}+w+{j,i}) 建一个点,对于每个位置建一个点,代价为 -a,对于每个字符建一个点,代价为 -b+a,
-
一类点连向二类点,二类点连向三类点
Code
Show Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar())
if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar())
x = x * 10 + c - '0';
return x * f;
}
struct Edge {
int n, t, d;
}e[N*4];
int h[N], edc;
void Add(int x, int y, int d) {
e[++edc] = (Edge) {h[x], y, d}; h[x] = edc;
e[++edc] = (Edge) {h[y], x, 0}; h[y] = edc;
}
char c[N];
int n, a[15], b[15], w[105][105], ans;
int s, t, cnt, dep[N], q[N], l, r, tmp[N];
bool Bfs() {
memcpy(h + 1, tmp + 1, cnt * 4);
memset(dep + 1, 0, cnt * 4);
dep[s] = 1; q[l=r=1] = s;
while (l <= r) {
int x = q[l++];
for (int i = h[x], y; i; i = e[i].n) {
if (!e[i].d || dep[y=e[i].t]) continue;
dep[y] = dep[x] + 1; q[++r] = y;
if (y == t) return 1;
}
}
return 0;
}
int Dinic(int x, int lim) {
if (x == t) return lim;
int sum = 0;
for (int i = h[x]; i && lim; i = e[i].n) {
int y = e[i].t; h[x] = i;
if (!e[i].d || dep[y] != dep[x] + 1) continue;
int f = Dinic(y, min(lim, e[i].d));
sum += f; lim -= f;
e[i].d -= f; e[i^1].d += f;
}
if (!sum) dep[x] = 0;
return sum;
}
int main() {
int T = read();
while (T--) {
memset(h + 1, 0, cnt * 4); edc = 1;
n = read(); ans = 0; cnt = n + 15;
s = ++cnt; t = ++cnt;
scanf("%s", c + 1);
for (int i = 0; i <= 9; ++i) {
a[i] = read(), b[i] = read();
Add(s, i + 1 + n, b[i] - a[i]);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
w[i][j] = read();
for (int i = 1; i <= n; ++i) {
Add(s, i, a[c[i]-'0']);
Add(c[i] - '0' + 1 + n, i, 1e9);
for (int j = i + 1; j <= n; ++j) {
cnt++; ans += w[i][j] + w[j][i];
Add(i, cnt, 1e9); Add(j, cnt, 1e9);
Add(cnt, t, w[i][j] + w[j][i]);
}
}
memcpy(tmp + 1, h + 1, cnt * 4);
while (Bfs()) ans -= Dinic(s, 1e9);
printf("%d
", ans);
}
return 0;
}