最新消息:点击查看大S的省钱秘笈

Vijos P1281 Easy Selection C语言版

Vijos题解 Slyar 61浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

背景 Background

wind发明了一个好玩的游戏,叫小杉(lolanv)一起玩。
但小杉玩了十几盘,总是输,他想知道是不是从一开始他就注定要输。

描述 Description

这个游戏是这样的,wind先写下一排数。既然是一排,当然有首尾咯。
wind和小杉(lolanv)每次只能从这排数的头或尾取一个数。
最后谁取的数的和多,谁就赢了。如果两人的和一样多,先取者胜。

有天swgr看到他们俩在玩这个游戏,很好奇。
他想知道,在两人总是做出最优决策的情况下,谁能取得最终的胜利呢?

输入格式 Input Format

第一行为一个数k(k<=10),表示有k组测试数据。
以下k组测试数据。
每组测试数据中,第一行仅有一个偶数n(0<n<=100000)
第二行也仅有一个数,0表示wind先取数,1表示小杉(lolanv)先取数
第三行有n个数,是wind给出的一排数。这n个数的绝对值均不超过1e6

输出格式 Output Format

对每组测试数据输出一行
表示在两人总是做出最优决策的情况下,
最终的胜利者的名字,即"wind"或"lolanv"(引号不输出)。

Tip:全部数字为偶数,则第一个数字为奇数位,最后一个数字为偶数位。如果先取者取奇数位上的数,后取者则不得不取偶数位上的数。因此只要预先计算奇数位上所有数的和与偶数位上所有数的和哪个大,则可一直取这个位上的数保证必胜。所以先手必胜...另外学会了使用 scanf("%*c%*[^\n]"); 可以跳过一行。跳过那行超大数据可以保证0ms完成。

转载请注明:Slyar Home » Vijos P1281 Easy Selection C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (2)

  1. @swgr, 呃...很久以前写的,我错了...我重新写分析...
    Slyar8年前 (2009-05-30)回复
  2. 对题目的分析完全错了....什么叫每次都可取当前最大数,所以先取者的和永远比后取者大? 你看这样的数据, 1 0 99 2 你要是先去最大数(2),那对方就取99,那你就输了... ps 这题我出的..
    swgr8年前 (2009-05-30)回复