周一

C. Petya and Spiders（状压dp）

很好的一道题

这种数据范围小的，棋盘的都可以考虑状压dp

首先这题看数据范围n*m<=40，和之前的数据范围20左右的状压dp不太像

但其实可以转化以下，也就是min(n, m) <= 6 通过这一点就可以有一个长度最多为6的二进制数，这样数据范围就对了

于是按照惯例，即dp[i][S]为前i行，第i行状态为S的最大零的个数

但是发展这个蜘蛛可以转移到其他行，所以与相邻的行有关

那么就dp[i][y][z]表示第i行为y，第i+1行为z，前i行的最多零的个数

转移挺容易想的，即

dp[i][y][z] = max(dp[i][y][z], dp[i-1][x][y]+num[y])

num[y]表示第i行的状态y的0的个数

但是转移的时候要考虑是否合法

对于x，y，z，x和z可以和其他行有关，所以关键是中间的状态y

要判断是否可能存在这样的相邻三行x y z 关键是中间的y

一个蜘蛛可以不动和上下左右五种情况

也就是说一个位置的蜘蛛去了这五个位置的某一个

这五个位置对应x,y,z,y>>1,y<<1 那么原来第i行是每个位置都有蜘蛛，所以把这5个状态或起来，也应该每个位置都有蜘蛛。这就是是否合法的判断

最后注意一下有些初始状态不合法，像第0行只能是全0

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;int dp[45][1 << 6][1 << 6], n, m;bool check(int x, int y, int z){    int cur = x | y | z | (y << 1) | (y >> 1), t = (1 << n) - 1;    return (cur & t) == t;}int get(int x){    int res = 0;    _for(i, 1, n)        if(!(x & (1 << (i - 1))))            res++;    return res;}int main(){    scanf("%d%d", &n, &m);    if(n > m) swap(n, m);     memset(dp, -0x3f, sizeof dp);   //设置为负的最小值 注意有些状态不合法    rep(x, 0, 1 << n) dp[0][0][x] = 0;    _for(i, 1, m)        rep(x, 0, 1 << n)            rep(y, 0, 1 << n)                rep(z, 0, 1 << n)                    if (check(x, y, z))                        dp[i][y][z] = max(dp[i][y][z], dp[i - 1][x][y] + get(y));                            int ans = 0;    rep(x, 0, 1 << n)        ans = max(ans, dp[m][x][0]);    printf("%d\n", ans);return 0;}

E. Moving Chips（状压dp）

这题首先要观察出一些性质

多余的列去掉

然后可以发现最优的肯定是从最左边一列一路到最右边一列

但是具体要怎么操作呢，我一开始思考一个具体的贪心策略，发现有反例。其实已经比较接近了。

这时其实就需要包含所有情况，也就是dp了

一列的时候肯定只有一个chip是最优的，因为这题是覆盖的。

那么dp[i][0/1]表示前i行，第i行在上面和下面的最优解

之后转移方程就很好写了

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;const int N = 2e5 + 10;char s0[N], s1[N];int dp[N][2], n; int main(){    int T; scanf("%d", &T);    while(T--)    {        scanf("%d%s%s", &n, s0 + 1, s1 + 1);        int l, r;        _for(i, 1, n)            if(s0[i] == '*' || s1[i] == '*')            {                l = i;                break;            }        for(int i = n; i >= 1; i--)            if(s0[i] == '*' || s1[i] == '*')            {                r = i;                break;            }                dp[l][1] = (s0[l] == '*');        dp[l][0] = (s1[l] == '*');        _for(i, l + 1, r)        {            dp[i][0] = min(dp[i - 1][1] + 2, dp[i - 1][0] + 1 + (s1[i] == '*'));            dp[i][1] = min(dp[i - 1][0] + 2, dp[i - 1][1] + 1 + (s0[i] == '*'));        }        printf("%d\n", min(dp[r][1], dp[r][0]));    }return 0;}

C. XOR Inverse(字典树+异或)

这题真的妙，原来字典树可以和逆序对扯上关系

我自己想的时候实在想不出异或和逆序对有什么关系，原来是通过字典树将两者联系在一起

首先两个数的大小可以比较得出来，从高位到低位看，一定是第一个不同的数决定了这两者的大小。

那么我们把数按顺序加到字典树中，在某一个节点，可以往1走也可以往0走，这时如果往0走，那么就由这一位产生了由1走的那个子树的大小的逆序对数，注意这一位这里的抉择会导致一些数能够比较出大小。同理，如果往1走，就产生了由0走的子树的大小那么多的顺序对

对于逆序对而言，如果x的这一位为0，那么逆序对就是往1走的子树的大小，如果为1，那么因这一位而产生的大小关系全部取反，也就是说顺序对的个数就是异或1后的逆序对的个数

因此我们可以统计每一位x为0还是为1产生的逆序对个数来决定这一位x为1还是为0

逆序对个数会超int 小心

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int N = 3e5 + 10;int t[N * 30][2], siz[N * 30], cnt, n;ll zh[30], ni[30];void add(int x){    int p = 0;    for(int k = 29; k >= 0; k--)    {        int cur = (x >> k) & 1;        if(cur) zh[k] += siz[t[p][0]];        else ni[k] += siz[t[p][1]];        if(!t[p][cur]) t[p][cur] = ++cnt;        p = t[p][cur]; siz[p]++;    }}int main(){    scanf("%d", &n);    _for(i, 1, n)     {        int x; scanf("%d", &x);        add(x);    }    ll ans = 0; int x = 0;    for(int k = 29; k >= 0; k--)    {        if(ni[k] > zh[k]) ans += zh[k], x |= 1 << k;        else ans += ni[k];    }    printf("%lld %d\n", ans, x);return 0;}

周二

D. Ehab the Xorcist（异或性质）

这题主要就是用到了异或的一个性质，即异或是不进位加法

换句话说，异或加上进位的也就等价于直接相加了

即a^b+2*(a&b)=a+b   2*(a&b)即进位的部分

从这个公式可以得出以下两点

①a+b >= a ^ b

②a+b和a^b的奇偶性相同   可以理解为最低位的相加是一样的

那么从这题而言，异或和为u，和为v

那么有v >= u且u和v的奇偶性相同

之后我们利用a^a=0这个性质

可以很容易构造u, x, x

其中x = (v - u) / 2

接下来考虑有无两个数的情况

两个数必须满足a^b=u  a+b=v

加法不好利用，位运算可以一位一位看，信息多一些

于是由公式可以退出a&b = (v - u) / 2 = x

也就是得出了a & b 和 a ^ b 的结果，接下来来一位一位看

如果a&b的一位为1，说明两个都是1，那么异或后为0，也就是a^b的这一位为0

那么就由x & u = 0(写代码注意括号，位运算优先级低)

这个是一个必要条件，我们看这是不是充分条件

原来三个数是[u, x, x]

在此基础上，两个数构造为[u+x,x] 这样和肯定是满足的，那么异或和呢

前面说的x & u = 0，可以推出x ^ u = x + u(最开始的公式)

那么(u+x) ^ x = (u ^ x) ^ x = u就恰好满足情况了

所以这也是一个充分条件，也就是说x & u = 0是一个充要条件

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;typedef long long ll;ll u, v;int main(){    scanf("%lld%lld", &u, &v);    if(u == v && u == 0) puts("0");    else if(u == v) printf("1\n%lld\n", u);    else if(u > v || (v - u) % 2 == 1) puts("-1");    else    {        ll x = (v - u) / 2;        if((x & u) == 0) printf("2\n%lld %lld\n", x, u + x);        else printf("3\n%lld %lld %lld\n", u, x, x);    }return 0;}

D. River Locks(思维)

很思维的一道题

首先要观察到一个性质，就是管子开最左边的肯定是最优的

那么可以想这样一个思路，计算出开i个管子最少需要的时间

这样子对于询问就可以二分找出答案

那么首先要计算出填满前i个罐子需要多少时间，用k[i]来计算

显然要先填满前i-1个管子，即k[i-1]

其次要填满第i个管子，这时可以用前缀和来表示，因为前面都满了，所以没有空的可以前缀和

也就是prei / i向上取整

所以k[i] = max(k[i-1],prei/i)

那么计算这个后，我们不仅要前i个填满，我们还需要整个填满

由于前i个填满了，所以我们可以前缀和，即sum/i

所以a[i] = max(k[i], sum / i)

这样就可以算出用i个管子最少需要多少时间了

好题

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int N = 2e5 + 10;ll v[N], a[N], k[N], sum;int n, q;int main(){    scanf("%d", &n);    _for(i, 1, n)    {        scanf("%lld", &v[i]);        sum += v[i];    }    ll t = 0;    _for(i, 1, n)     {        t += v[i];        k[i] = max(k[i - 1], (t + i - 1) / i);    }    _for(i, 1, n) a[i] = max(k[i - 1], (sum + i - 1) / i);    scanf("%d", &q);    _for(i, 1, q)    {       ll t; scanf("%lld", &t);       int pos = lower_bound(a + 1, a + n + 1, t, greater<int>()) - a;       printf("%d\n", pos > n ? -1 : pos);    }   return 0;}

周四

C. You Are Given a WASD-string...（思维）

首先可以上下左右分开看

用坐标的角度来看，一次改变可以改变所有的后缀

所以只需要维护前缀最值和后缀最值即可，枚举在每个地方插入

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int N = 2e5 + 10;int a[N], b[N], nmax[N], nmin[N], n;pair<int, int> solve(int c[])  //某一个方向{    int mi = 0, mx = 0;    _for(i, 1, n) mi = min(mi, c[i]), mx = max(mx, c[i]);    int t = mx - mi + 1;  //不操作的答案    nmax[n] = nmin[n] = c[n];    for(int i = n - 1; i >= 1; i--) nmax[i] = max(nmax[i + 1], c[i]), nmin[i] = min(nmin[i + 1], c[i]); //后缀最值        int cur = 0, res = t;    mx = 0, mi = 0;    _for(i, 0, n - 1)    {        mx = max(mx, c[i]);        mi = min(mi, c[i]);        int tmax, tmin;        //加1        tmax = max(mx, max(c[i] + 1, nmax[i + 1] + 1));        tmin = min(mi, min(c[i] + 1, nmin[i + 1] + 1));        res = min(res, tmax - tmin + 1);        //减1        tmax = max(mx, max(c[i] - 1, nmax[i + 1] - 1));        tmin = min(mi, min(c[i] - 1, nmin[i + 1] - 1));        res = min(res, tmax - tmin + 1);    }    return {t, res < t};}int main(){    int T; scanf("%d", &T);    while(T--)    {        string s;        cin >> s;        n = s.size();        s = " " + s;        //水平方向        int cur = 0;        _for(i, 1, n)        {            if(s[i] == 'A') cur--;            if(s[i] == 'D') cur++;            a[i] = cur;        }        pair<int, int> ta = solve(a);        //竖直方向        cur = 0;        _for(i, 1, n)        {            if(s[i] == 'S') cur--;            if(s[i] == 'W') cur++;            b[i] = cur;        }        pair<int, int> tb = solve(b);        ll ans = 1LL * ta.first * tb.first;        if(ta.second) ans = min(ans, 1LL * (ta.first - 1) * tb.first);        if(tb.second) ans = min(ans, 1LL * (tb.first - 1) * ta.first);        printf("%lld\n", ans);    }    return 0;}

上面比较粗暴，写起来比较麻烦。还有更简单的方法，就是观察性质

可以发现，想要减少只能是上界减1或者下界加1，那么根据一次操作可以使后缀最值加减1，那么就必须满足last_max < first_min或者last_min < first_max

此外，长度必须大于2。显然长度为1不能优化，长度为2也不能，因为一次操作就会导致长度为2，这两种特判一下。

#include <bits/stdc++.h>#define rep(i, a, b) for(int i = (a); i < (b); i++)#define _for(i, a, b) for(int i = (a); i <= (b); i++)using namespace std;const int N = 2e5 + 10;int a[N], b[N], n;pair<int, int> solve(int c[])  //某一个方向{    int mx = 0, mi = 0;    _for(i, 1, n) mi = min(mi, c[i]), mx = max(mx, c[i]);    int res = mx - mi + 1;    if(res <= 2) return {res, res};    vector<int> pos_mx, pos_mi;    _for(i, 0, n)    {        if(c[i] == mx) pos_mx.push_back(i);        if(c[i] == mi) pos_mi.push_back(i);    }        if(pos_mx.back() < pos_mi[0] || pos_mi.back() < pos_mx[0]) return {res, res - 1};    return {res, res};}int main(){    int T; scanf("%d", &T);    while(T--)    {        string s;        cin >> s;        n = s.size();        s = " " + s;        int cur1 = 0, cur2 = 0;        _for(i, 1, n)        {            if(s[i] == 'A') cur1--;            if(s[i] == 'D') cur1++;            a[i] = cur1;            if(s[i] == 'S') cur2--;            if(s[i] == 'W') cur2++;            b[i] = cur2;        }        pair<int, int> ta = solve(a), tb = solve(b);        printf("%lld\n", min(1LL * ta.first * tb.second, 1LL * ta.second * tb.first));    }    return 0;}