Codeforces #263 div2 解题报告-白红宇

Codeforces #263 div2 解题报告

阅读量：6997 次

发布时间：2019-06-27

本文共 4653 字，大约阅读时间需要 15 分钟。

比赛链接：

这次比赛的时候，刚刚注冊的时候非常想好好的做一下，可是网上喝了个小酒之后。也就迷迷糊糊地看了题目，做了几题。一觉醒来发现rating掉了非常多，那个心痛啊！

只是。后来认真的读了题目，发现这次的div2并非非常难！

官方题解：

A. Appleman and Easy Task

解析：

一个水题，推断每一个细胞周围是否都是有偶数个相邻细胞。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define Lowbit(x) ((x)&(-(x)))#define ll long long#define mp make_pair#define ff first#define ss second#define pb push_backconst int MAXN=1005;ll a[30];int n;char str[105][105];bool check(int i, int j){ int tmp = 0; if(i>0&&str[i-1][j]=='o') ++tmp; if(i
              
               0&&str[i][j-1]=='o') ++tmp; if(j

"YES":"NO"); return 0; }

B. Appleman and Card Game

解析：

两个水题，贪心问题，直接统计每一个字母出现的次数。然后sort一下，每次取最大的。

可是，这里要注意一下数据范围。结果用long long表示。在计算过程中须要强制类型转换。尤其k在计算中一定要是long long型

代码：

//#define LOCAL#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define Lowbit(x) ((x)&(-(x)))#define ll long long#define mp make_pair#define ff first#define ss second#define pb push_backconst int MAXN=1005;ll a[30];char str[100010];int main(){ #ifdef LOCAL freopen("1.in", "r",stdin); //freopen("1.out", "w", stdout); #endif int n; ll k; scanf("%d%I64d", &n, &k); scanf("%s", str); int len = strlen(str); memset(a, 0, sizeof(a)); for(int i=0; i
              
               =0&&k>0; --i){ if(k>=a[i]){ sum += a[i]*a[i]; k -= a[i]; } else{ sum += k*k; k-=k; } } printf("%I64d\n", sum); return 0;}

C. Appleman and Toastman

解析：

三个水题，贪心嘛，每次将最小的那个数字单独拆开。能够用sort也能够用priority_queue。

代码：

//#define LOCAL#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define Lowbit(x) ((x)&(-(x)))#define ll long long#define mp make_pair#define ff first#define ss second#define pb push_backconst int MAXN=1005;int main(){ #ifdef LOCAL freopen("1.in", "r",stdin); //freopen("1.out", "w", stdout); #endif int i,n; ll sum = 0; ll score = 0,tmp; priority_queue< ll, vector
              
               , greater
               
                 >pq; scanf("%d", &n); for(i=0; i
                
                 1){ score += sum; tmp = pq.top(); pq.pop(); sum -= tmp; } printf("%I64d", score); return 0;}

D. Appleman and Tree

解析：

这是一道DP问题，用到树形DP；

题意：给了一棵树以及每一个节点的颜色。1代表黑。0代表白，要求的是。假设将这棵树拆成k棵树，使得每棵树恰好有一个黑色节点

dp[v][0 ]表示以v为根没有黑节点子树的数目

dp[v][1] 表示以v为根有黑节点子树的数目

说实话。我遇到DP还是比較犯怵的，所以在比赛的时候发现这是道DP问题，也就懒得在动用喝醉的大脑了。直接GG了。

代码：

//#define LOCAL#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define Lowbit(x) ((x)&(-(x)))#define ll long long#define mp make_pair#define ff first#define ss second#define pb push_back#define mod 1000000007const int MAXN=100010;ll dp[MAXN][2];vector
              
                x[MAXN];int c[MAXN];void dfs(int v,int p){ dp[v][0] = 1; dp[v][1] = 0; for(int i=0; i

E. Appleman and a Sheet of Paper

解析：

说实话这个题目根本不须要怎么多读，直接看例子的分析就知道题意了。就是简单的叠纸条，然后查询区间的纸条总厚度

这里能够用BIT（树状数组）。也能够用线段树。

这里的代码，我用的是树状数组。

本题解答的一个巧妙的地方就是，假设左边叠的长。那么我们能够反过来把右边的叠过来，可是纸条的左右方向要转向，所以这里用了一个flag标记左右的方向。其它部分就和普通的树状数组是一样的做法。

代码：

//#define LOCAL#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define Lowbit(x) ((x)&(-(x)))//#define ll long long#define mp make_pair#define ff first#define ss second#define pb push_back#define mod 1000000007const int MAXN=100010;int c[MAXN], s[MAXN],n;void ADD(int p, int val){ s[p] += val; while(p<=n){ c[p] += val; p += Lowbit(p); }}int getsum(int p){ int sum = 0; while(p>0){ sum += c[p]; p -= Lowbit(p); } return sum;}int main(){ #ifdef LOCAL freopen("1.in", "r",stdin); //freopen("1.out", "w", stdout); #endif int i, p; scanf("%d%d", &n, &p); memset(c, 0, sizeof(c)); memset(s, 0, sizeof(s)); for(i=1; i<=n; ++i) ADD(i, 1); int l=1, r=n; int x,y,z; int flag = 0; for(int k=0; k
              
               (r-l+1)); int mid; if(flag) mid = r-y; else mid = l+y-1; int ll = mid-l+1; int rr = r-mid; if(ll<=rr){ for(i=l; i<=mid; ++i) ADD(2*mid+1-i, s[i]); l = mid+1; } else{ for(i=mid+1; i<=r; ++i) ADD(2*mid+1-i, s[i]); r = mid; } flag ^= fg; //标记。假设左边长。那么就向左叠，而且从右向左读； //假设左边短，那么就向右叠，而且从左向右读。 } else{ scanf("%d%d", &y,&z); if(flag) printf("%d\n", getsum(r-y)-getsum(r-z)); else printf("%d\n", getsum(l+z-1)-getsum(l+y-1)); } } return 0;}

转载于:https://www.cnblogs.com/clnchanpin/p/6803790.html

你可能感兴趣的文章

一个全新的无人机需用到哪些功能的传感器技术？