[BZOJ1982][POJ1740][Spoj 2021]Moving Pebbles|解题报告
2024-08-25 23:08:33
这道题的题意BZ和POJ上的都不大清楚...
大概就是给出n堆石子，以及初始每堆石子的个数
两个玩家交替操作，每个操作可以任意在一堆中取任意多的石子
然后再从这堆里拿若干个石子放到某个当前还存在的堆里，当然这个操作也可以不做
问先手还是后手有必胜策略
博弈的题目果然是脑洞大啊...
最后的结论：
对于奇数堆，先手必胜
偶数堆时，先手败当且仅当所有的堆都可以分成两两相等的堆
证明大概就是：
首先考虑1堆的情况，先手显然胜
考虑两堆且相等的情况，如果先手拿完，后手把剩下一堆拿完；如果先手没拿完
后手就在另一堆里重复和先手一模一样的操作直至结束
这样后手有必胜的策略
并且对于每两堆相等的堆，后手都会这样做
于是我们可以完全忽略这些堆
然后对于两堆不相等的情况，先手可以在一次操作内将两堆变成相等的两堆，转化成上面的必败态
这样先手必胜
对于三堆的情况，先手可以在一次操作内将三堆变成相等的两堆，同上
（无视上面这张图）
现在的理解大概就是移动的操作一次可以做无限次
然后先手就可以一步把目前形势转化到两两相等的情况
然后就没了
30/.April
最新文章
- OVS local network 连通性分析 - 每天5分钟玩转 OpenStack（132）
- 上层建筑——DOM元素的特性与属性（dojo/dom-prop）
- Linux搭建smtp服务器+laravel5.2发邮件配置
- 斯坦福第十四课：降维(Dimensionality Reduction)
- 图片_ _图片缓存之内存缓存技术LruCache,软引用
- python 简单实现文件拷贝
- httpClient.execute之后一直等待
- messagePack编解码
- [jquery]高级篇--标签选择
- 深入理解 Spring 事务原理【转】
- C# 堆栈和堆 Heap & Stack
- 认识 Less
- python学习之路网络编程篇（第二篇）
- 【代码笔记】Web-CSS-CSS Positioning
- Javaweb项目 利用JSP响应浏览器
- kvm 搭建
- wireshark抓包结果很多[TCP Retransmission]怎么办？
- css3硬件加速
- js 复制到剪切板
- mysql启动报错cannot allocate memory for the buffer pool处理