17南宁网络赛

77 阅读 0 评论 51 点赞

我是靠谱客的博主端庄蜜蜂，最近开发中收集的这篇文章主要介绍17南宁网络赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

G. Finding the Radius for an Inserted Circle

题目:链接

让求第k个内切圆的半径 r[k]

这题我们没做出来,主要是因为我发现的太晚了......

一开始看到的时候觉得图看起来太复杂就没去看....

最后还剩二十分钟的时候开始做,本来应该也是可以过的,结果读错输入格式了,然后就悲剧了...... 差点完成绝杀啊!!!

根据勾股定理很容易推出公式 r[i] = (√3 * R - R - 2 * c[i-1] )² / ( 2 * √3 * R - 4 * c[i-1] )

其中 c[i] 是 r[i] 的前缀和.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 double r[23];
 4 double c[23];
 5 int main(){
 6     int t;
 7     //freopen("in.txt","r",stdin);
 8     scanf("%d",&t);
 9     for(int i =0; i<=11;i++){
10          r[i]=c[i]=0;
11     }
12     double R;
13     int k;
14     scanf("%lf", &R);
15     for(int i = 1; i <= 10; i++){
16         double temp = (sqrt(3)-1)*R - 2*c[i-1];
17         r[i]=temp/(2*sqrt(3)*R-4*c[i-1])*temp;
18         c[i]=c[i-1]+r[i];
19     }
20     while(t--) {
21         scanf("%d", &k);
22         int a=r[k];
23         printf("%d %dn",k, a);
24     }
25     scanf("%d",&k);
26     return 0;
27 }

View Code

发现大家好像都不是很爱会几何题的样子~

F. Overlapping Rectangles

题库链接

题意:给n个矩形, 让求面积并.

之前做过的一道题,离散化 + 扫描线 + 线段树....

可是还是浪费了很多时间,因为昨天做了和这个很相似的题目,只不过那个是让找任意多边形面积的边界,思路就跑偏了,这题矩形比较特殊直接线段树+扫描线搞定~

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define lson l,m,rt<<1
 5 #define rson m,r,rt<<1|1
 6 using namespace std;
 7 const int maxn=2210;  //需要离散的x坐标数
 8 int cnt[maxn<<2];    //标记该线段是否被选
 9 double sum[maxn<<2];  //被选择的部分线段总长度
10 double X[maxn<<2];  //离散化
11 struct seg
12 {
13     double l,r;
14     double h;
15     int s;  //标记
16     seg(){}
17     seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s){}
18     bool operator < (const seg &cmp) const
19     {
20         return h<cmp.h;
21     }
22 }ss[maxn];
23 
24 void pushup(int rt,int l,int r)
25 {
26     if(cnt[rt]) sum[rt]=X[r]-X[l];  //如果该线段标记被完全选择，则长度为全长。。
27     else if(l+1==r) sum[rt]=0;   //若未被完全选择，且该线段只有一段，则长度为0
28     else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; //未被完全选择，且不止一段，则长度为被选择的部分
29 }
30 
31 void update(int L,int R,int c,int l,int r,int rt)
32 {
33     if(L<=l&&r<=R)
34     {
35         cnt[rt]+=c;  // 选则或者删除一次该线段
36         pushup(rt,l,r);
37         return ;
38     }
39     int m=(l+r)>>1;
40     if(L<m) update(L,R,c,lson);
41     if(m<R) update(L,R,c,rson);
42     pushup(rt,l,r);
43 }
44 int BIN(double key,int n,double X[])
45 {
46     int l=0,r=n-1;
47     while(l<=r)
48     {
49         int m=(l+r)>>1;
50         if(X[m]==key) return m;
51         if(X[m]<key) l=m+1;
52         else r=m-1;
53     }
54     return -1;
55 }
56 int main()
57 {
58     int n,cas=0;
59     //freopen("in.txt", "r", stdin);
60     while(scanf("%d",&n)&&n)
61     {
62         int m=0;
63         while(n--)
64         {
65             double a,b,c,d;
66             scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
67             X[m]=a;
68             ss[m++]=seg(a,c,b,1);
69             X[m]=c;
70             ss[m++]=seg(a,c,d,-1);
71         }
72         sort(X,X+m);
73         sort(ss,ss+m);
74         //离散化
75         int k=1;
76         for(int i=1;i<m;i++)
77             if(X[i]!=X[i-1]) X[k++]=X[i];
78 
79         memset(cnt,0,sizeof(cnt));
80         memset(sum,0,sizeof(sum));
81         double ans=0;
82         for(int i=0;i<m-1;i++)  //最上面的线段不用处理
83         {
84             int l=BIN(ss[i].l,k,X);
85             int r=BIN(ss[i].r,k,X);
86             if(l<r) update(l,r,ss[i].s,0,k-1,1);
87             ans+=sum[1]*(ss[i+1].h-ss[i].h);
88         }
89         printf("%.0lfn",ans);
90     }
91     puts("*");
92     return 0;
93 }

View Code

B. Train Seats Reservation

题目链接

题意: 告诉每批人上下车的站点,问公交车最少安排多少个座位.

本来想着扫描线,数据比较小,直接暴力~

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[110];
 4 int main(){
 5     int n;
 6     int s,t,k;
 7     while(scanf("%d", &n) && n) {
 8         memset(a, 0, sizeof(a));
 9         for(int i = 0; i < n; i++){
10             scanf("%d %d %d", &s, &t, &k);
11             for(int j = s; j < t; j++) a[j]+=k;
12         }
13         int ans = 0;
14         for(int i = 1; i <= 100; i++)
15             ans = max(a[i], ans);
16         printf("%dn", ans);
17     }
18     puts("*");
19     return 0;
20 }

View Code

M. Frequent Subsets Problem

题目链接

题意:给一个n排列的m个子集, 给一个参数r, 问n排列的所有子集中有多少个也是给出的m个集合中至少(m * r) 个集合的子集.

用二进制压一下,统计每一种集合出现的次数.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 double r;
 5 int a[1<<21];
 6 
 7 int check(int sum, int x) {
 8     for(int i = 1; i <= sum; i <<= 1) {
 9         if((i&x) && (!(sum&i))) return 0;
10     }
11     return 1;
12 }
13 int main(){
14     scanf("%d %lf", &n, &r);
15     getchar();
16     string s;
17     int k=0;
18     while(getline(cin,s)){
19         k++;
20         istringstream ss(s);
21         int x, sum = 0;
22         while(ss>>x) {
23             x--;
24             sum += (1<<x);
25         }
26         for(int i = 1; i <= sum; i++){
27             if(check(sum,i)) a[i]++;
28         }
29     }
30     k = ceil(k * r);
31     n = (1<<n);
32     int res = 0;
33     for(int i = 1; i <=n; i++) if(a[i] >= k) res++;
34     printf("%dn", res);
35 }

View Code

L. The Heaviest Non-decreasing Subsequence Problem

题目链接

题意:带权重的不下降子序列.

要用nlogn的做法

因为权重较小,直接把权拆成1.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6+10;
 4 const int inf = 1e9+10;
 5 int a[maxn], d[maxn], g[maxn];
 6 int main(){
 7     int n = 0, x;
 8     while(scanf("%d", &x)!=EOF){
 9         if(x >= 10000) {
10             x -= 10000;
11             a[++n] = x;
12             a[++n] = x;
13             a[++n] = x;
14             a[++n] = x;
15             a[++n] = x;
16         } else if(x >= 0) {
17             a[++n] = x;
18         }
19     }
20     for(int i = 0; i < maxn; i++) g[i] = inf;
21     for(int i = 1; i <= n; i++) {
22         int k = upper_bound(g+1, g+maxn, a[i]) - g;
23         d[i] = k;
24         g[k] = a[i];
25     }
26     int ans = lower_bound(g+1, g+maxn, inf) - g -1;
27     printf("%dn", ans);
28 }

View Code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6+10;
 4 const int inf = 1e9+10;
 5 int a[maxn], d[maxn];
 6 int main(){
 7     int n = 0, x;
 8     while(scanf("%d", &x)!=EOF){
 9         if(x >= 10000) {
10             x -= 10000;
11             a[++n] = x;
12             a[++n] = x;
13             a[++n] = x;
14             a[++n] = x;
15             a[++n] = x;
16         } else if(x >= 0) {
17             a[++n] = x;
18         }
19     }
20     int len = 1;
21     d[1] = a[1];
22     for(int i = 2; i <= n; i++) {
23         if(a[i] >= d[len]) d[++len] = a[i];
24         else{
25             int j = upper_bound(d+1, d+1+len, a[i]) - d;
26             d[j] = a[i];
27         }
28     }
29     printf("%dn", len);
30 }

View Code

J. Minimum Distance in a Star Graph

题库链接

题意: n维完全图,让求任意两点间的最短距离.

思路:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 15;
 4 int a[maxn], b[maxn];
 5 int n;
 6 int get(int x) {
 7     for(int i = 0; i < n; i++) if(b[i] == x) return i;
 8 }
 9 int ok(){
10     for(int i = 0; i < n; i++) {
11         if(a[i] != b[i]) return 0;
12     }
13     return 1;
14 }
15 int main(){
16     //freopen("in.txt", "r", stdin);
17     scanf("%d", &n);
18     int t = 5;
19     int x,y;
20     while(t--) {
21         scanf("%d %d", &x, &y);
22         int pos = 0;
23         while(x) {
24             a[pos++] = x % 10;
25             x /= 10;
26         }
27         pos = 0;
28         while(y) {
29             b[pos++] = y % 10;
30             y /= 10;
31         }
32         for(int i = 0; i < n/2; i++) {
33             swap(a[i], a[n-i-1]);
34             swap(b[i], b[n-i-1]);
35         }
36         int cnt = 0;
37         while(!ok()) {
38             if(a[0] == b[0]) {
39                 for(int i = n-1; i>=0; i--) {
40                     if(a[i] != b[i]) {
41                         swap(a[0],a[i]);
42                         cnt++;
43                         break;
44                     }
45                 }
46             } else {
47                 int k = get(a[0]);
48                 swap(a[0], a[k]);
49                 cnt++;
50             }
51         }
52         printf("%dn", cnt);
53     }
54 }

View Code

C. Auction Bidding

题mu链接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<string>
 7 #include<map>
 8 #include<sstream>
 9 #include<vector>
10 
11 using namespace std;
12 typedef long long ll;
13 const int maxn = 5005;
14 const double eps= 1e-9;
15 const int inf = 0x3f3f3f3f;
16 
17 ll ans[maxn];
18 struct node{
19     int id;
20     int p;
21     bool operator <(const node& s) const{
22         return p==s.p?id<s.id:p>s.p;
23     }
24 };
25 
26 vector<node> v[maxn];
27 
28 int main(){
29     int n,m;
30     scanf("%d%d",&n,&m);
31     memset(ans,0,sizeof(ans));
32     for(int i=1;i<=n;i++){
33         int r;
34         scanf("%d",&r);
35         int id;
36         node s;
37         s.id=inf;
38         s.p=r;
39         v[i].push_back(s);
40         while(scanf("%d",&id)==1){
41             if(id==-1) break;
42             int p;
43             scanf("%d",&p);
44             node x;
45             x.id=id;
46             x.p=p;
47             v[i].push_back(x);
48         }
49         sort(v[i].begin(),v[i].end());
50         if(v[i][0].id==inf) continue;
51         else{
52             int p2=v[i][1].p;
53             int p1=v[i][0].p;
54             p2=1.1*p2;
55     //        cout<<v[i][0].id<<' '<<v[i][0].p<<endl;
56             int sum=min(p1,p2);
57             ans[v[i][0].id]+=sum;
58         }
59     }
60     int k;
61     scanf("%d",&k);
62     while(k--){
63         int l;
64         scanf("%d",&l);
65         printf("%dn",ans[l]);
66     }
67     return 0;
68 }

View Code

H. A Cache Simulator

题库链接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<string>
 7 #include<map>
 8 
 9 using namespace std;
10 typedef long long ll;
11 const int maxn = 305;
12 
13 map<char,ll> dir;
14 map<ll,ll> ms;
15 const ll head=1LL<<10;
16 const ll mid=1LL<<6;
17 
18 void init(){
19     dir['0']=0;
20     dir['1']=1;
21     dir['2']=2;
22     dir['3']=3;
23     dir['4']=4;
24     dir['5']=5;
25     dir['6']=6;
26     dir['7']=7;
27     dir['8']=8;
28     dir['9']=9;
29     dir['A']=10;
30     dir['B']=11;
31     dir['C']=12;
32     dir['D']=13;
33     dir['E']=14;
34     dir['F']=15;
35     for(int i=0;i<(mid+10);i++){
36         ms[i]=-1;
37     }
38 }
39 
40 ll Hash(string str){
41     ll sum=0;
42     int len=str.size();
43     for(int i=0;i<len;i++){
44     //    cout<<i<<' '<<sum<<endl;
45         sum=sum*16+dir[str[i]];
46     }
47     return sum;
48 }
49 
50 
51 int main(){
52     init();
53     string str;
54     int cnt=0;
55     int tot=0;
56     while(cin>>str){
57 //        cout<<str<<endl;
58         if(str[1]=='N') break;
59         tot++;
60         ll num=Hash(str);
61         ll temp=(num%head)/16;
62         ll in=num/head;
63         if(ms[temp]!=in){
64             printf("Missn");
65             ms[temp]=in;
66         }else{
67             printf("Hitn");
68             cnt++;
69         }
70     }    
71     double ans=(double)(cnt)/(double)tot;
72     ans*=100;
73     printf("Hit ratio = %.2f",ans);
74     cout<<"%n";
75     return 0;
76 }