Codeforces Round #222 (Div. 2) ABCD-蒲公英云

继续总结做过的CF

比赛链接：http://codeforces.com/contest/378

A Playing with Dice

题意：a，b两个数字，扔一个骰子，求分别与a，b求差的绝对值，谁小就谁赢，相等平局，输出每种情况的个数。

#include <cstdio>
#include <cmath>
int a,b;
int Dis (int k)
{
    if (fabs(a-k)<fabs(b-k))
        return 1;
    else if (fabs(a-k)>fabs(b-k))
        return -1;
    else
        return 0;
}
int main ()
{
    scanf("%d%d",&a,&b);
    {
        int sa=0,sm=0,sb=0;
        for (int i=1;i<=6;i++)
        {
            if (Dis(i)==1)
                sa++;
            if (Dis(i)==-1)
                sb++;
            if (Dis(i)==0)
                sm++;
        }
        printf("%d %d %d\n",sa,sm,sb);
    }
    return 0;
}

B Semifinals
题意：有2场半决赛,各有n个参与者,一共将有n个参与者进入决赛.我们分别在2场比赛中选前k个直接进入决赛,再将剩下的人放在一起排名,选前n-2k个进入决赛.
在k不定的情况下,求哪些人有机会进入决赛,哪些人没有.
思路:k=0和k=n/2分别代表了两种极限情况,其他情况都在这两种之间,分别处理一下即可

#include <cstdio>
#include <cstring>
const int N = 100005;
int n,a[N],b[N];
int an[N],bn[N];
void Deal ()
{
    int i;
    for (i=0;i<n/2;i++)
        an[i]=bn[i]=1;
    int ida=0,idb=0;
    for (i=0;i<n;i++)
        if (a[ida] < b[idb])
            an[ida++] = 1;
        else
            bn[idb++] = 1;
}
int main ()
{
        scanf("%d",&n);
    memset(an,0,sizeof(an));
    memset(bn,0,sizeof(bn));
    int i;
    for (i=0;i<n;i++)
        scanf("%d%d",&a[i],&b[i]);
    Deal ();
    for (i=0;i<n;i++)
        printf("%d",an[i]);
    printf("\n");
    for (i=0;i<n;i++)
        printf("%d",bn[i]);
    printf("\n");
    return 0;
}

C Maze
题意:给n*m的迷宫,所有’.’为可以通过的地方(给出时所有’.’都四个方向连通),加入k块墙,另所有’.’依然连通,求方案
貌似我想的稍微复杂了些,这里有个简单的思路 http://blog.csdn.net/wangyuquanliuli/article/details/17675801

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int N=505;
struct Point
{
    int x,y,step;
};
char map[N][N];
int id[N][N]; //记录每个位置被BFS到时的距离
bool visit[N][N];
int cal[N*N]; //记录每种距离有多少个点
int m,n,k;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int OK (int x,int y)
{
    return x>=0 && x<n && y>=0 &&y<m && map[x][y]=='.' && visit[x][y]==false;
}
int BFS (int sx,int sy)
{
    Point top,t;
    queue <Point> Q;
    memset(visit,false,sizeof(visit));
    memset(id,0,sizeof(id));
    top.step=0;
    top.x=sx;
    top.y=sy;
    Q.push(top);
    visit[top.x][top.y]=true;
    int m=0; //记录BFS的最远距离
    while (Q.empty()==false)
    {
        top=Q.front();
        Q.pop();
        for (int i=0;i<4;i++)
        {
            t.x=top.x+dx[i];
            t.y=top.y+dy[i];
            t.step=top.step+1;
            if (OK(t.x,t.y))
            {
                visit[t.x][t.y]=true;
                id[t.x][t.y]=t.step;
                m=max(m,t.step);
                cal[t.step]++;
                Q.push(t);
            }
        }
    }
    return m;
}
int main ()
{
    scanf("%d%d%d",&n,&m,&k);
    int i,j;
    for (i=0;i<n;i++)
        scanf("%s",map[i]);
    int sx,sy;
    cal[0]++;
    bool flag=false;
    for (i=0;i<n;i++)
    {//找第一个'.'
        for (int j=0;j<m;j++)
            if (map[i][j]=='.')
            {
                sx=i;sy=j;
                flag=true;
                break;
            }
        if (flag)
            break;
    }
    int limit=BFS(sx,sy);
    if (limit == 0)
    {
        for (i=0;i<n;i++)
            printf("%s\n",map[i]);
        return 0;
    }
    int sum=0;
    for (i=limit;i>=0;i--)
    {//记录在哪些距离上的点可以被填充
        if (sum+cal[i]<=k)
            sum+=cal[i];
        else break;
    }
    int start=++i,ss=k-sum;//ss记录还需要填充多少点
    for (i=0;i<n;i++)
        for (j=0;j<m;j++)
        {
            if (id[i][j]>=start)
                map[i][j]='X';
            if (ss>0 && id[i][j]==start-1)
            {
                map[i][j]='X';
                ss--;
            }
        }
    for (i=0;i<n;i++)
        printf("%s\n",map[i]);
    return 0;
}

D Preparing for the Contest
有m个bug,每个bug有级别,有n个人去修复bug,每个人有能力等级和需求.现在总共有s个费用.求最少天数完成的方法,并且输出方案.
思路：二分+贪心+优先队列优化

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100005;
int n,m,s;
int ans[N];
struct Student
{
    int b,c,id;
    bool operator < (Student b) const
    {//花费小的优先
        return c>b.c;
    }
}stu[N];
struct Bug
{
    int a,id;
    bool operator < (Bug b) const
    {
        return a<b.a;
    }
}bug[N];
int cmp (Student a, Student b)
{
    return a.b > b.b;
}
void solve (int time)
{
    int limit=s,cnt=0;
    priority_queue <Student> Q;
    for (int i=m-1;i>=0;i-=time)
    {
        while (stu[cnt].b >= bug[i].a && cnt != n)
            Q.push(stu[cnt++]);
        Student t = Q.top();
        Q.pop();
        limit -= t.c;
        int e=i-time+1;
        if (e<0) e=0;
        for (int j=i; j>=e ;j--)
            ans[bug[j].id] = t.id;
    }
}
bool OK (int time)
{
    int limit=s, cnt=0;
    priority_queue<Student> Q;
    for (int i=m-1;i>=0;i-=time)
    {
        while (stu[cnt].b >= bug[i].a && cnt != n)
            Q.push(stu[cnt++]);//将所有能解决该问题的学生放入优先队列,花费小的优先
        if (Q.empty()) return false;
        Student t = Q.top();
        Q.pop();
        if (limit < t.c) return false;
        limit -= t.c;
    }
    return true;
}
void Deal ()
{
    if (OK(m)==false)
    {
        printf("NO\n");
        return;
    }
    int low=0,high=m,tmp;
/*    while (low < high) //这么写也可以
    {
        int mid=(low+high)>>1;
        if (OK(mid)) high=mid;
        else low=mid+1;
    }
    solve(high);
    */
    while (low <= high)
    {
        int mid=(low+high)>>1;
        if (OK(mid)) high=mid-1,tmp=mid;
        else low=mid+1;
    }
    solve(tmp);
    printf("YES\n");
    for (int i=0;i<m;i++)
        printf(i==m-1?"%d\n":"%d ",ans[i]+1);
}
int main ()
{
    int i;
    scanf("%d%d%d",&n,&m,&s);
    for (i=0;i<m;i++)
    {
        scanf("%d",&bug[i].a);
        bug[i].id=i;
    }
    for (i=0;i<n;i++)
    {
        scanf("%d",&stu[i].b);
        stu[i].id=i;
    }
    for (i=0;i<n;i++)
        scanf("%d", &stu[i].c);
    sort(bug, bug+m); //按照等级降序排序
    sort(stu, stu+n, cmp); //按照能力升序排序
    Deal ();
    return 0;
}