Codeforces Round #612 (Div. 2)
/ / 阅读耗时 21 分钟 Codeforces Round #612 (Div. 2)题解。
A. Angry Students
签到水题。直接从前往后扫一遍就可以，记录每一个P最左侧的L距离。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
char op[150];
int main()
{
int t, n;
scanf("%d", &t);
while (t--) {
int ans = 0, at = 0;
scanf("%d", &n);
scanf("%s", op);
for (int i = 0; op[i]; i++) {
if (op[i] == 'A')
at = 1;
else if (at)
++at;
ans = max(at, ans);
}
printf("%d\n", max(ans - 1, 0));
}
return 0;
}
B. Hyperset
考虑枚举2个，找合法的第三个。直接找第三个不能$O(n)$去找，考虑对所有卡片属性进行哈希，放到一个set里面，可以有效降低复杂度。最终复杂度为$O(n^2klogn)$。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
using namespace std;
long long bin[35];
int n, k;
char op[1600][35];
set<long long> ssp;
inline int get(char e)
{
if (e == 'S')
return 0;
else if (e == 'E')
return 1;
return 2;
}
inline int so(char a, char b)
{
if (a == b) return get(a);
if (a == 'S' && b == 'E' || a == 'E' && b == 'S')
return get('T');
else if (a == 'S' && b == 'T' || a == 'T' && b == 'S')
return get('E');
return get('S');
}
int main()
{
bin[0] = 1;
for (int i = 1; i <= 30; i++) bin[i] = bin[i - 1] * 3;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%s", op[i]);
long long hs = 0;
for (int j = 0; j < k; j++) hs += 1ll * get(op[i][j]) * bin[j];
ssp.insert(hs);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
long long hh = 0;
for (int z = 0; z < k; z++) {
hh += 1ll * so(op[i][z], op[j][z]) * bin[z];
}
if (ssp.count(hh)) ++ans;
}
}
printf("%d", ans / 3);
return 0;
}
C. Garland
标程是贪心，但其实这个题可以用DP强行水过。
考虑到放的数只与奇偶性有关，于是用$dp(n0,n1,x,i)$表示当前有$n0$个偶数可放，$n1$个奇数可放，第$x$位是否为奇数（对于$i=0/1$），对前$x$位放置的最小代价，转移方程很好列。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
using namespace std;
int dp[105][105][105][2], op[105], n, n0, n1;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
for (int i = 1; i <= n; i++) {
if (op[i]) {
if (op[i] & 1)
++n1;
else
++n0;
}
}
memset(dp, 0x3f, sizeof(dp));
n1 = ((n + 1) >> 1) - n1, n0 = (n >> 1) - n0;
for (int i = 0; i <= n0; i++) {
for (int j = 0; j <= n1; j++) dp[i][j][0][0] = dp[i][j][0][1] = 0;
}
for (int i = 1; i <= n; i++) {
for (int a = 0; a <= n0; a++) {
for (int b = 0; b <= n1; b++) {
if (op[i]) {
dp[a][b][i][op[i] % 2] =
min(dp[a][b][i - 1][0] + (op[i] % 2 == 1), dp[a][b][i - 1][1] + (op[i] % 2 == 0));
}
else {
if (a > 0) {
dp[a][b][i][0] = min(min(dp[a - 1][b][i - 1][0], dp[a - 1][b][i - 1][1] + 1), dp[a][b][i][0]);
}
if (b > 0) {
dp[a][b][i][1] = min(min(dp[a][b - 1][i - 1][0] + 1, dp[a][b - 1][i - 1][1]), dp[a][b][i][1]);
}
}
}
}
}
printf("%d", min(dp[n0][n1][n][0], dp[n0][n1][n][1]));
return 0;
}
D. Numbers on Tree
把树建出来，然后求DFS序，将子树上节点转化为区间。容易发现这些区间要么相互包含，要么互不相交。
将所有区间按长度从小到大排序，进行遍历，一个个放数。这里可以用随机乱搞法解决：
对于叶子节点，我们给它们赋上一个随机的权值（尽可能使各个节点之间权值互异），显然这是可行的。
对于更长的区间，我们对区间中已知的数排序，之后二分，根据给定的数量确定根节点权值，这里也可以用随机数调整一下。
最后得到的答案大概率是正确的，多交两发就A了。
无解的情况很容易判，只有数量少于0或多于子树节点数-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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
struct Edge
{
int next, to;
} edge[4000005];
struct Node
{
int l, r, v;
};
vector<Node> vec[N];
int head[N], cnt = 1, dfn[N], DFN, sz[N], n, c[N], to[N], rt;
double v[N];
inline void add(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void DFS(int x)
{
dfn[x] = ++DFN, sz[x] = 1, to[DFN] = x;
for (int i = head[x]; i; i = edge[i].next) {
if (!dfn[edge[i].to]) DFS(edge[i].to), sz[x] += sz[edge[i].to];
}
}
vector<int> tmp;
vector<double> zz;
int main()
{
srand(time(nullptr));
scanf("%d", &n);
for (int i = 1, p; i <= n; i++) {
scanf("%d%d", &p, c + i);
if (p == 0)
rt = i;
else
add(p, i);
}
DFS(rt);
for (int i = 1; i <= n; i++) {
Node nd;
nd.l = dfn[i], nd.r = dfn[i] + sz[i] - 1, nd.v = c[i];
vec[sz[i]].push_back(nd);
}
for (int i = 1; i <= n; i++) {
for (Node& s : vec[i]) {
if (s.v > i - 1) {
printf("NO");
return 0;
}
if (s.l == s.r) {
v[to[s.l]] = 1ll * rand() * rand();
continue;
}
tmp.clear();
for (int j = s.l + 1; j <= s.r; j++) tmp.push_back(to[j]);
sort(tmp.begin(), tmp.end(), [](int a, int b) {
return v[a] < v[b];
});
if (s.v >= 1 && s.v < i - 1) {
v[to[s.l]] = (v[tmp[s.v - 1]] + v[tmp[s.v]]) / 2;
}
else if (s.v == 0)
v[to[s.l]] = v[tmp[0]] - 1ll * rand() * rand() - 1;
else
v[to[s.l]] = v[tmp[i - 2]] + 1ll * rand() * rand() + 1;
}
}
for (int i = 1; i <= n; i++) zz.push_back(v[i]);
sort(zz.begin(), zz.end());
auto ss = unique(zz.begin(), zz.end());
printf("YES\n");
for (int i = 1; i <= n; i++) {
printf("%d ", lower_bound(zz.begin(), ss, v[i]) - zz.begin() + 1);
}
// PAUSE;
return 0;
}
E. Madhouse
交互题，考察智商。
首先其实询问两次就可以找到这个串。只需要询问$[1,n]$以及$[1,n-1]$，两个可重集合作差得到串的所有后缀，很快就确定了这个串。
然而，询问$[1,n]$以及$[1,n-1]$会导致超过$0.777(n+1)^2$的限制。考虑优化。
先求前半部分，$[1,\frac {n}{2}]$，这里用两次询问解决。
紧接着，询问$[1,n]$，统计字符$x$在长度为$l$的串中出现的次数$cnt(l,x)$。容易发现，若串的第$j$的位置为$x$，则它将在$cnt(l,x)$中的贡献是$min(l,j,n-j+1)$。那么，对$cnt(l+1,x)$的贡献就是$min(l+1,j,n-j+1)$。
那么$cnt(l+1,x)-cnt(l,x)$的值就是$l< j$且$l< n-j+1$的那一部分，即$l+1\leq j\leq n-l$中$x$出现的次数。我们于是得到了很多区间中某一个字符的出现次数。
由于前半部分已经得知，于是根据前半部分提供的信息，后半部分就可以推得。
注意$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
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
using namespace std;
int n, cnt[30], at, num[26][101], os[26][101], len[26][105];
string str;
char ans[205];
multiset<string> s1, s2;
char ms(const string& a, const string& b)
{
for (int i = 0; i < 26; i++) cnt[i] = 0;
for (char e : b) ++cnt[e - 'a'];
for (char e : a) --cnt[e - 'a'];
for (int i = 0; i < 26; i++) {
if (cnt[i]) return 'a' + i;
}
}
vector<string> vec;
int main()
{
cin >> n;
if (n / 2 >= 1) {
cout << "? 1 " << (n / 2) << endl;
for (int i = 1, p = (n / 2) * (n / 2 + 1) / 2; i <= p; i++) {
cin >> str;
sort(str.begin(), str.end());
s2.insert(str);
}
}
if (n / 2 - 1 >= 1) {
cout << "? 1 " << (n / 2 - 1) << endl;
for (int i = 1, p = (n / 2 - 1) * (n / 2) / 2; i <= p; i++) {
cin >> str;
sort(str.begin(), str.end());
s1.insert(str);
}
for (string ss : s1) s2.erase(s2.find(ss));
}
string tmp = "";
at = n / 2;
for (string ss : s2) vec.push_back(ss);
sort(vec.begin(), vec.end(), [&](string a, string b) {
return a.length() < b.length();
});
for (string ss : vec) ans[at--] = ms(tmp, ss), tmp = ss;
for (int i = 1; i <= n / 2; i++) {
for (int j = 0; j < 26; j++) {
os[j][i] = os[j][i - 1] + (ans[i] == 'a' + j);
}
}
cout << "? 1 " << n << endl;
for (int i = 1, p = n * (n + 1) / 2, ll; i <= p; i++) {
cin >> str;
for (char e : str) ++len[e - 'a'][str.length()];
}
for (int i = 2; i <= (n + 1) / 2; i++) {
for (int j = 0; j < 26; j++) { //[i,n-i+1]
num[j][i] = len[j][i] - len[j][i - 1];
}
}
for (int i = n / 2 + 1; i < n; i++) {
for (int j = 0; j < 26; j++) {
if (num[j][n + 1 - i] - (max(0, os[j][i - 1] - os[j][n - i]))) {
ans[i] = 'a' + j;
break;
}
}
for (int j = 0; j < 26; j++) {
os[j][i] = os[j][i - 1] + (ans[i] == 'a' + j);
}
}
for (int i = 0; i < 26; i++) {
if (len[i][n] - os[i][n - 1]) {
ans[n] = 'a' + i;
break;
}
}
cout << "! ";
for (int i = 1; i <= n; i++) cout << ans[i];
cout << endl;
// PAUSE;
return 0;
}
F. LCC
很好的题。
首先考虑概率DP。令$f(x,i)$表示前$x$个质子，第$x$个向$i,i=1/0$方向运动的概率。那么可以得到方程：
写成矩阵的形式就是：
考虑到初始条件，就是下面矩阵乘法链的首行元素之和：
现在将所有的相邻间隔拿出来，计算时间，并从小到大排序，考虑求各自成为最小的概率。显然，令某一个最小等价于当前这个碰撞事件发生，而比它小的都不发生，这一点可以从状态转移方程中体现。比如，若第2个质子向右运动与第3个质子向左运动不能同时发生，只需要使$f(3,1)$不能从$f(2,0)$转移来即可，即将对应的矩阵元素改成0。
这样问题转化为单点修改矩阵，求矩阵乘积，用线段树维护求解即可。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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
using namespace std;
struct P
{
int id, x1, x2, x, v;
};
struct Matrix
{
int op[3][3];
void toE()
{
op[1][1] = op[2][2] = 1, op[1][2] = op[2][1] = 0;
}
void operator*=(const Matrix& s)
{
int tmp[3][3];
tmp[1][1] = tmp[1][2] = tmp[2][1] = tmp[2][2] = 0;
for (int i = 1; i <= 2; i++) {
for (int j = 1; j <= 2; j++) {
for (int k = 1; k <= 2; k++) tmp[i][j] = (tmp[i][j] + 1ll * op[i][k] * s.op[k][j]) % MOD;
}
}
op[1][1] = tmp[1][1], op[1][2] = tmp[1][2], op[2][1] = tmp[2][1], op[2][2] = tmp[2][2];
}
} nd[N << 2], t1, t2, t3, t4;
vector<P> vec;
int n, x[N], v[N], p[N], ans;
inline int inv(int x)
{
int ans = 1, sta = x, y = MOD - 2;
while (y) {
if (y & 1) ans = 1ll * ans * sta % MOD;
sta = 1ll * sta * sta % MOD, y >>= 1;
}
return ans;
}
void getTime(int a, int b, int id, int& xx, int& vv)
{
int t = 0;
if (id == 0) {
if (v[a] > v[b])
xx = (x[b] - x[a]), vv = v[a] - v[b];
else
xx = inf;
}
else if (id == 3) {
if (v[b] > v[a])
xx = x[b] - x[a], vv = v[b] - v[a];
else
xx = inf;
}
else if (id == 1) {
xx = x[b] - x[a], vv = v[a] + v[b];
}
else
xx = inf;
}
void build(int l = 1, int r = n, int k = 1)
{
if (l == r) {
nd[k].op[1][1] = nd[k].op[2][1] = 1ll * (100 - p[l]) * inv(100) % MOD;
nd[k].op[1][2] = nd[k].op[2][2] = 1ll * p[l] * inv(100) % MOD;
return;
}
int mid = (l + r) >> 1;
build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
nd[k].toE(), nd[k] *= nd[k << 1], nd[k] *= nd[k << 1 | 1];
}
void change(int at, const Matrix& s, int l = 1, int r = n, int k = 1)
{
if (l == r) {
nd[k] = s;
return;
}
int mid = (l + r) >> 1;
if (at <= mid)
change(at, s, l, mid, k << 1);
else
change(at, s, mid + 1, r, k << 1 | 1);
nd[k].toE(), nd[k] *= nd[k << 1], nd[k] *= nd[k << 1 | 1];
}
const Matrix& getMatrix(int at, int l = 1, int r = n, int k = 1)
{
if (l == r) return nd[k];
int mid = (l + r) >> 1;
if (at <= mid) return getMatrix(at, l, mid, k << 1);
return getMatrix(at, mid + 1, r, k << 1 | 1);
}
inline int get()
{
return (nd[1].op[1][1] + nd[1].op[1][2]) % MOD;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d%d", x + i, v + i, p + i);
for (int i = 2; i <= n; i++) {
P ps;
ps.x1 = i - 1, ps.x2 = i;
for (int j = 0, pp; j < 4; j++) {
getTime(i - 1, i, j, ps.x, ps.v);
if (ps.x != inf) ps.id = j, vec.push_back(ps);
}
}
sort(vec.begin(), vec.end(), [](P a, P b) {
return 1ll * a.x * b.v < 1ll * b.x * a.v;
});
build();
for (P s : vec) {
t3 = t1 = getMatrix(s.x1), t4 = t2 = getMatrix(s.x2);
if (s.id & 1)
t2.op[1][2] = t2.op[2][2] = 0;
else
t2.op[1][1] = t2.op[2][1] = 0;
if (s.id & 2)
t1.op[1][2] = t1.op[2][2] = 0;
else
t1.op[1][1] = t1.op[2][1] = 0;
change(s.x1, t1), change(s.x2, t2);
ans = (ans + 1ll * s.x * inv(s.v) % MOD * get()) % MOD;
if (s.id == 0)
t4.op[2][2] = 0;
else if (s.id == 1)
t4.op[2][1] = 0;
else if (s.id == 3)
t4.op[1][1] = 0;
change(s.x1, t3), change(s.x2, t4);
}
printf("%d", (ans + MOD) % MOD);
// PAUSE;
return 0;
}