Problem A - Fox and Number Game
输入N个数，每次从中取出两个不同的数，a > b。把 a 变为 a - b。直到不能够操作为止，即所有的数都相等为止。求最后所有数的和。
上述操作就是辗转相减法求两个数字之间最大公约数，所以最后和为N个数的最大公约数 * N。
有函数可以直接求两者最大公约数：__gcd(a, b)
Problem B - Fox and Cross
有一副N * N 的图，其中有 . 和 # 组成。如下图，其中红色为#，白色为. 。
要求五个#组成一个十字，并且每个#只能被一个十字包含，问该图中所有的#能否全部划分为十字。
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int g[110][110], vis[110][110], n;
bool check(int x, int y)
{
if (g[x][y] && g[x + 1][y] && g[x+1][y-1] && g[x+1][y+1] && g[x+2][y])
{
g[x][y] = g[x+1][y] = g[x+1][y-1] = g[x+1][y+1] = g[x+2][y] = 0;
return true;
}
return false;
}
bool dfs()
{
int i, j;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) if (g[i][j])
{
if (!check(i, j)) return false;
}
return true;
}
int main ()
{
cin>>n;
int i, j;
char ch;
int sum =0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j ++)
{
cin>>ch;
if (ch == '#')
{
g[i][j] = 1;
sum ++;
}
}
if (sum % 5 == 0)
{
if (dfs()) puts("YES");
else puts("NO");
}
else puts("NO");
return 0;
}
Problem C - Fox and Box Accumulation
有N块木块，每个数字代表一块木块，每块木块上面最多只能放与自身数字相同的木块，现在要N块木块尽可能少的叠成堆，问最少多少堆。
由于N很小，可以直接用模拟的方法，不过要注意从数字小的开始放。
int main ()
{
int a[110], n;
cin>>n;
for (int i = 0 ; i < n; i++)
cin>>a[i];
sort(a, a + n);
int sum = 0, t = 0;
while (sum < n)
{
int h = 0;
for (int i = 0; i < n; i++)
{
if (a[i] >= h)
{
sum ++;
a[i] = -1;
h++;
}
}
t++;
}
cout<<t<<endl;
return 0;
}
如果N很大，可以用下面的方法
int main ()
{
int n, a[110] = {0}, i, t;
cin>>n;
for (i = 0; i < n; i++)
{
cin>>t;
a[t]++;
}
int s = 0, mx = 0;
for (i = 0; i <= 100; i++)
{
s += a[i];
int k = s / (i + 1);
if (s % (i + 1)) k++;
if (k > mx) mx = k;
}
cout<<mx<<endl;
return 0;
}
Problem D -
Fox and Minimal path
有一副无向图，其中给定一个数字k，代表从顶点1到顶点2的最短路径有k条。现在让你任意的输出符合条件的一幅图（用二维数组的形式）
例如：
input
2
output
4 NNYY NNYY YYNN YYNN
这道题的关键是将K用二进制表示，然后在图中实现。参考了别人的代码，方法很巧妙：
/*
ID: wuqi9395@126.com
PROG: beads
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int g[111][111], k, n;
void bit(int k)
{
while (k)
{
n++;
k >>= 1;
}
}
int main ()
{
int i, j;
cin>>k;
if (k == 1)
{
cout<<2<<endl;
puts("NY");
puts("YN");
return 0;
}
bit(k);
n--;
g[1][3] = g[1][4] = g[1][5] = 1;
for (j = 3; n > 1; n--, j += 3)
{
g[j][j+3] = g[j][j+4] = g[j+1][j+3] = g[j+1][j+4] = g[j+2][j+5] = 1;
if (k & 1 << n - 1) g[j+2][j+3] = g[j+2][j+4] = 1;
}
if (k & 1) g[j+2][2] = 1;
g[j][2] = g[j+1][2] = 1;
cout<<j+2<<endl;
for (i = 1; i <= j+2; i++, cout<<endl)
for (k = 1; k <= j+2; k++)
if (g[i][k] || g[k][i])
printf("Y");
else
printf("N");
return 0;
}
我后来自己又写了一个，就比较挫了：
int k, n, g[1000][1000];
void cal(int k)
{
while(k)
{
k >>= 1;
n++;
}
n--;
}
int main ()
{
int i, j, t = 1, x = 3, p = 3;
cin>>k;
if (k == 1)
{
puts("2");
puts("NY");
puts("YN");
return 0;
}
cal(k);
for (i = 0; i < n; i++)
{
g[t][x] = g[t][x+1] = 1;
t = x + 2;
g[t][x] = g[t][x+1] = 1;
x = x + 3;
}
g[t][2] = 1;
for (i = 0; i < n; i++) if (k & 1 << i)
{
g[1][x] = 1;
for (j = 0; j < n - i - 1; j++)
{
g[x][x+1] = 1;
g[x+1][x+2] = 1;
x = x + 2;
}
g[x][(n-i)*3+2] = 1;
x++;
}
cout<<x<<endl;
for (i = 1; i <= x; i++, cout<<endl)
for (j = 1; j <= x; j++)
if (g[i][j] || g[j][i]) printf("Y");
else printf("N");
return 0;
}
Problem
E - Fox and Card Game
题意：有许多堆卡片，每张卡片上面有数字，然后规定A只能每次从任意一堆中取最顶端的一张卡片，B每次只能从任意一堆中的最底部取一张卡片，A先去。假设规定取得的卡片数字之和越大越好，A与B都按照最优的方式取卡片，问最后两个人的数字和各位多少？
input
2 1 100 2 1 10
output
101 10
我看了很多人的写法，都是将为偶数堆的卡片两人对半分，奇数堆的卡片取出最中间一张，其余对半分。然后将所有从奇数堆中取出的卡片按大到小排好，A先取，B后取，取完为止。
没有想出到底这样就是最优解。疑惑中。
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int w[110], inx = 0;
int main ()
{
int sum = 0, s = 0, n, a, b, i, j;
cin>>n;
for (i = 0; i < n; i++)
{
scanf("%d", &a);
for (j = 1; j <= a; j++)
{
scanf("%d", &b);
sum += b;
if (j * 2 <= a) s += b;
if (j * 2 == a + 1) w[inx++] += b;
}
}
sort(w, w + inx);
for (i = inx - 1; i >= 0; i -= 2)
s += w[i];
cout<<s<<" "<<sum - s<<endl;
return 0;
}