抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

自闭了。

A - Sum of Odd Integers

题目传送门

题解

首先,我们尝试取出最小的 \(k\) 个正奇数:\(1,3,5,7,\cdots,2k-1\)

这些奇数的和为 \(\frac{(1+2k-1)k}{2}=k^2\)

那么我们如何构造才能使得 \(k\) 个奇数互不相同且和为 \(n\) 呢?

只要不断将最大的奇数加 \(2\) 即可。

所以当 \(n-k^2\) 是大于等于 \(0\) 的偶数时,一定能够构造出解。

而当 \(n < k^2\) 时,最小的 \(k\) 个正奇数的和已经有 \(k^2\),那么一定不能构造出解。

\(n-k^2\) 不为偶数时,由于任意 \(k\) 个奇数一定可以通过最小的 \(k\) 个正奇数中的数 \(+2,-2\) 得到,所以任意 \(k\) 个奇数的和一定与 \(k^2\) 的奇偶性相同,而 \(n\) 的奇偶性与 \(k^2\) 不同,所以一定不能构造出解。

所以「\(n-k^2\) 是大于等于 \(0\) 的偶数」是能构造出解的充要条件。

注意计算 \(k^2\) 时要开 long long。另外,\(k\)\(k^2\) 的奇偶性一定是相同的,所以我们判断 \(n\)\(k^2\) 的奇偶性是否相同只需要判断 \(n\)\(k\) 的奇偶性是否相同。

代码

1
2
3
4
5
6
int n, k;
void solve(){
read(n), read(k);
if ((n & 1) == (k & 1) && 1ll * k * k <= n) prints("YES");
else prints("NO");
}

B - Princesses and Princes

题目传送门

题解

我这个彩笔又看错题了...

题目里说只要能够增加就行...而我以为要取增加最多的方案...

那么只要模拟一遍以后,如果存在一个没有匹配的公主,任选一个王子与她匹配即可。

如果需要「增加最多」,这样构造是否正确呢 QAQ

有没有神仙来证明一下或者给出一个反例啊 QAQ

代码

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
const int N = 100005;
int n, vis[N];
std::vector<int> E[N];
void solve(){
read(n);
for (register int i = 1; i <= n; ++i)
vis[i] = 0, E[i].clear();
for (register int i = 1, k; i <= n; ++i){
read(k);
for (register int j = 0, x; j < k; ++j)
read(x), E[i].push_back(x);
}
int add_x = 0, add_y = 0;
for (register int i = 1; i <= n; ++i){
bool flag = 0;
for (register int j = 0; j < (int)E[i].size(); ++j)
if (!vis[E[i][j]]){ vis[E[i][j]] = 1, flag = 1; break; }
if (flag || add_x) continue;
add_x = i;
}
if (!add_x) prints("OPTIMAL");
else{
add_y = n;
while (vis[add_y]) --add_y;
prints("IMPROVE"), print(add_x, ' '), print(add_y);
}
}

C - Game with Chips

题目传送门

题解

考场上的我甚至想过把坐标旋转 \(x,y\) 独立等等奇怪的玩意。

在想这东西的时候,发现这东西是有边界的,而且到边界他就不会继续走了。

于是我不会了。

转念一想,既然可以走 \(2nm\) 步,好像直接把所有点移到 \((1,1)\),然后把所有点走一遍就好了!

移到 \((1,1)\) 需要 \(n+m-2\) 步,遍历所有点需要 \(nm-1\) 步,步数显然是不超过 \(2nm\) 的。

代码里移动到 \((1,1)\) 用了 \(n+m\) 步。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n, m, k;
void solve(){
read(n), read(m), read(k);
for (register int i = 1, x, y; i <= k; ++i) read(x), read(y);
for (register int i = 1, x, y; i <= k; ++i) read(x), read(y);
print(n + m + n * m - 1);
for (register int i = 1; i <= n; ++i) putchar('U');
for (register int i = 1; i <= m; ++i) putchar('L');
for (register int i = 1; i <= n; ++i){
for (register int j = 1; j < m; ++j) putchar(i & 1 ? 'R' : 'L');
if (i < n) putchar('D');
}
putchar('\n');
}

D - Infinite Path

题目传送门

题解

首先看到一个排列求 \(k\) 次幂,容易想到将排列看成若干置换环的形式。

如排列 \(p=\{2,4,1,3,6,5\}\) 可以看成:

1
2
3
4
1 --> 2
^ |
| v
3 <-- 4

以及

1
5 <==> 6

两个置换环。

将一个排列求 \(k\) 次幂以后,某个点 \(i\) 会重新指向原来环上从 \(i\) 开始第 \(k\) 个点。

那么由于我们只需要一个环满足颜色相等,容易想到将每个环单独处理以后取 \(\min\) 即可。

对于一个环长为 \(l\) 的环,我们将环上的点从某个点开始重新标号。我们判断一个 \(k\) 是否可行,只需要记 \(p=\gcd(k,l)\),我们判断是否存在一个 \(0\le t < p\) 使得环上所有模 \(p\) 等于 \(t\) 的点颜色是否相同即可。

那么显然只要枚举所有 \(l\) 的因数 \(k\) 即可。

时间复杂度 \(O(n\sqrt{n})\)

代码

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
const int N = 200005;
int n, p[N], c[N], vis[N];
int solve(std::vector<int> &a){
std::vector<int> d;
int l = a.size();
for (register int i = 1; 1ll * i * i <= l; ++i) // 求因数
if (l % i == 0){
d.push_back(i);
if (i * i < l) d.push_back(l / i);
}
std::sort(d.begin(), d.end());
for (int k : d){ // 枚举 k
for (register int i = 0; i < k; ++i){
bool flag = 1;
for (register int j = i; j < l; j += k)
flag &= a[j] == a[i]; // 判断颜色是否相同
if (flag) return k;
}
}
return l;
}
void solve(){
read(n);
for (register int i = 1; i <= n; ++i) read(p[i]), vis[i] = 0;
for (register int i = 1; i <= n; ++i) read(c[i]);
int ans = n;
for (register int i = 1; i <= n; ++i)
if (!vis[i]){
std::vector<int> tmp;
tmp.push_back(c[i]), vis[i] = 1;
for (register int j = p[i]; j != i; j = p[j])
tmp.push_back(c[j]), vis[j] = 1;
ans = std::min(ans, solve(tmp));
}
print(ans);
}

E - Count The Blocks

题目传送门

题解

设答案为 \(g_i\),考虑计算出 \(f_i=\sum\limits_{j=i}^{n} (j-i+1)g_j\),根据 \(f_i\) 的实际意义,显然有 \(f_i=(n-i+1)\times 10^{n-i+1}\)

根据容斥,可以得到 \(g_i=f_i-2f_{i-1}+f_{i-2}\)。这个式子的正确性也可以将 \(f_i\) 的定义式子代入证明。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 200005, P = 998244353;
int n, f[N];
void inc(int &a, int b){ (a += b) >= P ? a -= P : 0; }
void dec(int &a, int b){ a < b ? a += P - b : a -= b; }
void solve(){
read(n);
int pw = 10;
for (register int i = n; i; --i){
f[i] = 1ll * pw * (n - i + 1) % P;
pw = 10ll * pw % P;
}
for (register int i = 1; i <= n; ++i){
dec(f[i], f[i + 1]), dec(f[i], f[i + 1]), inc(f[i], f[i + 2]);
print(f[i], ' ');
}
putchar('\n');
}

F - AND Segments

题目传送门

题解

不错,最后 5min 开始写代码,没调出来,直接死在这题上了。


上面是一个菜鸡 xjb BB,不要管他。

首先看到这题,一看是位运算,先考虑每位是否独立。

因为只有 and 运算的限制,所以很显然每一位是独立的。那么我们只需要求出每一位满足限制的方案数,然后乘起来即可。

对于当前位,有若干个限制,每个限制规定了一个区间的 and 和是 \(0\) 还是 \(1\)

对于限制为 \(1\) 的区间,直接强制每一位必须填 \(1\)。而对于限制为 \(0\) 的区间,看上去非常难搞。

一开始我以为可以容斥,但是若干区间取并这玩意非常难处理。

突然想到了联赛前的一道作业题:P4229 某位歌姬的故事

那题由于需要离散,并且限制比较宽,所以 DP 是 \(O(nq)\) 的。

然而这题不需要离散,并且只有 \(0\)\(1\),所以我们尝试去优化这个 DP。

预处理 \(\operatorname{pos}[i]\) 表示 \(i\) 之前(不包括 \(i\))第一个 \(0\) 至少填在 \(\operatorname{pos}[i]\) 位置。这个预处理可以参考 P4229 中的预处理。

考虑 DP,\(f[i][j]\) 表示前 \(i\) 位,最后一个 \(0\) 的位置为 \(j\) 时满足限制的方案数。分三种情况进行转移:

  • \(j<\operatorname{pos}[i]\) 时,有 \(f[i][j]=0\)
  • \(\operatorname{pos}[i]\le j < i\) 时,有 \(f[i][j]=f[i-1][j]\)
  • \(j=i\) 时,若根据 \(1\) 的限制,第 \(i\) 位强制选 \(1\),那么 \(f[i][j]=0\);否则 \(f[i][j]=\sum\limits_{k=\operatorname{pos}[i]}^{i-1} f[i-1][k]\)

对于第一种情况,我们只需要维护一个最左边不为 \(0\) 的指针,每次把 \(< \operatorname{pos}[i]\) 的位置刷成 \(0\) 即可。

对于第二种情况,由于没有任何改变,所以我们不需要进行任何处理。

对于第三种情况,我们只要单点修改第 \(i\) 个位置的值即可。注意需要实时维护当前行的和。

于是这个 DP 的复杂度变成了 \(O(n)\)

每一位预处理复杂度为 \(O(m)\),所以总时间复杂度 \(O(k(n+m))\)


我的做法好像比官方题解的做法复杂一万倍。

另:这题跟绍一新生考试的 F 好像差不多...

代码

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
const int N = 500005, P = 998244353;
int n, k, m, a[N], l[N], r[N], x[N], f[N], pos[N];
void inc(int &a, int b){ (a += b) >= P ? a -= P : 0; }
void dec(int &a, int b){ a < b ? a += P - b : a -= b; }
void solve(){
read(n), read(k), read(m);
for (register int i = 1; i <= m; ++i)
read(l[i]), read(r[i]), ++r[i], read(x[i]);
int ans = 1;
for (register int p = 0; p < k; ++p){
for (register int i = 1; i <= n + 1; ++i) pos[i] = 0, a[i] = 0;
for (register int i = 1; i <= m; ++i)
if (x[i] >> p & 1) ++a[l[i]], --a[r[i]]; // 差分实现区间加
else pos[r[i]] = std::max(pos[r[i]], l[i]);
for (register int i = 2; i <= n + 1; ++i) a[i] += a[i - 1], pos[i] = std::max(pos[i], pos[i - 1]);
// a 预处理第 i 位是否强制选 1
// pos 预处理 i 之前第一个 0 至少选在哪里
for (register int i = 0; i <= n + 1; ++i) f[0] = 0;
f[0] = 1;
int sum = 1, l = 0;
for (register int i = 1; i <= n + 1; ++i){
while (l < pos[i]) dec(sum, f[l]), f[l] = 0, ++l; // 把 < pos[i] 的位置刷成 0
f[i] = a[i] ? 0 : sum, inc(sum, f[i]); // 修改第 i 个位置的 dp 值
}
ans = 1ll * ans * f[n + 1] % P;
}
print(ans);
}

G - Letters and Question Marks

题目传送门

题解

事实上这个题还是非常简单的。(别问我为什么现场没过

首先可以对所有模式串建个 AC 自动机,每个点的权值就是这个点在 \(fail\) 树上到根路径上所有点对应的字符串的权值和。

如果字符串 \(s\) 已经全部确定,那么我们只要把 \(s\) 在这个自动机上跑一遍,把经过节点的点权累加即可。

但是现在 \(s\) 有若干个字符不确定。我们考虑对于 \(s\) 的每段确定的极大子串,以及 AC 自动机上的点 \(u\),预处理从 \(u\) 开始,按照这段子串跑,最终跑到的点以及沿路经过的点权和。

然后我们就可以 DP 了。记 \(f_{S,u}\) 表示当前问号的位置用了 \(S\) 这些字符,跑到自动机上的节点 \(u\) 时,最大的权值和。

转移只需要枚举下一个问号填的字符即可。

\(n\) 为字符串 \(s\) 的长度,\(m\) 为模式串的长度之和,\(c\) 为字符集大小,则复杂度为 \(O(nm+2^cmc)\),可以通过本题。

代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const int N = 1005, C = 14;
int n;
char t[N], s[400005];
std::pair<int, long long> go[N][C + 1];
int bitcnt[1 << C];
long long f[1 << C][N];
struct AC_Automaton{
int rt, cnt, trans[N][C], fail[N];
long long w[N];
int new_node(){
int u = cnt++;
w[u] = 0, fail[u] = -1;
for (register int i = 0; i < C; ++i) trans[u][i] = -1;
return u;
}
void init(){
cnt = 0, rt = new_node();
}
void insert(const std::vector<int> &s, long long _w){
int u = rt;
for (register int i = 0; i < (int)s.size(); ++i){
if (trans[u][s[i]] == -1) trans[u][s[i]] = new_node();
u = trans[u][s[i]];
}
w[u] += _w;
}
void build(){
std::vector<int> Q;
fail[rt] = -1;
for (register int i = 0; i < C; ++i)
if (~trans[rt][i]) Q.push_back(trans[rt][i]), fail[trans[rt][i]] = rt;
else trans[rt][i] = rt;
for (register int i = 0; i < (int)Q.size(); ++i){
int u = Q[i];
w[u] += w[fail[u]];
for (register int j = 0; j < C; ++j)
if (~trans[u][j]) Q.push_back(trans[u][j]), fail[trans[u][j]] = trans[fail[u]][j];
else trans[u][j] = trans[fail[u]][j];
}
}
std::pair<int, long long> run(int u, const std::vector<int> &s){
long long sum = 0;
for (register int i = 0; i < (int)s.size(); ++i)
u = trans[u][s[i]], sum += w[u];
return {u, sum};
}
}A;
int main(){
#ifdef AT_HOME
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
read(n);
A.init();
for (register int i = 0; i < n; ++i){
int m = reads(t), w;
std::vector<int> tmp;
read(w);
for (register int j = 0; j < m; ++j) tmp.push_back(t[j] - 'a');
A.insert(tmp, w);
}
A.build();
int len = reads(s);
std::vector<int> tmp;
int cnt = 0;
for (register int i = 0; i <= len; ++i)
if (i == len || s[i] == '?'){
for (register int j = 0; j < A.cnt; ++j)
go[j][cnt] = A.run(j, tmp);
tmp.clear(), ++cnt;
}
else tmp.push_back(s[i] - 'a');
bitcnt[0] = 0;
for (register int i = 1; i < (1 << C); ++i)
bitcnt[i] = bitcnt[i >> 1] + (i & 1);
for (register int i = 0; i < (1 << C); ++i)
for (register int j = 0; j < A.cnt; ++j)
f[i][j] = -INF;
f[0][go[A.rt][0].first] = go[A.rt][0].second;
long long ans = -INF;
for (register int S = 0; S < (1 << C); ++S){
int k = bitcnt[S] + 1;
if (k == cnt){
for (register int u = 0; u < A.cnt; ++u)
ans = std::max(ans, f[S][u]);
}
if (k >= cnt) continue;
for (register int u = 0; u < A.cnt; ++u)
if (f[S][u] != -INF){
for (register int i = 0; i < C; ++i)
if (!(S >> i & 1)){
int v = A.trans[u][i];
int S_ = S | (1 << i), u_ = go[v][k].first;
f[S_][u_] = std::max(f[S_][u_], f[S][u] + A.w[v] + go[v][k].second);
}
}
}
print(ans);
}

我还是太菜了 /kk

评论