题意:n*m的棋盘,n 为偶数,每个棋子 1*2,可以横着或竖着放,无法落子的输,问先手胜负.
若 m 为偶数,则后手始终放在与先手中心对称的位置,则后手必胜.
若 m 为奇数,则先手放在最中心处,之后始终模仿后手,则先手必胜.
题意:交互题.给定 n,在环上是数字 111 到 2n2^n2n 的一个排列,从数字 111 顺时针与逆时针走到 2n2^n2n 的路径上都是递增的,从某个位置起从 1 开始编号,每次询问返回位置 xxx 上的数字,要求不超过 2n+22n+22n+2 次询问确定数字 2n2^n2n 所在位置.
总共有四种情况:先增再减,先减再增,先增再减再增,先减再增再减.
再二分.
如果 a1<a2a_1<a_2a1 <a2 ,则说明 a1a2a_1a_2a1 a2  这一段是增:
若 amid<a1a_{mid}<a_1amid <a1 ,则最高点一定在 midmidmid 左边;
题意:给定一种树的分治策略:每次选择一条边满足删去后得到的两棵子树点数差最小,删去这条边,递归至两棵子树,若没有边则返回.要求构造一棵树并给出分治方法,使得用你给出的分支方法的最大递归深度小于用题目给定的分治策略的最大递归深度.
如果只是一条链的话深度必定是 log,但是加上一朵花会使得分割点偏向花,使得另一边的递归深度变大.
发现可以把所有点分成两部分,左部分点要么不用传送门要么一定用左边的传送门,右部分点要么不用传送门要么一定用右边的传送门.
枚举这个分界线,左边的传送门一定设在左部分点的中点处,右部分的传送门一定设在右部分点的中点处.
则左部分最远的两个点为 111 和 iii,距离为 ai−a1a_i-a_1ai −a1 ,右部分最远的两个点为 i+1i+1i+1 和 nnn,距离为 an−ai+1a_n-a_{i+1}an −ai+1 .
一点在左另一点在右的情况中最远的点为 111 和 nnn,(iii 和 i+1i+1i+1 或 iii 和 nnn 可以通过讨论发现必定不大于 111 和 nnn),距离为 ai−a1+an−ai+12\frac{a_i-a_1+a_n-a_{i+1}}{2}2ai −a1 +an −ai+1  ,发现这个值小于等于 max⁡(ai−a1an−ai+1)\max(a_i-a_1a_n-a_{i+1})max(ai −a1 an −ai+1 ).
所以最终结果为 max⁡(ai−a1an−ai+1)\max(a_i-a_1a_n-a_{i+1})max(ai −a1 an −ai+1 ).