排位赛 09 题解
A - Fox and Number Game
题意
给出一列数，数之间可以相减（大数-小数），不限次数，求这列数可以得到的最小总和。
思路
观察数据加上思考不难发现，每个数最后都可以变成同一个数，就是他们的最大公约数。
代码
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n, num[105];
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", num+i);
int ans = num[0];
for (int i = 1; i < n;++i)
ans = __gcd(ans, num[i]);
printf("%d\n", ans*n);
return 0;
}
B - Fox and Cross
题意
给出一张由'.'和'#'组成的正方形图，需要判断是否图上的'#'可以不重叠地组成若干个十字。
思路
简单DFS。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
char maps[105][105];
const int dir[4][2] = {1,0,-1,0,0,1,0,-1};
void check(int x, int y) {
if (x == 0 || x == n-1 || y == 0 || y == n-1)
return;
for (int i = 0; i < 4; ++i)
if (maps[x+dir[i][0]][y+dir[i][1]] == '.')
return;
for (int i = 0; i < 4; ++i)
maps[x+dir[i][0]][y+dir[i][1]] = '.';
maps[x][y] = '.';
}
int main(){
bool flag = 1;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%s", maps+i);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (maps[i][j] == '#')
check(i, j);
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j)
if (maps[i][j] == '#')
flag = 0;
//printf("%s\n", maps[i]);
}
if (flag) printf("YES\n");
else printf("NO\n");
return 0;
}
C - Fox and Box Accumulation
题意
给出一列数，让你排成若干列。每个数字的值表示这个数字前面允许存在的数字个数。求最少要排几列。
思路
贪心分堆。先排个序，从头开始遍历，取一个作为一排的第一个，然后向后遍历数列，挨个判断是否可以放进这一排，并且标记。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int n, num[105], ans = 0, vis[105];
memset(vis, 0, sizeof vis);
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", num+i);
sort(num, num+n);
for (int i = 0, cnt = 0; i < n; ++i, cnt = 0) {
if (vis[i]) continue;
++vis[i], ++cnt, ++ans;
for (int j = i+1; j < n; ++j) {
if (vis[j]) continue;
if (num[j] >= cnt) ++vis[j], ++cnt;
}
}
printf("%d\n", ans);
return 0;
}
D - Fox and Minimal path
题意
给出一个数字n，求一张有着若干节点的图。输出这张图的邻接表。要求这张图从点1到点2的最短路的条数为n。输出时如果这条路存在则输出Y，否则为N。
思路
因为没有限定要节点数最少，所以任意。
一开始想的是，只要找出最多需要多少点，然后用这张表来处理就可以了。但是没有弄清楚到底是怎么添加最短路的，所以WA了。
我们换一种方式。1是起点，2是终点。我们先确定一条主链，主链规定了这条路会经过多少个节点。然后从起点开始，按照主链的节点数给副链添加节点。这里规定副链的一层有两个节点，这样n层就是 $2^n$ 条路径，这样的原始图建成之后，是 $2^n+1$ 条路径。
然后考虑添加路径数。i+1层主链和i层副链相连一条，可以添加 $2^{i-1}$ 条路径。
到这里我们的解法就出来了。首先因为我们有主链，所以先n-=1；然后找出最大的二进制位，这就是我们主链的长度，然后根据每一个二进制位选择是否要进行添加。
代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int maps[107][107];
void addEdge(int a, int b) {
maps[a][b] = maps[b][a] = 1;
}
int main(){
int n, size = 0, t;
scanf("%d", &n);
t = --n;
while (t) {
++size;
t >>= 1;
}
if (!size) {
printf("2\nNY\nYN\n");
return 0;
}
addEdge(1, 3);
addEdge(1, 4);
addEdge(1, 5);
addEdge(size*3, 2);
for (int i = 1; i < size; ++i) {
addEdge(i*3, (i+1)*3);
addEdge(i*3+1, (i+1)*3+1);
addEdge(i*3+2, (i+1)*3+2);
addEdge(i*3+1, (i+1)*3+2);
addEdge(i*3+2, (i+1)*3+1);
}
int now = 0;
while (n) {
++now;
if (n&1) {
if (now == size)
addEdge(2, 3*now + 1);
else
addEdge(3*(now+1), 3*now+1);
}
n >>= 1;
}
size = size * 3 + 2;
printf("%d\n", size);
for (int i = 1; i <= size; ++i) {
for (int j = 1; j <= size; ++j)
printf("%c", maps[i][j]?'Y':'N');
printf("\n");
}
return 0;
}
F - Water problem
题意
给一个一千以内的数字n，求从1到n的英文写法的字母总数。不计算空格和连字符。
思路
打表，1-100，然后预处理出1-1000的所有答案，O(1)输出。
代码
#include <cstdio>
using namespace std;
int a[1001] ={
0,
3, 3, 5, 4, 4, 3, 5, 5, 4, 3,
6, 6, 8, 8, 7, 7, 9, 8, 8, 6,
9, 9, 11, 10, 10, 9, 11, 11, 10, 6,
9, 9, 11, 10, 10, 9, 11, 11, 10, 5,
8, 8, 10, 9, 9, 8, 10, 10, 9, 5,
8, 8, 10, 9, 9, 8, 10, 10, 9, 5,
8, 8, 10, 9, 9, 8, 10, 10, 9, 7,
10, 10, 12, 11, 11, 10, 12, 12, 11, 6,
9, 9, 11, 10, 10, 9, 11, 11, 10, 6,
9, 9, 11, 10, 10, 9, 11, 11, 10, 10};
int main(){
for(int i = 20; i < 100; i += 10)
for(int j = i+1; j < i+10; ++j)
a[j] = a[i]+a[j-i];
for(int i = 100; i < 1000; i += 100){
a[i] = a[i/100] + 7;
for(int j = i+1; j <= i+99; ++j)
a[j]=a[i]+3+a[j-i];
}
a[1000] = 3+8;
for(int i = 2; i <= 1000; ++i)
a[i] += a[i-1];
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("%d\n", a[n]);
}
return 0;
}
H - Max Sum
题意
给一列数，求最大字段和。
思路
递推DP。稍微说下思路。首先因为是有负数的，所以记录最大值初始值为负，避免全负数情况。然后遍历数列，都加进计数器中，如果计数器变为负数就归零。如果大于记录最大值就记录下来，并且记录当前的子段位置。
代码
#include <cstdio>
using namespace std;
int main(){
int t, cas = 0;
scanf("%d", &t);
while (t--) {
int n, a, left = 1, right = 1;
int sum = 0, maxx = -1005, cur = 1;
scanf("%d", &n);
for (int i = 1; i <= n; ++i){
scanf("%d", &a);
sum += a;
if (sum > maxx) {
maxx = sum;
left = cur, right = i;
}
if (sum < 0) {
sum = 0;
cur = i + 1;
}
}
printf("Case %d:\n%d %d %d\n", ++cas, maxx, left, right);
if (t) printf("\n");
}
return 0;
}
