| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 9/12 | Ø | Ø | Ø | Ø | Ø | Ø | Ø | . | . | Ø | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
$x$ 轴上有一堆立着的圆形靶子，每次在 $(x,y)$ 射击，输出射到了哪个靶子。靶子可以动态添加，但是不会互相交错。
解题思路
一个固定 $x$ 上的靶子数是 $O(\log n)$ 个的，故离散化之后暴力线段树维护一下每个 $x$ 上面靶子的集合即可。
AC代码
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
typedef long long ll;
using namespace std;
struct Q{int op,x,y;}q[N];
int cnt,c[N];
int L[N<<2],R[N<<2];
set<int>tr[N<<2];
void build(int p,int l,int r){
L[p]=l;R[p]=r;
if(l==r)return;
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
}
void modify(int p,int l,int r,int x,int flag){
if(L[p]>r||R[p]<l)return;
if(L[p]>=l&&R[p]<=r){
if(flag)tr[p].insert(x);
else tr[p].erase(x);
return;
}
modify(p<<1,l,r,x,flag);
modify(p<<1|1,l,r,x,flag);
}
void query(int p,int l,int r,set<int>&res){
if(L[p]>r||R[p]<l)return;
for(auto x:tr[p])res.insert(x);
if(L[p]>=l&&R[p]<=r)return;
query(p<<1,l,r,res);
query(p<<1|1,l,r,res);
}
int main(){
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&q[i].op,&q[i].x,&q[i].y);
if(q[i].op==2)c[++cnt]=q[i].x;
}
sort(c+1,c+1+cnt);
cnt=unique(c+1,c+1+cnt)-c-1;
build(1,1,cnt);
auto lower_id=[&](const int x){return lower_bound(c+1,c+1+cnt,x)-c;};
auto upper_id=[&](const int x){return upper_bound(c+1,c+1+cnt,x)-c;};
for(i=1;i<=n;i++){
if(q[i].op==1){
int id1=lower_id(q[i].x-q[i].y);
int id2=upper_id(q[i].x+q[i].y)-1;
modify(1,id1,id2,i,1);
}else{
set<int>res;
int id=lower_id(q[i].x),found=0;
query(1,id,id,res);
for(auto x:res){
if(1LL*(q[x].x-q[i].x)*(q[x].x-q[i].x)+
1LL*(q[x].y-q[i].y)*(q[x].y-q[i].y)<
1LL*q[x].y*q[x].y){
found=1;
int id1=lower_id(q[x].x-q[x].y);
int id2=upper_id(q[x].x+q[x].y)-1;
modify(1,id1,id2,x,0);
printf("%d\n",x);
}
}
if(!found)printf("-1\n");
}
}
return 0;
}
B
题目描述
签到题
解题思路
分类讨论即可。
AC代码
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
typedef long long ll;
using namespace std;
int a[4],p[4];
int w,h,flag;
void update(int x,int y){
if(x>y)swap(x,y);
if(x<=w&&y<=h)flag=1;
}
void solve(int a,int b,int c){
update(2*c+b,2*a+2*c); // 1, 2
update(2*a+2*c,a+b+c); // 3, 5, 6
update(2*c+b,2*a+2*c); // 4
update(a+2*b,a+c+b+c); // 7
update(a+b+c,a+b+c+b); // 8
update(a+c,b+a+b+c+b); // 9
update(c+a+b,a+c+b+a); // 10
update(c+a+b,b+c+b+a); // 11
}
int main(){
int i;
for(i=1;i<=3;i++)p[i]=i;
scanf("%d%d%d",&a[1],&a[2],&a[3]);
scanf("%d%d",&w,&h);
if(w>h)swap(w,h);
do{solve(a[p[1]],a[p[2]],a[p[3]]);}while(next_permutation(p+1,p+4));
if(flag)printf("Yes");
else printf("No");
return 0;
}
C
题目描述
给一个无自环的有向连通图，求一个删掉 $m$ 条边后满足所有点互相连通的方案。
解题思路
经典套路题，就是保证所有点都能到 $1$，$1$ 能到所有点。搜一遍即可。
AC代码
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
typedef long long ll;
using namespace std;
vector<pii>G[N],rG[N];
int u[N],v[N],choose[N],v1[N],v2[N];
void dfs(int p,vector<pii>*G,int*vis){
vis[p]=1;
for(auto pr:G[p]){
auto q=pr.fi;
if(!vis[q]){
choose[pr.se]=1;
dfs(q,G,vis);
}
}
}
int main(){
int T,i,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)rG[i].clear(),G[i].clear(),v1[i]=v2[i]=0;
for(i=1;i<=m;i++){
scanf("%d%d",&u[i],&v[i]);
G[u[i]].pb(mp(v[i],i));
rG[v[i]].pb(mp(u[i],i));
choose[i]=0;
}
dfs(1,G,v1);
dfs(1,rG,v2);
int cnt=0;
for(i=1;i<=m;i++)if(!choose[i]){
if(++cnt<=m-2*n)printf("%d %d\n",u[i],v[i]);
}
}
return 0;
}
D
题目描述
在第一卦限放正方体。给定 $Oxy,Oxz,Oyz$ 三个平面上投影面积 $\le 100$，求方案。
解题思路
实际在一个平面上构造就可以。
2
3
0100
1000
可以通过旋转一下坐标系简化讨论过程。
AC代码
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
typedef long long ll;
using namespace std;
int vis[110][110];
struct A{
int x,id;
int X,Y,Z;
bool operator<(const A&b)const{return x<b.x;}
}a[N];
int main(){
int i,j;
for(i=0;i<3;i++)scanf("%d",&a[i].x),a[i].id=i;
a[0].X=a[0].Y=1;a[0].Z=0;
a[1].X=a[1].Z=1;a[1].Y=0;
a[2].Z=a[2].Y=1;a[2].X=0;
vector<tuple<int,int,int>>ans;
sort(a,a+3);
if(a[0].x*a[1].x<a[2].x)return printf("-1"),0;
for(i=0;i<a[0].x;i++){
ans.pb(mt(0,i,i));
vis[i][i]=1;
}
for(i=a[0].x;i<a[1].x;i++){
ans.pb(mt(0,a[0].x-1,i));
vis[i][a[0].x-1]=1;
}
int cnt=a[2].x-a[1].x;
for(i=0;i<a[0].x;i++){
for(j=0;j<a[1].x;j++){
if(vis[i][j]||cnt==0)continue;
vis[i][j]=1;
ans.pb(mt(0,i,j));
cnt--;
}
}
printf("%d\n",ans.size());
int pos[]={0,1,2};
auto get_index=[&](int x,int y){
return a[x].X&&a[y].X?0:
a[x].Y&&a[y].Y?1:2;
};
pos[get_index(0,1)]=0;
pos[get_index(0,2)]=1;
pos[get_index(1,2)]=2;
for(auto pr:ans){
int b[3]={get<0>(pr),get<1>(pr),get<2>(pr)};
printf("%d %d %d\n",b[pos[0]],b[pos[1]],b[pos[2]]);
}
return 0;
}
E
题目描述
签到题
解题思路
略
AC代码
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
typedef long long ll;
using namespace std;
int main(){
int n,i,a,cnt=0;
scanf("%d",&n);
multiset<int>S;
vector<int>unicorn;
for(i=0;i<n;i++){
scanf("%d",&a);
if(a>0)S.insert(a);
else if(a==0)cnt++;
else{
auto it=S.find(-a);
if(it==S.end()){
if(cnt>0){
cnt--;
unicorn.pb(-a);
}else{
return printf("No"),0;
}
}else{
S.erase(it);
}
}
}
while(cnt--)unicorn.pb(1);
printf("Yes\n");
for(auto p:unicorn)printf("%d ",p);
return 0;
}
F
题目描述
在二维网格放最少个数长度为 $n$ 的
L形通道，要求 $(0,0)(a,b)$ 相连。解题思路
贪心即可，同样旋转坐标系简化讨论过程。
AC代码
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
typedef long long ll;
using namespace std;
vector<pair<pii,pii>>ans;
int n;
void move(int &x,int &y,int tx,int ty,int dir){
if(dir)ans.pb(mp(mp(x,min(ty-n,y)),mp(max(tx,x+n),ty)));
else ans.pb(mp(mp(tx,max(ty,y+n)),mp(min(tx-n,x),y)));
x=tx,y=ty;
}
int main(){
int T,a,b;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&a,&b,&n);n--;
ans.clear();
int flipx=0,flipy=0;
if(a<0)flipx=1,a=-a;
if(b<0)flipy=1,b=-b;
int cx=0,cy=0,dir=0; // dir: 0 up, 1 right
while(a-cx>n||b-cy>n){
move(cx,cy,cx+min(n,a-cx),cy+min(n,b-cy),dir);
if(a-cx<b-cy)cy++,dir=0;
else cx++,dir=1;
}
move(cx,cy,a,b,dir);
printf("%d\n",ans.size());
for(auto pr:ans){
auto c1=pr.fi,c2=pr.se;
int x1=c1.fi,y1=c1.se,x2=c2.fi,y2=c2.se;
if(flipx)x1=-x1,x2=-x2;
if(flipy)y1=-y1,y2=-y2;
assert(abs(x1-x2)==n&&abs(y1-y2)==n);
printf("%d %d %d %d\n",x1,y1,x2,y2);
}
}
return 0;
}
G
题目描述
给三个长度为 $n$ 的序列 $a,b,c(a_i<b_i<c_i)$。
对于数对 $(x,y)$ 满足 $1\le x<y\le n-r+1$，定义 $I_x=[x,x+r-1]$，
函数 $f(x,y)=\sum_{i\in I_x \text{ and }i\in I_y}c_i+\sum_{i\in I_x\oplus i\in I_y}b_i+\sum_{i\text{ in other conditions}}a_i$
求第 $r$ 小的 $f$。
解题思路
考虑二分答案 $p$，算出有多少对 $(x,y)$ 的 $f(x,y)\le p$。
先把 $a$ 扔掉，即 $b\leftarrow b-a,c\leftarrow c-a$。设 $g_i=\sum_{j=0}^{r-1}b_{i-j}$ ，分两类情况讨论：
- $x+r-1<y$，枚举 $i=x+r-1$ ，$y\in [i+1,n-r+1]$，对应贡献为 $g_i+g_{y+r-1}$，可以用
set维护所有 $y$ 对应值，二分查一下小于某个值有多少个即可。- $y\le x+r-1$，枚举 $i$ 的时候 $y\in[i-r+2,i]$，对应贡献为 $g_i+g_{y+r-1}+\sum_{k=y}^{i}(c_k-2b_k)$，前缀和维护一下也可以用
set维护。由于要得到小于某个数的个数，使用
pb_ds的平衡树。AC代码
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
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pli,null_type,less<pli>,
rb_tree_tag,tree_order_statistics_node_update>order_set;
int a[N],b[N],c[N],r,k,n;
ll f[N],sc[N];
int check(ll x){
// <= x count
int i,res=0;
order_set S; // not multiset!
for(i=r;i+r-1<=n;i++)S.insert(mp(f[i+r-1],i));
for(i=r;i+r<=n;i++){
// [i-r+1, i] [j, j+r-1] j>i
S.erase(mp(f[i+r-1],i));
res+=S.order_of_key(mp(x-f[i],n+1)); // how many elements less than x
}
S.clear();
for(i=1;i<r&&i+r-1<=n;i++)S.insert(mp(f[i+r-1]-sc[i-1],i));
for(i=r;i<n;i++){
S.erase(mp(f[i]-sc[i-r],i-r+1));
if(r!=1&&i+r-1<=n)S.insert(mp(f[i+r-1]-sc[i-1],i));
res+=S.order_of_key(mp(x-(f[i]+sc[i]),n+1));
}
return res;
}
int main(){
int i;
ll s=0,L=0,R=0;
scanf("%d%d%d",&n,&r,&k);
for(i=1;i<=n;i++)scanf("%d",&a[i]),s+=a[i];
for(i=1;i<=n;i++)scanf("%d",&b[i]),b[i]-=a[i],R+=b[i];
for(i=1;i<=n;i++)scanf("%d",&c[i]),c[i]-=a[i],R+=c[i];
for(i=1;i<=r;i++)f[r]+=b[i];
for(i=r+1;i<=n;i++)f[i]=f[i-1]+b[i]-b[i-r];
for(i=1;i<=n;i++)sc[i]=sc[i-1]+c[i]-2*b[i];
while(L<R){
ll mid=(L+R)>>1;
if(check(mid)<k)L=mid+1;
else R=mid;
}
printf("%lld",L+s);
return 0;
}
H
题目描述
解题思路
AC代码
2
I
题目描述
解题思路
AC代码
2
J
题目描述
给一个 $n\le 3000,m\le 3000$ 的边权图，当走一条路径时，选择边权最高的 $k$ 个边权之和作为花费，问从 $1$ 走到 $n$ 的最小花费。
解题思路
如果最短路小于 $k$ 条边那就直接算最短路。
否则，考虑所有 $\ge k$ 条边的情况：边权最高的 $k$ 个边权设为 $c_1\le c_2\le \dots \le c_k$，则需要将所有小于 $c_1$ 的边置零。于是枚举最小边权 $w=c_1$，将所有边边权改为 $\max(0,c-w)$，最短路 $+kw$ 就是最小边权为 $w$ 的最短路。
这个做法有点妙，是看题解才知道的，记录一下。
AC代码
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
typedef long long ll;
using namespace std;
vector<pii>G[N];
ll dis[N];
int vis[N],n;
ll solve(int w){
priority_queue<pli>Q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
Q.push(mp(0,1));
while(!Q.empty()){
int p=Q.top().se;Q.pop();
if(vis[p])continue;
vis[p]=1;
for(auto pr:G[p]){
int q=pr.fi;
int l=max(0,pr.se-w);
if(dis[q]>dis[p]+l){
dis[q]=dis[p]+l;
Q.push(mp(-dis[q],q));
}
}
}
return dis[n];
}
int main(){
int i,m,k;
scanf("%d%d%d",&n,&m,&k);
vector<int>vec;vec.pb(0);
for(i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G[u].pb(mp(v,w));
G[v].pb(mp(u,w));
vec.pb(w);
}
ll ans=1e18;
for(auto x:vec)ans=min(ans,solve(x)+1LL*k*x);
printf("%lld",ans);
return 0;
}
K
题目描述
解题思路
AC代码
2
L
题目描述
给定一个树上的 $f\le 1e5$ 条点路径，问是否满足：两两之间，要么交集为零，要么有包含关系。
解题思路
把涉及到的所有点拿出来，必然是数条链（否则必然不满足条件），于是逐链处理即可。对于每一条链，按照左端点升、右端点降排序，是一个明显的栈结构，维护一下即可。
AC代码
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
typedef long long ll;
using namespace std;
vector<int>G[N];
vector<int>chain[N],intervals[N];
int n;
void add(int a,int b){
G[a].pb(b);
G[b].pb(a);
}
int dep[N],lg[N],fa[22][N];
vector<int>dfn;
void dfs(int p,int f){
fa[0][p]=f;
dep[p]=dep[f]+1;
dfn.pb(p);
for(auto q:G[p]){
if(q==f)continue;
dfs(q,p);
}
}
void init_lca(){
int i,j;
for(i=1;i<20;i++)
for(j=1;j<=n;j++)
fa[i][j]=fa[i-1][fa[i-1][j]];
for(i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
}
int lca(int x,int y){
int i;
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])x=fa[lg[dep[x]-dep[y]]][x];
if(x==y)return x;
for(i=lg[dep[x]];i>=0;i--)
if(fa[i][x]!=fa[i][y])
x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
void dfs4chain(int p,int f,vector<int>&points){
points.pb(p);
for(auto q:chain[p]){
if(q==f)continue;
dfs4chain(q,p,points);
}
}
pii sta[N];
int top,d[N],pos[N];
int main(){
int f,i,j,m;
scanf("%d%d",&n,&f);
for(i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
dfs(1,0);
init_lca();
for(i=0;i<f;i++){
int u,v;
scanf("%d%d",&u,&v);
int l=lca(u,v);
d[u]++;d[v]++;d[l]-=2;
intervals[u].pb(v);
}
for(i=dfn.size()-1;i>=0;i--){
int p=dfn[i];
d[fa[0][p]]+=d[p];
}
for(i=1;i<=n;i++)if(d[i])chain[i].pb(fa[0][i]),chain[fa[0][i]].pb(i);
for(i=1;i<=n;i++)if(chain[i].size()>2)return printf("No"),0;
for(i=1;i<=n;i++){
if(chain[i].size()==1){
vector<int>points;
dfs4chain(i,0,points);
for(j=0;j<points.size();j++)pos[points[j]]=j;
vector<pii>inter;
for(auto x:points)for(auto v:intervals[x]){
int p=x,q=v;
if(pos[p]>pos[q])swap(p,q);
inter.pb(mp(pos[p],pos[q]));
}
sort(inter.begin(),inter.end(),[&](const pii&i1,const pii&i2){
return i1.fi==i2.fi?i1.se>i2.se:i1.fi<i2.fi;
});
top=0;
for(auto pr:inter){
int l=pr.fi,r=pr.se;
while(top&&r>sta[top].se){
if(l<=sta[top].se)return printf("No"),0;
top--;
}
sta[++top]=pr;
}
}
}
printf("Yes");
return 0;
}