题很水，我很菜
T1
是个字符串匹配的大水题，但是我nt的写了个不能直接算区间的BKDRhash，然后就TLE了…T了…了……
考后发现竟然还没有我第一遍交的大暴力快 （暴力yyds）
考后果断换正常的hash，但是因为 long long 、重复算了lenb - i + 1 和 把lenb - i + 1打成i而调了一个上午和中午（我是sb
T2
我一看，哟！这不tarjan求割点嘛！然后意识到一个问题，我tarjan板子忘了（现在滚去背板子,其实就这：low[to] >= dfn[x]）
考完把tarjan打上，一交，0分。然后意识到一个问题：这道题不仅仅是求割点，因为有的割点虽然是割点但是可以不经过，就成了废点，不能算。就想不出来什么容易实现的方法了（指100行以下
中午的时候PYT想出来一个特别强的算法，50多行就能A掉。他把n的祖先链上的点都标记了一边，这样求割点时再加个vis[i]就能满足要求（Nie！NB！）
码！
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
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005 * 2;
int n, m, cnt, tote;
int head[maxn];
int points[maxn];
bool vis[maxn], b[maxn];
struct EDGE {
int to, next;
} edge[maxn];
void addEdge(int from, int to) {
edge[++tote].to = to;
edge[tote].next = head[from];
head[from] = tote;
}
int timestamp, dfn[maxn], low[maxn];
void tarjan(int x) {
dfn[x] = low[x] = ++timestamp;
for (int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to;
if (!dfn[to]) {
tarjan(to);
low[x] = min(low[to], low[x]);
if (low[to] >= dfn[x])
if (x != 1 && vis[to]) {
points[++cnt] = x;
// cout << x << endl;
}
if (vis[to]) vis[x] = true;
} else
low[x] = min(low[x], dfn[to]);
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
tote = cnt = timestamp = 0;
memset(dfn, 0, sizeof(dfn));
memset(vis, false, sizeof(vis));
memset(head, 0, sizeof(head));
memset(edge, 0, sizeof(edge));
scanf("%d%d", &n, &m);
for (int i = m; i >= 1; i--) {
int f, t;
scanf("%d%d", &f, &t);
if (f == t) {
continue;
}
addEdge(f, t);
addEdge(t, f);
}
vis[n] = true;
tarjan(1);
sort(points + 1, points + 1 + cnt);
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++) {
printf("%d ", points[i]);
}
printf("\n");
}
return 0;
}
|
T3
用两个字来评价：毒瘤
考完式分享的各种奇妙的 $O>n^2$ 的算法都听了听，直到我听到了战神的思路，这不就是我考试是思路的++++版嘛
思路：
统计每个R或B左右的B或R前（后）缀和为l和r然后每次选最小值移动，然后更新存有这两个值的数组（？）
我不会更新啊
upd:经过彭师傅的指导后会了
统计完前（后）缀和之后就考虑对答案的影响，因为移动一个寿司会使l和r都发生变化
$ ans=\sum_{i=1}^{totr} min(l[i],r[i]) $
$ ans= \frac {totr*totb}{2}+\max\sum\limits_{i}^{totr}\frac{\left | l[i]-r[i] \right | }{2} $
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
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
char in[maxn];
long long lqz[maxn], rqz[maxn];
long long btot, rtot, sum, pos, neg;
priority_queue<int, vector<int>, greater<int> > q;
int main() {
long long T;
scanf("%lld", &T);
while (T--) {
memset(lqz, 0, sizeof(lqz));
memset(rqz, 0, sizeof(rqz));
btot = rtot = sum = pos = neg = 0;
while (!q.empty()) q.pop();
scanf("%s", in + 1);
long long len = strlen(in + 1);
for (long long i = 1; i <= len; i++) {
lqz[i] = lqz[i - 1];
if (in[i] == 'R')
rtot++;
else {
btot++;
lqz[i]++;
}
}//左边的前缀和
for (long long i = 1; i <= len; i++) {
if (in[i] == 'R') {
rqz[i] = btot - lqz[i];//b总数不变，右的后缀和=总个数-b的前缀和
sum += abs(lqz[i] - rqz[i]);
if ((lqz[i] - rqz[i]) > 0) {
q.push(lqz[i] - rqz[i]);
pos++;
} else {
neg++;
}
}
}
long long lazy = 0;
long long maxx = sum;
for (long long i = 1; i < len; i++) {
if (in[i] == 'B') {
lazy++; // 和线段树上的懒标记差不多↓，因为若q.top()>=3就break掉了，无法再弹出
sum += neg * 2; //负值对总和做正贡献
while (!q.empty()) {
if (q.top() - lazy * 2 <= 0) {
if (q.top() - lazy * 2 == 0) {
sum -= 2;
neg++;
pos--;
q.pop();
} else {
neg++;
pos--;
q.pop();//小于0时不能再减了，但还要按负的情况处理
}
} else {
break;
}
}
sum -= 2 * pos;
maxx = max(maxx, sum);
} else {
pos++;
neg--;
q.push(2 * lazy + btot);
}
}
cout << (btot * rtot - maxx) / 2 << endl;
}
|