20191105测试总结

什么毒瘤题啊。。。爆零了

T1:WOJ4793

显然如果打了御牌就必须要打完,然后就可以贪心了:若打了御牌,那么兵牌就只用打小于0的,否则直接打;若没有打御牌,那么就拿大的兵牌打对方小的兵牌,知道不能打为止。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int n, m, mm, ans1, ans2;
struct node
{
int val;
int num;
} a[1000005], b[1000005], c[1000005], aa[1000005], bb[1000005], cc[1000005];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
bool cmp(node aa, node bb)
{
return aa.val < bb.val;
}
signed main()
{
n = read(), m = read(), mm = read();
for (int i = 1; i <= n; ++i)
{
a[i].val = read();
a[i].num = read();
}
for (int i = 1; i <= m; ++i)
{
b[i].val = read();
b[i].num = read();
}
for (int i = 1; i <= mm; ++i)
{
c[i].val = read();
c[i].num = read();
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + m + 1, cmp);
sort(c + 1, c + mm + 1, cmp);
for (int i = 1; i <= n; ++i)
aa[i] = a[i];
for (int i = 1; i <= m; ++i)
bb[i] = b[i];
for (int i = 1; i <= mm; ++i)
cc[i] = c[i];
int j = n;
for (int i = 1; i <= mm; ++i)
{
while (j && a[j].val >= c[i].val && a[j].num < c[i].num)
{
ans1 += a[j].num * (a[j].val - c[i].val);
c[i].num -= a[j].num;
a[j].num = 0;
--j;
}
if (!j || a[j].val < c[i].val)
break;
ans1 += c[i].num * (a[j].val - c[i].val);
a[j].num -= c[i].num;
c[i].num = 0;
}
swap(a, aa);
swap(b, bb);
swap(c, cc);
int pan = 0;
j = 1;
for (int i = 1; i <= m; ++i)
{
while (j < n && a[j].val < b[i].val)
++j;
while (j < n && a[j].val >= b[i].val && a[j].num < b[i].num)
{
b[i].num -= a[j].num;
a[j].num = 0;
++j;
}
if (a[j].num < b[i].num)
{
pan = 1;
break;
}
a[j].num -= b[i].num;
b[i].num = 0;
if (j == n && !a[j].num)
{
pan = 1;
break;
}
}
j = n;
for (int i = 1; i <= mm; ++i)
{
if (c[i].val >= 0)
break;
while (j && a[j].val >= c[i].val && a[j].num < c[i].num)
{
ans2 += a[j].num * (a[j].val - c[i].val);
c[i].num -= a[j].num;
a[j].num = 0;
--j;
}
if (!j || a[j].val < c[i].val)
break;
ans2 += c[i].num * (a[j].val - c[i].val);
a[j].num -= c[i].num;
c[i].num = 0;
}
if (!pan)
for (int i = 1; i <= n; ++i)
if (a[i].val > 0)
ans2 += a[i].val * a[i].num;
printf("%lld", max(ans1, ans2));
return 0;
}

T2:WOJ4794

按照最小生成树的思路乱搞,细节参考题解。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define mod 1000000007
#define int long long
using namespace std;
int t, n, m, xx, tot, sum, cnt, les, equ;
int fa[100005][25], maxn[100005][25];
int head[100005], nxt[200005], to[200005], w[200005], mo[100005], dep[100005];
int read()
{
int x = 0, f = 1;
char ch = 0;
while (!isdigit(ch))
{
ch = getchar();
if (ch == '-')
f = -1;
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int find(int x)
{
if (x == mo[x])
return x;
return mo[x] = find(mo[x]);
}
void add(int a, int b, int c)
{
nxt[++tot] = head[a];
head[a] = tot;
to[tot] = b;
w[tot] = c;
nxt[++tot] = head[b];
head[b] = tot;
to[tot] = a;
w[tot] = c;
}
void dfs(int u, int faa)
{
dep[u] = dep[faa] + 1;
fa[u][0] = faa;
for (int i = 1; i <= 20; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for (int i = 1; i <= 20; ++i)
maxn[u][i] = max(maxn[u][i - 1], maxn[fa[u][i - 1]][i - 1]);
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (v == faa)
continue;
maxn[v][0] = w[i];
dfs(v, u);
}
}
int query(int a, int b)
{
if (dep[a] < dep[b])
swap(a, b);
int tmp = 0;
for (int i = 20; i >= 0; --i)
{
if (dep[fa[a][i]] >= dep[b])
{
tmp = max(tmp, maxn[a][i]);
a = fa[a][i];
}
}
if (a == b)
return tmp;
for (int i = 20; i >= 0; --i)
{
if (fa[a][i] != fa[b][i])
{
tmp = max(tmp, max(maxn[a][i], maxn[b][i]));
a = fa[a][i], b = fa[b][i];
}
}
return max(tmp, max(maxn[a][0], maxn[b][0]));
}
struct node
{
int u, v, w, lazy;
void init()
{
lazy = 0;
}
} e[200005];
bool cmp(node a, node b)
{
return a.w < b.w;
}
int ksm(int a, int k)
{
int b = 1;
while (k)
{
if (k & 1)
b = b * a % mod;
a = a * a % mod;
k >>= 1;
}
return b;
}
int solve()
{
sum = 0;
cnt = 0;
les = 0;
equ = 0;
for (int i = 1; i <= m; ++i)
{
int x = find(e[i].u), y = find(e[i].v);
if (x != y)
{
++cnt;
sum += e[i].w;
mo[x] = y;
e[i].lazy = 1;
add(e[i].u, e[i].v, e[i].w);
if (cnt == n - 1)
break;
}
}
if (sum > xx)
return 0;
dfs(1, 0);
int now = sum;
for (int i = 1; i <= m; ++i)
{
if (!e[i].lazy)
{
now = sum + e[i].w - query(e[i].u, e[i].v);
if (now == xx)
equ++;
if (now < xx)
les++;
}
}
int ans = 0;
if (sum == xx)
ans = (ans + (ksm(2, m) - 2 * ksm(2, m - n + 1 - equ) % mod + mod) % mod) % mod;
else
ans = (ans + 2 * (ksm(2, m - n + 1 - les) - ksm(2, m - n + 1 - les - equ) + mod) % mod) % mod;
return ans;
}
signed main()
{
t = read();
for (int tt = 1; tt <= t; ++tt)
{
tot = 0;
memset(head, 0, sizeof(head));
n = read();
m = read();
xx = read();
for (int i = 1; i <= n; ++i)
mo[i] = i;
for (int i = 1; i <= m; ++i)
{
e[i].lazy = 0;
e[i].u = read();
e[i].v = read();
e[i].w = read();
}
sort(e + 1, e + m + 1, cmp);
printf("%lld\n", solve());
}
return 0;
}

T3:WOJ4795

非常毒瘤的数位DP,借助KMP,然后按位确定S的每一位的值,当然这样的复杂度暂时是不正确的。

考虑优化:将每个点的的重儿子提取出来,然后进行一次倍增,思路类似于20191026测试总结中的T3。

太毒瘤了。。。代码直接改了一下std。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
long long read()
{
long long x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
namespace io
{
const int MaxBuff = 1 << 15;
const int Output = 1 << 23;
char B[MaxBuff], *S = B, *T = B;
#define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
char Out[Output], *it = Out;
void flush()
{
fwrite(Out, 1, it - Out, stdout);
it = Out;
}
} // namespace io
template <class Type>
void Print(register Type x, register char ch = '\n')
{
using namespace io;
if (!x)
*it++ = '0';
else
{
if (x < 0)
*it++ = '-', x = -x;
static int s[100];
register int t = 0;
while (x)
s[++t] = x % 10, x /= 10;
while (t)
*it++ = '0' + s[t--];
}
*it++ = ch;
}
const int N = 5e4 + 5;
const int M = 21;
const int L = 17;
const int mod = 1e9 + 7;
const long long inf = (long long)1e18 + 1;
int T, n, m, q;
bool p[N][10];
int fail[M], val[L][N][M], trans[M][10], pw[L] = {10};
long long f[N][M], rkl[L][N][M], rkr[L][N][M];
char str[M], s[N], ed[L][N][M];
long long fix(long long x)
{
return x < inf ? x : inf;
}
void kmp()
{
fail[0] = fail[1] = 0;
for (int i = 2; i <= m; ++i)
{
int now = fail[i - 1];
while (now && str[now + 1] != str[i])
now = fail[now];
if (str[now + 1] == str[i])
fail[i] = now + 1;
else
fail[i] = 0;
}
}
void init()
{
for (int i = 0; i < m; ++i)
{
for (int j = 0; j <= 9; ++j)
{
int now = i;
while (now && str[now + 1] != j + '0')
now = fail[now];
if (str[now + 1] != j + '0')
trans[i][j] = 0;
else
trans[i][j] = now + 1;
}
}
for (int j = 0; j <= 9; ++j)
trans[m][j] = m;
}
void input()
{
n = read(), q = read();
scanf("%s%s", str + 1, s + 1);
m = strlen(str + 1);
for (int i = 1; i <= n; ++i)
{
if (s[i] == '?')
memset(p[i], 1, sizeof(p[i]));
else
memset(p[i], 0, sizeof(p[i])), p[i][s[i] - '0'] = 1;
}
kmp(), init();
}
int query(long long k)
{
if (k > f[1][0])
return -1;
int x = 1, y = 0, res = 0;
while (x <= n)
{
for (int i = L - 1; ~i; --i)
{
if (x + (1 << i) <= n + 1 && rkl[i][x][y] < k && k <= rkr[i][x][y])
{
res = ((long long)res * pw[i] + val[i][x][y]) % mod;
k -= rkl[i][x][y], y = ed[i][x][y], x += (1 << i);
}
}
if (x > n)
break;
for (int i = 0; i <= 9; ++i)
{
if (k > f[x + 1][trans[y][i]])
k -= f[x + 1][trans[y][i]];
else
{
res = (10LL * res + i) % mod;
++x, y = trans[y][i];
break;
}
}
}
return res;
}
int main()
{
for (int i = 1; i < L; ++i)
pw[i] = (long long)pw[i - 1] * pw[i - 1] % mod;
T = read();
while (T--)
{
input();
for (int i = 0; i <= m; ++i)
f[n + 1][i] = (i == m);
for (int i = n; i >= 0; --i)
{
for (int j = 0; j <= m; ++j)
{
f[i][j] = 0;
long long mx = -1;
int nxt = -1;
for (int k = 0; k <= 9; ++k)
{
if (p[i][k])
{
f[i][j] = fix(f[i][j] + f[i + 1][trans[j][k]]);
if (f[i + 1][trans[j][k]] > mx)
nxt = k, mx = f[i + 1][trans[j][k]];
}
}
ed[0][i][j] = trans[j][nxt];
val[0][i][j] = nxt, rkl[0][i][j] = 0;
for (int k = 0; k < nxt; ++k)
if (p[i][k])
rkl[0][i][j] = fix(rkl[0][i][j] + f[i + 1][trans[j][k]]);
rkr[0][i][j] = fix(rkl[0][i][j] + f[i + 1][trans[j][nxt]]);
}
}
for (int k = 1; k < L; ++k)
{
int len = (1 << (k - 1));
for (int i = 1; i + (1 << k) <= n + 1; ++i)
{
for (int j = 0; j <= m; ++j)
{
int x = ed[k - 1][i][j];
ed[k][i][j] = ed[k - 1][i + len][x];
val[k][i][j] = (1LL * val[k - 1][i][j] * pw[k - 1] + val[k - 1][i + len][x]) % mod;
rkl[k][i][j] = fix(rkl[k - 1][i][j] + rkl[k - 1][i + len][x]);
rkr[k][i][j] = fix(rkl[k - 1][i][j] + rkr[k - 1][i + len][x]);
}
}
}
while (q--)
{
long long k = read();
Print(query(k));
}
io::flush();
}
return 0;
}

评论

此博客中的热门博文