Day7 构造法 搜索

2018.1.12 学习笔记
湖南师大2018.1.6

构造法

T1

　　$O(19^2)$预处理辅音间的相邻关系，再$O(2^{19})$枚举所有辅音大小写情况。敢写。

Codeforces 911 F

　　猜想！
　　如果点x到直径两端点的距离不是最大距离，那就会形成一条新的直径。

BCPC 2017 A

　　边相等！

EC-Final 2017 G

　　排序，再暴力求相邻两个的第一个不一样的位置，即最长公共前缀；对于两个不相邻的，就区间取个min（类似SA？）。最后因为最多k-1位，要对答案去重。最后就是$O(nmlog_2n)+O(klog_2k)$。
　　在Trie树上求LCA好像也可以？觉得好像并不行...

CCPC 2017 H

　　法向量？在平面上找两个向量，法向量与这两个向量点积都为0。可以在更高维的空间上使用。
　　$O(Tn^4)$：把这n个点设出来，表示出来，会有平方项，做个差分消掉，再用高斯消元，需要n+1-m次消元。->$O(Tn^3)$优化，什么什么方程是不会变的，每次可以把上次消元的结果存下来。
　　几何方法：把每个点坐标和第一个点减一下，可以得到一个向量。XXX...法向量是垂直的，知道每个中点的位置，用勾股定理。

Codeforces 911 E

Codeforces 871 B

　　注意$^\wedge$的性质。
　　枚举$b_0$，整个b序列就可以确定。

搜索

BCPC 2017 J

　　爆搜，每次往前加一位，到4000多位就没有了？？？

BCPC 2017 E

　　每一次id+1时，值+3,3是个很小的值，相对就是$+\frac{t}{2}$。。时间大概就是$log_2n$。

BZOJ 1026 Windy数

JSTSC 2016 Day2T2

　　最大独立集，1特判。（或者随机多次，最后取个最大值）

沈阳赛区 2017 E

PKUSC 2016 Day1 AM A

ps Day8T1

这里也就是不考虑失败的情况
因为终止局面连续一段i个石头
所以枚举j为最后一个放的是第几个石头
那么因为j处有空位，从j到i这几个位置放石头都能够到达j处，也即(i-j+1)
又因为前j-1个石头和后i-j个石头已经不相连了，所以放置的方案数是独立的，所以C(i-1,j-1)代表两段的放置序列合并的方案数
最后还要乘上Cntj-1和Cnti-j就可以了