@Falsyta 2015-08-11T01:30:05.000000Z 字数 5384 阅读 1570

mxh带窝打多校之Contest 2

OI mxh带窝飞

约定

题意

1005 Eastest Magical Day Seep Group's Summer

给出无向图 $G=\{V,E\}$ ，求选出一个边的大小为 $|V|$ 的子集 $E'$ 使得 $G'=\{V,E'\}$ 仍然连通。

1008 He is Flying

给出长度为 $N$ 的非负整数序列 $A$ ，对于 $0\leq x\leq \sum_{i=1}^NA_i$ ，求

\sum i = 1 N \sum j = i N [\sum k = i j A k = x]

$\sum_{i=1}^{N}\sum_{j=i}^{N}[\sum_{k=i}^jA_k=x]$

1010 JRY is Fighting

有一个初始HP为 $M$ 的角色在一个 $N$ 轮的游戏中，在第 $i$ 轮角色HP会受到攻击减 $h_i$ （可以为负），在受到攻击后魔瓶中会多k点HP的储备，在第 $i$ 轮末角色可以决定是否使用魔瓶，使用后会取出魔瓶中的HP储备全部用来恢复角色的HP，角色的HP无上限。令 $r$ 为使用魔瓶的轮的编号组成的单调递增序列，要求最大化 $\min\{r_i-r_{i-1}|1<i\leq |r|\}$ ，在此基础上令 $r$ 字典序最小。

题解

1005 Eastest Magical Day Seep Group's Summer

考虑原问题即为基环树子图的计数。

考虑枚举环上的点的集合 $S$ 并将其缩成一个点，对于剩下的图做生成树计数，再乘上 $S$ 连成环的方案数即可。

时间复杂度 $O(2^{|V|}|V|^3)$ 。

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define Mimo(x) if (x >= P) x -= P;
# define RST(a) memset (a, 0, sizeof (a))
const int NR = 18, P = 998244353;
int n, m, deg[NR], inv[40], a[NR][NR], h[NR][1 << 16], ps[1 << 16], bc[1 << 16];
bool g[NR][NR];
inline int Pow (int a, int z) {int s = 1; do {if (z & 1) s = 1ll * s * a % P; a = 1ll * a * a % P;} while (z >>= 1); return s;}
inline int Inv (int x)
{
    if (x <= 30) return inv[x];
    if (x == P - 1) return inv[0];
    return Pow (x, P - 2);
}
int Gauss (int n)
{
    int s = 1;
    REP (i, n)
    {
        if (!a[i][i]) FOR (j, i + 1, n) if (a[j][i]) {if (s) s = P - s; REP (k, n) swap (a[i][k], a[j][k]); break;}
        if (!a[i][i]) return 0;
        FOR (j, i + 1, n)
        {
            if (!a[j][i]) continue;
            int t = 1ll * a[j][i] * Inv (a[i][i]) % P;
            REP (k, n) {a[j][k] = a[j][k] - 1ll * t * a[i][k] % P + P; Mimo (a[j][k]);}
        }
        s = 1ll * s * a[i][i] % P;
    }
    return s;
}
# define in(a, b) ((b) >> (a) & 1)
int main ()
{
    inv[0] = Pow (P - 1, P - 2);
    REP (i, 30) inv[i] = Pow (i, P - 2);
    while (scanf ("%d%d", &n, &m) != EOF)
    {
        int t1, t2;
        const int M = 1 << n;
        REP_0 (i, n) {deg[i] = 0; REP_0 (j, n) g[i][j] = 0; REP_0 (s, M) h[i][s] = 0;}
        REP (i, m) scanf ("%d%d", &t1, &t2), t1 --, t2 --, g[t1][t2] = g[t2][t1] = 1, deg[t1] ++, deg[t2] ++;
        REP_0 (i, n) 
        {
            ps[1 << i] = i, h[i][1 << i] = 1;
            REP (s, M - 1)
            {
                if ((s == 1 << i) || !in (i, s) || ((s & - s) != (1 << i))) continue;
                FOR (j, i + 1, n - 1) if (in (j, s)) {int sa = (s ^ (1 << j)); FOR (k, i, n - 1) if (in (k, sa) && g[k][j]) {h[j][s] += h[k][sa]; Mimo (h[j][s]);}}
            }
        }
        int ans = 0;
        REP (s, M - 1)
        {
            int pt = s & -s;
            bc[s] = bc[s ^ pt] + 1;
            if (bc[s] < 3) continue;
            pt = ps[pt]; int ts = 0;
            REP_0 (v, n) if (in (v, s) && g[v][pt]) {ts += h[v][s]; Mimo (ts);}
            ts = 1ll * ts * inv[2] % P;
            int c0 = 0;
            REP_0 (i, n)
            {
                if (in (i, s)) continue;
                c0 ++; int c1 = 0;
                REP_0 (j, n) if (!in (j, s)) a[c0][++ c1] = (i == j ? deg[i] : (g[i][j] ? P - 1 : 0));
            }
            int tmp;
            ans = (ans + 1ll * (tmp = Gauss (n - bc[s])) * ts) % P;
        }
        printf ("%d\n", ans);
    }
    return 0;
}

1008 He is Flying

考虑用前缀和转成卷积的形式 $ans[sum[j]-sum[i]]=j-i$ 即可，对于 $j$ 和 $-i$ 做两次卷积算贡献即可。
可以用long double或CRT。

# include <cstdio>
# include <algorithm>
# include <cmath>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
typedef long long ll;
typedef long double dd;
const dd PI = acosl (-1.0);
const int NR = 101000;
using namespace std;
struct cp
{
    dd r, i;
    cp () {r = i = 0;}
    cp (dd _r, dd _i) {r = _r, i = _i; }
    cp operator + (cp b) {return cp (r + b.r, i + b.i); }
    cp operator - (cp b) {return cp (r - b.r, i - b.i); }
    cp operator * (cp b) {return cp (r * b.r - i * b.i, r * b.i + i * b.r); }
} a[NR << 1], b[NR << 1];
ll ans[NR << 1], su[NR << 1];
int n, s[NR], q0;
void FFT (cp *a, int n, int ty = 1)
{
    for (int i = n >> 1, j = 1, k; j < n - 1; j ++)
    {
        if (i > j) swap (a[i], a[j]);
        for (k = n >> 1; k <= i; k >>= 1) i ^= k;
        i ^= k;
    }
    for (int m = 2; m <= n; m <<= 1)
    {
        int h = m >> 1;
        cp wm (cos (PI / h), sin (PI / h) * ty);
        for (int i = 0; i < n; i += m)
        {
            cp w (1, 0);
            for (int j = i; j < i + h; j ++)
            {
                cp u = a[j], v = w * a[j + h];
                a[j] = u + v, a[j + h] = u - v, w = w * wm;
            }
        }
    }
    if (ty == -1) REP_0 (i, n) a[i].r /= n;
}
int main ()
{
    REP (i, 100000) su[i] = su[i - 1] + 1ll * i * (i + 1) / 2;
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d", &n); int N = 1, lz = 0, ta;
        ans[0] = 0;
        REP (i, n) 
        {
            scanf ("%d", &ta), s[i] = s[i - 1] + ta;
            if (!ta) lz ++;
            else ans[0] += su[lz], lz = 0;
        }
        ans[0] += su[lz];
        for (; N <= 2 * s[n] + 20; N <<= 1) ;
        REP_0 (i, N) a[i] = b[i] = cp (0, 0);
        REP (i, n) a[s[i]].r += i;
        REP (i, n) b[s[n] - s[i - 1]].r += 1;
        FFT (a, N), FFT (b, N); REP_0 (i, N) a[i] = a[i] * b[i]; FFT (a, N, -1);
        REP (i, s[n]) ans[i] = (ll) (a[s[n] + i].r + 0.1);
        REP_0 (i, N) a[i] = b[i] = cp (0, 0);
        REP (i, n) a[s[i]].r += 1;
        REP (i, n) b[s[n] - s[i - 1]].r += i - 1;
        FFT (a, N), FFT (b, N); REP_0 (i, N) a[i] = a[i] * b[i]; FFT (a, N, -1);
        REP (i, s[n]) ans[i] -= (ll) (a[s[n] + i].r + 0.1);
        REP_0N (i, s[n]) printf ("%I64d\n", ans[i]);
    }
    return 0;
}

1010 JRY is Fighting

首先预处理出在第 $i$ 轮使用魔瓶后最多能撑到轮的编号 $r_i$ 。

考虑令

F i = max {min (F j, i - j) | 1 \leq j < i, i < r j}

$F_i=\max\{\min (F_j, i-j)|1\leq j<i, i<r_j\}$

用两个堆分别维护 $\max\{F_j\}$ 与 $\max\{i-j\}$ 即可。
算出 $F_i$ 后可以知道哪些 $i$ 可以在最终的 $r_i$ 中，从头扫一遍即可得到最小字典序方案。

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_D(i, n) for (int i = n; i >= 1; i --)
priority_queue <int> Q0;
priority_queue <pair <int, int> > Q1;
const int NR = 501000, inf = 1 << 30;
int n, m, K, a[NR], s[NR], c[NR], rib[NR], f[NR], li[NR], lim[NR];
bool g[NR];
int main ()
{
    while (scanf ("%d%d%d", &n, &m, &K) != EOF)
    {
        bool surv = 1;
        REP (i, n) 
        {
            scanf ("%d", &a[i]), s[i] = s[i - 1] + a[i], c[i] = 0, lim[i] = max (lim[i - 1], s[i]);
            if (s[i] >= m + (i - 1) * K) surv = 0;
        }
        if (!surv) {puts ("Poor Hero!"); continue;}
        s[n + 1] = s[n], c[n + 1] = 0;
        int ri = 0;
        REP (i, n)
        {
            while (ri < n && m + i * K > s[ri + 1]) ri ++;
            rib[i] = ri;
        }
        int ans = -1;
        REP (i, n)
        {
            f[i] = (m > lim[i] ? inf : 0);
            while (!Q0.empty ())
            {
                int j = -Q0.top ();
                if (i > rib[j]) {Q0.pop (); continue;}
                if (i - j > f[j]) {Q0.pop (); Q1.push (make_pair (f[j], j)); continue;}
                f[i] = max (f[i], i - j); break;
            }
            while (!Q1.empty ())
            {
                int j = Q1.top ().second;
                if (i > rib[j]) {Q1.pop (); continue;}
                f[i] = max (f[i], f[j]); break;
            }
            if (i * K + m > lim[n]) ans = max (ans, f[i]);
            Q0.push (-i);
        }
        if (ans == inf) {puts ("Poor JRY!"); continue;}
        REP_D (i, n)
        {
            if (i * K + m > lim[n]) {g[i] = 1, c[i] = c[i + 1] + 1; continue;}
            g[i] = 0, c[i] = c[i + 1];
            int l = i + ans, r = rib[i];
            if (l > r || c[r] == c[l + 1]) continue;
            g[i] = 1, c[i] ++;
        }
        int len = 0;
        REP (i, n) 
            if (g[i]) 
            {
                li[++ len] = i;
                if (i * K + m > lim[n]) break;
                i += ans - 1;
            }
        printf ("%d\n%d\n", ans, len);
        REP (i, len) printf ("%d ", li[i]); puts ("");
        while (!Q0.empty ()) Q0.pop ();
        while (!Q1.empty ()) Q1.pop ();
    }
    return 0;
}

mxh带窝打多校之Contest 2

约定

题意

1005 Eastest Magical Day Seep Group's Summer

1008 He is Flying

1010 JRY is Fighting

题解

1005 Eastest Magical Day Seep Group's Summer

1008 He is Flying

1010 JRY is Fighting

内容目录