Outlets

看一眼就应该知道是要求MST。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const int N=10000;
struct DST
{
    int father[N];
    void init()
    {
        for (int i=0; i<N; i++) father[i]=i;
    }
    int root(int k)
    {
        if (father[k]==k) return k;
        father[k]=root(father[k]);
        return father[k];
    }
    void merge(int x, int y)
    {
        x=root(x),y=root(y);
        father[x]=father[y];
    }
}s;
struct _point
{
    int x,y;
    double d;
}site[60],edge[N];
inline bool cmp(const _point &a, const _point &b)
{
    return (a.d<b.d);
}
int main()
{
    int i,j,k,n,p,q,x,y,K;
    double tot;
    while (scanf("%d",&n),n)
    {
        s.init();
        scanf("%d %d",&p, &q);
        for (i=1; i<=n; i++)
        {
            scanf("%d %d",&site[i].x,&site[i].y);
        }
        for (i=1,k=0; i<=n; i++)
          for (j=1; j<=n; j++)
          if (i!=j)
          {
            edge[k].d=sqrt(
                (site[i].x-site[j].x)*(site[i].x-site[j].x)
                +(site[i].y-site[j].y)*(site[i].y-site[j].y)+0.0);
            edge[k].x=i, edge[k].y=j;
            k++;
          }
        K=k;
        sort(edge,edge+K,cmp);
        tot=sqrt(
                (site[p].x-site[q].x)*(site[p].x-site[q].x)
                +(site[p].y-site[q].y)*(site[p].y-site[q].y)+0.0);
        s.merge(p,q);
        for (i=1,k=2; k<n; i++)
        {
            x=edge[i].x, y=edge[i].y;
            x=s.root(x), y=s.root(y);
            if (x==y) continue;
            s.merge(x,y);
            tot+=edge[i].d;
            k++;
        }
        printf("%.2f\n",tot);

    }
    return 0;
}

Friend Chains

点V=1000，边E=10000，floyd不靠谱，单点最短路径bfs的复杂度是O(V+E)，跑V次O(V^2+VE)，可以接受，水过。

那个名字用map来hash就好了

#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
using namespace std;
const int V = 1010;
const int E = 25010;
int n;
int g[V][V],cnt;
struct node{
    int x,y,w;
    node *next;
}edge[E],*head[V];
inline void addedge(int x, int y, int w){
    edge[cnt].x=x, edge[cnt].y=y, edge[cnt].w=w;
    edge[cnt].next=head[x]; head[x]=edge+cnt++;
}
void init(){
    cnt=0;
    memset(head,0,sizeof(head));
    memset(g,0,sizeof(g));
}
int q[V],vis[V],dis[V];
int bfs(int st){
    int he,ta,now;//head tail
    he=1,ta=0;
    memset(vis,0,sizeof(vis));
    memset(dis,7,sizeof(dis));
    q[0]=st;
    vis[st]=true;
    dis[st]=0;
    while (ta<he){
        now=q[ta++];
        //vis[now]=true;//useless
        for (node* p=head[now]; p; p=p->next){
            if (!vis[p->y] && dis[p->y]>dis[now]+p->w)
            {
                q[he++]=p->y;
                vis[p->y]=true;
                dis[p->y]=dis[now]+p->w;
            }
        }
    }
    int i,max=0;
    for (i=0; i<n; i++)
      if (dis[i]>max) max=dis[i];
    return max;
}
int main()
{
    map<string,int> name;
    char str[11],s1[11],s2[11];
    int m,i,j,k,x,y;
    while ( scanf("%d",&n),n){
        init();
        name.clear();
        k=0;
        for (i=0; i<n; i++)
        {
            scanf("%s",str);
            name[str]=i;
        }
        scanf("%d",&m);
        for (i=0; i<m; i++)
        {
            scanf("%s %s",s1,s2);
            x=name[s1], y=name[s2];
            g[x][y]=g[y][x]=1;
        }
        for (i=0; i<n; i++)
         for (j=0; j<n; j++)
          if (g[i][j]) addedge(i,j,1);
        int tmp;
        for (i=0,k=0; i<n; i++)
        {
            tmp=bfs(i);
            if (tmp>k) k=tmp;
            if (k>=n) break;
        }
        if (k>=n) k=-1;
        printf("%d\n",k);
    }
    return 0;
}

Scaring the Birds

这题二分稻草人的数量，dfs枚举稻草人的组合，然后验证即可。

n似乎不大，直接用循环赋值应该就能A，用线段树求覆盖长度是在干嘛。。。
 

#include <cstdio>
#include<cstring>
using namespace std;
#define L(u) ( u << 1 )
#define R(u) ( u << 1 | 1 )
#define N 55
struct item{ int l, r; int v, add;};
struct tree{
    item node[N*3];
    int num[N];
    int n, q;
    void init ( int u, int l, int r )
    {
        node[u].l = l;
        node[u].r = r;
        node[u].v = 0;
        node[u].add = 0;
        if ( l == r ) return;
        int mid = ( l + r ) >> 1;
        init ( L(u), l, mid );
        init ( R(u), mid+1, r );
    }
    int set ( int u, int l, int r)
    {
        int ret = 0;
        if ( node[u].v ==  node[u].r-node[u].l+1 ) return 0;
        if ( l == node[u].l && node[u].r == r ) {
            ret = r-l+1-node[u].v;
            node[u].v = r-l+1;
            return ret;
        }
        int mid = ( node[u].l + node[u].r ) >> 1;
        if ( r <= mid )
            ret = set ( L(u), l, r );
        else if ( l > mid )
            ret = set ( R(u), l, r );
        else {
            ret = set ( L(u), l, mid );
            ret+= set ( R(u), mid+1, r );
        }
        node[u].v += ret;
        return ret;
    }
    int sum ( int u, int l, int r )
    {
        if ( node[u].v ==  node[u].r-node[u].l+1 ) return r-l+1;
        if ( l == node[u].l && node[u].r == r ) {
            return node[u].v;
        }
        int mid = ( node[u].l + node[u].r ) >> 1;
        if ( r <= mid )
            return sum ( L(u), l, r );
        else if ( l > mid )
            return sum ( R(u), l, r );
        else
            return (sum ( L(u), l, mid ) + sum ( R(u), mid+1, r ));
    }
}s[N];
struct Vac{
    int x,y,r,vis;
}V[N];
bool check(int n, int k, int mid){
    int i,j,l,r,p;
    for (i=1; i<=n; i++) s[i].init(1,1,n);
    for (i=0; i<k; i++){
      s[ V[i].y ].set(1, V[i].x, V[i].x);
      if (V[i].vis) {
        for (j=0; j<=V[i].r; j++){
            l=V[i].x-(V[i].r-j), r=V[i].x+V[i].r-j;
            if (l<=0) l=1;
            if (r>=n) r=n;
            p=V[i].y-j;
            if (p>=1) s[p].set(1,l,r);
            p=V[i].y+j;
            if (p<=n) s[p].set(1,l,r);
        }
      }
    }
    for (i=1, j=0; i<=n; i++) j+=s[i].sum(1,1,n);
    if (j==n*n) return true; else return false;
}
bool dfs(int n,int k, int d, int mid, int p){
    if (d==mid){
        return check(n,k,mid);
    }
    bool tmp;
    for (int i=p; i<k; i++){
        if (V[i].vis==0){
            V[i].vis=1;
            tmp=dfs(n,k,d+1,mid,i+1);
            V[i].vis=0;
            if (tmp) return true;
        }
    }
    return false;
}
int solve(int n, int k){
    int l,r,mid;
    l=0, r=k+1;
    while (l<r){
        mid=(l+r)>>1;
        if ( dfs(n,k,0,mid,0) ) r=mid; else l=mid+1;
    }
    if (l==k+1) return -1; else return l;
}
int main(){
    int i,k,n;
    while ( scanf("%d",&n), n ){
        scanf("%d",&k);
        for (i=0; i<k; i++) scanf("%d %d",&V[i].x,&V[i].y);
        for (i=0; i<k; i++) scanf("%d",&V[i].r);
        printf("%d\n",solve(n,k));
    }
    return 0;
}