翻车笔记_ E46 Div2 A~F [图论, 联通块, tarjan, 线段树, dp]

考试的状态和平时做题的状态天壤之别

qwq

A

我也不知道为啥我写了这么长

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 <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAXN (100 + 5)
#define INF (0X7FFFFFFF)
using namespace std;
bool cmp(string& x, string& y)
{
if (x.length() != y.length())
return x.length() < y.length();
else
return x < y;
}
int pd(string x, string y)
{
int re = 0;
for (int i = 0; i < x.length(); i++)
if (x[i] != y[i])
++re;
return re;
}
int main()
{
string s[MAXN], t[MAXN];
int n, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) cin >> t[i];
sort(s + 1, s + n + 1, cmp);
sort(t + 1, t + n + 1, cmp);
bool viss[MAXN], vist[MAXN];
memset(viss, false, sizeof(viss));
memset(vist, false, sizeof(vist));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (viss[i])
break;
if (vist[j])
continue;
if (s[i] == t[j])
viss[i] = vist[j] = true;
}
for (int i = 1; i <= n; i++)
{
if (viss[i])
continue;
int dqans = INF, ansi = 0;
for (int j = 1; j <= n; j++)
if (!vist[j] && t[j].length() == s[i].length())
{
if (pd(s[i], t[j]) < dqans)
dqans = pd(s[i], t[j]), ansi = j;
}
vist[ansi] = true;
ans += dqans;
}
cout << ans;
return 0;
}

B

贪心找翻转的最大收益就行了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100000 + 5)
#define MAXM (1000000000 + 5)
#define INF (0x7fffffff)
#define LL long long
using namespace std;
int n, m, a[MAXN];
void solve()
{
int fa[MAXN];
for (int i = 1; i <= n; i++)
if (i & 1)
fa[i] = fa[i - 1] + a[i] - a[i - 1];
else
fa[i] = fa[i - 1];

int frdark = 0, frlight = 0, ansi = n, maxc = -INF, ans = 0;
for (int i = n; i >= 1; i--)
{
if (i & 1)
frdark += a[i + 1] - a[i];
else
frlight += a[i + 1] - a[i];
if (maxc < frdark - frlight)
maxc = frdark - frlight, ansi = i, ans = frdark;
}
printf("%d\n", max(fa[n], fa[ansi] + ans - 1));
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);

if (n %2 == 0)
a[++n] = m;
a[n + 1] = m;
solve();
return 0;
}

C

离散化前缀和随便做, 听说他们都打了线段树Orz

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define LL long long
#define pii pair<LL, LL>
using namespace std;
int n, f[MAXN << 1], a[MAXN << 1];
LL sora[MAXN << 1];
pii s[MAXN];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &s[i].first, &s[i].second), ++s[i].second, sora[++sora[0]] = s[i].first, sora[++sora[0]] = s[i].second;
sort(sora + 1, sora + sora[0] + 1);
sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
for (int i = 1; i <= n; i++)
{
LL le = lower_bound(sora + 1, sora + sora[0] + 1, s[i].first) - sora, ri = lower_bound(sora + 1, sora + sora[0] + 1, s[i].second) - sora;
++f[le], --f[ri];
}
LL cnt[MAXN];
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= sora[0] + 1; i++)
f[i] += f[i - 1];
for (int i = 1; i <= sora[0] + 1; i++)
cnt[f[i]] += sora[i + 1] - sora[i];
for (int i = 1; i <= n; i++)
printf("%lld ", cnt[i]);
return 0;
}

D

考场上想的dp状态非常鬼畜…要不然是记录了能分成几个好数组, 要不然是记录了左右端点, 然后就一直$n ^ 3$凉了

后来翻$Claris$爷爷代码, 发现根本不用记录这玩意23333

f[i]以为第i位为第一个好数组的第一个数, 到n能凑出的好子序列的数量

转移的时候

  • 初始为$f_i = \mathrm C_{n - i}^{a_i}$
  • 转移的时候$f_i += \sum{f_{j + 1} \cdot \mathrm C_{j - i}^{a_i}} \,\,\,\, j \in [i + a_i, n)$, $j$就代表我们枚举的分界限, $f_{j + 1}$代表后面的部分, $\mathrm C_{j - i}^{a_i}$代表在界限之前可以新加入的好子数组, 乘法代表我们可以和后面的任意一个好子序列组成新的好子序列(而且乘法也有去重的作用, 如果$f_{j + 1} =0$的话也不会重复记录$\mathrm C_{j - i}^{a_i}$)

$Claris$ Orz

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define LL long long
#define Refun (998244353ll)
using namespace std;
int n, a[MAXN];
LL f[MAXN], c[MAXN][MAXN];
int main()
{
c[0][0] = 1;
for (int i = 1; i < MAXN; i++)
for (int j = 0; j <= i; j++)
c[i][j] = (c[i - 1][j] + (j > 0 ? c[i - 1][j - 1] : 0)) % Refun;

scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n - 1; i >= 1; i--)
{
if (a[i] <= 0) continue;
if (a[i] <= n - i)
f[i] = c[n - i][a[i]];
for (int j = i + a[i]; j < n; j++)
if (a[i] <= j - i)
f[i] = (f[i] + (f[j + 1] * c[j - i][a[i]]) % Refun) % Refun;
}
LL ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans + f[i]) % Refun;
printf("%lld", ans);
return 0;
}

E

简单题, 只要把所有的联通块缩点(或者说只保留桥), 然后跑直径就行了

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <set>
#define MAXN (300000 + 5)
using namespace std;
struct edg
{
int from, to, next;
}b[MAXN << 1], bn[MAXN << 1];
int g[MAXN], cntb, gn[MAXN], cntn, n, m, belong[MAXN], dfn[MAXN], low[MAXN], cntdfn, f[MAXN];
stack<int> gary;
void tarjan(int dq, int fa)
{
dfn[dq] = low[dq] = ++cntdfn;
gary.push(dq);
for (int i = g[dq]; i; i = b[i].next)
if (!dfn[b[i].to])
{
tarjan(b[i].to, dq);
low[dq] = min(low[dq], low[b[i].to]);
}
else if (b[i].to != fa)
low[dq] = min(low[dq], dfn[b[i].to]);
if (low[dq] == dfn[dq])
{
while (!gary.empty() && gary.top() != dq)
belong[gary.top()] = dq, gary.pop();
if (!gary.empty())
gary.pop();
belong[dq] = dq;
}
}
void adn(edg* bx, int* gx, int& cntx, int from, int to)
{
bx[++cntx].next = gx[from];
bx[cntx].from = from, bx[cntx].to = to;
gx[from] = cntx;
}
void dfs(int dq, int fa)
{
for (int i = gn[dq]; i; i = bn[i].next)
if (bn[i].to != fa)
{
f[bn[i].to] = f[dq] + 1;
dfs(bn[i].to, dq);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1, srx, sry; i <= m; i++)
{
scanf("%d%d", &srx, &sry);
adn(b, g, cntb, srx, sry);
adn(b, g, cntb, sry, srx);
}
tarjan(1, 1);
set<int> te[MAXN];
for (int i = 1; i <= n; i++)
for (int j = g[i]; j; j = b[j].next)
if (belong[i] != belong[b[j].to] && te[belong[i]].find(belong[b[j].to]) == te[belong[i]].end())
{
te[belong[i]].insert(belong[b[j].to]);
te[belong[b[j].to]].insert(belong[i]);
adn(bn, gn, cntn, belong[i], belong[b[j].to]);
adn(bn, gn, cntn, belong[b[j].to], belong[i]);
}
dfs(belong[1], belong[1]);
int ans = 0, ansi;
for (int i = 1; i <= n; i++)
if (ans < f[belong[i]])
ans = f[belong[i]], ansi = belong[i];
memset(f, 0, sizeof(f));
dfs(ansi, ansi);
ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, f[belong[i]]);
printf("%d", ans);
return 0;
}

F

要口胡了qwq

我们搞一个nex数组, 把询问按照左端点排序, 然后从左到右扫描

遇到一个数, 我们把他的nex[i]nex[nex[i]]用标记永久化置为a[i], 如果已经有数了, 就撤销后调整边界重新赋值, 让左边界靠左的右边界也靠左, 然后查询的时候就直接在线段树上单点查询就行了

我猜这样是对的23333333

By 沙茶 Cansult