The 19th Zhejiang University Programming Contest

rank solved A B C D E F G H I J
114 6 O O O . O . O Ø . O

Record

XLor(背锅):

  • 贡献了全队的所有罚时,锅++。

  • H 忘记变换缩点后的坐标,锅++。

  • H wa了之后,确定算法是真的,没有出数据 check,锅++。

A Thanks, TuSimple!

Solved by Rainstar, XLor(+1).

$0$ 和 $1$ 必须配对。

分两类排序,对于每一个男生二分到大于其身高的最小女生,或者小于其身高的最大女生。

B Even Number Theory

Solved by Forsaken(+2).

C Robot Cleaner I

Solved by Forsaken, Rainstar, XLor(+6).

模拟很多很多轮即可。

E Potion

Solved by Forsaken.

G Postman

Solved by Forsaken.

H Rescue the Princess

UpSolved by XLor(+10).

给定一个 $n$ 个点 $m$ 条边的无向图,每次询问是否存在两条路径 $u$ 到 $v$ 和 $u$ 到 $w$,使得两条路径没有交。

注意到 $u,v,w$ 在一个边双联通分量中,一定存在路径。

考虑对图边双联通分量缩点,变成询问一棵树上有没有这样的两条路径,观察到 $u$ 一定在 $v$ 和 $w$ 的树上路径上。

具体条件是 $LCA(v,w)$ 是 $u$ 的祖先,$u$ 至少是 $v$ 和 $w$ 中一个的祖先,判断祖先用 $dfs$ 序的区间是否包含来判断。

边双联通分量缩点后的树上,判断 $v$ 到 $w$ 的路径上是否有 $u$。

J Extended Twin Composite Number

Solved by XLor(+3).

输出 $8n$ 和 $9n$。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int n, m, a[maxn], b[maxn], p[maxn], q[maxn];

int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int i = 1; i <= m; i++) scanf("%d", b + i);
multiset<int> v1[2], v2[2];
for (int i = 1, p; i <= n; i++) {
scanf("%d", &p); v1[p].insert(a[i]);
}
for (int i = 1, p; i <= m; i++) {
scanf("%d", &p); v2[p].insert(b[i]);
}
int ans = 0;
for (int x: v1[0]) {
auto it = v2[1].lower_bound(x);
if (it == v2[1].begin()) continue;
it--; ans++; v2[1].erase(it);
}
for (int x: v1[1]) {
auto it = v2[0].upper_bound(x);
if (it == v2[0].end()) continue;
ans++; v2[0].erase(it);
}
printf("%d\n", ans);
}
return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
T = int(input())

def cal(n, p):
if n < p: return 0
return cal(n // p, p) + n // p

for i in range(T):
n = int(input())
n /= 2
ans = cal(n, 2) + n
print(int(ans))

C

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=2005;
int T;
int n,m;
int a,b;ll k;
char s[max_n],ss[max_n];
int mp[max_n][max_n];
int cnt[max_n][max_n];
char opt(int x,int y)
{
int t=81*mp[x][y]+27*mp[x-1][y]+9*mp[x+1][y]+3*mp[x][y-1]+mp[x][y+1];
t++;
return s[t];
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%lld",&n,&m,&a,&b,&k);
scanf(" %s",s+1);
for(int i=1;i<=n;i++)
{
scanf(" %s",ss+1);
for(int j=1;j<=m;j++)mp[i][j]=ss[j]-'0';
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)cnt[i][j]=0;
}
int x=a,y=b;
int ans=0;
for(ll i=1;i<=k;i++)
{
cnt[x][y]++;
char op=opt(x,y);
if(op=='U')
{
int nx=x-1,ny=y;
if(mp[nx][ny]==1||cnt[nx][ny]>=10000)break;
x=nx,y=ny;
}
else if(op=='D')
{
int nx=x+1,ny=y;
if(mp[nx][ny]==1||cnt[nx][ny]>=10000)break;
x=nx,y=ny;
}
else if(op=='L')
{
int nx=x,ny=y-1;
if(mp[nx][ny]==1||cnt[nx][ny]>=10000)break;
x=nx,y=ny;
}
else if(op=='R')
{
int nx=x,ny=y+1;
if(mp[nx][ny]==1||cnt[nx][ny]>=10000)break;
x=nx,y=ny;
}
else if(op=='P')
{
if(mp[x][y]==2)ans++,mp[x][y]=0;
else break;
}
else if(op=='I')break;
}
printf("%d\n",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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=105;
ll a[max_n],b[max_n];
int n;
int T;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",a+i);
for(int i=1;i<=n;i++)scanf("%lld",b+i);
bool f=true;
for(int i=n;i>=1;i--)
{
if(a[i]>b[i])f=false;
else b[i-1]+=b[i]-a[i];
}
if(f)printf("Yes\n");
else printf("No\n");
}
return 0;
}

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
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=100005;
int n,k;
int T;
int a[max_n];
vector<int> v[2];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",a+i);
v[0].clear();v[1].clear();
ll ans=0;
for(int i=1;i<=n;i++)if(a[i]>0)v[0].push_back(a[i]);
for(int i=1;i<=n;i++)if(a[i]<0)v[1].push_back(-a[i]);
sort(v[0].begin(),v[0].end());
sort(v[1].begin(),v[1].end());
for(int i=0;i<2;i++)
{
int sz=v[i].size();
for(int j=sz-1;j>=0;j-=k)
{
ans+=v[i][j]*2;
}
}
int mv=0;
if(v[0].size())mv=max(mv,v[0].back());
if(v[1].size())mv=max(mv,v[1].back());
ans-=mv;
printf("%lld\n",ans);
}
return 0;
}

H

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#ifdef XLor
#define dbg(args...) do {cout << #args << " -> "; err(args);} while (0)
#else
#define dbg(...)
#endif
void err() {std::cout << std::endl;}
template<typename T, typename...Args>
void err(T a, Args...args){std::cout << a << ' '; err(args...);}
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;

int pre[maxn];
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
void join(int x, int y) {
x = find(x); y = find(y);
if (x == y) return ;
pre[x] = y;
}

vector<int> edge[maxn];
int n, m, q;

int cnt, bel[maxn]; // important!
namespace Tarjan {
int tot, dfn[maxn], low[maxn], st[maxn], top, vis[maxn];
void clear(int n) {
tot = top = cnt = 0;
for (int i = 1; i <= n; i++) {
edge[i].clear(); dfn[i] = vis[i] = bel[i] = 0;
}
}
void dfs(int u, int f) {
dfn[u] = low[u] = ++tot;
st[++top] = u; vis[u] = 1;
int k = 0;
for (int& v: edge[u]) {
if (v == f && !k) {
k++; continue;
}
if (!dfn[v]) {
dfs(v, u); low[u] = min(low[u], low[v]);
} else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
cnt++; int t = 0;
do {
t = st[top--];
bel[t] = cnt;
vis[t] = 0;
} while (t != u);
}
}
void scc(int n, vector<int> * g) {
for (int i = 1; i <= n; i++) if (!dfn[i]) Tarjan::dfs(i, 0);
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i <= n; i++) {
int u = bel[i];
for (int& x: edge[i]) {
int v = bel[x];
if (u != v) {
g[u].push_back(v);
}
}
}
}
}

namespace Tree {
vector<int> block[maxn];
int tin[maxn], tout[maxn], vis[maxn], tot;
int dp[maxn][22], dep[maxn];
void dfs(int u, int fa){
tin[u] = ++tot;
vis[u] = 1;
dp[u][0] = fa;
dep[u] = dep[fa] + 1;
for (int& v: block[u]) {
if (v == fa) continue;
dfs(v, u);
}
tout[u] = tot;
}
int qlca(int x, int y){
if (dep[x] < dep[y]) swap(x, y);
int tmp = dep[x] - dep[y];
for (int i = 0; tmp; i++, tmp >>= 1)
if (tmp & 1) x = dp[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--){
if (dp[x][i] != dp[y][i]){
x = dp[x][i]; y = dp[y][i];
}
}
return dp[x][0];
}
void init() {
for (int i = 0; i <= cnt; i++) {
vis[i] = 0; ms(dp[i], 0);
}
dep[0] = tot = 0;
for (int i = 1; i <= cnt; i++) if (!vis[i]) {
dfs(i, 0);
}
for (int j = 1; j < 20; j++)
for (int i = 1; i <= cnt; i++)
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int check(int p, int u) {
return tin[p] <= tin[u] && tout[p] >= tout[u];
}
}

int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &q);
Tarjan::clear(n);
for (int i = 1; i <= n; i++) {
pre[i] = i;
}
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
edge[u].push_back(v); edge[v].push_back(u);
join(u, v);
}
Tarjan::scc(n, Tree::block);
Tree::init();
while (q--) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
if (find(u) != find(v) || find(u) != find(w)) {
puts("No"); continue;
}
u = bel[u]; v = bel[v]; w = bel[w];
int g = Tree::qlca(v, w);
if (Tree::check(g, u)) {
if (Tree::check(u, v) || Tree::check(u, w)) puts("Yes");
else puts("No");
} else puts("No");
}
}
return 0;
}

J

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 100000 + 5;

int main() {
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
printf("%lld %lld\n", 8ll * n, 9ll * n);
}
return 0;
}