网站 › 『编程语言讨论求助区』 › 一道算法题，要求用Python或C/C++或JavaScript实现

CatciSurn 发表于 2022-6-18 20:38

一道算法题，要求用Python或C/C++或JavaScript实现

本帖最后由 CatciSurn 于 2022-6-18 20:58 编辑

描述
Catci和Surn两个人在玩博弈小游戏。他们面前有n个绳圈，每个圈上分别有ai个绳结，两个人轮流切绳子（只能切在两个绳结之间），如果一个人切完一刀之后存在一段绳子上只有一个绳结，那么这个人可以获得这个绳结，然后再切一刀；否则就换一个人切。所有的绳结被分配完成后停止。每个人都想自己获得的绳结尽可能多，请输出前手的人和后手的人分别最多获得多少绳结。
输入格式
第一行一个整数 n(1≤n≤100)，表示环的数量。
第二行n个整数ai(3≤ai≤10^9)，表示每个环上的绳结数量。
输出格式
一行，两个整数，表示两个人分别最多得到多少绳结。
输入数据 1
2
3 3
输出数据 1
3 3
输入数据 2
2
5 5
输出数据 2
4 6
样例解释2
第一个人先将长度为5的环切成一条长度为5的链；第二个人将5切成1 4，得到1，然后再将4切成2 2；
接下来第一个人可以得到2+2，然后将另一个环切成链；最后第二个人可以得到整条长度为5的链。
数据范围

对于30%的数据，n≤5，ai≤5对于60%的数据，n≤10, ai≤10

fangchao 发表于 2022-6-18 20:53

这是让人看的么，aia_iai​这玩意怕不是外星人才能看懂吧

CatciSurn 发表于 2022-6-18 20:54

fangchao 发表于 2022-6-18 20:53
这是让人看的么，aia_iai​这玩意怕不是外星人才能看懂吧

不好意思哈，之前文章编辑的时候都没有出现这种问题。我再修改修改

CatciSurn 发表于 2022-6-18 21:32

等待大佬出现

破wu解 发表于 2022-6-18 23:08

等大佬出现 {:1_918:}

康娜喵 发表于 2022-6-19 08:17

不知道这个题考查的是什么模型，等一个大佬。动规我好像也没有找到转移方程，搜索感觉又要爆时间。这只有两例数据，我怕我写出来也不过了全部数据。
但是目前分析出来的就是：
先手的对立结果就是后手，所以只用求一个，另一个作减法即可求出。
分析一下：如果下一个环>4，那么这个环就先一刀一刀的砍成一节。=4时，最后一刀，砍成2 2，把破环的机会给对方，然后自己再继续砍链（因为砍链如果砍成1 + n-1的形式的话是可以稳定获取1长度的）。
如果链长=2，那么就是+2，破环，然后让下一个人砍链。
如果链长=3，那么就是+3，破环，然后让下一个人砍链。
如果链长=4，可以两个选择：+4，然后破环，让下一个人砍链；还有就是+0，下一个人+4，然后下一个人破环，自己砍下一个链。
分析到这里可以写出一段代码，但我不知道能不能过全数据。

Ldfd 发表于 2022-6-19 08:30

编辑一下，思路错了

LiHuaming 发表于 2022-6-19 09:35

你这个问题好像有一点小问题，就是当一个环变成一条链的时候，切绳子的那个人可以把这条链的第一个切下来，例如5变成1和4，然后他又可以切，他又把四4切成1和3（在第一个和第二个之间切），然后他又可以切，把3切成1和2，直到把整条链切完为止，如果这样的话，这个算法就非常简单了。
当环的数量为双数的时候，两个人理论上获得的解的数量相等，当环的数量为单数的时候，两个人获得的结的数量后手比前手收多一个还的数量-1

zhao1619 发表于 2022-6-19 09:49

康娜喵 发表于 2022-6-19 08:17
不知道这个题考查的是什么模型，等一个大佬。动规我好像也没有找到转移方程，搜索感觉又要爆时间。这只有两 ...

好思路，大佬大佬！

zhao1619 发表于 2022-6-19 10:29

本帖最后由 zhao1619 于 2022-6-19 10:41 编辑

康娜喵 发表于 2022-6-19 08:17
不知道这个题考查的是什么模型，等一个大佬。动规我好像也没有找到转移方程，搜索感觉又要爆时间。这只有两 ...
我认为可以接着分析




--------------------看了下题干，我写的就是辣鸡，别看了------------

挨个拆环时：


先手获得最多的情况是后手纯辅助：
存在绳结大于3的环由先手破环，后手砍掉两个绳结，然后先手收割。一直这样下去直到不存在绳结数量大于3的环。
绳结数量为3的环个数为奇数时，先手获得的个数比后手少3个，偶数时两者相同。(如果后手破3的环，则后手至少先收4个，4>3故让先手破环)
即先手获得数量为：环绳结大于3的绳结数+(绳结数量为3的环的个数)/2*3注意，环数/2设为计算机自己取舍，即对应环数为整型 int

后手获得最多的情况时先手纯辅助：分两种情况
存在绳结大于等于6的环时，先手破环，后手砍两个，先手砍两个，后手收割，接下来后手破环，绳结大于等于6的环后手破坏，先手砍两个，后手收割，接下来后手破环；剩余环绳结小于6大于3时，后手破环，先手砍两个，后手收割，或先手破环后手收割。即环绳结大于3都可由后手收割。
绳结数量为3的环个数为奇数时，后手获得的个数比先手少3个，偶数时两者相同。
即后手获得数量为：环绳结大于3的绳结数+(绳结数量为3的环的个数)/2*3注意，环数/2设为计算机自己取舍，即对应环数为整型 int
有特殊情况，环绳结数量全为3时，此时先手先破环，即绳结数量为3的环个数为奇数时，后手获得的个数比先手多3个，(绳结数量为3的环的个数+1)/2*3，环数/2设为计算机自己取舍，即对应环数为整型 int



允许有剩余直链拆环时：
情况复杂，不会，有请大佬！

查看完整版本: 一道算法题，要求用Python或C/C++或JavaScript实现