2022年暑期集训队选拔赛
FallenGemini

比赛前

提前一个小时去了机房,为什么呢?因为 Switch 就应该在寝室以外的地方玩

玩了会【星之卡比探索发现】,接着玩了会【动物森友会】

比赛时

比赛链接

先看了一圈题,最后又从 开始做

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
#include<bits/stdc++.h>
struct node {
int l,r,id;
};
bool cmp(node x,node y) {
return x.l < y.l;
}
int f[300000];
int lowbit(int x) {
return x & -x;
}
void add(int x,int val) {
for(int i = x; i <= 200000; i += lowbit(i))
f[i] += val;
}
int query(int x) {
int sum = 0;
for(int i = x; i ; i -= lowbit(i))
sum += f[i];
return sum;
}
int main() {
int n;
std::cin >> n;
std::vector<node> a(n);
std::vector<int> ans(n);
std::vector<int> hash(n);
int cnt = 0;
for(int i = 0; i < n; i++) {
std::cin >> a[i].l >> a[i].r;
hash[i] = a[i].r;
a[i].id = i;
}
std::sort(a.begin(), a.end(), cmp);
std::sort(hash.begin(), hash.end());
for(int i = n - 1; i >= 0; i--) {
int l = 0, r = n - 1;
int pos = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(hash[mid] < a[i].r) l = mid + 1;
else if(hash[mid] > a[i].r) r = mid - 1;
else if(hash[mid] == a[i].r) {
pos = mid;
break;
}
}
pos++;
ans[a[i].id] = query(pos);
add(pos, 1);
}
for(int i = 0; i < n; i++)
std::cout << ans[i] << '\n';
}

C

小学数学题,思想出问题了,错了两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define LL long long
int main() {
LL n,a,b;
std::cin >> n >> a >> b;
for(LL i = 2; i * i <= b; i++) {
while(a % i == 0 && b % i == 0) {
a /= i;
b /= i;
}
}
std::vector<LL> x(n);
for(LL i = 0; i < n; i++)
std::cin >> x[i];
for(LL i = 0; i < n; i++) {
LL pos = x[i] * a / b;
LL p = pos * b;
LL ans = x[i] - (p / a) - (p % a != 0);
std::cout << ans << ' ';
}
}

G

找找规律,不难发现数字只能在副对角线上移动

简单统计判断一下就行

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
#include<bits/stdc++.h>
int n,m;
int a[2000][2000],b[2000][2000];
int main() {
std::cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
std::cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
std::cin >> b[i][j];
bool flag = true;
for(int j = 1; j <= 1000; j++) {
std::priority_queue<int> A,B;
for(int i = 1; j - i + 1 > 0; i++) {
A.push(a[i][j - i + 1]);
B.push(b[i][j - i + 1]);
}
while(!A.empty()) {
if(A.top() != B.top()) flag = false;
A.pop();B.pop();
}
}
if(flag) std::cout << "YES";
else std::cout << "NO";
return 0;
}

E

简单模拟

多进行个 1e6 次就差不多行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
#define LL long long
int main() {
int a,b,c,d;
std::cin >> a >> b >> c >> d;
long double x,y,z,ans = 0;
x = (long double) a / b;
y = (long double) c / d;
z = 1;
for(int i = 1; i <= 1e6; i++) {
ans += z * x;
z = z * (1 - x) * (1 - y);
}
printf("%.12Lf\n",ans);
}

F

简单模拟

找到度数最大的点,需要的颜色数量为度数 + 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
#include<bits/stdc++.h>
int n,root = 1,ans;
std::vector<std::vector<int>> To;
std::vector<int> color;
void dfs(int u,int fa) {
std::vector<bool> book(ans + 1);
book[color[fa]] = true;
book[color[u]] = true;
int cnt = 1;
for(int v : To[u]) {
if(v == fa) continue;
while(book[cnt]) cnt++;
color[v] = cnt;
dfs(v,u);
book[cnt] = true;
}
}
int main() {
std::cin >> n;
To.resize(n + 1);
color.resize(n + 1);
for(int i = 1; i < n; i++) {
int x,y;
std::cin >> x >> y;
To[x].push_back(y);
To[y].push_back(x);
}
for(int i = 1; i <= n; i++) {
if(To[i].size() > To[root].size())
root = i;
}
ans = To[root].size() + 1;
color[root] = 1;
dfs(root, 0);
std::cout << ans << '\n';
for(int i = 1; i <= n; i++)
std::cout << color[i] << ' ';
}

B

简单

前缀和记录一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
const int mod = 1e9+7;
int f[100010],ans[100010];
int main() {
int t,k;
std::cin >> t >> k;
f[0] = 1;
for(int i = 1; i <= 100000; i++) {
f[i] = (f[i] + f[i - 1]) % mod;
f[i] = (f[i] + f[i - k]) % mod;
}
ans[0] = 0;
for(int i = 1; i <= 100000; i++)
ans[i] = (ans[i - 1] + f[i]) % mod;
for(int i = 1; i <= t; i++) {
int a,b;
std::cin >> a >> b;
int ANS = (ans[b] - ans[a - 1] + mod) % mod;
std::cout << ANS << '\n';
}
}

D

简单模拟

似乎不能开 2e5queue ,会莫名死机,返回信息却是 WA ,挺恶心的。。。

合法的序列需要满足的条件有

  • 深度单调不下降
  • 当前的点对应的父亲节点应该是满足一定序列的
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
#include<bits/stdc++.h>
int n;
std::vector<std::vector<int>> To;
std::vector<int> deep,Fa,a;
void dfs(int u,int fa) {
deep[u] = deep[fa] + 1;
for(int v : To[u]) {
if(v == fa) continue;
Fa[v] = u;
dfs(v,u);
}
}
int main() {
std::cin >> n;
To.resize(n + 1);
deep.resize(n + 1);
Fa.resize(n + 1);
a.resize(n + 1);
for(int i = 1; i < n; i++) {
int u,v;
std::cin >> u >> v;
To[u].push_back(v);
To[v].push_back(u);
}
for(int i = 1; i <= n; i++)
std::cin >> a[i];
dfs(1, 0);
bool flag = true;
int Dp = 0;
for(int i = 1; i <= n; i++) {
int u = a[i];
if(deep[u] < Dp) flag = false;
if(deep[u] > Dp) Dp = deep[u];
}

if(flag) {
std::queue<int> q[2];
int cnt = 0;
int now = 0,DP = 1;
for(int i = 1; i <= n; i++) {
int u = a[i], Deep = deep[u];
if(Deep == 1) {
q[now].push(u);
continue;
}
if(Deep != DP) {
DP = Deep;
now ^= 1;
}
if(To[u].size() != 1) q[now].push(u);
int ls = q[now ^ 1].front();
if(Fa[u] != ls) {
flag = false;
break;
}
cnt++;

if(deep[ls] == 1 && cnt == To[ls].size()) {
q[now ^ 1].pop();
cnt = 0;
}
if(deep[ls] != 1 && cnt + 1 == To[ls].size()) {
q[now ^ 1].pop();
cnt = 0;
}
}
}

if(flag) std::cout << "Yes";
else std::cout << "No";
return 0;
}

H

状压

预处理可能的情况,最多也不过是 1e2 的数量级,实测应该在 60 左右

然后四重循环

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
// 状压dp
#include<bits/stdc++.h>
int N,M,ans;
std::string a[110];
int s[110];
int use[100],sum[100],cnt;
int f[110][70][70];
void DFS(int x,int step) {
if(step >= M) {
use[++cnt] = x;
int S = 0;
for(int i = 0; i < M; i++)
if(x & (1 << i)) S++;
sum[cnt] = S;
return;
}
bool flag = true;
if(step >= 1 &&
(x & (1 << (step - 1)) ) ) flag = false;
if(step >= 2 &&
(x & (1 << (step - 2)) ) ) flag = false;
DFS(x,step + 1);
if(flag) DFS(x | (1 << step),step + 1);
}
int main() {
std::cin >> N >> M;
for(int i = 1; i <= N; i++) {
std::cin >> a[i];
for(int j = 0; j < M; j++)
if(a[i][j] == 'H') s[i] |= 1 << j;
}
DFS(0,0);
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= cnt; j++) {
if(s[i] & use[j]) continue;
for(int k = 1; k <= cnt; k++) {
if(use[j] & use[k]) continue;
for(int p = 1; p <= cnt; p++) {
if(use[j] & use[p]) continue;
f[i][j][k] = std::max(f[i][j][k],
f[i - 1][k][p] + sum[j]);
}
}
}
}
int ans = 0;
for(int i = 1; i <= cnt; i++)
for(int j = 1; j <= cnt; j++)
ans = std::max(ans,f[N][i][j]);
std::cout << ans << '\n';
return 0;
}

比赛后

为了看 提前一个小时 然后溜了

顺便取了个快递:喷射战士2!!!

QQ截图20220529170850

QQ截图20220529170908