codeforces_#242 (Div. 2)

这个在codeforces的题目编号是424A-424E

424A，Squats

题目意思：

就是给你n个人，X表示站着，x表示坐着

你在一秒可以让一个人站着或坐着

给你n个人的状态，问你要几秒可以让一般人站着，并输出改变后的结果，很水，不想多说

#include
  
   
#include
   
     using namespace std; const int maxn = 200+20; bool flag[maxn]; char s[maxn]; int n,cnt; int main() { while(~scanf(%d,&n)) { cnt = 0; scanf(%s,s); for(int i=0;i
    
     0) { printf(X); ca--; } else printf(%c,s[i]); } printf( ); } else { int ca = cnt-n/2; printf(%d ,ca); for(int i=0;i
     
      0) { printf(x); ca--; } else printf(%c,s[i]); } printf( ); } } } return 0; } 
     
    
   
  

题目地址：http://codeforces.com/problemset/problem/424/B

题目大意：

你在（0，0）位置上，已经有了s个人，但是你需要1000000个人，你需要扩展

然后你周围的城市的坐标和人告诉你，问你抽气这么多人，需要扩张多大

解题思路：

把周围的按半径排序，然后一个一个加，加够了就break

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const double eps = 1e-10; const int maxn =1000+20; const int billion = 1000000; int n; struct pp { int x,y,k; double r; }; pp p[maxn]; bool cmp(pp a,pp b) { return a.r
      
       = billion) { ans = p[i].r; break; } } if(ans<0) printf(-1 ); else printf(%.8lf ,ans); } return 0; } 
      
     
    
   
  

题目地址：http://codeforces.com/problemset/problem/424/C

题目意思：

给你p1,p2,...,pn

然后定义：

解题思路：

我们发现异或是满足交换律的，所以首先可以是p1^p2^p3^...^pn

然后再就是后面的mod之后的异或

我们发现可以归纳为(1%i)^(2%i)^(3%i)^...^(n%i)，i from 1 to n

那么对于一个i来说，上面就为1^2^3^...^(i-1)^0 这样的一个循环，最后再加上一个尾巴

这样如果前面的循环是偶数就是0了，如果是奇数个，就是他本身，最后再异或上那个尾巴就可以了，这里可以先预处理一下

对于每个i我们都这么求，就可以解决了

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int maxn = 1000000+20; int xor_n[maxn]; int p[maxn]; int n; int q; void init() { xor_n[0]=0; for(int i=1;i
      
        424D，Biathlon Track
       
 
       
题目地址：http://codeforces.com/problemset/problem/424/D
       
题目大意：
       
给你一个N×M的矩阵，上面有数字，从大的到小的要花费td，从小的到大的要花费tu，大小一样花费tp
       
要你这一个顺时针的圈，使这个花费加起来最接近t，四个边都要>=3
       
解题思路：
       
这是第一种方法，比较暴力，先预处理从4个方向到自己的花费
       
然后枚举4个点用O（1）算，注意这里abs最后自己写，并且只用一次，用多了就TLE了
       
 
       
#include
        
         
#include
         
           #include
          
            #include
           
             using namespace std; const int maxn=300+10; struct node { int up,down,left,right; int height; }; node ma[maxn][maxn]; int n,m; int tp,tu,td,t; inline int abs2(int x) { if (x < 0) x = -x; return x; } int main() { while(~scanf(%d%d%d,&n,&m,&t)) { scanf(%d%d%d,&tp,&tu,&td); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf(%d,&ma[i][j].height); ma[i][j].up = ma[i][j].down = ma[i][j].left = ma[i][j].right = 0; if(i!=1) { if(ma[i-1][j].height < ma[i][j].height) { ma[i][j].up = ma[i-1][j].up + tu; } else if(ma[i-1][j].height > ma[i][j].height) { ma[i][j].up = ma[i-1][j].up + td; } else ma[i][j].up = ma[i-1][j].up + tp; } if(j!=1) { if(ma[i][j-1].height < ma[i][j].height) { ma[i][j].left = ma[i][j-1].left + tu; } else if(ma[i][j-1].height > ma[i][j].height) { ma[i][j].left = ma[i][j-1].left + td; } else ma[i][j].left = ma[i][j-1].left + tp; } } } for(int i=n;i>=1;i--) { for(int j=m;j>=1;j--) { if(i!=n) { if(ma[i+1][j].height < ma[i][j].height) { ma[i][j].down = ma[i+1][j].down + tu; } else if(ma[i+1][j].height > ma[i][j].height) { ma[i][j].down = ma[i+1][j].down + td; } else ma[i][j].down = ma[i+1][j].down + tp; } if(j!=m) { if(ma[i][j+1].height < ma[i][j].height) { ma[i][j].right = ma[i][j+1].right + tu; } else if(ma[i][j+1].height > ma[i][j].height) { ma[i][j].right = ma[i][j+1].right + td; } else ma[i][j].right = ma[i][j+1].right + tp; } } } int ar1,ar2,ac1,ac2; bool f=false; int ans = 2000000000; for(int r1=1;r1<=n;r1++) { for(int c1=1;c1<=m;c1++) { for(int r2=r1+2;r2<=n;r2++) { for(int c2=c1+2;c2<=m;c2++) { int tmp = abs(t- (ma[r2][c2].up - ma[r1][c2].up + ma[r1][c2].left - ma[r1][c1].left + ma[r2][c1].right - ma[r2][c2].right + ma[r1][c1].down - ma[r2][c1].down)); if(tmp < ans) { ans = tmp; ar1 = r1; ar2 = r2; ac1 = c1; ac2 = c2; } } } } } printf(%d %d %d %d ,ar1,ac1,ar2,ac2); // printf(ans %d ,ans); } return 0; } 
           
          
         
        
 
       
 
       
 
       
 
 
       
 
 
       
还有一种更效率的方法以及最后一题我后面再更新。