Croc Champ 2013 - Round 2 (Div. 2 Edition) 贪心+ 搜索+剪枝 + 数学-白红宇

Croc Champ 2013 - Round 2 (Div. 2 Edition) 贪心+ 搜索+剪枝 + 数学

阅读量：7088 次

发布时间：2019-06-28

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

A：

直接找出最小值，看是否能被所有数整除即可

判断是否出现连续的“#”>=m若果存在肯定不能调。

题意：

两个人玩游戏（A，B），每个人分配一个字符串长度为2*n的字符串s1,s2,然后A先从[1~2*n]选一个数i，然后他就从s1中取走s1[i]，然后是B从[1~2*n]中选一个还未曾被选过的数然j后取走s2[j]最后他们分别否会获得n个“0”，“1”他们可以任意组合这些0,1最后谁组合出来的数最大谁赢，若想等则平局。

思路：

首先分析如果出现s1[i] = s2[i] = 1的话，他们肯定会去这个“1”因为这样既保证自己得到一个1，另一方失去一个1，如果存在计数个那么最后A肯定比B多1，如果是偶数个，那么两人得到的1的个数相同，然后就看剩下的怎么取了，如果剩下的为偶数个那么第一个取的是A，首先我会把所有能够取到的1取得，然后将对方能够消除的1消除，奇数时B先取同上。然后我们判断只要先取的一方把能取的都取完了，然后对方只能获得剩下他能取的一半了。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 2000017using namespace std;const int inf = 100000007;const int mod = 1000000007;char s1[N],s2[N];int main(){// Read(); int i; int n; scanf("%d",&n); scanf("%s%s",s1,s2); int n1 = 0; int n2 = 0; int ct = 0; for (i = 0; i < 2*n; ++i) { if (s1[i] == '1' && s2[i] == '1') { s1[i] = '0'; s2[i] = '0'; ct++; } } int tmp = 0; if (ct%2 == 1) tmp = 1; for (i = 0; i < 2*n; ++i) { if (s1[i] == '1') n1++; if (s2[i] == '1') n2++; } int mk = (2*n - ct)/2; if ((2*n - ct)%2 == 1) { if (n1 > n2) { n1 = n2 + (n1 - n2)/2; } else { n2 = n1 + (n2 - n1 + 1)/2; }// printf("%d %d\n",n1,n2); } else { if (n1 > n2) { n1 = n2 + (n1 - n2 + 1)/2; } else { n2 = n1 + (n2 - n1)/2; } } n1 += tmp;// printf("%d %d\n",n1,n2); if (n1 > n2) printf("First\n"); else if (n1 == n2) printf("Draw\n"); else printf("Second\n"); return 0;}

题意:

给你一个n*m的矩阵，里面的有些方格被染色了，有些没有，让我们用小于k的的颜色,将该矩形染满颜色，要求从左上角到右下角的路径中不存在两个颜色相同的。问一共有多少中可能。

思路：

暴力搜索+强剪纸

用u[i]记录每一中颜色的在已经走过的矩阵中使用的次数，如果x,y在这之前还没出现过，那么当前小方格内取x或者y所形成的方法数目是相同的利用这个剪纸可以减少很多搜索，还可以利用类似A*的，当前路径已经用了多少颜色，后边每一步还需要多少颜色，如果总和超过k就是不合法的路径。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 1025using namespace std;const int inf = 0x7f7f7f7f;const int mod = 1000000007;int state[N];int a[1007][1007];int s[1007][1007];int u[11];int n,m,k;ll dfs(int x,int y){ if (y > m) return dfs(x + 1,1); if (x > n) return 1; ll ans = 0; int cur = s[x - 1][y]|s[x][y - 1]; if (n + m - x - y + __builtin_popcount(cur) >= k) return 0;//剪枝2 ll w = -1; for (int v = (~cur)&((1<

题意：

给出n（n<= 10^14）求满足 a^3 + b^3 + c^3 + n = (a + b + c)^3 的a,b,c的个数。

思路：

首先我们能够推出公式(a + b)*(a + c) *(b + c) = n;

然后我们就可以枚举

(a + b) = i; (a + c) = j; (b + c) = k;

a >= 1; b >= 1; c >= 1; === > i + j - k >= 1 ......

a <= b <= c ;

然后求解即可。

这里好像根据线性代数对着三个方程证明一定存在可行解。

View Code

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  #include 
                   
                    #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define ll __int64#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout);#define M 137#define N 100007using namespace std;const int inf = 100000007;const int mod = 1000000007;ll fact[N];int len;int main(){// Read(); int i,j; ll n; while (~scanf("%I64d",&n)) { if (n%3 == 1) { printf("0\n"); continue; } n /= 3; len = 0; for (ll p = 1; p*p <= n; ++p) { if (n%p == 0) { fact[len++] = p; } } ll ans = 0; for (i = 0; i < len; ++i) { for (j = i; j < len; ++j) { ll ti = fact[i]; ll tj = fact[j]; ll tk = n/(fact[i]*fact[j]); if (tk < ti || tk < tj) break; if (n%(fact[i]*fact[j]) != 0) continue; if ((ti + tk + tj)%2 != 0) continue; if (ti + tk - tj >= 2 && tj + tk - ti >= 2 && ti + tj - tk >= 2) { if (ti == tj && tj == tk) ans++; else if (ti == tj || tj == tk || tk == ti) ans += 3; else ans += 6; } } } cout<
                    
                     <

转载地址：http://mxyql.baihongyu.com/

你可能感兴趣的文章