Codeforces Round #222 (Div. 2) ABCD

待我称王封你为后i 2022-08-24 14:14 155阅读 0赞

继续总结做过的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;
    }