数学推演题目—UMR祝你元宵节快乐！

川长思鸟来 2022-07-12 05:42 171阅读 0赞

think:  
1感觉很明显是一道数学推演题目，在假定两个玩家足够聪明的情况下，其实就是把自己带入情景，如果是自己，自己会怎样来选择，感觉一个很笨也是一个很有效的办法就是用笔把可能的情况列举出来，然后再从简单的假定的例子逐渐扩展到一些特殊情况，其实经过简单的列举后会发现如果要使得cyk赢就得类似于像  
6  
1 1 2 2 3 3  
8  
1 2 3 3 2 1 4 4  
的情况，因此就会发现规律，也就是cyk胜利的条件，然后在考虑时间复杂度的问题，考虑能否优化时间复杂度，这时候可以考虑用快排函数  
2 数学推演类题目不是简单从难易程度上来判断的，很多时候在没思路的情况下不妨简单列举一下，运用一下数学归纳法的思想  
3 有时候所谓的困难只是我们的不自信，我们又为什么不会成为最优秀的人呢？希望往往在转角处，而这个转角又往往是我们是否自信，满怀信心对待每一天，即使前方风雨交加，我们也要满怀希望的前行，失败或许很可怕，但因为失败而放弃未来无疑意味着那才是真正的失败，我们每个人都将会成为运气的宠儿，只是现在仍需坚持奋斗

[sdut原题链接][sdut]

UMR祝你元宵节快乐！  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
元宵节到了，cyk 表示对 UMR 不服，于是他们进行了一场游戏：  
他们面前有 n 个数，玩家轮流每次从这 n 个数中挑选出一个数拿走。  
玩家选取的数字大小不能超过上一次玩家所拿的数的大小（譬如，上一个玩家拿了 3，那么下一次玩家只能选择 3, 2, …）。  
当一名玩家无法挑选（没有数字了，或者剩下的数字都比上次玩家挑选的大）的时候则该玩家输掉比赛。  
今天的比赛是 UMR 先手，两个人都足够聪明，然后 UMR 能不能够赢得比赛呢？

Input  
输入数据有多组（数据组数不超过 50），到 EOF 结束。  
第一行输入一个整数数 n (1 <= n <= 1000) 表示游戏开始时可以挑选的数的总个数。  
第二行 n 个以空格分隔的整数，每个数的范围属于 \[1, 1000\]。

Output  
对于每组数据：  
如果 UMR 赢了，输出 “a ha ! cyk , too young too simple sometimes native !”。  
如果 cyk 赢了， 输出 “en heng UMR , you also have today !”。  
输出均不包括引号。

Example Input  
4  
2 3 3 3  
5  
1 2 3 4 5  
2  
1 1

Example Output  
a ha ! cyk , too young too simple sometimes native !  
a ha ! cyk , too young too simple sometimes native !  
en heng UMR , you also have today !

Hint  
Author  
「2017年寒假集训 阶段测试赛2 - 元宵节专场」UMR

以下为accepted代码

#include <stdio.h>
    #include <stdlib.h>
    int cmp(const void *a, const void *b)
    {
        return ((*(int *)a) - (*(int *)b));
    }
    int main()
    {
        int n, i, a[1004];
        while(scanf("%d", &n) != EOF)
        {
            int flag = 1;
            for(i = 0; i < n; i++)
            {
                scanf("%d", &a[i]);
            }
            qsort(&a[0], n, sizeof(a[0]), cmp);
            for(i = 0; i < n-1; i += 2)
            {
                if(a[i] != a[i+1])
                {
                    flag = 0;
                    break;
                }
            }
            if(flag && n % 2 == 0)
                printf("en heng UMR , you also have today !\n");
            else
                printf("a ha ! cyk , too young too simple sometimes native !\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 8ms
    Take Memory: 124KB
    Submit time: 2017-02-13 17:43:11
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1997/pid/3790