2017 CCPC 哈尔滨

8/13

Permutation
A Simple Stone Game
Geometry Problem
K-th Number
Palindrome
Color a Tree
X-Men
Server
Interview

链接

Permutation

根据题意构造一个A[i]-A[i-2]=1的数列即可
easy

A Simple Stone Game

很容易想到求出N堆石子的总数量后，枚举每种因子得到一个解（将每堆石子模mid后贪心的凑出k堆）然后取最小值。但是因子的数量可能会很多会超时，那么我们在仔细想想发现其实只需要要枚举素因子就能得到正确的答案。

Geometry Problem

由于有N/2个点都在圆上，那其实任意选3个点后，这3个点不属于那N/2个点的概率只有1/8，题目保证有解，所以我们每次随机三个点后找到外心，在O（n）判断是否满足题意，直到有解

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<LL> VL;
const int maxn=2e6+6;
const double eps=1e-8;
LL _,n,a[maxn],cnt=0;
struct P{
   double x,y;
   P (double x=0,double y=0):x(x),y(y){}
   double norm2(){return x*x+y*y;}
}p[maxn],O;
double R;
double sqr(double x) {return x*x;}
int sgn(double x){return x<-eps?-1:x>eps;}
P operator + (P a,P b){return P(a.x+b.x,a.y+b.y);}
P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
P operator * (P a,double b){return P(a.x*b,a.y*b);}
P operator / (P a,double b){return P(a.x/b,a.y/b);}
double cj(P a,P b){return a.x*b.y-a.y*b.x;}
double dis(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
P waixin(P a,P b,P c){
    P p=b-a,q=c-a;
    P s(p.norm2()/2,q.norm2()/2);
    double d=cj(p,q);
    return a+P(cj(s,P(p.y,q.y)),cj(P(p.x,q.x),s))/d;
}
mt19937 rnd(time(NULL));
int main(){
    scanf("%lld",&_);
    while(_--){
        scanf("%lld",&n);
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        if(n<=2){
            printf("%.6f %.6f 0\n",p[0].x,p[0].y);
        }
        else if(n<=4){
            O=(p[1]+p[2])/2;
            R=dis(O,p[1]);
            printf("%.6f %.6f %.6f\n",O.x,O.y,R);
        }
        else {
            for(;;){
                int x=rnd()%n,y=rnd()%n,z=rnd()%n;
                if(x==y||x==z||y==z) continue;
                O=waixin(p[x],p[y],p[z]);
                R=dis(O,p[x]);
                cnt=0;
                if(fabs(O.x)>1e9||fabs(O.y)>1e9) continue;
                for(int i=0;i<n;i++) if(!sgn(R-dis(O,p[i]))) cnt++;
                if(cnt>=(n+1)/2) break;
            }
            printf("%.6f %.6f %.6f\n",O.x,O.y,R);
        }
    }
}

K-th Number

这个题感觉还蛮难想的，但好多人过啊…

突破口：直接考虑最后的B序列是一个由原序列中的数字多次或0次出现构成的序列，那么将B序列排序之后我们发现，对于每个数字出现的位置都有一个L，R，并且数字越小的其实排名越靠后，由这里我们就可以发现，最后的答案是满足二分性质的，所以我们可以直接二分Mst求出mid在B序列中的R即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<LL> VL;
const int maxn=2e6+6;
const double eps=1e-8;

LL sum[maxn],a[maxn],n,k,m,b[maxn];
vector<LL>G;
int _;
LL ok(LL x){
     G.clear();
     G.push_back(0);
     for(int i=1;i<=n;i++){
        if(a[i]>=x){
            G.push_back(i);
        }
     }
     G.push_back(n+1);
     LL res=0;
     for(int i=k;i<G.size()-1;i++){
        res=res+1ll*(G[i+1]-G[i])*(G[i-k+1]);
     }
     return res;
}
int main(){
    scanf("%d",&_);
    while(_--){
         scanf("%lld%lld%lld",&n,&k,&m);
         for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            b[i]=a[i];
         }
         sort(b+1,b+1+n,greater<int>());
         int l=1,r=n,ans=n;
         while(l<=r){
            int mid=l+r>>1;
            if(ok(b[mid])>=m){
                ans=mid;r=mid-1;
            }
            else l=mid+1;
         }
         printf("%d\n",b[ans]);
    }
}

Palindrome

一个半回文串。。学长讲过
考虑一个回文中心 i 和 i 能扩展的最长回文范围i+Ri，那么我们实际上就是统计由多少个j满足j-Rj<=i&&i<j<=Ri+i，所以我们可以按j-rj排序后树状数组维护i+1~i+Ri的个数即可

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<LL> VL;
const int maxn=2e6+6;
const double eps=1e-8;

int _,n,r[maxn],R[maxn];
LL c[maxn];
PII b[maxn];
char s[maxn],ma[maxn];
void add(int x,LL val){
     for(;x<=n;x+=x&(-x)) c[x]+=val;
}
LL ask(LL x){
   LL res=0;
   while(x){
      res+=c[x];
      x-=x&(-x);
   }return res;
}


int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%s",s+1);
        n=strlen(s+1);

        int l=0,p=0,an=0,mx=0;
        ma[l++]='$';ma[l++]='#';
        for(int i=1;i<=n;i++) ma[l++]=s[i],ma[l++]='#';
        ma[l]='\0';
        for(int i=0;i<l;i++){
            r[i]=mx>i?min(r[2*p-i],mx-i):1;
            for(;ma[i+r[i]]==ma[i-r[i]];r[i]++);
            if(i+r[i]>mx) mx=i+r[i],p=i;
        }

        //cout<<l<<endl;

        //for(int i=1;i<=l;i++) cout<<r[i]<<',';cout<<'\n';

        for(int i=1;i<=n;i++){
            R[i]=(r[i*2]-1)/2;
            //cout<<R[i]<<',';
        }
        //cout<<'\n';

        for(int i=1;i<=n;i++) b[i].fi=i-R[i],b[i].se=i,c[i]=0;

        sort(b+1,b+1+n);
        int j=1;
        LL ans=0;
        for(int i=1;i<=n;i++){
            for(;b[j].fi<=i&&j<=n;j++)add(b[j].se,1);
            ans=ans+ask(i+R[i])-ask(i);
        }
        printf("%lld\n",ans);
    }
}

Color a Tree

非常好的一道题
其实遇到这种至多至少，然后询问最少的题目，应该就要想到上下界的判断了。
不难看出，答案一定满足单调性，那么难度就在于写ok函数
对于条件1来说我们能得到每个子树黑色数量的下限，通过mid能构造出每个子树的上限，然后判断上限下限是否合理。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<LL> VL;
const int maxn=2e6+6;
const double eps=1e-8;
int n,_,A,x,y,u,v,flag,k=0,res,sz[maxn],down[maxn],up[maxn],L[maxn],R[maxn];
vector<int>G[maxn];
void dfs(int u,int fa){
     sz[u]=1;
     for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
     }
}
void dfs1(int u,int fa,int val){
     L[u]=0,R[u]=1;

     for(int v:G[u]){
        if(v==fa) continue;
        dfs1(v,u,val);
        L[u]+=L[v];
        R[u]+=R[v];
     }
     L[u]=max(L[u],down[u]);
     R[u]=min(R[u],min(sz[u],val-up[u]));
}
bool ok(int x){
     dfs1(1,-1,x);

     for(int i=1;i<=n;i++){
        //cout<<L[i]<<"#"<<R[i]<<'\n';
        if(L[i]>R[i]) return 0;
     }
     if(L[1]>x||R[1]<x) return 0;
     return 1;
}
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)G[i].clear(),up[i]=down[i]=0;
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1,-1);
        flag=0;
        scanf("%d",&A);
        for(int i=1;i<=A;i++){
            scanf("%d%d",&x,&y);
            if(sz[x]<y) flag=1;
            down[x]=max(down[x],y);
        }
        scanf("%d",&A);
        for(int i=1;i<=A;i++){
            scanf("%d%d",&x,&y);
            if(n-sz[x]<y) flag=1;
            up[x]=max(up[x],y);
        }
        if(flag){
            printf("-1\n");continue;
        }

        int l=1,r=n,ans=-1;
        while(l<=r){
            int mid=l+r>>1;
            //cout<<mid<<','<<'\n';
            if(ok(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
}

X-Men

这个题很迷啊，说是让求期望，其实不然
仔细分析题里要求的每个人走的方向可以发现，对于这些人中距离最远的两个人一定是相向走的（即距离-2），所以每秒过后距离这些人中的最远距离-2，那么这个走的过程其实就可以看作一个收缩的过程，所以我们只需要算出这些人的最短距离/2输出即可

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const double eps=1e-8;
const int maxn = 2e6+6;
vector<int>G[maxn];
int vis[maxn],a[maxn],root,n,m,_;
int mx=0;
void dfs(int u,int fa,int dis){
     if(vis[u]&&dis>mx) mx=dis,root=u;
     for(int v:G[u]){
        if(v==fa) continue;
        dfs(v,u,dis+1);
     }
}
int main(){
     scanf("%d",&_);
     while(_--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) G[i].clear(),vis[i]=0;

        for(int i=1;i<=m;i++) scanf("%d",&a[i]),vis[a[i]]++;
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            G[u].pb(v);
            G[v].pb(u);
        }
        root=-1,mx=1;
        dfs(a[m],-1,0);
        if(root==-1){
            printf("0.00\n");continue;
        }
        mx=1;
        dfs(root,-1,0);
        printf("%d.00\n",mx/2);
     }
}

Server

max/min{∑Ai/∑Bi }
对于这种形式的式子一般属于01分数规划问题，解决方法通常是令∑Ai/∑Bi =k然后二分。具体请看01分数规划
本题可以看出与01分数规划问题相差不大，主要是怎么考虑ok函数，即是否能满足使全部区间覆盖的Ai-mid*Bi<=0。
神奇的树状数组优化dp来了：
我们令C【i】为覆盖1~i区间的最小花费，那么对于一个区间L···R来说，他能影响到的区间就是C【L】··C【R】然后将所有区间按R排序在用树状数组加速dp即可 ~~感觉这种DP枚举起来还是有点奇怪，可能是没做过类似题目的原因吧~~

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const int maxn = 2e6+6;
double c[maxn],s[maxn],t[maxn],a[maxn],b[maxn];
int n,m,_,id[maxn];
bool cmp(int a,int b){
     return t[a]<t[b];
}
void update(int x,double val){
     for(;x;x-=x&(-x)) c[x]=min(c[x],val);
}
bool ok(double k){
    for(int i=1;i<=m;i++) c[i]=1e9;
    c[0]=0;
    //cout<<k<<'!'<<'\n';
    double res=0;
    for(int i=1;i<=n;i++){
        double val=a[id[i]]-k*b[id[i]];
        if(val<=0) res+=val,val=0;
        update(t[id[i]],c[int(s[id[i]]-1)]+val);
    }
    return  res+c[m]<=0;
}
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&s[i],&t[i],&a[i],&b[i]);
            id[i]=i;
        }
        sort(id+1,id+1+n,cmp);
        //for(int i=1;i<=n;i++) cout<<s[id[i]]<<','<<t[id[i]]<<'\n';
        double l=0,r=1e9,ans=0;
        while(fabs(r-l)>eps){
            double mid=(l+r)/2;
            if(ok(mid)) r=mid,ans=mid;
            else l=mid;
        }
        printf("%.3f\n",ans);
    }
}