Rating.png:
正常发挥吧。毕竟就这水平。
AB没啥好说的，读题速度要是快点就好了。
C题不知道在想啥。想了一堆奇怪的东西（觉得区间是不交，是包含的，然后求每个数在的最小满足条件的区间就好了），然后发现这东西就是个错的（eg:03030）。莫名其妙花了好久，数组没清对还WA了一下。
D题做的挺慢的，想当然写个贪心然后WA。然后想了好久把才贪心叉掉。(eg: R:5 G:4 B:4,3)。就是两个较小的数相同的时候，选其中的一个是不对的。（R和G选了，B自己剩下两个没法配对）。然后改了个DP花了半个小时，虽然水的没办法，不过因为好久没写过DP了，勉强也能接受。
然后就只有半小时了，读了E和F。感觉比较麻烦，比赛时间是写不完了。但是应该都是可做题，这几天找个时间写一下。
发现最近学习效率都不太行，还是要高效一点。
Day2：发现E题看错了，以为是有负数收益的法术。草，有SB。
题意
有两种法术，火焰法术造成一定伤害，雷电法术造成一定伤害还会使得下次伤害翻倍。
现在一个人啥也不会，每次学会一个法术或者忘掉之前的一个法术，问用现有的法术如何打出最大伤害（每个法术的收益大于0）。
题解
如果有个雷电法术，那么翻倍的一定是目前会的伤害最大前个。除非前个全是雷电法术，那么放最前面的第一个雷电法术是不能翻倍的，这个时候还不如把一个最大的火焰法术放进去翻倍（也就是用最大的火焰法术换最小的雷电法术）。
支持插入和删除，要求维护：
- 雷电法术的个数（)
- 数组里面前大的和
- 非前大的数的和
- 第大
- 最大的火焰法术
知道这些东西以后，就可以判断是否都是雷电法术。如果不是都是，答案就是前大×2+后面的和；
如果都是，答案就是前大×2+后面的和-最小的雷电法术+最大的火焰法术。
平衡树
这些东西可以用数据结构去维护。平衡树维护子树和，树枝数组要离线和二分， 线段树维护子树大小和子树和然后二分。
这个是直接的做法。
std::set
基于每次的最多加/减，其实也有用set的维护方法。
分别用两个set表示前大的数和剩下的数。
顺便维护每个set中所有元素的和。
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
| #include<bits/stdc++.h>
using namespace std;
int read() {
int x; scanf("%d", &x); return x;
}
const int maxn = 1e6 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
int A, B, C;
#define ll long long
set<int>F[2];
set<int>Good, Bad;
ll sumG, sumB;
void Fix() {
if (Good.size() < F[1].size()) {
int x = *(--Bad.end());
Bad.erase(--Bad.end());
sumB -= x;
Good.insert(x);
sumG += x;
}
else if (Good.size() > F[1].size()) {
int x = *Good.begin();
Good.erase(Good.begin());
sumG -= x;
Bad.insert(x);
sumB += x;
}
if (Good.size() && Bad.size() && *(Good.begin()) < *(--Bad.end())) {
int t = *(Good.begin());
int p = *(--Bad.end());
Good.erase(Good.begin()); Good.insert(p);
sumG -= t; sumG += p;
Bad.erase(--Bad.end()); Bad.insert(t);
sumB -= p; sumB += t;
}
}
int main() {
#ifdef LOCAL
freopen("1.in", "r", stdin);
#endif
int n = read();
while (n--) {
int opt = read(), Di = read();
if (Di > 0) {
F[opt].insert(Di);
Bad.insert(Di); sumB += Di;
Fix();
}
else if (Di < 0) {
Di = -Di;
F[opt].erase(F[opt].find(Di));
if (Good.count(Di)) Good.erase(Good.find(Di)), sumG -= Di;
if (Bad.count(Di)) Bad.erase(Bad.find(Di)), sumB -= Di;
Fix();
}
if (!Good.size()) {
cout << sumB << endl;
}
else if (!F[0].size() || *(--F[0].end()) < *Good.begin()) {
int t = *Good.begin();
if (Bad.size()) {
int p = *(--Bad.end());
cout << 2ll * sumG - t + p + sumB << endl;
} else {
cout << 2ll * sumG - t << endl;
}
}
else {
cout << sumG + sumG + sumB << endl;
}
}
return 0;
}
|
题意
给出一个长为n的由01?三个东西构成的字符串。
?可以变成0或者1。
字符串中每有一个连续k个0或者k个1（长为k的连续段），答案就能加一，但是这些段都不能重合。
（题目把是连赢k次（对应字符串的1），或者连输k次（对应字符串的0）叫做一轮，问最多能有多少轮）
对于每个k从1到n，求最大答案。
题解
比赛的时候感觉这题有点数学，想到了按照相同长度的去处理，复杂度nlogn，然后就不会做了= =
实际上除了复杂度以外啥都没想对。
这种题一起不好算，可以在之前的基础上考虑一个一个加，也就是按照顺序一个一个算，复杂度慢慢变小。
显然答案的和是级别的。
可以有一个的做法就是先计算二分开始的最长的可能，然后排序，从大到小把每个位置加进一个set，每次计算的时候lower_bound(i+size)。
这样做其实多算了不必要的信息。
我们假设我们现在在点，要求长度为，暴力地比较了是不是有可能满足条件，一直找到了一个满足符合条件。
根据这题的特殊性质：
那当我们算长度的时候，之前算过的不满足条件的区间后面再加一个数字也不会满足条件。这些区间也不可能是答案
（因为在长为的时候就不是全或者全，的话更不是了）
我们直接去看。
用nextQ[i]表示如果i不行，下一次应该从哪个位置开始。
当长度为算完后，nexQ[i]表示从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
| #include<bits/stdc++.h>
using namespace std;
int read() {
int x; scanf("%d", &x); return x;
}
const int maxn = 1e6 + 10;
const int INF = 1e9;
int mod = 1e9 + 7;
#define ll long long
int suma[maxn], sumb[maxn], nextQ[maxn];
char s[maxn];
int n;
bool itworks(int x, int size) {
int y = x + size - 1;
return suma[y] - suma[x - 1] == (y - x + 1) || suma[y] - suma[x - 1] == 0
|| sumb[y] - sumb[x - 1] == (y - x + 1) || sumb[y] - sumb[x - 1] == 0;
}
int find_next(int x, int size) {
if (x + size - 1 > n) return x;
if (itworks(x, size)) return x;
return nextQ[x] = find_next(nextQ[x], size);
}
int main() {
#ifdef LOCAL
freopen("1.in", "r", stdin);
#endif
n = read();
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i)
suma[i] = suma[i - 1] + (s[i] == '1' || s[i] == '?'),
sumb[i] = sumb[i - 1] + (s[i] == '0' || s[i] == '?');
for (int i = 1; i <= n; ++i) nextQ[i] = i + 1;
for (int size = 1; size <= n; ++size) {
int ans = 0;
int position = 1;
while (position + size - 1 <= n) {
if (itworks(position, size)) position = position + size, ans++;
else position = find_next(position, size);
}
printf("%d\n", ans);
}
return 0;
}
|
