37 条题解

  • 0
    @ 2015-12-03 11:13:13

    写了一下证明 觉得还是蛮清晰的QAQ

    -Proof:

    我们先证明 当有 起初态任意一个为 1 4 5 先手必胜

    先手:x,1——取x——>胜
    先手:x,4——取x——>后手:2,2(只能取2...)——>先手:1,1——>胜
    先手:x,5——取x——>后手:2,3(剩下2的上面讨论了..于是取2剩下3)
    ——>先手:1,2——>胜

    对于任意一个数 x ≡ 2 or 3 (mod 5) 我们将他拆成两个数 a b 那么我们可以断定 a 和 b其中一定有一个 mod 5 ≠ 2 or 3

    然而对于任意一个 x ≡ 0 or 1 or 4 我们都可以拆成两个数 且都满足 mod 5余 2 or 3 然后这样就必胜态一直可以是自己保持着必胜态 然后数会一直减小 所以最后回到了我们最早的证明

    end-
    代码在这里 http://blog.csdn.net/fd_xuan/article/details/50158065
    (我不会说是来骗访问量的QAQ...跪求进...TAT)

  • 0
    @ 2014-01-29 22:48:26

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 244 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 244 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 244 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 248 KiB, score = 10
    Accepted, time = 0 ms, mem = 248 KiB, score = 100

    #include<stdio.h>
    #include<string.h>

    int judge(const int &x)
    {
    if (x==2||x==3||x==7||x==8) return 1;
    return 0;
    }

    int main()
    {
    char s1[50],s2[50];

    while (scanf("%s",s1),s1[0]!='-')
    {
    scanf("%s",s2);
    if (!judge(s1[strlen(s1)-1]-48)) printf("MengMeng\n");
    else if (!judge(s2[strlen(s2)-1]-48)) printf("MengMeng\n");
    else printf("SheepDaddy\n");
    }

    return 0;
    }

    规律不难找,我这里就直接描述之:先定义N/P点,N点:必胜点,P点:必败点,其实只要该数模5结果为2或者3则为必败点,如果结果为0或1或4就为必胜点,对于此题设初态为(a,b),则易知,当且仅当a和b都为P点,那么SheepDaddy wins,否则MengMeng wins,还没完呢。。。由简单的数论知识我们知道 “一个数模5等于其个位数模5!!”,所以。。。你懂得了吧。。

  • -1
    @ 2014-11-03 22:29:01

    P1655萌萌的糖果博弈
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1655 萌萌的糖果博弈
    递交时间 2014-11-03 22:28:37
    代码语言 C++
    评测机 上海红茶馆
    消耗时间 15 ms
    消耗内存 560 KiB
    评测时间 2014-11-03 22:28:39

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 556 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 556 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #5: Accepted, time = 15 ms, mem = 560 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10

    测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 556 KiB, score = 10

    Accepted, time = 15 ms, mem = 560 KiB, score = 100

    代码

    #include <iostream>
    #include <cmath>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    char a[100];
    char c;
    int i;

    int main()
    {
    while( scanf( "%s" , a ) != EOF )
    {
    if( a[0] == '-' )
    break;
    for( i = 0 ; i < 128 ; i++ )
    if( a[i] == 0 )
    {
    c = a[i - 1];
    break;
    }
    scanf( "%s" , a );
    if( ( c - '0' ) % 5 == 2 || ( c - '0' ) % 5 == 3 )
    for( i = 0 ; i < 128 ; i++ )
    if( a[i] == 0 )
    {
    c = a[i - 1];
    break;
    }
    if( ( c - '0' ) % 5 == 2 || ( c - '0' ) % 5 == 3 )
    cout << "SheepDaddy\n";
    else
    cout << "MengMeng\n";
    }
    return 0;
    }

    too weak!

  • -1
    @ 2013-08-06 17:22:26

    第111道

  • -1
    @ 2009-11-01 20:35:22

    为什么有的时候字符串val('-1',d)

    d的值会是0?

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:运行超时|格式错误...

    ├ 测试数据 03:运行超时|格式错误...

    ├ 测试数据 04:运行超时|格式错误...

    ├ 测试数据 05:运行超时|格式错误...

    ├ 测试数据 06:运行超时|格式错误...

    ├ 测试数据 07:运行超时|格式错误...

    ├ 测试数据 08:运行超时|格式错误...

    ├ 测试数据 09:运行超时|格式错误...

    ├ 测试数据 10:运行超时|格式错误...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:10 有效耗时:0ms

    ++++++++++++++++++++++++++++++++++++++++++

    改了之后的

    program p1655;

    var str1,str2:ansistring;

    str3:string;

    i,a,b,j:byte;

    code:longint;

    c:array[1..200] of string;

    begin

    readln(str1); i:=1;

    while str1'-1' do

    begin

    readln(str2);

    val(str1[length(str1)],a,code);

    val(str2[length(str2)],b,code);

    a:=a mod 5;

    b:=b mod 5;

    if ((a=2) or (a=3)) and ((b=2) or (b=3)) then

    c[i]:='SheepDaddy' else c[i]:='MengMeng';

    str1:=''; str2:='';

    readln(str1);

    inc(i);

    end;

    for j:=1 to i-1 do

    writeln(c[j]);

    end.

  • -1
    @ 2009-11-01 16:45:07

    program t1196(input,output);

    var c,c1,c2:char;

    i:longint;

    ab:set of '0'..'9';

    begin

    ab:=['2','3','7','8'];

    read(c);

    while c'-' do

    begin

    while ord(c)13 do

    begin

    c1:=c;

    read(c);

    end;

    readln;

    read(c);

    while ord(c)13 do

    begin

    c2:=c;

    read(c);

    end;

    readln;

    if (c1 in ab) and (c2 in ab)

    then writeln('SheepDaddy')

    else writeln('MengMeng');

    read(c);

    end;

    end.

    so easy!

    ==1196^_^

  • -1
    @ 2009-11-01 16:26:01

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    和1196一样

    水水

  • -1
    @ 2009-10-30 22:06:20

    program lq;

    var

    n,t1,i,j,cha,ans:longint;

    w,t,f:array[0..1002] of longint;

    function max(i,j:longint):longint;

    begin

    if i=0 then

    f[j]:=max(f[j],f[j-t[i]]+w[i]);

    //print

    writeln(f[t1]);

    end.

    {开始把范围定义为100,忘打0啦,冤!!!}

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

  • -1
    @ 2009-10-26 21:12:56

    #inlcude

    using namespace std;

    int main(){

    if(n==1) cout

  • -1
    @ 2009-10-24 09:56:58

    finding the rules~~

  • -1
    @ 2009-10-15 15:02:05

    可以这样考虑,

    拆分某堆一堆是胜还是负。

    结论:

    某堆只要可以拆成2个负的,那么这堆就是胜的。

    分析:

    1

    根据题意,显然拆掉1是必胜的

    2

    拆分方案为 1 1

    对手怎么拿都是赢,2是必负态

    3

    拆分方案为 1 2

    对手可以去拆1,所以3是必负态

    4

    拆分方案为 1 3 或 2 2

    只要拆成 2 2 这样对手只能拆必负态,所以4是必胜态

    5

    拆分方案为 1 4 或 2 3

    只要拆成 2 3 这样对手只能拆必负态,所以5是必胜态

    6

    拆分方案为 1 5 或 2 4 或 3 3

    只要拆成 3 3 这样对手只能拆必负态,所以6是必胜态

    7

    拆分方案为 1 6 或 2 5 或 3 4

    没有一组有两个必负态,所以7是必胜负

    每次看能不能拆成2个必负态,依次类推...

    你会发现除以5的余数为2和3的时候,都是必负态

    余数为0,1,4 的时候都是必胜态。

    每组数据有两堆,只要留下必胜态的那堆进行拆分,就一定能赢。

    所以,每组数据只要判断一下余数,

    只要存在一个必胜态,就可以赢。

    数据有2^127,我写了高精度除法求余,0秒AC

    看了看下楼的讨论,确实除以5的余数的大小只要看末位就可以了。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • -1
    @ 2009-10-10 14:22:55

    就是1196么,结果我看都没看就照抄,结果WA啊WA……

  • -1
    @ 2009-10-05 21:06:05

    现在才发现是抄Matrix67神牛的题目

    大家看1196 的吃糖果游戏

  • -1
    @ 2009-10-03 21:06:16

    为什么vijos上又出现重题了。。。。。。这道题不是有过么。。。。

  • -1
    @ 2009-10-02 20:21:22

    做一题A两题

  • -1
    @ 2009-10-02 11:25:18

    orz 本来乱写的 竟然ac了……

  • -1
    @ 2009-10-01 21:47:49

    #include

    char ch,ch1;

    int t,k;

    int main()

    {

    while(1)

    {

    k=0;

    ch=getchar();

    if(ch=='-')break;

    while(ch!='\n')

    {

    ch1=ch;

    ch=getchar();

    }

    t=(ch1-'0')%5;

    if(t==2||t==3)k+=1;

    ch=getchar();

    while(ch!='\n')

    {

    ch1=ch;

    ch=getchar();

    }

    t=(ch1-'0')%5;

    if(t==2||t==3)k+=1;

    if(k!=2)printf("MengMeng\n");

    else printf("SheepDaddy\n");

    }

    return 0;

    }

  • -1
    @ 2009-10-01 21:21:38

    一开始输出的时候写成writeln(ans[i])

    结果一堆空行wa掉了

    冤啊!!!

    const

    lose:set of char=['2','3','7','8'];

    var

    ans:array[0..100]of string;

    i,j:integer;

    a,b:string;

    x,y:char;

    begin

    i:=0;

    repeat

    inc(i);

    readln(a);

    if a='-1' then break;

    readln(b);

    x:=a[length(a)];

    y:=b[length(b)];

    if (x in lose) and (y in lose) then ans[i]:='SheepDaddy' else ans[i]:='MengMeng';

    until a='-1';

    for j:=1 to i-1 do writeln(ans[j]);

    end.

  • -1
    @ 2009-10-01 19:56:10

    Var

    a,b:string;

    c:char;

    Begin

    Readln(a);

    While a'-1' Do Begin

    c:=a[length(a)];

    Readln(a);

    If (c='0') or (c='1') or (c='4') or (c='5') or (c='6') or (c='9') Then

    Writeln('MengMeng')

    Else Begin

    c:=a[length(a)];

    If (c='0') or (c='1') or (c='4') or (c='5') or (c='6') or (c='9') Then

    Writeln('MengMeng') Else Writeln('SheepDaddy');

    End;

    Readln(a);

    End;

    End.

    博弈论……

  • -1
    @ 2009-10-01 19:22:53

    博弈论!!!!!!!!!!!!!!!!!!!!!偶不会...........

    AC!!!!!!!!!!!!!!!!!!!!!!!!!!!!

信息

ID
1655
难度
3
分类
博弈论 点击显示
标签
(无)
递交数
1430
已通过
765
通过率
53%
被复制
3
上传者