组队赛 01 题解（部分）

作者: 染微言 | 来源:发表于2017-07-17 21:33 被阅读16次

组队赛 01 题解

感想

组队赛用的是11年福州赛区的网络赛。

这场的题目A、F、H、J是大家都能做的，剩下的题目就很坑，出现了Dancing Links、插头DP、神坑的计算几何和贪心+费用流的操作。最坑的是代码都很长……

赛后我只补了一题计算几何就不再补了。

A - Card Game

题意

有若干张卡牌，牌面为1~m，牌面为i的牌的张数为a_i。将牌打乱顺序，随机分成m堆，第i堆牌中有a_i张。游戏开始时，从第一堆中抽牌一张，上一张抽到的牌决定下一张牌从那一堆中抽取。如果上一张牌指向的牌堆是空的，游戏结束。

求游戏结束时所有牌堆都为空的概率。

思路

概率公式题。

这里有一个点要注意：因为必须要从第一堆中抽第一张牌，所以说，如果能抽光牌的话，那么最后一张牌必须是指向第一堆的。也就是说，最后一张抽到的牌必须是1。

为什么呢？我们来分析一下：首先，一共有a_1张1，那么如果抽光了牌，在抽牌过程中，1会被抽到a_1次，第一牌堆就会被指向a_1次。但是第一张牌是从第一堆中抽取的，那么第一堆中只会有a_1-1张牌可以被指向然后抽取。所以最后一个必须是a_1。

这一点有点难理解，但是理解了之后公式就出来了——概率就是全排列中最后一位是1的概率，那么就是 $a_1/\sum{a_i}$ 。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100+7;

void solve(int cas) {
    int m, num[maxn], sum = 0; scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", num+i);
        sum += num[i];
    }
    printf("Case %d: %.6lf\n", cas, 1.0*num[0]/sum);
}

int main(){
    int t, cas = 1; scanf("%d", &t);
    while (t--) solve(cas++);
}

C - Aircraft

题意

有若干个信号圈，飞机只能在信号圈飞行。现在飞机要从一个信号圈的圆心（起点）飞到另一个的圆心（终点），求最短路。

思路

计算几何。

很容易想到飞机的路径只会经过起点、信号圆的交点、终点这些点。讲这些点加入点集当中，然后求最短路即可。但是这里有个难点，就是判断这些点之间是否能够互相到达，即他们的连线是否完全被信号圈覆盖。在比赛时也是因为这个点所以没能过。

下面说说解决方案：判断一条线段是否在多个圆内，只要求这条线段和多个圆的交点，然后看交点之间的线段是不是都在某一个圆内。这个方法时间复杂度很高，但是好在数据量小。最终的时间复杂度大概O(n^5)左右。

补题的时候抄两三个板子，用spfa过了。代码足有三百行不到。

代码

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define eps 1e-10

int cmp(double x)
{
    if(fabs(x)<eps) return 0;
    if(x>0) return 1;
    return -1;
}

double sqr(double x)
{
    return x*x;
}

struct point
{
    double x,y;
    point(){};
    point(double a,double b):x(a),y(b){};
    void out()
    {
        printf("%lf %lf\n",x,y);
    }
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    friend point operator +(const point &a,const point &b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    friend point operator -(const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend bool operator ==(const point &a,const point &b)
    {
        return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
    }
    bool operator <(const point &a) const
    {
        if(x==a.x) return y<a.y;
        return x<a.x;
    }
    friend point operator *(const point &a,const double &b)
    {
        return point(a.x*b,a.y*b);
    }
    friend point operator *(const double &a,const point &b)
    {
        return point(a*b.x,a*b.y);
    }
    friend point operator /(const point &a,const double &b)
    {
        return point(a.x/b,a.y/b);
    }
    double norm()
    {
        return sqrt(sqr(x)+sqr(y));
    }
};
double det(const point &a,const point &b)
{
    return a.x*b.y-a.y*b.x;
}
double dot(const point&a,const point &b)
{
    return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b)
{
    return (a-b).norm();
}
point rotate_point(const point &p,double A)
{
    double tx=p.x,ty=p.y;
    return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
point rotate(const point &p,double cost,double sint)
{
    double x=p.x,y=p.y;
    return point(x*cost-y*sint,x*sint+y*cost);
}

pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
    double d=(ap-bp).norm();
    double cost = (ar*ar + d*d -br*br)/(2*ar*d);
    double sint=sqrt(1.0-cost*cost);
    point v=(bp-ap)/(bp-ap).norm()*ar;
    return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) {
    double x0 = o.x ,y0 = o.y;
    double x1 = a.x, y1 = a.y;
    double x2 = b.x, y2 = b.y;
    double dx = x2-x1, dy = y2-y1;
    double A = dx*dx+dy*dy;
    double B = 2*dx*(x1-x0) + 2*dy*(y1-y0);
    double C = sqr(x1-x0) + sqr(y1-y0)-sqr(r);
    double delta = B*B-4*A*C;
    if( cmp(delta) >= 0) {
        double t1 = (-B - sqrt(delta)) / (2*A);
        double t2 = (-B + sqrt(delta)) / (2*A);
        if(cmp(t1-1)<=0 && cmp(t1)>=0)
        ret[num++] = point(x1+t1*dx,y1+t1*dy);
        if(cmp(t2-1) <=0 && cmp(t2)>=0)
        ret[num++] = point(x1+t2*dx,y1+t2*dy);
    }
}
struct rad
{
    point c;
    double r;
}ra[300];
int n;
map<point,int> mp;
int ID;
int que[123456];
point xx[100005];
struct node2
{
    int v,next;
    double w;
}e[123456];
int head[12345];
bool in[12345];
double d[12345];
int en;
void add(int a,int b,double c)
{
  //  printf("%d %d %lf\n",a,b,c);
    e[en].v=b;
    e[en].w=c;
    e[en].next=head[a];
    head[a]=en++;

    e[en].v=a;
    e[en].w=c;
    e[en].next=head[b];
    head[b]=en++;
}
void spfa(int st)
{
    queue<int> q;
    memset(in,0,sizeof(in));
    for(int i=1;i<=ID;i++) d[i]=1000000000;
    q.push(st);
    in[st]=1;
    d[st]=0;
    int tmp;
    while(!q.empty())
    {
        tmp=q.front();q.pop();
        in[tmp]=0;
        for(int i=head[tmp];~i;i=e[i].next)
        {
            if(d[e[i].v]>d[tmp]+e[i].w)
            {
                d[e[i].v]=d[tmp]+e[i].w;
                if(!in[e[i].v])
                {
                    in[e[i].v]=1;
                    q.push(e[i].v);
                }
            }
        }
    }
}
bool inra(point &x,point &y)
{
    for(int i=1;i<=n;i++)
    {
        if(dist(x,ra[i].c)<=ra[i].r+eps && dist(y,ra[i].c)<=ra[i].r+eps)
        {
            return true;
        }
    }
    return false;
}
point my[12345];
bool cal(point &a,point &b)
{
    my[0]=a;
    int top=1;
    for(int i=1;i<=n;i++)
    {
        circle_cross_line(a,b,ra[i].c,ra[i].r,my,top);
    }
    my[top++]=b;
    sort(my,my+top);
    for(int i=1;i<top;i++)
    {
        if(!inra(my[i-1],my[i])) return false;
    }
    return true;
}
void solve(int cas) {
    mp.clear();
    scanf("%d",&n);
    ID=0;
    for(int i=1;i<=n;i++) {
        ra[i].c.input();
        scanf("%lf",&ra[i].r);
    }
    printf("Case %d: ",cas);

    if(cal(ra[1].c,ra[n].c)) {
        printf("%.4f\n",dist(ra[1].c,ra[n].c));
        return;
    }
    en=0;
    memset(head, -1, sizeof head);
    int top = 0;
    for(int i=1; i<=n; i++){
        mp[ra[i].c]=++ID;
        que[top++]=ID;
        xx[ID] = ra[i].c;
        for(int j=i+1; j<=n; j++) {
            if(dist(ra[i].c,ra[j].c)>(ra[i].r+ra[j].r)+0.0) continue;
            pair<point,point> tmp=crosspoint(ra[i].c,ra[i].r,ra[j].c,ra[j].r);
            if(mp[tmp.first]==0) {
                mp[tmp.first]=++ID;
                que[top++]=ID;
                xx[ID]=tmp.first;
            }
            if(mp[tmp.second]==0) {
                mp[tmp.second]=++ID;
                que[top++]=ID;
                xx[ID]=tmp.second;
            }
        }
    }
    mp[ra[n].c]=++ID;
    que[top++]=ID;
    xx[ID]=ra[n].c;
    for(int i=0;i<top;i++) {
        for(int j=i+1;j<top;j++) {
            if(cal(xx[que[i]],xx[que[j]])) {
                add(que[i],que[j],dist(xx[que[i]],xx[que[j]]));
            }
        }
    }
    spfa(1);

    if(d[ID]>=1000000000) puts("No such path.");
    else printf("%.4f\n",d[ID]);
}

int main(){
    int t, cas = 0; scanf("%d", &t);
    while (t--) solve(++cas);
}

F - Random Sequence

题意

一个串完全由-1和1组成，每个位置出现哪个数是随机的。求固定长度的串最大子段和的绝对值的期望是多少。

思路

找规律离线打表。

求出了n=1...10的答案，然后找规律即可。

规律是：e_{2n} = e_{2n-1} + 1*(1/2)*(3/4)*(5/6)*...*((2n-1)/2n)

代码

#include <bits/stdc++.h>
using namespace std;

double table[2000];

void init() {
    double x = 1.0;
    table[1] = 1;
    for (int i = 2; i <= 1500; ++i) {
        if (!(i&1)) x *= 1.0*(i-1)/(1.0*i);
        table[i] = table[i-1]+x;
    }
}

int main() {
    int t, n, cas = 1;
    scanf("%d", &t);
    init();
    while (t--) {
        scanf("%d", &n);
        printf("Case %d: %.6lf\n", cas++, table[n]);
    }
}

J - Phage War

题意

最开始你有一个细胞，细胞会源源不断地生成噬菌体，一秒一个，细胞周围若干个细胞，占领这些细胞需要花费D_i个噬菌体，噬菌体到达这个细胞需要花费t_i的时间，求占领所有细胞的最短时间。

思路

贪心水题。

给所有细胞排个序，先给最远的细胞输送噬菌体。这样是效率最高的方式，遍历细胞时记录每一个细胞按顺序需要花费的时间，最后排个序，取最小值，就是答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+7;

struct cell {
    int d, t;
} cells[maxn];

bool cmp (cell a, cell b) {
    if (a.t == b.t) return a.d > b.d;
    return a.t > b.t;
}

void solve(int cas) {
    int ans = 0, n, dp[maxn]; scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &cells[i].d, &cells[i].t);
    sort(cells, cells+n, cmp);
    int sum = cells[0].d;
    dp[0] = cells[0].d + cells[0].t;
    for(int i = 1; i < n; ++i) {
        dp[i] = sum + cells[i].d + cells[i].t;
        sum += cells[i].d;
    }
    sort(dp, dp+n);
    printf("Case %d: %d\n", cas, dp[n-1]);
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t, cas = 1; scanf("%d", &t);
    while (t--) solve(cas++);
}

组队赛 01 题解（部分）