Codeforces Beta Round #4 (Div. 2 Only)

点击打开链接

A

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

int main(){
   int n;
   while(scanf("%d" , &n) != EOF){
      if(n < 4)
        printf("NO\n");
      else{
        if(n%2 == 0)
          printf("YES\n");
        else
          printf("NO\n");
      }
   }

   return 0;
}

B

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

#define MAXN 35

int d , sumTime;
int minTime[MAXN] , maxTime[MAXN];

int main(){
   int tmpMin , tmpMax;
   while(scanf("%d%d" , &d , &sumTime) != EOF){
      tmpMin = tmpMax = 0;
      for(int i = 0 ; i < d ; i++){
         scanf("%d%d" , &minTime[i] , &maxTime[i]);
         tmpMin += minTime[i];
         tmpMax += maxTime[i];
      }
      if(tmpMin > sumTime || sumTime > tmpMax)
         printf("NO\n");
      else{
         int mark = 0;
         printf("YES\n");
         for(int i = 0 ; i < d ; i++){
            if(tmpMin != sumTime){
               int count = minTime[i];
               for(int j = minTime[i]+1 ; j <= maxTime[i] ; j++){
                  if(tmpMin == sumTime)
                    break;
                  count++;
                  tmpMin++;
               }
               if(!mark){
                 printf("%d" , count);
                 mark = 1;
               }
               else
                 printf(" %d" , count);
            }
            else{
              if(!mark){
                printf("%d" , minTime[i]);
                mark = 1;
              }
              else
                printf(" %d" , minTime[i]);
            }
         }
      }
   }
   return 0;
}

C

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

#define MAXN 100010
#define N 40

int n , pos;
char ch[MAXN][N];
int vis[MAXN];

int main(){
  char name[N];
  while(scanf("%d" , &n) != EOF){
      memset(vis , 0 , sizeof(vis));
      pos = 0;

      int mark , cnt , p;
      for(int i = 0 ; i < n ; i++){
         scanf("%s" , name);
         mark = 1;
         for(int j = 0 ; j < pos ; j++){
            if(strcmp(ch[j] , name) == 0){
              mark = 0;
              cnt = vis[j]++;
              p = j;
              break;
            }
         }
         if(mark){
           printf("OK\n");
           strcpy(ch[pos] , name);
           vis[pos++]++;
         }
         else
           printf("%s%d\n" , ch[p] , cnt);
      }
  }
  return 0;
}

D

/*
思路：dp+路径输出
分析：
1 题目要求的是找到最多的信封的个数并输出编号，如果没有则输出0
2 很明显额矩形嵌套问题，利用dp求解，路径输出利用回溯法记录前驱点。

代码：
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 5010

int n , w , h;
int pos , ans , mark;
int pre[MAXN];
int dp[MAXN];
struct envelop{
   int w;
   int h;
   int number;
}e[MAXN];

/*排序*/
bool cmp(envelop e1 , envelop e2){
   if(e1.w != e2.w)
     return e1.w < e2.w;
   return e1.h < e2.h;
}

/*事先判断有没有满足的信封*/
bool judge(){
   for(int i = 0 ; i < n ; i++){
      if(e[i].w > w && e[i].h > h){
        pos = i;
        return true;
      }
   }
   return false;
}

/*回溯法输出*/
void output(int x){
  if(pre[x] == x){
     printf("%d" , e[x].number);
     return;
  }
  output(pre[x]);
  printf(" %d" , e[x].number);
}

void solve(){

   ans = 0;
   for(int i = pos ; i < n ; i++){
      dp[i] = 1;
      pre[i] = i;
      for(int j = pos ; j < i ; j++){
         if(e[j].w > w && e[j].h > h && e[i].w > e[j].w && e[i].h > e[j].h && dp[j]+1 > dp[i]){
            dp[i] = dp[j] + 1;
            pre[i] = j;
         }
      }
      if(ans < dp[i]){
        ans = dp[i];
        mark = i;
      }
   }
   printf("%d\n" , ans);
   output(mark);
   printf("\n");
}

int main(){
   while(scanf("%d%d%d" , &n , &w , &h) != EOF){
      for(int i = 0 ; i < n ; i++){
         scanf("%d%d" , &e[i].w , &e[i].h);
         e[i].number = i+1;
      }
      sort(e , e+n , cmp);
      if(!judge())
        printf("0\n");
      else
        solve();
   }
   return 0;
}