首页 > ACM题库 > HDU-杭电 > HDU 3557-Divide Game[解题报告]HOJ
2014
11-05

HDU 3557-Divide Game[解题报告]HOJ

Divide Game

问题描述 :

Divide Game is a combination of the two games.
First, given a string, one of the player’s task is to divide the string into several nonempty strings, we define a legal division generates several shorter strings in the order as they are in the original string, and every two adjacent strings are not similar. We call two strings are similar only if they have at least one character whose number of occurrences in the two strings are equal and not zero.
Then they two play another totally different sub-divide game. To ensure fairness, another player has the first chance.
In this game, two players make an operation in turn. In a round, a player chooses one string, divides the pile into two non-similar strings, if he can’t divide it, then he just moves the string away. The one who gets the last operation is the winner.
Now iSea have a clever challenger, who always choose the optimum strategy, if they two play the divide game, and iSea have the chance to divide the string in the first game, can he win the final game?

输入:

There are several test cases in the input.

Each test case only contain one string (length <= 50000, and only include uppercase), indicating the original string.

The input terminates by end of file marker.

输出:

There are several test cases in the input.

Each test case only contain one string (length <= 50000, and only include uppercase), indicating the original string.

The input terminates by end of file marker.

样例输入:

AA
ABC

样例输出:

No
Yes

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
char st[50005];
int the[30];
int main() {
    while (~scanf("%s", st)) {
        memset(the, 0, sizeof(the));
        int len = strlen(st);
        bool flag = true;
        int tot = 0;
        for (int i = 0; i < len; ) {
            char ch = st[i];
            //the[ch - 'A']++;
            int k = i;
            while (k < len && ch == st[k]) k++;
            k = k - i;
            if (k == 1 || k == 2) tot++;
            else {
                int t = 1, x = k;
                while (x >= 2 * t) {
                    x -= t;
                    tot++; t++;
                }
                tot++;
            }
            i += k;
            the[ch - 'A'] += k;
            //if (k == 1 && i >= 2 && st[i] == st[i - 2]) tot -= 2;
        }
        int num = tot;
        if (st[0] == st[len - 1] && the[st[0] - 'A'] == 2) flag = false;
        //printf("%d", the[0]);
        int lim = 2 * tot - 1; tot--;
        //printf("%d", tot);
        if ((num & 1) && tot <= 0) flag = false;
        //printf("%d\n", tot);
        if (!flag) puts("No");
        else puts("Yes");
    }
}

  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的