2015 ACM/ICPC 长春现场赛部分题解

昨天全队做了这个比赛，做一个小小的总结，写一写部分题的题解。

【E - Rebuild】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5199

【题意】依次输入n个点的坐标，分别为圆心。保证相邻圆心的距离是个正整数。第n个圆和第1个圆相邻。要求相邻两个圆要相切，求全部圆面积和的最小值，以及此时半径的取法。

【解题方法】

先根据坐标求出相邻圆心距离依次为a0,a1,...,an−1
设圆半径分别为x0,x1,...,xn−1
化为方程

然后把这n-1个方程，如果是奇数用当前方程减去下一个，否则加上下一个。最后得到的方程为2*x0=（a1-a2+a3-a4....+(-1)^n*a[n-1]），代码用last来维护一下这个东西。

【AC 代码】

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4+10;
const double eps = 1e-8;
const double PI = acos(-1);

struct point{
    int x,y;
    point(int x,int y):x(x),y(y){}
    point(){}
    void read(){
        scanf("%d%d",&x,&y);
    }
}p[maxn];
double A[maxn];
double dist(point a,point b)
{
    double x=(a.x-b.x),y=(a.y-b.y);
    return sqrt(x*x+y*y);
}
int n;
double solve(double r)
{
    double ans=r*r;
    double last=r;
    A[0]=r;
    for(int i=1; i<n; i++){
        double d=dist(p[i],p[i-1])-last;
        A[i]=d;
        ans+=d*d;
        last=d;
    }
    return ans*PI;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++){
            p[i].read();
        }
        p[n]=p[0];
        double maxx=1e9,minn=0;
        double last=0;//represent r0
        for(int i=1; i<=n; i++){
            double d=dist(p[i],p[i-1]);
            if(i&1){
                last+=d;
                maxx=min(maxx,last);
            }
            else{
                last-=d;
                minn=max(minn,last);
            }
        }
        if((minn-maxx)>eps){
            printf("IMPOSSIBLE\n");
            continue;
        }
        if(n&1){
            printf("%.2f\n",solve(last/2.0));
            for(int i=0; i<n; i++)
            {
                printf("%.2f\n",A[i]);
            }
            continue ;
        }
        else{
            if(fabs(last)>eps){
                printf("IMPOSSIBLE\n");
                continue ;
            }
        }
        double l=minn,r=maxx;
        double m,mm;
        for(int i=0; i<100; i++){
            m=(l+r)/2;
            mm=(m+r)/2;
            if(solve(m)>solve(mm)){
                l=m;
            }else{
                r=mm;
            }
        }
        printf("%.2f\n",solve(l));
        for(int i=0; i<n; i++){
            printf("%.2f\n",A[i]);
        }
    }
    return 0;
}

【 F - Almost Sorted Array】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5199

【题意】给一个序列，你可以删除一个元素，如果使得这个序列有序输出YES，否则输出NO。

【解题方法】ＬＩＳ即可。

【AC 代码】

#include<bits/stdc++.h>
using namespace std;
const int N =2e5;
int a[N],dp[N];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int len=1,flag=0;
        dp[0]=a[0];
        for(int i=1;i<n;i++){
            int pos=lower_bound(dp,dp+len,a[i])-dp;
            //while(dp[pos]==dp[pos+1]&&pos<len) pos++;
            if(pos==len) len++;
            dp[pos]=a[i];
        }
        //printf("%d\n",len);
        if(len>=n-1) flag=1;
        len=1;
        dp[0]=a[n-1];
        for(int i=n-2;i>=0;i--){
            int pos=lower_bound(dp,dp+len,a[i])-dp;
            //while(dp[pos]==dp[pos+1]&&pos<len) pos++;
            if(pos==len) len++;
            dp[pos]=a[i];
        }
        //printf("%d\n",len);
        if(len>=n-1) flag=1;
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

【 G - Dancing Stars on Me】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5201

【题意】给n个点，判断能否组成正多边形。我直接维护了一个凸包，正解应该是只需要考虑正方形，其他的正多边形顶点不可能全是整数点。。。。

【AC 代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 110;
struct point{
    LL x,y;
    void read()
    {
        scanf("%lld%lld",&x,&y);
    }
}p[maxn],ans[maxn];
point operator-(point a,point b)
{
    return point{a.x-b.x,a.y-b.y};
}
LL Cross(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
LL dist(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(point a,point b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
int solve(point *p,int n,point *ch)
{
    sort(p,p+n,cmp);
    int m=0;
    for(int i=0; i<n; i++){
        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2; i>=0; i--){
        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}

int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0; i<n; i++) p[i].read();
        int m=solve(p,n,ans);
        if(m!=n){
            printf("NO\n");
            continue;
        }
        else{
            bool ok=1;
            for(int i=0; i<n; i++){
                if(dist(ans[i],ans[(i+1)%n])!=dist(ans[0],ans[1])) ok=0;
            }
            if(ok) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}

【 H - Partial Tree】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5202

【题意&&解题思路】脑洞题，队友一直卡在了O(n*n*n)的树dp。赛后补题，题解参见http://blog.csdn.net/snowy_smile/article/details/49592537

【AC 代码】

【J - Chip Factory】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5204

【题意】在一个序列中，求(a[i]+a[j])^(a[k])的最大值。暴力和01Trie都可以过，比赛直接上暴力，这里写一个01trie吧。

【AC 代码--字典树】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000*34;
struct Trie{
    int ch[maxn][2],cnt[maxn];
    int root,L;
    int newnode(){
        ch[L][0]=ch[L][1]=-1;
        cnt[L]=0;
        return L++;
    }
    void init(){
        L=0;
        root=newnode();
    }
    void Insert(int x)
    {
        int now=root;
        for(int j=30; j>=0; j--){
            int go=(x&(1<<j))?1:0;
            if(ch[now][go]==-1){
                ch[now][go]=newnode();
                now=ch[now][go];
                cnt[now]++;
            }
            else{
                now=ch[now][go];
                cnt[now]++;
            }
        }
    }
    void Delete(int x)
    {
        int now=root;
        for(int j=30; j>=0; j--){
            int go=(x&(1<<j))?1:0;
            now=ch[now][go];
            cnt[now]--;
        }
    }
    int queryans(int x)
    {
        int now=root;
        int ans=0;
        for(int j=30; j>=0; j--){
            int go=(x&(1<<j))?1:0;
            if(ch[now][!go]!=-1&&cnt[ch[now][!go]]){
                ans|=(1<<j);
                now=ch[now][!go];
            }
            else{
                now=ch[now][go];
            }
        }
        return ans;
    }
}trie;
int a[1010];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        trie.init();
        scanf("%d",&n);
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            trie.Insert(a[i]);
        }
        int ans=0;
        for(int i=1; i<n; i++){
            for(int j=i+1; j<=n; j++){
                trie.Delete(a[i]);
                trie.Delete(a[j]);
                ans=max(ans,trie.queryans(a[i]+a[j]));
                trie.Insert(a[i]);
                trie.Insert(a[j]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

【暴力版本】

【L - House Building】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5206

【题意】一个n*m的矩阵，每个点有一根柱子，长度为C(i,j)，问除了底面，其他所有面的表面积为多少？

【解题方法】水题，见代码。

【AC 代码】

#include<bits/stdc++.h>
using namespace std;
const int N =60;
int a[N][N];
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]) ans+=4*a[i][j]+1;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                ans-=min(a[i-1][j],a[i][j])*2+min(a[i][j-1],a[i][j])*2;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

2015 ACM/ICPC 长春现场赛 部分题解

2015 ACM/ICPC 长春现场赛部分题解