Top

2019 Wannafly Camp day5

自闭感受

参加Camp第五天，今天是dls的计算几何专场，可是说是几何板子讲解，也是这几天听得最明白，学得最多的一天。dls从基础的点积叉积到线到圆等，感觉非常Nice，相对dls说。

下午依旧是训练赛，比昨天感觉好不少，真的是越来越亲民了，还以为今天要爆零自闭呢。同时经过今天的计算几何，感觉自己整理一套计算几何板子真的非常有必要，结束后也该操手了。

上题解

A - Cactus Draw

把节点的深度做x坐标，儿子序做y坐标，进行DFS遍历，因为是棵树所以肯定不会交边

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
struct edge{
    int v,next;
}e[maxn];
int head[maxn],hcnt=0;
int u[maxn],v[maxn];
void add(int u,int v){
    e[hcnt]=edge{v,head[u]};
    head[u]=hcnt++;
}
pair<int,int> point[maxn];
bool vi[maxn];
int vis[maxn];
void dfs(int u,int x){
    if(vi[u])return;
    vi[u]=1;
    if(!vis[x])
    vis[x]=1;
    point[u]=make_pair(x,vis[x]++);
    for(int i=head[u];i>=0;i=e[i].next){
        int v=e[i].v;
        if(vi[v])continue;
        dfs(v,x+1);
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    scanf("%d%d",&u[i],&v[i]),add(u[i],v[i]),add(v[i],u[i]);
    dfs(1,1);
    for(int i=1;i<=n;i++)
    cout<<point[i].first<<' '<<point[i].second<<endl;
    return 0;
}

C - Division

把每个数先压到优先队列中，每次操作取队顶元素除2再压进去，同时判断下队顶是否为0，如果为0就没必要继续操作了。因为数大小1e9所以每个数最多就操作30次。

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
priority_queue<int>a;
int main(){
    int n,k,aa;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&aa);
        a.push(aa);
    }
    ll ans=0;
    for(int i=0;i<k;i++){
        aa=a.top();
        a.pop();
        if(aa==0){
            break;
        }
        a.push(aa/2);
    }
    while(!a.empty()){
        if(a.top()==0)break;
        ans+=a.top();
        a.pop();
    }
    printf("%lld\n",ans);
    return 0;
}

I - Sorting

将小于等于X的数当做0，大于x的数当做1，因为交换后相对顺序不会变，就可以预处理出各自的前缀和，根据处于的位置计算值。用线段树来维护区间内01的个数，Ok啦

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define ls rt<<1
#define rs rt<<1|1
int a[maxn],b[maxn];
long long int r0[maxn],r1[maxn];
int cnt1=1,cnt0=1;

struct tree{
    int l,r;
    int x;
    int sum;
    int lazy;
}t[maxn*4];
void pushdown(int rt){

    if(t[rt].lazy==1){
        t[ls].sum=t[ls].r-t[ls].l+1;
        t[rs].sum=t[rs].r-t[rs].l+1;
        t[ls].lazy=1;
        t[rs].lazy=1;
    }
    else if(t[rt].lazy==-1){
        t[ls].sum=0;
        t[rs].sum=0;
        t[ls].lazy=-1;
        t[rs].lazy=-1;
    }
    t[rt].lazy=0;
}
void build(int rt,int l,int r){
    t[rt].l=l;
    t[rt].r=r;
    t[rt].x=0;
    t[rt].sum=0;
    t[rt].lazy=0;
    if(t[rt].l==t[rt].r){
        return ;
    }
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void dadd(int rt,int x){
    if(t[rt].l==x && t[rt].r==x){
        t[rt].x=1;
        t[rt].sum++;
        return;
    }
    int mid=t[rt].l+t[rt].r>>1;
    if(mid<x)
    dadd(rs,x);
    else
    dadd(ls,x);
    t[rt].sum=t[ls].sum+t[rs].sum;
}
void change(int rt,int ql,int qr,int l,int r,int x,int type){

    if(ql>=l && qr<=r){
            if(x==0){
                 t[rt].sum=0;
                 t[rt].lazy=-1;
            }
            else{
                t[rt].sum=qr-ql+1;
                t[rt].lazy=1;
            }

        return ;
    }
    pushdown(rt);
    int mid=ql+qr>>1;
    if(l<=mid)
        change(ls,ql,mid,l,r,x,type);
    if(r>mid)
        change(rs,mid+1,qr,l,r,x,type);
    t[rt].sum=t[ls].sum+t[rs].sum;
}
int query(int rt,int ql,int qr,int l,int r){
    if(l>r)return 0;
     if(ql>=l && qr<=r){
        return t[rt].sum;
    }
    pushdown(rt);
    int mid=ql+qr>>1;
    int sum=0;
    if(l<=mid)
      sum+=  query(ls,ql,mid,l,r);
    if(r>mid)
    sum+=query(rs,mid+1,qr,l,r);
    return sum;
}
int main(){

    int n,q,x;
    cin>>n>>q>>x;
    build(1,1,n);
    for(int i=1;i<=n;i++){
         cin>>a[i];
        if(a[i]<=x)r0[cnt0]=r0[cnt0++-1]+a[i];
        else dadd(1,i),r1[cnt1]=r1[cnt1++-1]+a[i];
    }
    int o,L,R;

    for(int i=1;i<=q;i++){
          cin>>o>>L>>R;
          if(o==1){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=query(1,1,n,1,L-1);//前面有k1个1
            int S=R-L+1;
            int k0=S-k;
            int k00=L-1-k1;
            long long int sum1=r1[k1+k]-r1[k1];
            long long int sum0=r0[ S-k + L-1-k1 ]-r0[L-1-k1];
            cout<<sum1 + sum0<<endl;
          }
          else if(o==2){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=R-L+1-k;//k1个0
            change(1,1,n,L,L+k1-1,0,0);
            change(1,1,n,L+k1,R,1,1);
          }
          else if(o==3){
            int k=query(1,1,n,L,R);//区间内有k个1
            int k1=R-L+1-k;//k1个0
            change(1,1,n,L,L+k-1,1,1);
            change(1,1,n,L+k,R,0,0);
          }
    }

    return 0;
}

J - Special Judge

对任意两条边都进行判断是否相交，如果相交则在判断是否是相交于端点，不过不是则ans++。是的话在判断下是不是重合边，如果不是重合边就不符合，是就ans++.

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
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	double x;
	double y;
};
bool judge(node a,node b,node c,node d)
{
	if(min(a.x,b.x) <= max(c.x,d.x) && min(c.x,d.x) <= max(a.x,b.x) && min(a.y,b.y) <= max(c.y,d.y) &&min(c.y,d.y)<=max(a.y,b.y))
	{

		double u,v,w,z;//保存叉乘
          u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
          v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
          w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
          z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
          return (u*v<=0.00000001 && w*z<=0.00000001); //浮点数判断大小
	}
	return false;
}
bool onsegment(node pi,node pj,node Q)
{
    if((Q.x-pi.x)*(pj.y-pi.y)==(pj.x-pi.x)*(Q.y-pi.y)&&min(pi.x,pj.x)<=Q.x&&Q.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=Q.y&&Q.y<=max(pi.y,pj.y)){
        return true;
    }else{
        return false;
    }
}
bool check(node a,node b,node c,node d){
    double len=(a.x-b.x)*(c.y-d.y)-(c.x-d.x)*(a.y-b.y);
    if(len==0)return 1;
    else return 0;
}
const int maxn=1020;
struct Node{
    int a,b;
}mp[2*maxn];
node p[maxn];
int main(){
    int n,m;
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&mp[i].a,&mp[i].b);
    }
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=m;i++){
        for(int j=i+1;j<=m;j++){
                if(judge(p[mp[i].a],p[mp[i].b],p[mp[j].a],p[mp[j].b])){
                    if(mp[i].a==mp[j].a||mp[i].a==mp[j].b||mp[i].b==mp[j].a||mp[i].b==mp[j].b){	//判断是否是交于端点
                        if(check(p[mp[i].a],p[mp[i].b],p[mp[j].a],p[mp[j].b])){	//看两边是否平行
								//如果平行，通过判断一边的两端点是否在另外一边上
                                if((onsegment(p[mp[j].a],p[mp[j].b],p[mp[i].a])&&onsegment(p[mp[j].a],p[mp[j].b],p[mp[i].b]))||(onsegment(p[mp[i].a],p[mp[i].b],p[mp[j].a])&&onsegment(p[mp[i].a],p[mp[i].b],p[mp[j].b])))
                                ans++;
                        }
                    }
                    else ans++;
                }
        }
    }
    printf("%d\n",ans);
	return 0;
}


未经允许不得转载： Anoyer's Blog » 2019 Wannafly Camp day5
 Camp
 上一篇