Codeforces Round #652 (Div. 2)lyh's blog

D. TediousLee

容易发现这个树是有规律的，可以直接上$DP$。
定义$dp(x,y)$表示第$x$轮，根是否涂色（用$y=0$和$y=1$区分）情况下，能够找到的最多的$claw$数量。这样有状态转移方程：

$dp(x,0)=2\max(dp(x-2,0),dp(x-2,1))+\max(dp(x-1,0),dp(x-1,1))\\ dp(x,1)=2dp(x-2,0)+dp(x-1,0)+1$

        答案就是$4\max(dp(n,0),dp(n,1))$。
        这样看起来好像没有什么问题，但是仔细一想是没法操作的。方程中有取$\max$的成分，但是一旦取了模，就没法比较大小。
        仔细观察方程，我们可以发现$dp(x,0)$与$dp(x,1)$的大小关系是有一些情况的，具体来说有以下几种（下面情况按顺序依次判断）：

若$dp(x-2,1)>dp(x-2,0)$，必然有$dp(x,0)>dp(x,1)$。
若$dp(x-1,1)>dp(x-1,0)$，必然有$dp(x,0)=dp(x,1)$。
其余情况$dp(x,0)<dp(x,1)$。

在递推$dp$时，同时维护每一个$dp$值对应的大小关系，递推出后来的大小关系，这样就可以边取模，边比较大小了。

#include <bits/stdc++.h>
#define MOD (int(1e9 + 7))
using namespace std;
typedef long long ll;
int n;
ll dp[2000005][2], xz[2000005];
int main()
{
    int t;
    scanf("%d", &t);
    dp[1][0] = dp[1][1] = dp[2][0] = dp[2][1] = 0;
    xz[1] = xz[2] = 0;
    for (int i = 3; i <= 2000000; i++) {
        if (xz[i - 2] >= 0)
            dp[i][0] = 2 * dp[i - 2][1];
        else
            dp[i][0] = 2 * dp[i - 2][0];
        if (xz[i - 1] >= 0)
            dp[i][0] += dp[i - 1][1];
        else
            dp[i][0] += dp[i - 1][0];
        dp[i][0] %= MOD;
        dp[i][1] = (2 * dp[i - 2][0] + dp[i - 1][0] + 1) % MOD;
        if (xz[i - 2] == 1)
            xz[i] = -1;
        else if (xz[i - 1] == 1)
            xz[i] = 0;
        else
            xz[i] = 1;
    }
    while (t--) {
        scanf("%d", &n);
        if (xz[n] >= 1)
            printf("%lld\n", dp[n][1] * 4ll % MOD);
        else
            printf("%lld\n", dp[n][0] * 4ll % MOD);
    }
    return 0;
}

E. DeadLee

        对于每一种事物，求出其需求量$s(i)$，若$w(i)\geq s(i)$，则食物$i$的喜爱者必然都是可满足的。这是因为无论如何这些人都可以吃食物$i$。这时我们就认为他们只吃食物$i$，让他们把其余的食物让出来给别人。
        上面这些人全部放到答案序列的最后，他们一定是可满足的。同时，使他们腾出各自的另一种喜爱的食物（使对应的需求量减少）。这样会得到更多的满足$w(i)\geq s(i)$的食物，递归进行以上操作。
        容易证明，如果最后没有一种食物满足$w(i)\geq s(i)$，就是无解的。
        但是纯暴力是$O(nm)$，可以使用队列优化，复杂度降至$O(n+m)$。

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n, m, w[N], a[N], b[N], xq[N], sw[N], gg[N];
queue<int> que;
vector<int> ans, gk[N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", w + i);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", a + i, b + i), ++xq[a[i]], ++xq[b[i]];
        gk[a[i]].push_back(i);
        gk[b[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (w[i] >= xq[i]) que.push(i), sw[i] = 1;
    }
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        for (int i = 0; i < gk[f].size(); i++) {
            if (gg[gk[f][i]] == 0) {
                gg[gk[f][i]] = 1, ans.push_back(gk[f][i]);
                int other = a[gk[f][i]] == f ? b[gk[f][i]] : a[gk[f][i]];
                --xq[other];
                if (sw[other] == 0) {
                    if (sw[other] == 0) {
                        if (w[other] >= xq[other]) que.push(other), sw[other] = 1;
                    }
                }
            }
        }
    }
    if (ans.size() != m) {
        printf("DEAD");
    } else {
        printf("ALIVE\n");
        for (int i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
    }
    return 0;
}

F. BareLee

博弈论，先考虑一轮的情况。
设$win(s,e)$表示在$(s,e)$的情况下，先手是否能必胜，同理可有$lose(s,e)$。其中$win(s,e)$的取值有以下几种情况：

$e$为奇数，此时只有$s$是偶数时，先手才能必胜。可以使用数学归纳法证明。可以见得$e$是必输点，而$e-1$是必胜点。假设对于$i>k$都有：$i$是奇数时必输，偶数时必胜，那么取$k$时，有$2k$和$k+1$两种转移。若$k$是奇数，则$2k$和$k+1$都是偶数，都必胜，那么$k$必输；若$k$是偶数，则$k+1$是奇数，必输，那么$k$必胜。
当$2s>e$时，只有$s$是奇数才能必胜。因为此时双方都不会采取$2s$这样的决策，都只会$s+1$，这样当$s$是奇数时才能胜。
当$4s>e$时，先手必胜。这是因为此时采取$2s$的决策会进入上一种情况，而此时$2s$是偶数，必胜。
其余情况与答案与$win(s,\lfloor\frac {e}{4}\rfloor)$相同。由于$4s>e$时先手必胜，双方都会尽量使值不超过$\lfloor\frac {e}{4}\rfloor$。如果能让后手先超过$\lfloor\frac {e}{4}\rfloor$，先手必胜，问题即转化为$win(s,\lfloor\frac {e}{4}\rfloor)$。

$lose(s,e)$的情况：

$2s>e$时，只需要进行一次$2s$操作就输了，先手必输。
其余情况答案与$win(s,\lfloor\frac {e}{2}\rfloor)$相同。因为$2s>e$时先手就必输了，所以双方都尽量使值不超过$\lfloor\frac {e}{2}\rfloor$，首先超过的必胜。如果能让后手先超过，则先手必输，即$win(s,\lfloor\frac {e}{2}\rfloor)$。

于是我们可以在$O(log(e))$复杂度下求出$win$和$lose$。再考虑多轮比赛的情况，可以$DP$。
设$dp(x,y)$表示将要进行第$x$轮比赛，现在$Lee$是不是先手（$y=0$是先手，$y=1$不是），采取策略必胜的情况（值为$0$或$1$），那么可以进行如下操作序列（伪代码）来更新$DP$：

$dp(x,y)=0\\ if(win(s[x], e[x])+y==1) dp(x,y)|=dp(x+1,1)\\ if(lose(s[x], e[x]) +y==1) dp(x,y)|=dp(x+1,0)$

必输的类似可得。

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int t, dp[N][2];
int win(ll s, ll e)
{
    if (s > e) return 0;
    if (e & 1) return (~(s & 1)) & 1;
    if ((s << 1) > e) return s & 1;
    if ((s << 2) > e) return 1;
    return win(s, e >> 2);
}
int lose(ll s, ll e)
{
    if ((s << 1) > e) return 1;
    return win(s, e >> 1);
}
ll s[N], e[N];
int main()
{
    scanf("%d", &t);
    for (int i = 1; i <= t; i++) scanf("%lld%lld", s + i, e + i);
    dp[t + 1][1] = 1, dp[t + 1][0] = 0;
    for (int rd = t; rd >= 1; rd--) {
        for (int who = 0; who < 2; who++) {
            dp[rd][who] = 0;
            if (win(s[rd], e[rd]) ^ who) dp[rd][who] |= dp[rd + 1][1];
            if (lose(s[rd], e[rd]) ^ who) dp[rd][who] |= dp[rd + 1][0];
        }
    }
    printf("%d ", dp[1][0]);
    dp[t + 1][1] = 0, dp[t + 1][0] = 1;
    for (int rd = t; rd >= 1; rd--) {
        for (int who = 0; who < 2; who++) {
            dp[rd][who] = 0;
            if (win(s[rd], e[rd]) ^ who) dp[rd][who] |= dp[rd + 1][1];
            if (lose(s[rd], e[rd]) ^ who) dp[rd][who] |= dp[rd + 1][0];
        }
    }
    printf("%d", dp[1][0]);
    return 0;
}