2024杭电多校第10场

10

1002 scenery (hdu7542)

由于 \(l\) 序列不增、 \(r\) 序列不降，每处景色的拍摄安排在可选时间的开始/结束位置显然是最优的。设 \(dp[i][j]\) 表示（从后往前）考虑到第 \(i\) 处景色、可选时间从 \(j\) 开始的最晚结束位置，则转移方程：

\(dp[i][max(l_i, j) + t_i] = max(dp[i][max(l_i, j) + t_i], dp[i - 1][j])\) （开始位置）

\(dp[i][j] = max(dp[i][j], min(dp[i - 1][j], r_i + 1) - t_i)\) （结束位置）

预先将所有状态赋为不合法情况 \(-1\)，最后检查 \(dp[1][j]\) 中是否有合法情况即可。

    memset(dp, -1, sizeof(dp));
    int it = 1;
    dp[1][0] = m + 1;
    for(int i = n; i; i--) {
        it ^= 1;
        for(int j = 0; j <= m; j++) {
            dp[it][j] = -1;
        }
        for(int j = 0; j <= m; j++) {
            int l = max(a[i].l - 1, j) + a[i].t;
            if(l > a[i].r || l >= dp[it ^ 1][j]) continue;
            dp[it][l] = max(dp[it][l], dp[it ^ 1][j]);
        }
        for(int j = 0; j <= m; j++) {
            int r = min(dp[it ^ 1][j], a[i].r + 1) - a[i].t;
            if(r < a[i].l || r <= j) continue;
            dp[it][j] = max(dp[it][j], r);
        }
    }
    bool flag = 0;
    for(int j = 0; j <= m; j++) {
        if(dp[it][j] >= 0) {
            flag = 1;
            break;
        }
    }
    if(flag) printf("YES\n");
    else printf("NO\n");

居然能在赛时写对dp，挺难得的）

1008 SunBian (hdu7548)

对于 \(n\) 为偶数的情况，除非Alice能够一次将所有笋变成横向，即 \(k=n\)，否则无论她如何操作，Bob都可以在对称位置模仿操作、使自己必胜。\(n\) 为奇数时，若 \(1<k<n\)，Bob可将整个环隔开成为两个对称的部分、同理模仿操作；\(k=1\) 或 \(n\) 时则Bob必败。

1010 A+B Problem (hdu7550)

一个小规律：\(ans_i\) 的二进制最低位与 \(ans_{i - 1}\) 无关，对于确定的 \(a_i,b_i\)，\(ans_i\space \&\space 1\)为定值。而其他每位上的取值只与 \(a_i,b_i\) 以及 \(ans_{i - 1}\) 的较低位有关，因此确定最低位后、可通过递推求出完整的 \(ans_i\)，即最终答案唯一。

    for(int i = 1; i <= q; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        c[i] = (a[i] ^ b[i]) & 1;
    }
    c[0] = c[q];
    for(int z = 1; z < 32; z++) {
        for(int i = 1; i <= q; i++) {
            ll y = (a[i] ^ c[i - 1]) + (b[i] ^ c[i - 1]);
            c[i] += (y & (1ll << z));
        }
        c[0] = c[q];
    }
    for(int i = 1; i <= q; i++) {
        printf("%lld\n", c[i]);
    }