2023.02.04 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

给定序列 $a_i$$a_i$，将序列的位置 $i$$i$ 染色将会获得 $a_i$$a_i$ 的贡献，但要求对于任意两个染色的位置 $i,j$$i, j$ 满足 $a_i\le a_j$$a_i \le a_j$，同时对于连续 $m$$m$ 个未染色的位置会失去 ${\displaystyle \frac{m(m+1)}{2}}$$\dfrac{m(m + 1)}{2}$ 的贡献，最大化贡献，求最大值。

emm 第一眼想到的是 $\mathtt{\text{2D0D}}$$\texttt{2D0D}$ 的 DP，就是设 $dp(i,j,0/1)$$dp(i, j, 0/1)$ 表示前 $i$$i$ 个最后染色的价值为 $j$$j$ 然后末尾是否染色，这个东西离散化一下理论是 $O(n^2)$$O(n^2)$ 的，然后发现无法转移，想到添加一维 $k$$k$ 表示末尾连续多少个未染色的，想转移时发现 $j$$j$ 和 $0/1$$0/1$ 就没用了，于是最终 $\mathtt{\text{2D0D}}$$\texttt{2D0D}$ 的 DP 是令 $dp(i,j)$$dp(i, j)$ 表示前 $i$$i$ 个结尾连续 $j$$j$ 个未染色的最大贡献，转移显然：

后者整理得：

前者二维偏序可以优化到 $O(n)$$O(n)$，后者发现化简完似乎并没有什么优化的方式，于是寄掉，最终 $41\mathtt{\text{pts}}$$41\texttt{pts}$。

Upd：也可以强行优化，发现 $dp(i,j)(j\ne 0)$$dp(i, j)(j \neq 0)$ 都可以 $O(1)$$O(1)$ 求，对于 $dp(i,0)$$dp(i, 0)$ 的转移将后者所有全部转化为 $dp(j,0)+C$$dp(j, 0) + C$ 的形式，此时就和 $\mathtt{\text{1D1D}}$$\texttt{1D1D}$ 的方程十分相似，二维偏序然后 cdq 维护一下即可。

Code

xxxxxxxxxx
89
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define INF (0x3f3f3f3f)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29

30
namespace Sub_1_2{
31
    ll A[5100];
32
    ll dp[5100][5100];
33
    void Make(void){
34
        memset(dp, 0xc0, sizeof dp);
35
        for(int i = 1; i <= N; ++i)A[i] = read();
36
        A[0] = -INF;
37
        dp[1][0] = A[1], dp[1][1] = -1;
38
        for(int i = 2; i <= N; ++i){
39
            for(int j = 0; j <= i - 1; ++j)
40
                if(A[i] >= A[i - 1 - j])
41
                    dp[i][0] = max(dp[i][0], dp[i - 1][j] + A[i]);
42
            for(int j = 1; j <= i; ++j)
43
                dp[i][j] = dp[i - 1][j - 1] + (((j - 1) * j) >> 1) - ((j * (j + 1)) >> 1);
44
        }
45
        ll ans(-INF);
46
        for(int j = 0; j <= N; ++j)ans = max(ans, dp[N][j]);
47
        printf("%lld\n", ans);
48
    }
49
}
50
namespace Sub_3_4{
51
    ll A[1100000];
52
    void Make(void){
53
        for(int i = 1; i <= N; ++i)A[i] = read();
54

55
    }
56
}
57
int main(){
58
    freopen("paint.in", "r", stdin);
59
    freopen("paint.out", "w", stdout);
60
    N = read();
61
    if(N <= 10000)Sub_1_2::Make();
62
    else exit(1);
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66

67
/*
68
7
69
1 3 2 7 3 2 4
70

71
7
72
-3 -4 -2 -2 -6 -8 -1
73
*/
74

75
template < typename T >
76
inline T read(void){
77
    T ret(0);
78
    int flag(1);
79
    char c = getchar();
80
    while(c != '-' && !isdigit(c))c = getchar();
81
    if(c == '-')flag = -1, c = getchar();
82
    while(isdigit(c)){
83
        ret *= 10;
84
        ret += int(c - '0');
85
        c = getchar();
86
    }
87
    ret *= flag;
88
    return ret;
89
}

T2

给定字符串 $S$$S$，存在 $n-2$$n - 2$ 次修改操作，第 $i$$i$ 次会将 $i+1$$i + 1$ 的字符变为 $w_i$$w_i$，每次求最长回文子串，包括未修改时，求出对于所有答案中最大值。

基于 LG-P4324 [JSOI2016]扭动的回文串 修改的。

赛时一看默认这是 PAM 之类的东西（犇犇 @sssmzy 真的写了个 PAM）于是就跳了，写了个 $O(n)$$O(n)$ 预处理前缀后缀哈希，$O(n^2)$$O(n^2)$ 枚举子串 $O(1)$$O(1)$ 验证共做 $O(n)$$O(n)$ 次的 $O(n^3)$$O(n^3)$，于是寄掉了，最终 $30\mathtt{\text{pts}}$$30\texttt{pts}$。

正解真的巨简单

Code

xxxxxxxxxx
93
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define BASE (31)
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
string S;
30

31
namespace Sub_1_2{
32
    int ans(0);
33
    unll pow_base[210];
34
    unll hash[210], rhash[210];
35
    void Cal(void){
36
        hash[0] = rhash[N + 1] = 0;
37
        for(int i = 1; i <= N; ++i)hash[i] = hash[i - 1] * BASE + S.at(i - 1);
38
        for(int i = N; i >= 1; --i)rhash[i] = rhash[i + 1] * BASE + S.at(i - 1);
39
        for(int l = 1; l <= N; ++l){
40
            for(int r = l; r <= N; ++r){
41
                unll hash1 = hash[r] - hash[l - 1] * pow_base[r - l + 1];
42
                unll hash2 = rhash[l] - rhash[r + 1] * pow_base[r - l + 1];
43
                if(hash1 == hash2)ans = max(ans, r - l + 1);
44
            }
45
        }
46
    }
47
    void Make(void){
48
        pow_base[0] = 1;
49
        for(int i = 1; i <= 205; ++i)pow_base[i] = pow_base[i - 1] * BASE;
50
        Cal();
51
        for(int i = 1; i <= N - 2; ++i){
52
            char c = getchar(); while(!isalpha(c))c = getchar();
53
            S.at(i) = c;
54
            Cal();
55
        }printf("%d\n", ans);
56
    }
57
}
58

59

60
int main(){
61
    freopen("str.in", "r", stdin);
62
    freopen("str.out", "w", stdout);
63
    N = read(); cin >> S;
64
    if(N <= 600)Sub_1_2::Make();
65
    else puts("qwq");
66
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
67
    return 0;
68
}
69

70
/*
71
6
72
ABAECB
73
B
74
C
75
D
76
E
77
*/
78

79
template < typename T >
80
inline T read(void){
81
    T ret(0);
82
    int flag(1);
83
    char c = getchar();
84
    while(c != '-' && !isdigit(c))c = getchar();
85
    if(c == '-')flag = -1, c = getchar();
86
    while(isdigit(c)){
87
        ret *= 10;
88
        ret += int(c - '0');
89
        c = getchar();
90
    }
91
    ret *= flag;
92
    return ret;
93
}

T3

还算是相对比较接近切掉的一道题。

给定序列 $x_n$$x_n$，给定 $k,T$$k, T$，每次操作会使其变为序列 $y_n$$y_n$ 满足：

求操作 $T$$T$ 次后的序列。

Tips：序列下标从 $0$$0$ 开始。

手画一下，例如 $k=3$$k = 3$，一次操作大概是其之后连续 $3$$3$ 个数亦或起来，即 $1,1,1$$1, 1, 1$，两次后就是 $1,0,1,0,1$$1, 0, 1, 0, 1$，即第 $1,3,5$$1, 3, 5$ 亦或起来，发现似乎就是将 $1,1,1$$1, 1, 1$ 多项式乘法乘上 $T$$T$ 次，然后将 $n$$n$ 之外的部分类似 P3321 [SDOI2015]序列统计 去覆盖上去即可，这个东西只能用两只 $\log$$\log$ 的多项式快速幂，此处复杂度 $O(n\log n\log T)$$O(n \log n \log T)$，最终赋值复杂度 $O(n^2)$$O(n^2)$，可以通过 $50\mathtt{\text{pts}}-80\mathtt{\text{pts}}$$50\texttt{pts}-80\texttt{pts}$，当然我最终得到 $50$$50$。

Code

xxxxxxxxxx
173
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define DFT (true)
24
#define IDFT (false)
25
#define MOD (998244353ll)
26

27
template < typename T = int >
28
inline T read(void);
29

30
int N, K; ll T;
31
int pos[410000];
32
ll g(3), inv_g;
33
ll A[410000];
34

35
ll qpow(ll a, ll b){
36
    ll ret(1), mul(a);
37
    while(b){
38
        if(b & 1)ret = ret * mul % MOD;
39
        b >>= 1;
40
        mul = mul * mul % MOD;
41
    }return ret;
42
}
43

44
class Polynomial{
45
private:
46
public:
47
    int len;
48
    ll poly[410000];
49
    Polynomial(void){
50
        len = 0;
51
        memset(poly, 0, sizeof poly);
52
    }
53
    void Reverse(void){
54
        for(int i = 0; i < len; ++i)
55
            pos[i] = (pos[i >> 1] >> 1) | (i & 1 ? len >> 1 : 0);
56
        for(int i = 0; i < len; ++i)if(i < pos[i])swap(poly[i], poly[pos[i]]);
57
    }
58
    void Shrink(void){
59
        for(int i = N; i < len; ++i)(poly[i % N] += poly[i]) %= MOD, poly[i] = 0;
60
        for(int i = 0; i < len; ++i)poly[i] %= 2;
61
        len = min(len, N);
62
    }
63
    void NTT(bool pat){
64
        Reverse();
65
        for(int siz = 2; siz <= len; siz <<= 1){
66
            ll gn = qpow(pat ? g : inv_g, (MOD - 1) / siz);
67
            for(auto p = poly; p != poly + len; p += siz){
68
                int mid = siz >> 1; ll g(1);
69
                for(int i = 0; i < mid; ++i, (g *= gn) %= MOD){
70
                    auto tmp = g * p[i + mid] % MOD;
71
                    p[i + mid] = (p[i] - tmp + MOD) % MOD;
72
                    p[i] = (p[i] + tmp) % MOD;
73
                }
74
            }
75
        }
76
        if(!pat){
77
            ll inv_len = qpow(len, MOD - 2);
78
            for(int i = 0; i < len; ++i)(poly[i] *= inv_len) %= MOD;
79
            Shrink();
80
        }
81
    }
82
    void Print(void){
83
        printf("Polynomial(len = %d): ", len);
84
        for(int i = 0; i < len; ++i)printf("%lld ", poly[i]);
85
        printf("\n");
86
    }
87
};
88

89
Polynomial ret, mul;
90
void qpow(Polynomial* a, ll b){
91
    for(int i = 0; i < ret.len; ++i)ret.poly[i] = 0;
92
    ret.len = 1, ret.poly[0] = 1;
93
    mul = *a;
94
    while(b){
95
        if(b & 1){
96
            int base(1); while(base < ret.len + mul.len - 1)base <<= 1;
97
            ret.len = mul.len = base;
98
            ret.NTT(DFT), mul.NTT(DFT);
99
            for(int i = 0; i < base; ++i)ret.poly[i] = ret.poly[i] * mul.poly[i] % MOD;
100
            ret.NTT(IDFT), mul.NTT(IDFT);
101
        }
102
        b >>= 1;
103
        int base(1); while(base < mul.len + mul.len - 1)base <<= 1;
104
        mul.len = base;
105
        mul.NTT(DFT);
106
        for(int i = 0; i < base; ++i)mul.poly[i] = mul.poly[i] * mul.poly[i] % MOD;
107
        mul.NTT(IDFT);
108
    }
109
}
110

111

112
int main(){
113
    freopen("xortwo.in", "r", stdin);
114
    freopen("xortwo.out", "w", stdout);
115
    inv_g = qpow(g, MOD - 2);
116
    N = read(), K = read(); T = read < ll >();
117
    Polynomial origin;
118
    origin.len = K;
119
    for(int i = 0; i < origin.len; ++i)origin.poly[i] = 1;
120
    // {
121
    //     int base(1); while(base < origin.len)base <<= 1;
122
    //     origin.len = base;
123
    //     origin.Print();
124
    //     origin.NTT(DFT), origin.NTT(IDFT);
125
    //     origin.Print();
126
    //     base = (1); while(base < origin.len)base <<= 1;
127
    //     origin.len = base;
128
    //     origin.NTT(DFT), origin.NTT(IDFT);
129
    //     origin.Print();
130
    // }
131
    qpow(&origin, T);
132
    basic_string < int > isTrue;
133
    for(int i = 0; i < N; ++i)if(ret.poly[i])isTrue += i;
134
    // ret.Print();
135
    for(int i = 0; i < N; ++i)A[i] = read();
136
    for(int i = 0; i < N; ++i){
137
        ll val(0);
138
        for(auto j : isTrue)val ^= A[(i + j) % N];
139
        printf("%lld%c", val, i == N - 1 ? '\n' : ' ');
140
    }
141
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
142
    return 0;
143
}
144

145
/*
146
5 3 1
147
3 0 2 1 2
148

149
5 3 2
150
3 0 2 1 2
151

152
5 3 15
153
3 0 2 1 2
154

155
11 5 1000000000000000000
156
2 2 4 5 9 1 5 7 7 1 8
157
*/
158

159
template < typename T >
160
inline T read(void){
161
    T ret(0);
162
    int flag(1);
163
    char c = getchar();
164
    while(c != '-' && !isdigit(c))c = getchar();
165
    if(c == '-')flag = -1, c = getchar();
166
    while(isdigit(c)){
167
        ret *= 10;
168
        ret += int(c - '0');
169
        c = getchar();
170
    }
171
    ret *= flag;
172
    return ret;
173
}

正解

T1

简单设一个 $\mathtt{\text{1D1D}}$$\texttt{1D1D}$ 的 DP 然后斜率优化十分显然，偏序部分套个 CDQ 即可，复杂度 $O(n\log n)$$O(n \log n)$。

T2

就是个哈希，类比一下原题就行，分割成中间的回文串和左右相同的两串，中间回文串满足单调性，跑一下即可。

另外对于一般的哈希也是满足单调性的，枚举每一个中点然后取最大值并令其不降最终就是 $O(n)$$O(n)$ 的。

T3

考虑最终将二进制拆位并 NTT 即可，此时就能几乎拿满了。对于过程中会发现有一些难以想到的性质，emm 大概就是能推成一个新的柿子，然后就能优化，emmmmmm 这个东西吧。。反正很奇怪就对了。

代码实现就先都咕着了。

UPD

update-2023_02_04 初稿