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] 的前缀和.

#include <bits/stdc++.h>
using namespace std;
double r[23];
double c[23];
int main(){
    int t;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    for(int i =0; i<=11;i++){
         r[i]=c[i]=0;
    }
    double R;
    int k;
    scanf("%lf", &R);
    for(int i = 1; i <= 10; i++){
        double temp = (sqrt(3)-1)*R - 2*c[i-1];
        r[i]=temp/(2*sqrt(3)*R-4*c[i-1])*temp;
        c[i]=c[i-1]+r[i];
    }
    while(t--) {
        scanf("%d", &k);
        int a=r[k];
        printf("%d %d
",k, a);
    }
    scanf("%d",&k);
    return 0;
}

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

F. Overlapping Rectangles

 题库链接

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

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

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
using namespace std;
const int maxn=2210;  //需要离散的x坐标数
int cnt[maxn<<2];    //标记该线段是否被选
double sum[maxn<<2];  //被选择的部分线段总长度
double X[maxn<<2];  //离散化
struct seg
{
    double l,r;
    double h;
    int s;  //标记
    seg(){}
    seg(double l,double r,double h,int s):l(l),r(r),h(h),s(s){}
    bool operator < (const seg &cmp) const
    {
        return h<cmp.h;
    }
}ss[maxn];

void pushup(int rt,int l,int r)
{
    if(cnt[rt]) sum[rt]=X[r]-X[l];  //如果该线段标记被完全选择，则长度为全长。。
    else if(l+1==r) sum[rt]=0;   //若未被完全选择，且该线段只有一段，则长度为0
    else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; //未被完全选择，且不止一段，则长度为被选择的部分
}

void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        cnt[rt]+=c;  // 选则或者删除一次该线段
        pushup(rt,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(L<m) update(L,R,c,lson);
    if(m<R) update(L,R,c,rson);
    pushup(rt,l,r);
}
int BIN(double key,int n,double X[])
{
    int l=0,r=n-1;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(X[m]==key) return m;
        if(X[m]<key) l=m+1;
        else r=m-1;
    }
    return -1;
}
int main()
{
    int n,cas=0;
    //freopen("in.txt", "r", stdin);
    while(scanf("%d",&n)&&n)
    {
        int m=0;
        while(n--)
        {
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            X[m]=a;
            ss[m++]=seg(a,c,b,1);
            X[m]=c;
            ss[m++]=seg(a,c,d,-1);
        }
        sort(X,X+m);
        sort(ss,ss+m);
        //离散化
        int k=1;
        for(int i=1;i<m;i++)
            if(X[i]!=X[i-1]) X[k++]=X[i];

        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        double ans=0;
        for(int i=0;i<m-1;i++)  //最上面的线段不用处理
        {
            int l=BIN(ss[i].l,k,X);
            int r=BIN(ss[i].r,k,X);
            if(l<r) update(l,r,ss[i].s,0,k-1,1);
            ans+=sum[1]*(ss[i+1].h-ss[i].h);
        }
        printf("%.0lf
",ans);
    }
    puts("*");
    return 0;
}

 B. Train Seats Reservation 

题目链接

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

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

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int n;
    int s,t,k;
    while(scanf("%d", &n) && n) {
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; i++){
            scanf("%d %d %d", &s, &t, &k);
            for(int j = s; j < t; j++) a[j]+=k;
        }
        int ans = 0;
        for(int i = 1; i <= 100; i++)
            ans = max(a[i], ans);
        printf("%d
", ans);
    }
    puts("*");
    return 0;
}

 M. Frequent Subsets Problem

 题目链接

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

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

#include <bits/stdc++.h>
using namespace std;
int n;
double r;
int a[1<<21];

int check(int sum, int x) {
    for(int i = 1; i <= sum; i <<= 1) {
        if((i&x) && (!(sum&i))) return 0;
    }
    return 1;
}
int main(){
    scanf("%d %lf", &n, &r);
    getchar();
    string s;
    int k=0;
    while(getline(cin,s)){
        k++;
        istringstream ss(s);
        int x, sum = 0;
        while(ss>>x) {
            x--;
            sum += (1<<x);
        }
        for(int i = 1; i <= sum; i++){
            if(check(sum,i)) a[i]++;
        }
    }
    k = ceil(k * r);
    n = (1<<n);
    int res = 0;
    for(int i = 1; i <=n; i++) if(a[i] >= k) res++;
    printf("%d
", res);
}

 L. The Heaviest Non-decreasing Subsequence Problem

 题目链接

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

要用nlogn的做法

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

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int inf = 1e9+10;
int a[maxn], d[maxn], g[maxn];
int main(){
    int n = 0, x;
    while(scanf("%d", &x)!=EOF){
        if(x >= 10000) {
            x -= 10000;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
        } else if(x >= 0) {
            a[++n] = x;
        }
    }
    for(int i = 0; i < maxn; i++) g[i] = inf;
    for(int i = 1; i <= n; i++) {
        int k = upper_bound(g+1, g+maxn, a[i]) - g;
        d[i] = k;
        g[k] = a[i];
    }
    int ans = lower_bound(g+1, g+maxn, inf) - g -1;
    printf("%d
", ans);
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int inf = 1e9+10;
int a[maxn], d[maxn];
int main(){
    int n = 0, x;
    while(scanf("%d", &x)!=EOF){
        if(x >= 10000) {
            x -= 10000;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
            a[++n] = x;
        } else if(x >= 0) {
            a[++n] = x;
        }
    }
    int len = 1;
    d[1] = a[1];
    for(int i = 2; i <= n; i++) {
        if(a[i] >= d[len]) d[++len] = a[i];
        else{
            int j = upper_bound(d+1, d+1+len, a[i]) - d;
            d[j] = a[i];
        }
    }
    printf("%d
", len);
}

 J. Minimum Distance in a Star Graph

 题库链接

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

思路:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 15;
int a[maxn], b[maxn];
int n;
int get(int x) {
    for(int i = 0; i < n; i++) if(b[i] == x) return i;
}
int ok(){
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) return 0;
    }
    return 1;
}
int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    int t = 5;
    int x,y;
    while(t--) {
        scanf("%d %d", &x, &y);
        int pos = 0;
        while(x) {
            a[pos++] = x % 10;
            x /= 10;
        }
        pos = 0;
        while(y) {
            b[pos++] = y % 10;
            y /= 10;
        }
        for(int i = 0; i < n/2; i++) {
            swap(a[i], a[n-i-1]);
            swap(b[i], b[n-i-1]);
        }
        int cnt = 0;
        while(!ok()) {
            if(a[0] == b[0]) {
                for(int i = n-1; i>=0; i--) {
                    if(a[i] != b[i]) {
                        swap(a[0],a[i]);
                        cnt++;
                        break;
                    }
                }
            } else {
                int k = get(a[0]);
                swap(a[0], a[k]);
                cnt++;
            }
        }
        printf("%d
", cnt);
    }
}

---

---

 C. Auction Bidding

 题mu链接

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<sstream>
#include<vector>

using namespace std;
typedef long long ll;
const int maxn = 5005;
const double eps= 1e-9;
const int inf = 0x3f3f3f3f;

ll ans[maxn];
struct node{
    int id;
    int p;
    bool operator <(const node& s) const{
        return p==s.p?id<s.id:p>s.p;
    }
};

vector<node> v[maxn];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++){
        int r;
        scanf("%d",&r);
        int id;
        node s;
        s.id=inf;
        s.p=r;
        v[i].push_back(s);
        while(scanf("%d",&id)==1){
            if(id==-1) break;
            int p;
            scanf("%d",&p);
            node x;
            x.id=id;
            x.p=p;
            v[i].push_back(x);
        }
        sort(v[i].begin(),v[i].end());
        if(v[i][0].id==inf) continue;
        else{
            int p2=v[i][1].p;
            int p1=v[i][0].p;
            p2=1.1*p2;
    //        cout<<v[i][0].id<<' '<<v[i][0].p<<endl;
            int sum=min(p1,p2);
            ans[v[i][0].id]+=sum;
        }
    }
    int k;
    scanf("%d",&k);
    while(k--){
        int l;
        scanf("%d",&l);
        printf("%d
",ans[l]);
    }
    return 0;
}

 H. A Cache Simulator

 题库链接

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<map>

using namespace std;
typedef long long ll;
const int maxn = 305;

map<char,ll> dir;
map<ll,ll> ms;
const ll head=1LL<<10;
const ll mid=1LL<<6;

void init(){
    dir['0']=0;
    dir['1']=1;
    dir['2']=2;
    dir['3']=3;
    dir['4']=4;
    dir['5']=5;
    dir['6']=6;
    dir['7']=7;
    dir['8']=8;
    dir['9']=9;
    dir['A']=10;
    dir['B']=11;
    dir['C']=12;
    dir['D']=13;
    dir['E']=14;
    dir['F']=15;
    for(int i=0;i<(mid+10);i++){
        ms[i]=-1;
    }
}

ll Hash(string str){
    ll sum=0;
    int len=str.size();
    for(int i=0;i<len;i++){
    //    cout<<i<<' '<<sum<<endl;
        sum=sum*16+dir[str[i]];
    }
    return sum;
}


int main(){
    init();
    string str;
    int cnt=0;
    int tot=0;
    while(cin>>str){
//        cout<<str<<endl;
        if(str[1]=='N') break;
        tot++;
        ll num=Hash(str);
        ll temp=(num%head)/16;
        ll in=num/head;
        if(ms[temp]!=in){
            printf("Miss
");
            ms[temp]=in;
        }else{
            printf("Hit
");
            cnt++;
        }
    }    
    double ans=(double)(cnt)/(double)tot;
    ans*=100;
    printf("Hit ratio = %.2f",ans);
    cout<<"%
";
    return 0;
}