Codeforces Round #154 (Div. 2)

从此醉

浏览: 1044334 次
性别:
来自: US

最近访客更多访客>>

billyhhzh

u012363178

devcang

宝帅啊啊啊

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

点击打开链接codeforce#154

A
思路：水题
分析：题目要求‘B’和‘G’是交替出现，所以应该要注意判断一下男生和女生的数量，然后是先B还是先G。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int main(){
  int n , m;
  while(scanf("%d%d" , &n , &m) != EOF){
     if(n > m){
       for(int i = 0 ; i < m ; i++)
          printf("BG");
       int tmp = n-m;
       while(tmp--)
          printf("B");
     }
     else{
       for(int i = 0 ; i < n ; i++)
          printf("GB");
       int tmp = m-n;
       while(tmp--)
          printf("G");
     }
     printf("\n");
  }
  return 0;
}

B
思路：水题
分析：
1 先注意一个事实就是不能够从后面和前面找，然后找到num[i]*2 >= num[j]满足了就认为是ans。
2 这种思想是错误的，正确的思路就是枚举每一个可能的起始值，然后求当前要删除的个数，最后得到最少的值即可。
3 那么我们就应该要先排序，然后是一个有序的序列，我们可以利用维护一个指针j，j是不用回溯的，因为随着i的增大，num[i]*2 >= num[j]肯定是满足的。所以复杂度完全可以接受。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 100010

int main(){
  int n;
  int num[MAXN];
  while(scanf("%d" , &n) != EOF){
     for(int i = 0 ; i < n ; i++)   
       scanf("%d" , &num[i]);
     sort(num , num+n);
     int ans = 0xFFFFFFF;
     int j = 0;
     for(int i = 0 ; i < n ; i++){
        if(i && num[i-1] == num[i])
           continue;
        for(; j < n ; j++){
           if(num[i]*2 < num[j])
             break;
        }
        int tmp = i+n-j;
        ans = min(ans , tmp);
     }
     cout<<ans<<endl;
  }
  return 0;
}

思路：bfs 或枚举中间行

分析：
1 bfs的时候要注意判断什么时候不满足
2 枚举中间行的做法应该注意如果从r1->i->r2后现在没有改变当前所在的列那么应该是c1->c2，这个地方注意。

代码：

//bfs
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define MAXN 110

int n;
int Sx , Sy , Ex , Ey;
int num[MAXN];
bool vis[MAXN][100000];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
struct Node{
   int x;
   int y;
   int step;
};
queue<Node>q;

int BFS(){
    while(!q.empty())
        q.pop();
    memset(vis , false , sizeof(vis));
    Node tmp;
    tmp.x = Sx , tmp.y = Sy , tmp.step = 0;
    vis[Sx][Sy] = true;
    q.push(tmp);
    
    while(!q.empty()){
       tmp = q.front();
       q.pop();
       if(tmp.x == Ex && tmp.y == Ey)
         return tmp.step;
       int x , y;
       for(int i = 0 ; i < 4 ; i++){
          x = tmp.x+dir[i][0];
          y = tmp.y+dir[i][1];
          if(x < 1 || x > n)
             continue;
          //注意判断y是否满足
          if(y < 1 || dir[i][1] && y > num[tmp.x])
             continue;
          //求出具体的点（y肯定是小的那一个）
          y = min(y , num[x]);
          if(vis[x][y])
             continue;
          vis[x][y] = true;
          Node tmpNode;
          tmpNode.x = x;
          tmpNode.y = y;
          tmpNode.step = tmp.step+1;
          q.push(tmpNode);
       }
    }
}

int main(){
   while(scanf("%d" , &n) != EOF){
      for(int i = 1 ; i <= n ; i++){
         scanf("%d" , &num[i]);
         num[i]++;//最末尾位置可以用
      }
      scanf("%d%d%d%d" , &Sx , &Sy , &Ex , &Ey);
      printf("%d\n" , BFS());
   }
   return 0;
}

//枚举中间行
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define MAXN 110

int n;
int num[MAXN];
int R1 , C1 , R2 , C2;

int main(){
    while(scanf("%d" , &n) != EOF){
       for(int i = 1 ; i <= n ; i++){
          scanf("%d" , &num[i]);
          num[i]++;
       }
       scanf("%d%d%d%d" , &R1 , &C1 , &R2 , &C2);
       int ans = 1<<30;

       for(int i = 1 ; i <= n ; i++){
          int MIN , min1 , min2;
          if(i < R1)
             min1 = *min_element(num+i , num+R1+1);
          else
             min1 = *min_element(num+R1 , num+i+1);
          if(i < R2)
             min2 = *min_element(num+i , num+R2+1);
          else
             min2 = *min_element(num+R2 , num+i+1);
          MIN = min(min1 , min2);
          MIN = min(C1 , MIN);//这里还要和C1做一下比较
          int tmpAns = abs(R1-i)+abs(R2-i)+abs(MIN-C2);
          ans = min(ans , tmpAns);
       }
       cout<<ans<<endl;
    }
    return 0;
}

题意：

1 给定一个n*m的矩阵每个格子有一个字母，现在要求有多少的子矩阵满足四个角的字母相同并且这个子矩阵的字母的个数不大于k

分析：

1 首先利用o(n*m)的时间求出每个点到左上角这个矩阵字母'a'的个数

2 枚举子矩阵的起始行和末尾行，如果直接枚举列总的时间复杂度是O(n^2*m^2)效率肯定是不行的。我们需要把时间优化到O(x*n^2*m)，x是常数。

我们利用vector记录每个字母在每一行中的位置，然后对于同一行来说越后面总的子矩阵的'a'的个数越来越多，我们可以利用二分，最后总的时间复杂度为O(logm*n^2*m)

代码：

#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 410;
const int N = 26;

int n , m , k;
int sum[MAXN][MAXN];
char mat[MAXN][MAXN];
vector<int>v[N];

void clear(){
	for(int i = 0 ; i < N ; i++)
		v[i].clear();
}

bool isOk(int r1 , int r2 , int c1 , int c2){
	int num = sum[r2][c2]-sum[r2][c1-1]-sum[r1-1][c2]+sum[r1-1][c1-1];
	return (num <= k);
}

int64 getSub(int x , int r1 , int r2 , int c){
    int64 ans = 0;
	int left = 0;
	int right = v[x].size()-1;
	while(left < right){
		int mid = (left+right)>>1;
		if(isOk(r1 , r2 , v[x][mid] , c)){
			ans += right-mid;
			right = mid;
		}
		else
			left = mid+1;
	}
	return ans;
}

int64 solve(){
	int64 ans = 0;
	memset(sum , 0 , sizeof(sum));
	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= m ; j++)
			sum[i][j] = sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(mat[i][j] == 'a');
	// begin and end row
	for(int i = 1 ; i <= n ; i++){
		for(int j = i+1 ; j <= n ; j++){
			clear();
			// col
			for(int c = 1 ; c <= m ; c++){
				// 两点相等
				if(mat[i][c] == mat[j][c]){
				   v[mat[i][c]-'a'].push_back(c);
                   ans += getSub(mat[i][c]-'a' , i , j , c);
				}
			}
		}
	}
	return ans;
}

int main(){
	while(scanf("%d%d%d%*c" , &n , &m , &k) != EOF){
		for(int i = 1 ; i <= n ; i++)
			gets(mat[i]+1);
		cout<<solve()<<endl;
	}
	return 0;
}

题意：

1 有一个打印机每秒钟只能打印一页，现在有n个任务，每个任务有一个到来的时间t，以及这个任务要打印的页数s，还有打印的优先级p

2 现在我们知道n-1任务的优先级，还有一个不知道，但是这个不知道的任务我们知道它完成打印的时间T，问这个不知道的认为的优先级

分析：

1 对于给定的优先级，我们可以求出所有的任务的结束时间。

2 我们已经知道了n-1个任务的优先级，那么我们可以利用二分来求未知任务的优先级，然后根据结果进行判断。

3 求所有任务的结束时间，我们只要维护一个优先队列即可。

代码：

#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int INF = 1e9;
const int MAXN = 50010;

struct Node{
	int t;
	int s;
	int p;
	int id;
	bool operator<(const Node& tmp)const{
		return p < tmp.p;
	}
};
int n , pos , maxP;
int64 T;
int64 ans[MAXN];
Node node[MAXN];
Node tmpNode[MAXN];
map<int64 , int>mp;

bool cmp(const Node& a , const Node& b){
	if(a.t < b.t)
		return true;
	else if(a.t == b.t && a.p > b.p)
		return true;
	return false;
}

int64 getTime(int p){

	memcpy(tmpNode , node , sizeof(node));
	tmpNode[pos].p = p;
	sort(tmpNode , tmpNode+n , cmp);

	priority_queue<Node>q;
	int i = 1;
	int64 time = tmpNode[0].t;
	int64 val;
	q.push(tmpNode[0]);

    // push n tmpNodes
	while(!q.empty() || i < n){
		Node tmp;
		if(!q.empty()){
			tmp = q.top();
			q.pop();
		}
		else{
			time = tmpNode[i].t;
			q.push(tmpNode[i++]);
			continue;
		}

		if(i >= n){
			time += tmp.s;
			ans[tmp.id] = time;
			if(tmp.id == pos)
				val = time;
			continue;
		}
		int t = tmpNode[i].t-time;
		if(tmp.s > t){
			tmp.s -= t;
			q.push(tmp);
			q.push(tmpNode[i]);
			time = tmpNode[i++].t;
		}
		else{
			time += tmp.s;
			ans[tmp.id] = time;
			if(tmp.id == pos)
				val = time;
		}
	}
	return val;
}

void solve(){
	// binary search
	int left = 1;
	int right = maxP+1; 
	int ansp = -1;
	while(left < right){
		int mid = (left+right)>>1;
		int64 time = getTime(mid);
		if(time == T && mp[mid] == 0){
            ansp = mid;
			break;;
		}
		else if(time < T)
			right = mid;
		else
			left = mid+1;
	}
	if(ansp == -1){
		ansp = left;
		getTime(left);
	}
	cout<<ansp<<endl<<ans[0];
	for(int i = 1 ; i < n ; i++)
		cout<<" "<<ans[i];
	puts("");
}

int main(){
	while(scanf("%d" , &n) != EOF){
		maxP = 0;
		mp.clear();
		for(int i = 0 ; i < n ; i++){
			scanf("%d%d%d" , &node[i].t , &node[i].s , &node[i].p);
			node[i].id = i;
			maxP = max(maxP , node[i].p);
			mp[node[i].p] = 1;
			if(node[i].p == -1)
				pos = i;
		}
		cin>>T;
		solve();
	}
	return 0;
}

分享到：