前一个小时看这几道题感觉要爆零

A. 仓鼠的石子游戏

分析一下发现a[i]>1a[i]>1a[i]>1时后先手必输，a[i]=1a[i]=1a[i]=1时先手必赢

然后直接看1的个数奇偶性就行了

CODE

#include <bits/stdc++.h>

using namespace std;

int main () {

    int T, n, a; scanf("%d", &T);

    while(T--) {

        scanf("%d", &n);

        int ans = 0;

        for(int i = 1; i <= n; ++i)

            scanf("%d", &a), ans ^= (a == 1);

        puts(ans ? "rabbit" : "hamster");

    }

}

B.乃爱与城市拥挤程度

f[i][j],g[i][j]f[i][j],g[i][j]f[i][j],g[i][j]分别表示iii点下方走jjj步的答案。

答案就是f[i][k],g[i][k]f[i][k],g[i][k]f[i][k],g[i][k]

傻逼树形DP

O(nklog⁡)O(nk\log)O(nklog)，有log⁡\loglog是因为求逆元，实际上可以把要求逆元的数取出来O(n)O(n)O(n)求一遍就可以做到O(nk)O(nk)O(nk)，不过没必要。

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

const int MAXK = 12;

const int mod = 1e9 + 7;

int n, k, f[MAXN][MAXK], g[MAXN][MAXK];

int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;

inline void link(int u, int v) {

    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

    to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

inline int qpow(int a, int b) {

    int re = 1;

    while(b) {

        if(b&1) re = 1ll * re * a % mod;

        a = 1ll * a * a % mod; b >>= 1;

    }

    return re;

}

void dfs1(int u, int ff) {

    for(int j = 0; j <= k; ++j) f[u][j] = 1, g[u][j] = 1;

    for(int i = fir[u], v; i; i = nxt[i])

        if((v=to[i]) != ff) {

            dfs1(v, u);

            for(int j = 1; j <= k; ++j) {

                f[u][j] += f[v][j-1];

                g[u][j] = 1ll*g[u][j]*g[v][j-1]%mod;

            }

        }

    for(int j = 0; j <= k; ++j)

        g[u][j] = 1ll * g[u][j] * f[u][j] % mod;

}

int F[MAXN], G[MAXN];

void dfs2(int u, int ff) {

    F[u] = f[u][k], G[u] = g[u][k];

    for(int i = fir[u], v; i; i = nxt[i])

        if((v=to[i]) != ff) {

            for(int j = k; j >= 1; --j) {

                g[v][j] = 1ll * g[v][j] * qpow(f[v][j], mod-2) % mod * (f[v][j]+f[u][j-1]-(j>=2?f[v][j-2]:0)) % mod * g[u][j-1] % mod * qpow(f[u][j-1], mod-2) % mod * (f[u][j-1] - (j>=2?f[v][j-2]:0)) % mod * (j>=2?qpow(g[v][j-2], mod-2):1) % mod;

                f[v][j] += f[u][j-1]-(j>=2?f[v][j-2]:0);

            }

            dfs2(v, u);

        }

}

int main () {

    scanf("%d%d", &n, &k);

    for(int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), link(u, v);

    dfs1(1, 0), dfs2(1, 0);

    for(int i = 1; i <= n; ++i) printf("%d%c", F[i], " \n"[i==n]);

    for(int i = 1; i <= n; ++i) printf("%d%c", G[i], " \n"[i==n]);

}

C.小w的魔术扑克

把一张牌的两面的值连边。

最后发现一个连通块，如果里面有重边或者环，这个连通块所有的值肯定都能凑出来。

只需要考虑那些树形态的连通块。

对于一棵树，询问区间是[l,r][l,r][l,r]，如果整棵树值域都在[l,r][l,r][l,r]内，一定不能满足，否则就可以。所以求出每棵树的值域[mn,mx][mn,mx][mn,mx]，然后包含这个区间的[l,r][l,r][l,r]答案都是NoNoNo。区间排序后O(n)O(n)O(n)直接做。

总时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)

upd:upd:upd:也可以在mxmxmx处附上mnmnmn的值，然后求一个前缀最大值，然后对于一个询问，如果1→r1\to r1→r的前缀最大值>=l>=l>=l就一定包含了一个区间。这样做是O(n)O(n)O(n)的。还更好写。。

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;

int n, m, k, Q;

int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt = 1;

inline void link(int u, int v) {

    to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt;

    to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt;

}

int mn, mx;

bool vis[MAXN], inq[MAXN], flg;

void dfs(int u, int ff) {

    vis[u] = inq[u] = 1;

    mn = min(mn, u);

    mx = max(mx, u);

    for(int i = fir[u], v; i; i = nxt[i]) if((i^1) != ff){

        if(!vis[v=to[i]]) dfs(v, i);

        else if(inq[v]) flg = 1;

    }

    inq[u] = 0;

}

struct node {

    int l, r, id;

    inline bool operator <(const node &o)const {

        return r < o.r;

    }

}a[MAXN], q[MAXN];

bool ans[MAXN];

int main () {

    scanf("%d%d", &n, &k);

    for(int i = 1, u, v; i <= k; ++i) scanf("%d%d", &u, &v), link(u, v);

    for(int i = 1; i <= n; ++i)

        if(!vis[i]) {

            flg = 0; mn = i, mx = i;

            dfs(i, 0);

            if(!flg) a[++m] = (node){ mn, mx };

        }

    sort(a + 1, a + m + 1);

    scanf("%d", &Q);

    for(int i = 1; i <= Q; ++i)

        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;

    sort(q + 1, q + Q + 1);

    int pos = 0;

    for(int i = 1, j = 1; i <= Q; ++i) {

        while(j <= m && a[j].r <= q[i].r) pos = max(pos, a[j++].l);

        ans[q[i].id] = q[i].l <= pos;

    }

    for(int i = 1; i <= Q; ++i) puts(ans[i] ? "No" : "Yes");

}

然后莫名其妙就AK了。

巴特西

20191029 牛客CSP-S提高组赛前集训营1

A. 仓鼠的石子游戏

CODE

B.乃爱与城市拥挤程度

CODE

C.小w的魔术扑克

CODE

最新文章

热门文章