2022-9-5总结

Or Plus Max

需要求 $i \operatorname{or} j \le k, i \not= j$ 条件下 $\max\{A_i+A_j\}$，我们可以找出 $k$ 的二进制子集内的最大值和次大值。

暴力枚举子集肯定会超时，所以我们可以利用已有的子集信息进行转移，具体就是尝试抠掉 $k$ 的某一个 $1$，从这个子集转移一下最大值和次大值。

因为抠掉 $1$ 之后的那个子集也是用同样的方法转移过来的，所以就相当于枚举子集了。

可以看代码实现，更好理解一些。

#include <algorithm>
#include <cstdio>
using namespace std;
 
const int N = 300005;
 
int n;
int a[N];
int f[N], g[N], id[N]; // id记录最大值的位置

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < (1<<n); i++)
        scanf("%d", &a[i]);
 
    for(int i = 0; i < (1<<n); i++)
    {
        f[i] = a[i];
        id[i] = i;
        for(int j = 0; j < 18; j++)
        {
            if(!(i&(1<<j))) continue;
            int k = i-(1<<j); //抠掉一位
            if(f[k] > f[i])
            {
                g[i] = max({f[i], g[k]});
                f[i] = f[k];
                id[i] = id[k];
            }
            else
            {
                if(f[k] > g[i] and id[k] != id[i])
                    g[i] = f[k];
                else if(g[k] > g[i])
                    g[i] = g[k];
            }
        }
    }
    int val = 0;
    for(int i = 1; i < (1<<n); i++)
    {
        val = max(val, f[i]+g[i]);
        printf("%d\n", val);
    }
}

LEGOndary Grandmaster

把两个相邻的相同的数取反这个操作不好做，可以考虑一个套路的做法：把偶数位置的数取反一下。

这样做的话这个操作就变成了交换两个相邻的数，因为交换相同的数没有用，所以求解最短距离时一定不会有这种操作，也就是不会出现非法操作。

现在用交换两个相邻的数的操作使得偶数位置取反后的两个串 $s', t'$ 相同，其实就是求所有第 $k$ 个 $1$ 的位置差。

但是由于题目中有 ? 的存在，我们不太好求相同位置的 $1$ 的位置差（因为不确定这是第几个 $1$）。

解决方法也很套路：拆贡献。具体就是统计每个间隔处需要交换多少次，很明显这个间隔处的前面 $1$ 的数量差多少个就需要交换多少次。所以我们可以统计一下 $1$ 的前缀和。

而题目需要求所有方案的距离和，所以我们可以设 $g_{i,j}$ 为在第 $i$ 个间隔处， $1$ 的个数的差为 $j(-i \le j \le i)$ 的方案数，这样记录一下的话转移就比较好写了。

因为下标有负数所以需要整体平移一下。

#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
 
typedef long long ll;
const int N = 2005;
const int P = 1e9+7;
 
int n;
ll f[N][N*2];
ll g[N][N*2];
char s[N], t[N];
 
void solve();
 
int main()
{
    int t; scanf("%d", &t);
    while(t --> 0) solve();
}
 
void solve()
{
    scanf("%d", &n);
    scanf("%s%s", s+1, t+1);
    for(int i = 1; i <= n; i++)
    {
        memset(f[i], 0, sizeof(f[i]));
        memset(g[i], 0, sizeof(g[i]));
    }
    for(int i = 2; i <= n; i += 2)
    {
        if(s[i] != '?') s[i] ^= 1;
        if(t[i] != '?') t[i] ^= 1;
    }
    g[0][N] = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = -i; j <= i; j++)
        {
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++)
                {
                    if(s[i+1] != '?' and k != s[i+1]-'0') continue;
                    if(t[i+1] != '?' and l != t[i+1]-'0') continue;
                    int p = j+k-l;
                    (g[i+1][p+N] += g[i][j+N]) %= P;
                    (f[i+1][p+N] += g[i][j+N]*abs(j) + f[i][j+N]) %= P;
                }
        }
    }
    printf("%lld\n", f[n][N]);
}

数列

先考虑求出原序列的 $f(a)$ 值，很明显就是 $max\{a_i-premin_i\}$，于是考虑前缀 $min$ 值。

可以发现，前缀 $min$ 值相同的一段可以一起处理，前缀 $min$ 值不同的段互不影响。

对于相同的一段，如果这一段中有 $f(a)$ 值的话就需要对这段进行修改，我们可以选择一个位置，将这个位置前面的最小值都删掉，这个位置后面的最大值都删掉，这样就可以使 $f(a)$ 值减小了，我们直接处理出前缀后缀，然后枚举这个位置就行了。

#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
using namespace std;
 
const int N = 1000005;
 
int n, d;
int a[N];
int pre[N], suf[N];
 
int solve(int l, int r);
 
int main()
{
    int minv = 0x3f3f3f3f;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        d = max(d, a[i] - minv);
        minv = min(minv, a[i]);
    }
 
    int l = 1, r = 1, ans = 0;
    minv = a[1];
    for(int i = 2; i <= n+1; i++)
    {
        if(a[i] < minv or i == n+1)
        {
            ans += solve(l, r);
            l = r = i;
        }
        else
            r = i;
        minv = min(minv, a[i]);
    }
 
    printf("%d", ans);
}
 
int solve(int l, int r)
{
    int minv = INT_MAX;
    int maxv = -INT_MAX;
    for(int i = l; i <= r; i++)
    {
        minv = min(minv, a[i]);
        maxv = max(maxv, a[i]);
    }
    if(maxv - minv != d)
        return 0;
    pre[l-1] = suf[r+1] = 0;
    for(int i = l; i <= r; i++)
        pre[i] = pre[i-1]+(a[i]==minv);
    for(int i = r; i >= l; i--)
        suf[i] = suf[i+1]+(a[i]==maxv);
 
    int ans = INT_MAX;
    for(int i = l-1; i <= r; i++)
        ans = min({ans, pre[i]+suf[i+1]});
    return ans;
}