2023牛客暑期多校训练营2

题意

定义一种 CRC−LINKCRC-LINK 校验方式。给定 headerheader 长度为 n1n_1 个字节，footerfooter 长度为 n2n_2 个字节，要求构造一个长度为 44 个字节的 checksumchecksum，使得 header,checksum,footerheader,checksum,footer 的拼接经 CRC−LINKCRC-LINK 校验后得到的 checksum′checksum' 与 checksumchecksum 一致。

数据范围： 1≤n1,n2≤1051\leq n_1,n_2\leq 10^5。

题解

我们考虑输入的每一位对最终 checksumchecksum 的贡献：记 fif_i 为输入中从低到高第 i−32i-32 位的贡献。特别地，f0∼31=20∼31f_{0\sim31}=2^{0\sim31}。然后，考虑 i≥32i\geq 32 时，它会将低它 3232 位中 PP 对应为 11 的位翻转，那么它的贡献就是这些位的贡献的异或，所以我们可以递推计算。

具体地，

fi={2ii<32⊕jfi−ji≥32f_i= \begin{cases} 2^i &i<32\\ \underset{j}{\oplus}f_{i-j} &i\geq 32 \end{cases}

其中 jj 满足 PP 从高到低的第 jj 位为 11。

那么，给定的 headerheader 和 footerfooter 对答案的贡献就可以计算了，我们记为 aa。再记 checksumchecksum 从第到高的每一位为 bib_i，那么我们要解的方程就是：

(⊕i=031bi×fi+8×n2)⊕a=∑i=031bi×2i(\oplus_{i=0}^{31}b_i\times f_{i+8\times n_2})\oplus a=\sum_{i=0}^{31}b_i\times 2^i

这个方程每个位是独立的，可以按位拆成 3232 个方程：

f8×n2,0b0⊕f8×n2+1,0b1⊕⋯⊕f8×n2+31,0b31⊕a0=b0f8×n2,1b0⊕f8×n2+1,1b1⊕⋯⊕f8×n2+31,1b31⊕a1=b1⋯f8×n2,31b0⊕f8×n2+1,31b1⊕⋯⊕f8×n2+31,31b31⊕a31=b31\begin{aligned} &f_{8\times n_2,0} b_0\oplus f_{8\times n_2+1,0} b_1\oplus \cdots \oplus f_{8\times n_2+31,0} b_{31}\oplus a_0 =b_0\\ &f_{8\times n_2,1} b_0\oplus f_{8\times n_2+1,1} b_1\oplus \cdots \oplus f_{8\times n_2+31,1} b_{31}\oplus a_1 =b_1\\ &\cdots\\ &f_{8\times n_2,31} b_0\oplus f_{8\times n_2+1,31} b_1\oplus \cdots \oplus f_{8\times n_2+31,31} b_{31}\oplus a_{31} =b_{31}\\ \end{aligned}

其中 fk,i,aif_{k,i},a_i 表示 fk,af_k,a 从低到高的第 ii 位。

这个方程可以用高斯消元法求解。（std用的是线性基，但我不是很能看明白。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
const int N=1e5*16+100;
unsigned f[N];
bitset<35> matrix[35];//matrix[1~n]:增广矩阵，0位置为常数
// n 为未知数个数，m 为方程个数，返回方程组的解
// 无解返回一个空的 vector
vector<bool> GaussElimination(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=m;j++)
        {
            if(matrix[j][i])
            {
                swap(matrix[i],matrix[j]);
                break;
            }
        }
        if(!matrix[i][i]&&matrix[i][0]) return vector<bool>(0);
        for(int j=1;j<=m;j++)
            if(j!=i&&matrix[j][i]) matrix[j]^=matrix[i];
    }
    vector<bool> ans(n+1,0);
    for(int i=1;i<=n;i++) ans[i]=matrix[i].test(0);
    return ans;
}
void init()
{
    for(int i=0;i<32;i++) f[i]=1u<<i;
    for(int i=32;i<N;i++)
    {
		f[i]^=f[i-6];
		f[i]^=f[i-9];
		f[i]^=f[i-10];
		f[i]^=f[i-16];
		f[i]^=f[i-20];
		f[i]^=f[i-21];
		f[i]^=f[i-22];
		f[i]^=f[i-24];
		f[i]^=f[i-25];
		f[i]^=f[i-27];
		f[i]^=f[i-28];
		f[i]^=f[i-30];
		f[i]^=f[i-31];
		f[i]^=f[i-32];
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n1,n2;cin>>n1>>n2;
    unsigned target=0;
    for(int i=1;i<=n1;i++)
    {
        int a;cin>>a;
        for(int j=7;j>=0;j--)
            if(a>>j&1) target^=f[32+n2*8+32+(n1-i)*8+j];
    }
    for(int i=1;i<=n2;i++)
    {
        int b;cin>>b;
        for(int j=7;j>=0;j--)
            if(b>>j&1) target^=f[32+(n2-i)*8+j];
    }
    for(int i=0;i<32;i++)
    {
        matrix[i+1]=target>>i&1;
        for(int j=0;j<32;j++) matrix[i+1][j+1]=f[32+n2*8+j]>>i&1;
        matrix[i+1].flip(i+1);
    }
    vector<bool> ans=GaussElimination(32,32);
    unsigned sum=0;
    for(int i=0;i<32;i++)
        if(ans[i+1]) sum+=(1<<i);
    cout<<sum<<'\n';
    return 0;
}

C graph

题意

给出一张没有自环的 nn 个点 mm 条边的无向图（可能有重边）。现在给每个点黑白染色，然后将所有连接了不同色点的边删除，要求得到的图中每个连通块都存在一条欧拉路径。判断是否存在一种染色方案。

数据范围：1≤n≤100,0≤m≤100001\leq n\leq 100,0\leq m\leq 10000。

题解

我们猜测，存在一种构造方案，不仅符合题意，而且每个连通块内所有的点度数都是偶数。（证明参考题解）

用 xi=0x_i=0 表示点 ii 为黑色，xi=0x_i=0 表示点 ii 为白色。记 aija_{ij} 为点 ii 和点 jj 间连边数量，degideg_i 为点 ii 的度数。可以得到异或方程组：

a11(x1⊕x1)⊕a12(x1⊕x2)⊕⋯⊕a1n(x1⊕xn)=deg1a21(x2⊕x1)⊕a22(x1⊕x2)⊕⋯⊕a2n(x2⊕xn)=deg2⋯an1(xn⊕x1)⊕an2(xn⊕x2)⊕⋯⊕ann(xn⊕xn)=degn\begin{aligned} &a_{11}(x_1\oplus x_1)\oplus a_{12}(x_1\oplus x_2)\oplus \cdots \oplus a_{1n}(x_1\oplus x_n)=deg_1\\ &a_{21}(x_2\oplus x_1)\oplus a_{22}(x_1\oplus x_2)\oplus \cdots \oplus a_{2n}(x_2\oplus x_n)=deg_2\\ &\cdots\\ &a_{n1}(x_n\oplus x_1)\oplus a_{n2}(x_n\oplus x_2)\oplus \cdots \oplus a_{nn}(x_n\oplus x_n)=deg_n\\ \end{aligned}

异或相当于是不进位的加法，对乘法具有分配律。所以我们可以改写一下方程，以第一个为例：

a11(x1⊕x1)⊕a12(x1⊕x2)⊕⋯⊕a1n(x1⊕xn)=deg1a11x1⊕a11x1⊕a12x1⊕a12x2⊕⋯⊕a1nx1⊕a1nxn=deg1(a12⊕⋯a1n)x1⊕a12x2⊕⋯⊕a1nxn=deg1\begin{aligned} a_{11}(x_1\oplus x_1)\oplus a_{12}(x_1\oplus x_2)\oplus \cdots \oplus a_{1n}(x_1\oplus x_n)&=deg_1\\ a_{11}x_1\oplus a_{11}x_1\oplus a_{12}x_1\oplus a_{12}x_2\oplus\cdots\oplus a_{1n}x_1\oplus a_{1n}x_n&=deg_1\\ (a_{12}\oplus\cdots a_{1n})x_1\oplus a_{12}x_2\oplus\cdots\oplus a_{1n}x_n&=deg_1\\ \end{aligned}

（x1x_1 的系数中两个 a11a_{11} 抵消了）

即

(a12⊕⋯⊕a1n)x1⊕a12x2⊕⋯⊕a1nxn=deg1a21x1⊕(a21⊕⋯⊕a2n)x2⊕⋯⊕a2nxn=deg2⋯an1x1⊕an2x2⊕⋯⊕(an1⊕an2⊕⋯ )xn=degn\begin{aligned} &(a_{12}\oplus\cdots\oplus a_{1n})x_1\oplus a_{12}x_2\oplus\cdots\oplus a_{1n}x_n=deg_1\\ &a_{21}x_1\oplus (a_{21}\oplus\cdots\oplus a_{2n})x_2\oplus\cdots\oplus a_{2n}x_n=deg_2\\ &\cdots\\ &a_{n1}x_1\oplus a_{n2}x_2\oplus\cdots\oplus(a_{n1}\oplus a_{n2}\oplus\cdots)x_n=deg_n\\ \end{aligned}

然后直接套用高斯消元法就可以求解了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
bitset<105> matrix[105];//matrix[1~n]:增广矩阵，0位置为常数
// n 为未知数个数，m 为方程个数，返回方程组的解
// 无解返回一个空的 vector
vector<bool> GaussElimination(int n,int m)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=m;j++)
        {
            if(matrix[j][i])
            {
                swap(matrix[i],matrix[j]);
                break;
            }
        }
        if(!matrix[i][i]&&matrix[i][0]) return vector<bool>(0);
        for(int j=1;j<=m;j++)
            if(j!=i&&matrix[j][i]) matrix[j]^=matrix[i];
    }
    vector<bool> ans(n+1,0);
    for(int i=1;i<=n;i++) ans[i]=matrix[i].test(0);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        matrix[u].flip(v);
        matrix[v].flip(u);
        matrix[u].flip(u);
        matrix[v].flip(v);
        matrix[u].flip(0);
        matrix[v].flip(0);
    }
    vector<bool> ans=GaussElimination(n,n);
    for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    return 0;
}

题意

给定一个串 ss，判断它是否可以被表示为若干个对称串的拼接。满足以下条件的串 tt 是对称的：

  • tt 是空串。
  • tt 是 o、s、x、z
  • tt 是 bTq、dTp、pTd、qTb、nTu、 uTn、oTo、 sTs 、xSx、 zSz。其中 T 是对称串。

数据范围：1≤∣s∣≤1061\leq |s|\leq 10^6。

题解

定义 fif_i 表示前缀 ii 是否能表示为若干个串的拼接。那么，fif_i 只需要从 fjf_j 转移，其中 s[j+1:i]s[j+1:i] 为 s[0:i]s[0:i] 的最长对称后缀。所以，我们只需要处理出每个位置 ii 对应的转移点 lstilst_i，这可以用 Manacher 解决。

我们修改 Manacher 的过程：将扩展的判断改为条件 3，奇对称的对称中心用条件 2 判断。每次求出最长对称子串后，我们用它的左端点来更新右端点的答案。Manacher 结束后，我们倒序枚举 ii，lsti=min⁡(lsti,lsti+1+1)lst_i=\min(lst_i,lst_{i+1}+1)。这样就做完了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
string s;
int d1[N],d2[N];//d1为奇回文中心，d偶回文中心。d2_i表示以第i个字符前一个位置为回文中心的最长回文半径
int lst[N],f[N];
bool check(int i)
{
    return s[i]=='o'||s[i]=='s'||s[i]=='x'||s[i]=='z';
}
bool check(int i,int j)
{
    if(s[i]=='b'&&s[j]=='q') return 1;
    if(s[i]=='d'&&s[j]=='p') return 1;
    if(s[i]=='p'&&s[j]=='d') return 1;
    if(s[i]=='q'&&s[j]=='b') return 1;
    if(s[i]=='n'&&s[j]=='u') return 1;
    if(s[i]=='u'&&s[j]=='n') return 1;
    if(s[i]==s[j]&&check(i)) return 1;
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;cin>>t;
    while(t--)
    {
        cin>>s;
        int n=(int)s.size();
        for(int i=0;i<n;i++) lst[i]=0x3f3f3f3f,f[i]=0;
        for(int i=0,l=0,r=-1;i<n;i++)
        {
            if(check(i))
            {
                int k=(i>r?1:min(d1[l+r-i],r-i+1));
                while(i-k>=0&&i+k<n&&check(i-k,i+k)) k++;
                d1[i]=k;
                lst[i+k-1]=min(lst[i+k-1],i-k+1);
                k--;
                if(i+k>r) l=i-k,r=i+k;
            }     
            else d1[i]=0;
        }
        for(int i=0,l=0,r=-1;i<n;i++)
        {
            int k=(i>r?0:min(d2[l+r-i+1],r-i+1));
            while(i-k-1>=0&&i+k<n&&check(i-k-1,i+k)) k++;
            d2[i]=k;
            lst[i+k-1]=min(lst[i+k-1],i-k);
            k--;
            if(i+k>r) l=i-k-1,r=i+k;
        }
        for(int i=n-2;i>=0;i--) lst[i]=min(lst[i],lst[i+1]+1);
        for(int i=0;i<n;i++)
        {
            if(lst[i]==0x3f3f3f3f) f[i]=0;
            else if(lst[i]==0) f[i]=1;
            else f[i]=f[lst[i]-1];
        }
        cout<<(f[n-1]?"Yes":"No")<<'\n';
    }
    return 0;
}
ACM
#2023牛客多校 #高斯消元 #Manacher
2023牛客暑期多校训练营2
https://je3ter.github.io/2023/08/21/ACM/2023牛客暑期多校训练营2/
作者
Je3ter
发布于
2023年8月21日
许可协议