CF228 Div2

Problem A - Fox and Number Game

输入N个数,每次从中取出两个不同的数,a > b。把 a 变为 a - b。直到不能够操作为止,即所有的数都相等为止。求最后所有数的和。

上述操作就是辗转相减法求两个数字之间最大公约数,所以最后和为N个数的最大公约数 * N。

有函数可以直接求两者最大公约数:__gcd(a, b)


Problem B - Fox and Cross

有一副N * N 的图,其中有 . 和 # 组成。如下图,其中红色为#,白色为. 。CF228 Div2要求五个#组成一个十字,并且每个#只能被一个十字包含,问该图中所有的#能否全部划分为十字。


#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;
}




CF228 Div2

上一篇:化学品问题 I


下一篇:鼠标 hook 源码 C#版