20191012测试总结

原地爆炸。。。

T1:WOJ4749

点双连通分量,挺裸的
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, x, y, sum = 1, cnt, col, top, ttop, ans;
int s[1000005], dfn[1000005], low[1000005];
int head[1000005], use[1000005], co[1000005];
int num[1000005], tot[1000005], ss[1000005];
struct node
{
int v;
int next;
} a[2000005];
int read()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
while (isdigit(c))
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
void ins(int u, int v)
{
++sum;
a[sum].v = v;
a[sum].next = head[u];
head[u] = sum;
return;
}
void tarjan(int k)
{
++cnt;
dfn[k] = cnt;
low[k] = cnt;
ss[++ttop] = k;
int d = head[k];
while (d)
{
if (!use[d >> 1])
{
use[d >> 1] = 1;
s[++top] = (d >> 1);
if (!dfn[a[d].v])
{
tarjan(a[d].v);
low[k] = min(low[k], low[a[d].v]);
if (low[a[d].v] >= dfn[k])
{
++col;
while (s[top] != (d >> 1))
{
co[s[top]] = col;
--top;
++num[col];
}
co[s[top]] = col;
--top;
++num[col];
while (ss[ttop] != a[d].v)
{
--ttop;
++tot[col];
}
--ttop;
tot[col] += 2;
}
}
else
low[k] = min(low[k], dfn[a[d].v]);
}
d = a[d].next;
}
return;
}
int main()
{
n = read();
m = read();
for (int i = 1; i <= m; ++i)
{
x = read();
y = read();
ins(x, y);
ins(y, x);
}
tarjan(1);
for (int i = 1; i <= m; ++i)
if (co[i] && tot[co[i]] == num[co[i]])
ans ^= i;
printf("%d", ans);
return 0;
}

T2:WOJ4750

很套路的AC自动机DP,注意需要用矩阵快速幂优化
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m, sum = 1, a[105], bo[205], tr[205][26], nxt[205];
char s[205];
long long n, ans;
void insert(int k)
{
int root = 1, len = strlen(s);
for (int i = 0; i < len; ++i)
{
int k = s[i] - 'a';
if (!tr[root][k])
tr[root][k] = ++sum;
root = tr[root][k];
}
bo[root] += a[k];
return;
}
struct matrix
{
long long a[205][205];
matrix()
{
memset(a, 0, sizeof(a));
}
matrix(long long x)
{
for (int i = 1; i <= sum; ++i)
for (int j = 1; j <= sum; ++j)
a[i][j] = x;
}
matrix operator*(const matrix &bb) const
{
matrix cc(-1);
for (int i = 1; i <= sum; ++i)
for (int j = 1; j <= sum; ++j)
for (int k = 1; k <= sum; ++k)
if (a[i][k] != -1 && bb.a[k][j] != -1)
cc.a[i][j] = max(cc.a[i][j], a[i][k] + bb.a[k][j]);
return cc;
}
};
void build()
{
for (int i = 0; i < 26; ++i)
tr[0][i] = 1;
int h = 0, t = 1, q[205];
q[1] = 1;
while (h < t)
{
++h;
int k = q[h];
for (int i = 0; i < 26; ++i)
if (tr[k][i])
{
nxt[tr[k][i]] = tr[nxt[k]][i];
bo[tr[k][i]] += bo[tr[nxt[k]][i]];
q[++t] = tr[k][i];
}
else
tr[k][i] = tr[nxt[k]][i];
}
return;
}
matrix ksm(matrix aa, long long k)
{
matrix x(-1);
x.a[1][1] = 0;
while (k)
{
if (k & 1)
x = x * aa;
aa = aa * aa;
k >>= 1;
}
return x;
}
int main()
{
scanf("%lld%d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i)
{
scanf("%s", s);
insert(i);
}
build();
matrix aa(-1);
for (int i = 1; i <= sum; ++i)
for (int j = 0; j < 26; ++j)
aa.a[i][tr[i][j]] = bo[tr[i][j]];
aa = ksm(aa, n);
for (int i = 1; i <= sum; ++i)
ans = max(ans, aa.a[1][i]);
printf("%lld", ans);
return 0;
}

T3:WOJ4751

显然的差分约束

不过由于边数太多,需要线段树优化建图。。。

由于这道题鸽的有点久,改的时候已经记不大清一些具体内容了,又半天调不对,因此直接代码是std。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 400010, E = 2000000;
int n, s, m, i, x, y, z, tot, l[N << 1], r[N << 1], pos[N];
int a[M], d[M], g[M], v[E], nxt[E], ed;
char w[E];
int h, t, q[M], f[M];
inline void read(int &a)
{
char c;
while (!(((c = getchar()) >= '0') && (c <= '9')))
;
a = c - '0';
while (((c = getchar()) >= '0') && (c <= '9'))
(a *= 10) += c - '0';
}
inline void add(int x, int y, char z)
{
d[y]++;
v[++ed] = y;
w[ed] = z;
nxt[ed] = g[x];
g[x] = ed;
}
inline int build(int a, int b)
{
int x = ++tot;
if (a == b)
return pos[a] = x;
int mid = (a + b) >> 1;
add(l[x] = build(a, mid), x, 0);
add(r[x] = build(mid + 1, b), x, 0);
return x;
}
void ask(int x, int a, int b, int c, int d)
{
if (c > d)
return;
if (c <= a && b <= d)
{
add(x, tot, 1);
return;
}
int mid = (a + b) >> 1;
if (c <= mid)
ask(l[x], a, mid, c, d);
if (d > mid)
ask(r[x], mid + 1, b, c, d);
}
int main()
{
read(n), read(s), read(m);
build(1, n);
while (s--)
read(x), read(y), a[pos[x]] = y;
while (m--)
{
read(x), read(y), read(z);
tot++;
for (i = 1; i <= z; i++)
read(q[i]), add(tot, pos[q[i]], 0);
ask(1, 1, n, x, q[1] - 1);
ask(1, 1, n, q[z] + 1, y);
for (i = 1; i < z; i++)
ask(1, 1, n, q[i] + 1, q[i + 1] - 1);
}
for (h = i = 1; i <= tot; i++)
if (!d[i])
f[q[++t] = i] = 1;
while (h <= t)
{
x = q[h++];
if (f[x] > 1000000000)
return puts("Impossible"), 0;
if (a[x])
{
if (a[x] < f[x])
return puts("Impossible"), 0;
if (a[x] > f[x])
f[x] = a[x];
}
for (i = g[x]; i; i = nxt[i])
{
if (f[v[i]] < f[x] + w[i])
f[v[i]] = f[x] + w[i];
if (!(--d[v[i]]))
q[++t] = v[i];
}
}
if (t < tot)
return puts("Impossible"), 0;
for (puts("Possible"), i = 1; i <= n; i++)
printf("%d ", f[pos[i]]);
return 0;
}

评论

此博客中的热门博文

min-max反演