Codeforces Round #228 (Div. 2)

A. Fox and Number Game

题意：有 n 个数， 每次找一对 i ， j 满足a[i] > a[j],然后 a[i] = a[i] - a[j],问最后剩下的数的和最小是多少。

分析： 每次找最小的数，看看哪些数比它大，然后减去，直到所有数相等。

/****************************************
* File Name: 228d2a.cpp
* Author: sky0917
* Created Time: 2014年02月 5日 13:32:03
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 102;int a[maxn];
int main(){int n;while (scanf("%d",&n)!=EOF){for (int i=0; i<n; i++)scanf("%d",&a[i]);while (1){int d = a[0];for (int i=1; i<n; i++){if (a[i] < d)d = a[i];   }int f = 1;for (int i=0; i<n; i++){if (a[i] > d){a[i] -= d;f = 0;}}if (f) break;}int sum = 0;for (int i=0; i<n; i++)sum += a[i];printf("%d\n",sum);}   return 0;
}

 

B. Fox and Cross

题意：有个grid，里面有 "#" 和 “." ，问是否可以找到一些十字，如下：

         #

      ###

        #

      把grid 中的 # 全部覆盖，并且不能相交。

分析：从上往下，从左往右，遍历方格，第一次遇到的"#" 一定是十字的最上方那个部分，看看是不是合法的十字，然后把这个十字全部标记掉。

       最后看看grid 中是否有没有标记的 #。

/****************************************
* File Name: 228d2b.cpp
* Author: sky0917
* Created Time: 2014年02月 5日 13:42:30
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 102;char s[maxn];
int  g[maxn][maxn]; 
int main(){int n;while (scanf("%d",&n)!=EOF){for (int i=0; i<n; i++){scanf("%s",s);for (int j=0; s[j]; j++){g[i][j] = (s[j]=='#'?1:0);}}int f = 1;for (int i=0; i<n-2 && f; i++){for (int j=1; j<n-1 && f; j++){if (g[i][j]){int sum = g[i+1][j] + g[i+2][j] + g[i+1][j-1] + g[i+1][j+1];if (sum == 4){g[i][j] = g[i+1][j] = g[i+2][j] = g[i+1][j-1] = g[i+1][j+1] = 0;}       else f = 0;}}}for (int i=0; i<n && f; i++){for (int j=0; j<n && f; j++){if (g[i][j]) f = 0;}       }   printf("%s\n",f?"YES":"NO");}   return 0;
}

 

C. Fox and Box Accumulation

题意：有 n 个盒子，每个盒子有一个属性，si, 表示这个盒子上方能连续放的盒子的数目，每个盒子形状相同，如果一些盒子能摞在一起就称为一堆，

        问怎样摞，最后的堆数最少。

分析：二分 + 贪心。

       先对盒子按si 大小排序，大的尽量放下面，二分枚举最后的堆数 k;

      把盒子从大到小依次放在第 1。。。k 堆，构成最底层，然后在从大到小放好第二层，看看最后能否把盒子放完。

/****************************************
* File Name: 228a.cpp
* Author: sky0917
* Created Time: 2014年02月 3日 23:28:25
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int INF = 0x1f1f1f1f;int n, m;
int a[maxn];
int b[maxn];
int h[maxn];
bool ok(int x){sort(a, a+n);memset(h, INF, sizeof(h));      for (int i=n-1; i>=0; i--){int u = i % x;if (h[u] == 0)return false;   h[u] = min(h[u]-1, a[i]);}return true;
}
void solve(){int l = 1, r = n, mid;int res;while (l <= r){mid = (l+r)>>1;if (ok(mid)){r = mid-1;res = mid;}else{l = mid+1;}}printf("%d\n",res);
}
int main(){while (scanf("%d",&n)!=EOF){for (int i=0; i<n; i++){scanf("%d",&a[i]);}solve();}return 0;
}

 

 

D. Fox and Minimal path

题意： 给出一个 k 表示最短路的个数。要求构造出一个节点不大于1000的无向图，使得其最短路的个数为 k ，无向图的边长为1.

分析：可以把 k 看成二进制数，如 k = 100100. 那么 k = 2^5 + 2^2;

        2 ^ m 个最短路可以这样构造：取两个节点作为第一层，再取两个节点作为第二层，第一层的每个点和第二层的每个点连一条边，

       一直构造出 m 层， 那么从第一层到第 m 层的最短路的个数就是 2^m 个。

        最后只要把最短路数的个数加起来得到 k 即可。注意点数不够，要重复利用 2 ^ m 中部分点。 

        这里的程序用 四进制。

/***************************************** File Name: 228b.cpp* Author: sky0917* Created Time: 2014年02月 4日 12:28:25****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1001;int K;
int d[maxn];
int g[maxn][maxn];
int tp;
inline void mark(int x, int y){g[x][y] = g[y][x] = 1;
}
void solve(){memset(g, 0, sizeof(g));tp = 0;while (K){d[tp++] = K % 4;K /= 4;}   int n = 2;for (int i=0; i<tp; i++){if (d[i]){n += d[i] + i * 4 + (tp-i-1);}}printf("%d\n",n);int cnt = 2;int st;for (int i=0; i<tp; i++){if (d[i] != 0){if (i != tp-1){if (tp != 1){   mark(0, cnt);cnt++;for (int j=1; j<tp-i-1; j++){mark(cnt-1, cnt);cnt++;}}       }   if (i == 0){st = cnt-1;if (tp == 1)st = 0;for (int j=0; j<d[i]; j++)mark(st, cnt+j);st = cnt;cnt += d[i];for (int j=st; j<st+d[i]; j++)mark(j, 1); continue;}st = cnt-1;if (i == tp-1)st = 0;if (d[i] == 1){mark(st, cnt);}else if (d[i] == 2){mark(st, cnt);mark(st, cnt+1);}   else if (d[i] == 3){mark(st, cnt);mark(st, cnt+1);mark(st, cnt+2);}st = cnt;cnt += d[i];for (int j=st; j<cnt; j++){for (int k=0; k<4; k++){mark(j, cnt+k);}}st = cnt;cnt += 4;for (int j=1; j<i; j++){for (int l=0; l<4; l++){for (int k=st; k<st+4; k++){mark(k, cnt+l);}       }   st = cnt;cnt += 4;}for (int j=st; j<st+4; j++){mark(j, 1);}}}for (int i=0; i<n; i++){for (int j=0; j<n; j++){if (g[i][j])putchar('Y');else putchar('N');}puts("");}
}
int main(){while (scanf("%d",&K)!=EOF){solve();    }   return 0;
}

 

E. Fox and Card Game

题意：给出 n 堆纸牌，每堆纸牌中每张卡片都有一个数值。

        有两个人依次取纸牌， 第一个人只能取任意一堆最上方的纸牌，第二个人只能去任意一堆最下方的纸牌，问采取最优策略的情况下，

        第一个人拿到的纸牌数值和 和 的二个人的 最大是多少。

分析： 对于纸牌数为偶数的牌堆，两个人最后一定是各取一半，因为如果某一堆超过一半对第一个人有利，那么第二个人完全可以采取策略让他

        无法使那堆超过一半，第二个人也一样。

        对于纸牌数为奇数的堆数要放在一起考虑，第一个人可以利用先手的优势保证一定取到中间的纸牌，第二个人可以控制不让他拿到中间纸牌下方的

        牌，但是第一个人拿了某堆中间的牌之后，剩下的牌堆对第二人来说就是先手的形式，他可以取到中间值最大的那堆牌的中间值。最后两个人交替

        取完第一大的中间牌，第二大的，...。中间牌上面的牌都是第一个人拿的，下面的都是第二个人拿的最后。

/****************************************
* File Name: 228c.cpp
* Author: sky0917
* Created Time: 2014年02月 3日 23:37:46
****************************************/
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;int a[maxn];
int b[maxn];
int main(){int n;while (scanf("%d",&n)!=EOF){int l = 0, r = 0;int tp = 0;for (int i=0; i<n; i++){int m;scanf("%d",&m);for (int j=0; j<m; j++)scanf("%d", &a[j]);if (m & 1){b[tp++] = a[m>>1];}for (int j=0; j<m/2; j++){l += a[j];r += a[m-j-1];}}sort(b, b+tp);for (int i=tp-1; i>=0; i-=2){l += b[i];if (i >= 0)r += b[i-1];}printf("%d %d\n",l, r);}   return 0;
}