排位赛 09 题解

A - Fox and Number Game

CodeForces - 389A

题意

给出一列数,数之间可以相减(大数-小数),不限次数,求这列数可以得到的最小总和。

思路

观察数据加上思考不难发现,每个数最后都可以变成同一个数,就是他们的最大公约数。

代码

#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

CodeForces - 389B

题意

给出一张由'.''#'组成的正方形图,需要判断是否图上的'#'可以不重叠地组成若干个十字。

思路

简单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

CodeForces - 389C

题意

给出一列数,让你排成若干列。每个数字的值表示这个数字前面允许存在的数字个数。求最少要排几列。

思路

贪心分堆。先排个序,从头开始遍历,取一个作为一排的第一个,然后向后遍历数列,挨个判断是否可以放进这一排,并且标记。

代码

#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

CodeForces - 389D

题意

给出一个数字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

HDU - 5867

题意

给一个一千以内的数字n,求从1n的英文写法的字母总数。不计算空格和连字符。

思路

打表,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

HDU - 1003

题意

给一列数,求最大字段和。

思路

递推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;
}