NOIP 模拟 2017 03 17

发表于 | 分类于

NOIP 模拟 Day1

AUTHOR：Colin

计算几何

题意描述

花花对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：

首先，花花会在$ x $轴正半轴和$ y $轴正半轴分别挑选 $n$ 个点。随后，他将$ x $轴的点与$ y $轴的点一一连接，形成 $n $条线段，并保证任意两条线段不相交。花花确定这种连接方式有且仅
有一种。最后，花花会给出 m 个询问。对于每个询问，将会给定一个点 $P(x_p ,y_p )$，问线段$OP $（$O $为坐标原点）与 $n$ 条线段会产生多少个交点？

输入格式

第 1 行包含一个正整数$ n$，表示线段的数量；

第 2 行包含 $n $个正整数，表示花花在$ x $轴选取的点的横坐标；

第 3 行包含$ n $个正整数，表示花花在$ y$ 轴选取的点的纵坐标；

第 4 行包含一个正整数 $m$，表示询问数量；

随后 $m $行，每行包含两个正整数$ x_p$ 和 $y_p$ ，表示询问中给定的点的横、纵坐标。

输出格式

共 m 行，每行包含一个非负整数，表示你对这条询问给出的答案。

样例输入

3
4 5 3
3 5 4
2
1 1
3 3

样例输出

0
3

样例解释

3 条线段分别为：

$(3,0) − (0,3)$

$(4,0) − (0,4)$

$(5,0) − (0,5)$

$(0,0) − (1,1)$ 不与他们有交点，答案为 $0$。

$(0,0) − (3,3)$ 与三条线段均有交点，答案为 $3$。

数据规模与约定

• 对于 $40%$ 的数据：$n,m ≤ 10$；

• 另有 $20%$ 的数据：$n,m ≤ 100$；

• 另有 $20%$ 的数据：$n,m ≤ 1000$；

• 对于 $100%$ 的数据：$n,m ≤ 10^5$ ,$1 ≤ x,y < 2^{31}$

题解

比较水的一道题，首先因为给出的直线没有交点，所以一定是按顺序依次连接，快排一下就可以了，可以用终点和给出的$x,y$轴上的点以及原点构成的四边形面积和直线与坐标轴围成的三角形面积来比较

code

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=2e5+1e3;
long long n,m,x[N],y[N];
struct P{
    long long x,y;	
}pt[N];
int main()
{
    freopen("geometry.in","r",stdin);
    freopen("geometry.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&y[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&pt[i].x,&pt[i].y);
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);
    for(int i=1;i<=m;i++)
    {
        int l=0,r=n+1;
        while(r-l>1)
        {
            int mid=(l+r)>>1;
            if((x[mid]*pt[i].y)+(y[mid]*pt[i].x)>=(x[mid]*y[mid]))
                l=mid;
            else
                r=mid;
        }
        printf("%d\n",l);
    }
}

花花的聚会

题意描述

花花住在 H 国。H 国有 $n $个城市，其中$ 1 $号城市为其首都。城市间有$ n − 1 $条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都。事实上，从任何一个城市
走到首都的路径是唯一的。过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H 国一共有 $m $种过路券，每张过路券以三个整数表示：$v k w$：你可以在城市$ v $以价格 $w $买到一张过路券。这张券可以使用$ k $次。这意味着，拿着这张券通过了$ k $条道路之后，这张券就不能再使用了。请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。

花花家在首都。他有$ q $位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。

花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？

输入格式

输入的第一行包含两个空格隔开的整数$ n$ 和$ m$，表示 H 国的城市数量和过路券的种数。
之后的 $n − 1$ 行各自包含两个数$ a_i $和$ b_i$ ，代表城市 $a_i$ 到城市 $b_i$ 间有一条单向道路。
之后的 m 行每行包括三个整数 $v_i$ ,$k_i$ 和 $w_i$ ，表示一种过路券。

下一行包含一个整数$ q$，表示花花朋友的数量。

之后的 $q $行各自包含一个整数，表示花花朋友的所在城市。

输出格式

输出共 $q$ 行，每一行代表一位朋友的路费。

样例输入

7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
4
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7

样例输出

10
22
5

样例解释

对于第一位朋友，他在 5 号城市只能购买一种过路券，花费 10 元并且可以使用 3 次。这足够他走到首都，因此总花费是 10 元。

对于第二位朋友，他在 6 号城市只能购买 20 元的过路券，并且只能使用一次。之后，他可以在 3 号城市购买 2 元，可以使用 3 次的过路券走到首都。总花费是 22 元。

对于第三位朋友，他在 7 号城市可以购买两种过路券。他可以花 3 元买一张可以使用 2次的券，然后在 3 号城市再买一张 2 元，可以使用 3 次的券，走到首都。总花费是 5 元，而且
其他的购买方式不会比这种更省钱。

数据规模与约定

• 对于 40% 的数据：$n,m,q$ ≤ 10,$w_i ≤ 10$；
• 另有 20% 的数据：$n,m,q ≤ 500$,$w_i ≤ 100$；
• 另有 20% 的数据：$n,m,q ≤ 5000$,$w_i ≤ 1000$；
• 对于 100% 的数据：$n,m,q ≤ 10^5$ ,$w_i ≤ 10000$,$1 ≤ v_i$ ,$k_i ≤ n$。

题解

多么裸的树形DP，但是数据范围较大，需要一些特殊的处理方法，可以倍增，也可以树剖，这里选择了倍增实现。

设：
$$f[i]$$
为$i$到根节点最小花费

则
$$f[i]=min(f[j]+w[i][x])$$
$$anc[i]=j \&\& dep[j]-dep[i]>=k[i]$$

code

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
#include<iostream>
   #include<algorithm>
   #include<cstdio>
   using namespace std;
   const int inf=0x7fffffff;
   const int N=1e5+1;
   const int maxlogn=21;
   int deep[N],head[N],head2[N];
   long long st[N][maxlogn],minn[N][maxlogn],f[N];
   int tot,tot2,n,m,qu;
   struct edg{
       int t,ne;
   }e[N*2];
   struct edg2{
       int k,w,ne;
   }e2[N*2];
   void in(int x,int y)
   {
       e[++tot].t=y;
       e[tot].ne=head[x];
       head[x]=tot;
       return;
   }
   void in2(int x,int k,int w)
   {
       e2[++tot2].k=k;
       e2[tot2].w=w;
       e2[tot2].ne=head2[x];
       head2[x]=tot2;
       return;
   }
   void getf(int x,int pre)
   {
       st[x][0]=pre;
       minn[x][0]=f[pre];
       for(int i=1;i<maxlogn;i++)
       {
           st[x][i]=st[st[x][i-1]][i-1];
           minn[x][i]=min(minn[x][i-1],minn[st[x][i-1]][i-1]);
       }
       f[x]=x==1?0:inf;
       for(int i=head2[x];i;i=e2[i].ne)
       {
           long long tmp=inf,y=x,k=e2[i].k,p=0;
           while(k)
           {
               if(k&1)tmp=min(tmp,minn[y][p]),y=st[y][p];
               p++;k>>=1;
           }
           f[x]=min(f[x],tmp+e2[i].w);
       }
       for(int i=head[x];i;i=e[i].ne)
       {
           int y=e[i].t;
           if(y!=pre)getf(y,x);
       }
       return;
   }
   int main()
   {
   //    freopen("party.in","r",stdin);
   //    freopen("party.out","w",stdout);
       scanf("%d%d",&n,&m);
       for(int i=1,x,y;i<n;i++)
           scanf("%d%d",&x,&y),in(x,y),in(y,x);
       for(int i=1,x,k,w;i<=m;i++)
           scanf("%d%d%d",&x,&k,&w),in2(x,k,w);
       scanf("%d",&qu);getf(1,1);
       for(int i=1,x;i<=qu;i++)
       {
           scanf("%d",&x);printf("%d\n",f[x]);
       }
   }

文本编辑器

描述

体面在此不再描述
（0_0）好心的链接

链表维护，加上SPLAY翻转操作，SPLAY还不会,不过借用lazy tag的思想，就不用了，就给个ProSTKhala大神的题解吧

code

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
#include<iostream>
   #include <cstdio>
   #include <cstring>
   using namespace std;
   const int N=1e7+1;
   int tot,m,pos[2],cnt[2],pre[N],next[N];
   char opreator,ch[N],str[N];
   int move(){getchar();return getchar()=='L'?0:1;}
   void in(int opreator,char c)
   {
       ++tot;
       ch[tot]=c;
       int u=pos[opreator],v=next[u];
       pre[tot]=u;next[tot]=v;
       next[u]=tot;pre[v]=tot;
       if (cnt[opreator^1]>=cnt[opreator])cnt[opreator^1]++;
       pos[opreator]=tot;cnt[opreator]++;
       if (pos[opreator^1]==u)pos[opreator^1]=tot;
       printf("T\n");
   }
   void ll(int opreator)
   {
       if (pos[opreator]==1){printf("F\n");return;}
       int u=pos[opreator],v=pre[u];
       if (next[v]!=u)swap(next[v],pre[v]);
       pos[opreator]=v; cnt[opreator]--;
       printf("T\n");
   }
   void rl(int opreator)
   {
       if (next[pos[opreator]]==2){printf("F\n");return;}
       int u=next[pos[opreator]],v=next[u];
       if(pre[v]!=u)swap(next[v],pre[v]);
       pos[opreator]=u;cnt[opreator]++;
       printf("T\n");    
   }
   void D(int opreator)
   {
       if (next[pos[opreator]]== 2){printf("F\n");return;}
       int u = pos[opreator], v = next[u], w = next[v];
       if (pre[w]!=v) swap(next[w], pre[w]);
       if (cnt[opreator^1]>cnt[opreator])cnt[opreator^1]--;
       if (pos[opreator^1]==v)pos[opreator^1]=u;
       next[u]= w;pre[w]=u;
       printf("T\n");
   }
   void R()
   {
       if (cnt[1]-cnt[0]<=0){printf("F\n");return;}
       if (cnt[1]-cnt[0]==1){printf("T\n");return;}
       int now=pos[0],ne=next[now],c=pos[1],d=next[c];
       swap(pre[ne], next[ne]);swap(pre[c],next[c]);
       next[now]=c;pre[c]=now;next[ne]=d;pre[d]=ne;
       pos[1]=ne;
       printf("T\n");
   }
   void show()
   {
       int u=1;
       while(true)
       {
           if(pre[next[u]]!= u)swap(pre[next[u]],next[next[u]]);
           u=next[u];
           if (u==2)break;
           putchar(ch[u]);
       }
       printf("\n");
   }
   void init()
   {
       tot=2;
       pre[1]=-1;next[1]= 2;
       pre[2]=1;next[2]=-1;
       pos[0]=pos[1]=cnt[0]=cnt[1]=1;
       int len=strlen(str);
       for(int i=0;i<len;i++)
       {
           ++tot;
           ch[tot]=str[i];
           pre[tot]= i==0?1:tot-1;
           next[tot]= i==len-1?2:tot+1;
       }
       if(len>0)
       {
           next[1]=3;pre[2]=tot;
           pos[1]=tot;cnt[1]=len+1;
       }
   }
   int act()
   {
       if(opreator=='<')         ll(move());
       if(opreator=='>')         rl(move());
       if(opreator=='I')
       {
           int d=move();
           char c=getchar();
           while (c<33||c>126)c=getchar();
           in(d,c);
       }
       if (opreator=='D')         D(move());
       if (opreator=='R')         R();
       if (opreator=='S')         show();
   }
   int main()
   {
   //    freopen("editor.in","r", stdin);
   //    freopen("editor.out","w", stdout);
       scanf("%s",str);
       init();
       scanf("%d",&m);
       for (int i=1;i<=m;i++)
       {
           getchar();
           opreator=getchar();
           while (opreator!='<'&& opreator!='>'&&!(opreator >='A'&& opreator <='Z'))opreator=getchar();
           act();
       }
       return 0;
   }