前言
关于我想整理思路结果全忘了这件事（
复盘
B - Sample Game
期望$DP$。设$f(x)$为$E[x]$，$g(x)$为$E[x^2]$，最后所求的期望即为$g(0)$。
需要注意的是对$E((x+1)^2)$的处理，要使用两个数组，转化为$E(x^2)+2 * E(x) + 1$进行递推。
这一题也有生成函数的推导方法，但是感觉没有期望$DP$容易理解。
一份比较优秀的期望$DP$推导博客：2021牛客多校#4 B-Sample Game(概率DP)
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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
template<typename T>
void Print(T value){
std::cout << value << '\n';
}
template<typename Head, typename... Rail>
void Print(Head head, Rail... rail){
std::cout << head << ", ";
Print(rail...);
}
int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int qpow(int a, int b, int p){
if(b == 0) return 1;
int tmp = qpow(a, b / 2, p);
tmp = (tmp * tmp) % p;
if(b & 1) tmp = (tmp * a) % p;
return tmp;
}
const int p = 998244353;
int inv(int val){
if(val < 0) val = (val % p) + p;
return qpow(val, p - 2, p);
}
int n, sw, w[maxn], pi[maxn], f[maxn], g[maxn];
signed main(void)
{
n = read();
for(int i = 1; i <= n; i++) w[i] = read(), sw = (sw + w[i]) % p;
for(int i = 1; i <= n; i++) pi[i] = (w[i] * inv(sw)) % p;
for(int i = n; i >= 0; i--)
{
int sum = 0;
for(int j = i + 1; j <= n; j++)
sum = (sum + ((pi[j] * f[j]) % p)) % p;
f[i] = ((1 + sum) * inv(1 - pi[i])) % p;
}
for(int i = n; i >= 0; i--)
{
int sum = 0;
for(int j = i + 1; j <= n; j++)
sum = ((sum + ((pi[j] * g[j]) % p) % p) + ((2 * pi[j] * f[j]) % p)) % p;
g[i] = (((((1 + 2 * f[i] * pi[i]) % p) + sum) % p) * inv(1 - pi[i])) % p;
}
printf("%lld\n", g[0]);
return 0;
}
|
C - LCS
构造题，一般来说优先考虑约束最弱的条件，再依次推导，尝试构造一个长度最小的解。
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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int a, b, c, n;
string s1, s2, s3;
int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
signed main(void)
{
int f1 = 0, f2 = 0, f3 = 0;
a = read(); b = read(); c = read(); n = read();
int ra = a, rb = b, rc = c;
if(ra > rb) swap(ra, rb);
if(ra > rc) swap(ra, rc);
if(rb > rc) swap(rb, rc);
for(int i = 1; i <= ra; i++)
s1 += 'a', s2 += 'a', s3 += 'a';
for(int i = 1; i <= a - ra; i++)
s1 += 'g', s2 += 'g';
for(int i = 1; i <= b - ra; i++)
s2 += 'b', s3 += 'b';
for(int i = 1; i <= c - ra; i++)
s1 += 'c', s3 += 'c';
while(s1.length() < n) s1 += 'd';
while(s2.length() < n) s2 += 'e';
while(s3.length() < n) s3 += 'f';
if(s1.length() > n || s2.length() > n || s3.length() > n) cout << "NO\n";
else
{
cout << s1 << '\n';
cout << s2 << '\n';
cout << s3 << '\n';
}
return 0;
}
|
E - Tree Xor
狗题。出题人利用了一个很巧妙的二进制位的性质，使得这一题可以区间维护。
首先把问题简化，令任意一个$w[i] = 0$，由此可以唯一推导出树上其他节点的值$w’[i]$。
而后，令最初的$w[i]=a$，可以发现，树上其他节点的值均会$xor \ a$，也就是说，我们需要解决：
存在多少个$a$，使得$a \ xor \ w’[i] \in [l_i,r_i]\ $。
可以转化为，将每一$w’[i] \ xor \ [l_i, r_i]$解出，得到若干个区间，最后对这些区间求交，则得到所有可取的$a$。
本题的难点就在这里，普通情况下$[l_i, r_i] \ xor \ C$得到的是不连续的区间，难以进行统计。
这里构造一棵线段树，最开始的时候，维护的左右端点为$[(000 \dots 00)_2, (111 \dots 11)_2]$。
这是为什么呢？以一个较小的例子引入：
$[0/000, 7/111] \rightarrow [0/000, 3/011], [4/100, 7/111] \rightarrow [0/000, 1/001],[2/010, 3/011],[4/100,5/101],[6/110, 7/111]$
可以看出，前$x$位二进制相同，而后$y$位均为$(000 \dots 00)_2$和$(111 \dots 11)_2$。
而任何数$C$在异或后$y$位为$(000 \dots 00)_2 \rightarrow (111 \dots 11)_2$的区间后
得到的数字仍在$(000 \dots 00)_2 \rightarrow (111 \dots 11)_2$内，由此保证了区间的连续。
因此，只需要对前$x$位异或。最后得到的区间就是：$(@@@\dots@@0000)_2, (@@@\dots@@0000)_2 + len$
其中，$@@@$为前$x$位异或后得到的值，而$len$是原来区间长度。
最后求一个区间交即可。
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>
#define maxn 800005
#define int long long
using namespace std;
int n, ll[maxn], rr[maxn], wn[maxn];
int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int k, head[maxn];
struct Edge{
int to;
int nxt;
int weight;
}E[maxn];
void add(int u, int v, int w){
E[k].to = v;
E[k].nxt = head[u];
E[k].weight = w;
head[u] = k++;
}
map<int, int> mp;
void calc(int lf, int rt, int wi){
int len = rt - lf + 1;
int nlf = (lf ^ wi) & (~(len - 1));
int nrt = nlf + len;
mp[nlf]++; mp[nrt]--;
}
void modify(int lf, int rt, int wl, int wr, int val){
if(lf > wr || rt < wl){
return;
}
if(wl <= lf && rt <= wr){
calc(lf, rt, val); return;
}
int mid = (lf + rt) / 2;
modify(lf, mid, wl, wr, val);
modify(mid + 1, rt, wl, wr, val);
}
void dfs(int now, int fa, int val){
wn[now] = val;
for(int i = head[now]; ~i; i = E[i].nxt)
{
if(E[i].to == fa) continue;
dfs(E[i].to, now, val ^ E[i].weight);
}
}
signed main(void)
{
memset(head, -1, sizeof(head));
n = read();
for(int i = 1; i <= n; i++)
ll[i] = read(), rr[i] = read();
for(int i = 1; i <= n - 1; i++)
{
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
dfs(1, 0, 0);
for(int i = 1; i <= n; i++)
modify(0, (1 << 30) - 1, ll[i], rr[i], wn[i]);
int s = 0, las = 0, ans = 0;
for(auto x : mp){
if(s >= n) ans += x.first - las;
s += x.second;
las = x.first;
}
printf("%lld\n", ans);
return 0;
}
|
F - Just a joke
签到题。之前读的时候差点读假了QwQ
没有环的连通分量，实际上就是一棵树。
因此，若选择操作一，删除了一条边之后，会剩下一个孤立的点，或两个连通分量。
如果删掉一条边之后剩下一个孤立的点，那么这个删除对获胜没有半点帮助。
如果是两个连通分量，则需要进一步推导。最终可以推出胜负只和连通分量的数目与环的数目有关。
对两个数目的和求一下奇偶性就能做出来了。
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
|
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, cnt;
int uset[maxn];
int find(int x){
return x == uset[x] ? x : uset[x] = find(uset[x]);
}
void unioon(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx == fy)
{
cnt++;
return;
}
uset[fx] = fy;
}
int main(void)
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) uset[i] = i;
for(int i = 1; i <= m; i++)
{
int u, v;
scanf("%d %d", &u, &v);
unioon(u, v);
}
for(int i = 1; i <= n; i++)
if(find(i) == i) cnt++;
printf(cnt & 1 ? "Alice\n" : "Bob\n");
return 0;
}
|
事实上还能更加简单，不需要并查集维护。
Just a Joker
I - Inverse Pair
签到题。当且仅当$x$在$x+1$后面的时候，构造$b[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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int n, ans;
int a[maxn], o[maxn], tmp[maxn];
void merge(int lf, int rt){
if(lf == rt) return;
int mid = (lf + rt) / 2;
merge(lf, mid);
merge(mid + 1, rt);
int i = lf, j = mid + 1, k = lf;
while(i <= mid && j <= rt)
{
if(o[i] > o[j])
tmp[k++] = o[j++], ans += mid - i + 1;
else
tmp[k++] = o[i++];
}
while(i <= mid) tmp[k++] = o[i++];
while(j <= rt) tmp[k++] = o[j++];
for(int i = lf; i <= rt; i++) o[i] = tmp[i];
}
set<int> s1;
int vis[maxn];
signed main(void)
{
scanf("%lld", &n);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]), o[i] = a[i];
merge(1, n);
int flag = 0;
for(int i = 1; i <= n; i++) s1.insert(a[i]);
for(int i = 1; i <= n; i++)
{
s1.erase(a[i]);
if(!vis[a[i]] && !vis[a[i] - 1] && s1.count(a[i] - 1))
{
vis[a[i] - 1] = 1;
flag++;
}
vis[a[i]] = 1;
}
printf("%lld\n", ans - flag);
return 0;
}
|
J - Average
前置知识：二分求最大平均值的写法（虽然是板子，但是比赛时候写挂了…）
不知道为什么比赛脑抽写了尺取，喜提3.23
主要是将序列平均值转化为利用前缀和$O(n)$求的非负序列问题，再进行$check$就可以了。
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
|
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int read(){
int x = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int n, m, x, y;
int a[maxn], b[maxn];
double s[maxn];
bool check(int num[], int len, int lim, double avg){
for(int i = 1; i <= len; i++)
s[i] = s[i - 1] + num[i] - avg;
double minn = 0;
for(int i = lim; i <= len; i++)
{
if(s[i] >= minn) return true;
minn = min(minn, s[i - lim + 1]);
}
return false;
}
double solve(int num[], int len, int lim){
double lf = 0, rt = 1e5;
while(fabs(rt - lf) > 1e-8)
{
double mid = (lf + rt) / 2;
check(num, len, lim, mid) ? lf = mid : rt = mid;
}
return lf;
}
signed main(void)
{
n = read(); m = read(); x = read(); y = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++) b[i] = read();
double ans1 = solve(a, n, x);
double ans2 = solve(b, m, y);
printf("%.10lf", ans1 + ans2);
return 0;
}
|