A - Yet Another AB Problem
对于几种情况，分类讨论一下：
s[i]!=t[i],t[i]=='A'：这种情况，需要向后找一个t[j]=='B'；s[i]!=t[i],t[i]=='B'：这种情况，需要向前找一个t[j]=='A'。
若所有条件满足，则可以判定可行。要取得最小值，显然我们应当尽可能将1、2两种s[i]!=t[i]情况合起来（一次操作可以解决两个冲突），若是找不到，再与s[i]==t[i]的合起来（一次操作只解决一个冲突）。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
void work()
{
cin >> n;
string s1, s2;
cin >> s1 >> s2;
if (s1 == s2)
{
cout << 0 << endl;
return;
}
bool isA = 0, needB = 0;
int cnt = 0, turnA = 0;
for (int i = 0; i < n; i++)
{
if (s1[i] == s2[i] && s1[i] == 'A')
isA = 1;
else if (s1[i] == s2[i])
needB = 0;
else if (s1[i] == 'A')
{
if (turnA > 0)
turnA--, needB = 0;
else if (isA)
cnt++, needB = 0;
else
{
cout << "-1\n";
return;
}
}
else
{
turnA++;
cnt++;
isA = 1;
needB = 1;
}
}
if (needB == 0)
cout << cnt << endl;
else
cout << -1 << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
work();
}
|
B - Arithmetic
Progression Subsequence
容易想到通过枚举中间值，两边找等差数的想法。但是，很难解决子段重复计数的问题（一个区间可能包含多对等差数）。考虑其他做法。
注意到a[i]的值域很小(1~10)，那么，最小的合法子段的长度也很小（至多21个数就会出现3个相等的数）。这样，我们可以暴力枚举子段，然后直接暴力判断字段的合法性。当第一次合法时直接计算剩余贡献即可。时间复杂度为\(\Theta(n\omega^4)\)（\(\omega\)为值域），大约为\(O(1e9)\)左右，可以通过此题。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
int n, m, k, q;
int a[N];
int pre[N][11];
void work()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
for (int j = 1; j <= 10; j++)
pre[i][j] = pre[i - 1][j];
pre[i][a[i]] = i;
}
auto check = [&](int l, int r)
{
for (int i = l;i <= r; i++)
for (int j = i + 1; j <= r; j++)
for (int k = j + 1; k <= r; k++)
if (a[j] - a[i] == a[k] - a[j])
return true;
return false;
};
ll ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (check(i, j))
{
ans += n - j + 1;
break;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
work();
}
|
C - Prefix Mex Sequence
一道很巧妙的dp题。
一开始，想的是令dp[i][j]表示前\(i\)项，\(mex=j\)的情况总数。然后发现状态非常复杂，无法判断之前放置了多少个大于\(mex\)的数，转移无法进行。
官方题解采用了一种很巧妙的思路避开了\(mex\)前后的不确定性。
\(mex\)的本质，就是一个不同于集合内任何一个数的数；将\(mex\)放进集合内，相当于令集合内不同数的个数+1。
于是，我们令dp[i][j]表示前\(i\)项，集合内有\(j\)个不同的数。接下来讨论：
\(s[i]=1\)：加入了一个\(mex\)，相当于加入了一个不同于之前任意一个值的数，则直接转移：
\[
f[i][j] =f[i-1][j-1]
\]
s[i]=0：加入一个不等于\(mex\)的数，则这个数可能是小于\(mex\)的数，也可能是大于的数。但是，归根结底，这只分为两种情况：
- 这个数在原来有的\(j\)个数内，总共\(j\)种可能性。
- 这个数不在原来的\(j\)个数内，总共\(m-j+1\)种可能性。
那么，我们就可以根据这个写出递推方程： \[
f[i][j]=f[i-1][j]*j+f[i-1][j-1]*(m-j+1)
\]
通过这样的方式，我们就很巧妙地避开了对\(mex\)的讨论，转而讨论更容易维护的种类数，从而在\(\Theta(n\min(n,m))\)的时间内完成了这道题目。
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
|
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
ll n, m, k, q, lim;
const ll mod = 998244353ll;
ll f[N][N];
void work()
{
cin >> n >> lim;
m = min(lim + 1, n);
f[0][0] = 1;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
if (x == 1)
{
for (int j = 1; j <= m; j++)
f[i][j] = f[i - 1][j - 1];
}
else
{
for (int j = 1; j <= m; j++)
f[i][j] = (f[i - 1][j - 1] * (lim - j + 1) + f[i - 1][j] * (j)) % mod;
}
}
ll ans = 0;
for (int i = 0; i <= m; i++)
ans = (ans + f[n][i]) % mod;
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
work();
}
|