G. Finding the Radius for an Inserted Circle

題目:鏈接

讓求第k個內切圓的半徑 r[k]

這題我們沒做出來,主要是因為我發現的太晚了......

一開始看到的時候覺得圖看起來太復雜就沒去看....

最后還剩二十分鐘的時候開始做,本來應該也是可以過的,結果讀錯輸入格式了,然后就悲劇了......? 差點完成絕殺啊!!!

根據勾股定理很容易推出公式 r[i] = (√3 * R? - R - 2 * c[i-1] )^2? / ( 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 %d\n",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("%.0lf\n",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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n",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("Miss\n"); 65 ms[temp]=in; 66 }else{ 67 printf("Hit\n"); 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 } View Code

?

轉載于:https://www.cnblogs.com/yijiull/p/7588052.html

總結

以上是生活随笔為你收集整理的17南宁网络赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。