CF1699.

A. The Third Three Number Problem

分析

首先判断无解。

异或运算可以看作二进制「不进位加法」，而在二进制加法中，第一位也不会存在进位，所以 \((a \oplus b) + (b \oplus c) + (a \oplus c)\) 与 $(a+b) + (b + c) + (a + c) = 2(a+b+c) $ 奇偶性相同。所以 \(n\) 必然是个偶数，当 \(n\) 为奇数时无解。

考虑 \(a,b,c\) 可以相同且能够取 \(0\)，而 \(0 \oplus x = x\)，那么只要取 \(a=0\)，\(b=0\)，\(c = \frac{n}{2}\) 就能够满足条件。

CODE

#include<bits/stdc++.h>
using namespace std;
int t, n;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        if(n&1) puts("-1");
        else printf("%d %d %d\n",0,0,n/2);
    }
}

B. Almost Ternary Matrix

分析

很关键的一点，\(n\) 与 \(m\) 都是偶数。

称如下矩形为 \(1\) 类矩形。

称如下矩形为 \(2\) 类矩形。

那么，无论 \(n\) 与 \(m\) 取何值，\(n \times m\) 的矩阵必然能够由若干 \(1\) 类与 \(2\) 类矩形构成。不难发现，对于单个的 \(1\) 或 \(2\) 类矩形，一定满足条件。如果在 \(1\) 类矩形的左边或右边拼上一个 \(2\) 类矩形，仍然满足条件，反之亦然；如果在一个 \(1\) 类矩形的上方或下方拼上一个 \(2\) 类矩形，仍然满足条件，反之亦然。

那么对于每 \(2\) 行，每 \(2\) 列，交替填入 \(1\) 类或 \(2\) 类矩形就得到答案了。

CODE

#include<bits/stdc++.h>
using namespace std;
int t, m, n, ans[100][100];
const int SB1[2][2]={
    {0,1},
    {1,0}
};
const int SB2[2][2]={
    {1,0},
    {0,1}
};
void solve1() {
    memset(ans,0,sizeof(ans));
    scanf("%d%d",&n,&m);
    for(int i=1,fg1=1;i<=n;i+=2,fg1^=1) {
        for(int j=1,fg2=1;j<=m;j+=2,fg2^=1) {
            // 注意原本两行算一行，两列算一列
            if(fg1&&fg2||!fg1&&!fg2) {
                // 在奇数行中，奇数个放 1 类
                // 在偶数行中，偶数个放 1 类
                ans[i][j]=SB1[0][0], ans[i][j+1]=SB1[0][1];
                ans[i+1][j]=SB1[1][0], ans[i+1][j+1]=SB1[1][1];
            } else if(fg1&&!fg2||!fg1&&fg2) {
                // 在奇数行中，偶数个放 2 类
                // 在偶数行中，奇数个放 2 类
                ans[i][j]=SB2[0][0], ans[i][j+1]=SB2[0][1];
                ans[i+1][j]=SB2[1][0], ans[i+1][j+1]=SB2[1][1];
            }
        }
    }
    for(int i=1;i<=n;++i,puts("")) for(int j=1;j<=m;++j) {
        printf("%d ",ans[i][j]);
    }
}
int main() {
    scanf("%d",&t);
    while(t--) solve1();
}

C. The Third Problem

分析

\(\operatorname{MEX}\)，完全不会啊！

首先对于任意 \(l,r \in [1,n]\)，满足 \[ \operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]) \] 这表明，假如他们的值为 \(x\)，那么 \([1,x-1]\) 一定都在 \([l,r]\) 中出现过了。

设 \(p(x)\) 表示 \(x\) 在 \(a\) 中的位置，由于是 \([0,n-1]\) 的排列，所以为了防止混淆，下文无论是数字都是 \([0,n-1]\) 中的。

尝试直接构造 \(b\)。首先，\(a\) 与 \(b\) 中 \(0\) 的位置是不能变化的，否则 \(\operatorname{MEX} ([a_{p(0)},a_{p(0)}])\) 必然不同于 \(\operatorname{MEX} ([b_{p(0)},b_{p(0)}])\)。\(1\) 的位置也不能变化，可以轻松构造例子，不再赘述。

设当前区间为 \(l,r\)，假设 \(p(0)< p(1)\)，起初 \(l=p(0)\)，\(r=p(1)\)。

如果 \(p(2) \in [l,r]\)，那么 \(2\) 放在哪里都可以。因为此时这个区间的 \(\operatorname{MEX}\) 已经和 \(0,1,2\) 无关了，由于 \(0,1\) 已经被确定，方案数累乘 \((r-l+1) -2\)。如果 \(p(2)<p(0)\) 或者 \(p(2)>p(1)\) 呢？那就令 \(l=p(2)\) 或者 \(r=p(2)\)。同时对方案数没有贡献，因为只要 \(2\) 不在 \(b_{p(2)}\) 的位置，一定不合法，同样很容易找出例子。

接下来，如果 \(p(3) \in [l,r]\)，那么分两种情况讨论

• 在上一轮中，\(p(2) \in [l',r']\)，那么此时 \([l',r'] = [l,r]\)，确定了 \(0,1,2\) 的位置，\(3\) 只有 \((r-l+1) - 3\) 种选择，累乘即可。
• 在上一轮中，\(p(2) \notin [l,r]\)，那么区间的边界一定会变化并让 \(p(2)\) 在新区间的一端，仍然确定了 \(0,1,2\)，累乘 \((r-l+1)-3\)。

如果 \(p(3) \neq [l,r]\)，修改区间就行了。

以此类推，最终就能得到答案。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5, mod=1e9+7;
int t, n, a[N], p[N];
ll ans;
void solve() {
    ans=1;
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&a[i]), p[a[i]]=i;
    int l=p[0], r=p[1];
    if(l>r) swap(l,r);
    for(int i=2;i<n;++i) {
        if(p[i]<l) l=p[i];
        else if(p[i]>r) r=p[i];
        else {
            (ans*=(r-l+1)-i)%=mod;
        }
    }
    printf("%lld\n",ans);
}
int main() {
    scanf("%d",&t);
    while(t--) solve();
}

D. Almost Triple Deletions

先证明一个结论，如果一个区间 \([l,r]\)，满足 \(a_l \ldots a_r\) 能够用题目中的操作完全删去，那么一定满足 \(r-l+1\) 是偶数且 \([l,r]\) 中出现次数最多的数，其出现次数不超过 \(\frac{r-l+1}{2}\)。

证明：

每一次操作只能选择 \(2\) 个数，如果 \(r-l+1\) 是个奇数，显然不行。而每次操作只能选择 \(2\) 个不同的数，如果某个数出现次数超过了 \(\frac{r-l+1}{2}\)，那么将这个数与一个与它不想等的数两两配对后，会只剩下这个数，无法进行操作。

考虑 \(DP\)。

设 \(f(i)\) 为由 \([1,i-1]\) 某些子序列和 \(a_i\) 构成的最终序列的长度。初始时，如果 \([1,i-1]\) 能够完全删去，\(f(i)=1\)，表示长度为 \(1\) 的序列。否则 \(f(i)=0\)，表示长度为 \(0\) 的子序列。

转移，枚举 \(j \in [i+1,n+1]\)，如果 \(a_i = a_j\) 并且 \([i+1,j-1]\) 这一段能够完全消掉，那么就能将 \(a_j\) 放在 \(a_i\) 后面，\(f(j) = f(i) +1\)。需要注意的是 \(i\) 必须满足 \(f(i) > 0\) ，因为最终序列只能由相同数字构成，而上述转移让 \(j\) 从 \(i+1\) 开始，默认了 \([i,i-1]\) 这部分能被消去。

特别地，当 \(j=n+1\) 时，如果 \([i+1,n]\) 能被消去，就让 \(f(n+1)=f(i) +1\)。最终答案是 \(f(n+1)-1\)。

为啥要这么干？因为状态时这样设计的，核心思想是将两个想等元素之间所有元素消除之后，让这两个元素使得答案序列长度 \(+1\)。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int t, n, a[N], f[N], cnt[N];
void solve() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) cnt[i]=0;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    f[0]=f[n+1]=0;
    int most_element=0;
    for(int i=1;i<=n+1;++i) {
        if(i%2&&most_element<=(i-1)/2) f[i]=1;
        else f[i]=0;
        most_element=max(most_element,++cnt[a[i]]);
    }
    for(int i=1;i<=n;++i) {
        for(int awa=1;awa<=n;++awa) cnt[awa]=0;
        most_element=0;
        if(f[i]) for(int j=i+1;j<=n+1;++j) {
            if((j-i)%2&&most_element<=(j-i-1)/2&&(a[i]==a[j]||j==n+1))
                f[j]=max(f[j],f[i]+1);
            most_element=max(most_element,++cnt[a[j]]);
        }
    }
    printf("%d\n",f[n+1]-1);
}
int main() {
    scanf("%d",&t);
    while(t--) solve();
}

E. Three Days Grace

太菜了看都没看。