题目大意:
一个人在nxn的棋盘上任意走(至少走n步至多299步),起点在左上角,每次走完以后,你可以去掉一些格子使得他不能走到那些格子
人如何走是不确定的,但走的步数和删去多少格子以及哪些格子由你来确定,不能删掉人有可能在的格子
给出一种方案,使得最后只剩下一个格子
这题是构造……最不喜欢这种题了……
如果走的步数是偶数,那么有可能回到出发点,这样显然不好,因为有可能你永远删不了出发点……所以除了第一步以外,尽量走奇数步
然后把棋盘黑白染色,如果走奇数步就可以保证出发和落脚点的颜色不同
有一个很简单的构造就是在第一步把所有不可能走到的位于右下角的格子删去,然后每次删一条对角线,
打个比方
如果人在白格子上,那么走完之后肯定在黑格子上,不会影响我删这条白色对角线,而且由于对角线在边缘,删去以后也不会导致人的可能的位置不连通
最后就能把人“逼”到左上角
分享到:
相关推荐
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU 385,我写的程序,一道DP题,跟概率有关
SGU题库整合 Volume (200 - 299) pdf版
sgu oj上的 101-121 的AC代码
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
SGU离线题库(2015-6-8整理),图片可以显示。。
SGU-801综合通讯接入装置使用说明书
SGU 103AC 代码 质量有保证!
SGU 333 集训队AC程序,秒过,CPP
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
SGU题库 Volume (100-199) pdf整合版
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
ID 标题 交流电 A + B 18881 互质 7697 第3分部 6906 总和 6185 日历 4336 画线 4159 987654321问题 4014 肉饼 3998 几乎素数 3845 a ^ b-b ^ a 3673 骨牌 3621 花小店 3417 ...1884
下载调度程序,用于低带宽环境。 全天扩展下载量
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
HJVXJVHSKVH JHDK JH DFKSDYFS DVJDSVXCVXCVZXCVZXCV
“#babylonjs-sgu”
SGU-用于搜索github用户的输入表单- 描述 您可以通过输入一些文本来找到github用户。 然后,您将拥有一个用户名和用户图标。 仅显示搜索关键字和用户名之间的数据。 库版本 下一个v10.0.7 Reactv17.0.1 react-dom ...