题解 | #J 小沙的中饭#
小沙的中饭
https://ac.nowcoder.com/acm/contest/27740/J
设A为小红,B为小沙,A先手
第一层:A:我先排序,从小拿起,先拿走1,怕B拿走大的,再开一个最小的给B
第二层:B:我开其他环会给A拿走,我只能拿最小的,再开个最小的给A
第三层:A:我为什么要拿B给的最小的?我既然不能开环,如果下一个很大,我可以先不拿分,选个不连的点,让B强制拿我这个,他肯定会开下一个最小的,我拿他开的,扰乱顺序!
第四层:B:下一个大肯定要A来开,前提是他要能扰乱顺序,我要防止他扰乱顺序,也就是能让他被迫连起来,2,3的话可以,4的话他选个对角点,我就寄了。
第五层:A:确实,我除了4可以选,还有其他选的吗?选4也就是说只要选完能让B被迫连起来,就是隔点选,但改了怕A又会改回来,照这么说,4,5,8 ,9,12,13这种n/2为偶数,我就能改顺序,否则我就不能改。
第六层:B:对的,如果确实这个环具有n/2为偶的性质的话,那必是我开下一个,我就可以选能控制A能连起来的操作,这是否跟下下个小的数有关?
第七层:A:无关,如果你开n/2为奇来强制我得分,万一该数很大,我确实可以全部拿走,不需要你来强制给我得分,你开的数必然是从最小的一个开启,开大了我就拿了,再给你开小的。
第八层:B:也对吼,而且如果总强制让你得分,我的分也好少,那如果我拿的数很大,下个数也大,上面结果推出了要不这个我拿下个你拿,要不下个我拿这个你拿,能不能在你开下个的基础上我在这个数上拿一点分?
第九层:A:我肯定是不会开下一个的,除非不得已,也就是我得被迫连起来,就是这个环你操作后就得不剩隔点。
第十层:B:我得分肯定得连,连肯定得中止,中止得选一个隔点,诶那如果你选了一个点的环,我留1个隔点其余全连得分不就行了?
第十一层:A:草!
策略总结:
A:作为先手,先把1给拿掉,然后怕B拿大分,再从最小开环。之后在能不开环的情况下不会开环,将获此环的大部分分并让B开环。
B:作为后手,在能不开环的情况下不会开环,将获此环的大部分分并让A开环。
必要开环情况:1,2,3