前言
建立这个文档呢，主要是因为感觉做了题目很快又忘掉了，或者做到某一道题目的时候觉得跟以前自己做过的某道题目很像就想找一找，但是却找不到jhlp。
因此这个文档应运而生啦~一方面增加自己做题的成就感，另一方面方便自己查看和查询。
按时间顺序
2020/08/31 CF 1397A Juggling Letters
n个字符串，可以随意把一个字母从一个串移到另一个串，问能否使得n个串相同。统计所有字母的个数，全部都能被n整除即可。
2020/08/31 CF 1397B Power Sequence
n个数，求把他变成一个power序列的最小花费。power序列是指(a[i]=c^i,iin[0,n-1])
显然n>40以后，c=1是最优的答案，因为a[i]<=1e9，如果c!=1那么把最大的数变成第n项的代价就足够大了。
n<40的时候枚举c，寻找最小的花费，为了防止(c^i)溢出，当答案>9e18的时候结束循环即可。
2020/08/31 CF 1397C Multiples of Length
给一个数组，定义每次操作，能选择一个区间，给区间的每一个数加上区间长度的倍数，区间里的数可以选择加不同的数，只要是区间长度的倍数即可。需要在3次操作内使数组全部变为0。
想法题，首先一次操作把第一个数变为0，第二次操作把2-n这些数全都变成原来的n倍（因为区间长度=n-1，通过加上自己的n-1倍完成），第三次操作把整个序列（除了第一位）都减去原来的数的n倍（因为区间长度为n，第二步又把2-n个数都变成了原来的n倍，现在减去即可完成任务）。
2020/08/31 CF 1397D Stoned Game
两个人玩取石子游戏，一开始有n堆石子，每次可以从一堆非空石子堆取走一个，规定每个人不能取前一轮被取过的石子堆，给出石子堆情况问谁能赢？
如果最大的一堆能够大于剩下所有堆，那么先手一定能赢。否则一定会形成所有堆都是1的情况，因此总和为奇数先手赢，否则后手赢（其实这里不是很懂，是看别人的博客的）
2020/09/01 牛客小白月赛27 A 巨木之森
给一棵n个结点的树，m块钱。定义从一个点出发遍历整棵树的花费是路径的边权和。
求最多能选择多少个不同的起点使得从这些起点分别遍历整棵树的花费<=m。
把一个点出发的花费转化成整棵树边权和的两倍减去最长链长度。再通过树的直径的性质维护直径的两个端点到所有点的距离即可O(1)求出对某个点来说距离他最远点的距离是多少。
2020/09/01 HDU-5418 Victor and World
TSP模板题
时间复杂度2^n *n^2
状压DP做法
2020/09/01 牛客小白月赛27 C光玉小镇
TSP模板题，把点挑出来，n次bfs求出任意点对之间的最短距离开始跑模板即可
时间复杂度2^n *n^2
状压DP做法
2020/09/02 HDU-3062 Party
2-SAT模板题，两个人不能同时去婚礼。
2020/09/02 HDU-1824 Let's go home
2-SAT模板题，队长回家两个队员必须留下，队员回家队长必须留下，m对队员，一个留下，另一个则必须离开，建边跑模板即可。
2020/09/02 POJ-3207 Ikki's Story IV - Panda's Trick
2-SAT模板题
类似洛谷P3209
考虑一个有哈密顿路径的图，非圈上的边要么在圈外，要么在圈内
两条边的区间如果部分相交的话则表示这两条边不能在同侧，据此建边跑2-SAT即可
2020/09/02 HDU-1815 Building roads
2-SAT进阶题
两个中转点s1,s2，n个谷仓，每个谷仓只能选择其中一个谷仓建路，两个中转点之间建了一条边
有仇的两个谷仓不能连在同一个中转点上
有好感的两个谷仓一定要连在同一个中转点上
求一种使得任意两点之间的距离中的最大值最小的方案
二分最大距离，根据目前二分到的最大距离，如果某种连接方式会>当前二分到的最大距离
那么说明这样连边不可行
①dis[i,s1]+dis[j,s1]>DIS 若i连到s1，则j一定连到s2。 若j连到s1，则i一定连到s2
②dis[i,s1]+dis[j,s2]>DIS 若i连到s1，则j一定连到s1。 若j连到s2，则i一定连到s2
③dis[i,s2]+dis[j,s1]>DIS 若i连到s2，则j一定连到s2。 若j连到s1，则i一定连到s1
④dis[i,s2]+dis[j,s2]>DIS 若i连到s2，则j一定连到s1。 若j连到s2，则i一定连到s1
建边跑模板即可。
2020/09/02 HDU-3622 Bomb Game
2-SAT进阶题
每次给出两个点，可以选择一个点放炸弹，并且可以选择一个爆炸半径
要求n次爆炸范围不相交
求爆炸半径最小值最大是多少。
一般这种最小值最大、最大值最小基本上都是用二分
这里是二分最小半径。
两个爆炸点之间爆炸半径取多少是收益最大化的呢，显然是取两点距离的一半，否则会让最小半径变小，不利于最小值最大化
因此每次确定一个mid作为DIS
判断第i次给出的两个点和第j次给出的两个点两两之间距离的一半是否小于DIS
若是则说明这两个点不能同时选择。
与HDU1815想法相似，建边跑2-SAT即可，由于是double类型需要注意精度问题
2020/09/03 HDU-3715 Go Deeper
2-SAT进阶题
函数表达的是，如果x[a[i]]+y[b[i]]!=c[i],则i一直++，直到i>=m为止。
给定a,b,c数组，求i的最大值，二分最大值
check的时候，假设从0~当前位置上式均不成立，以此为约束条件，对c[i]=0/1/2分别讨论，根据约束条件建边，跑2-SAT模板即可。
二分出答案后+1即可，因为二分出来的答案最大的满足上式的答案，但在判断出不符合条件时i已经++了，所以需要+1
2020/09/03 ZJNU-1420 TSP问题
TSP模板题
时间复杂度2^n *n^2
分类
签到
2020/08/31 CF 1397A Juggling Letters
n个字符串，可以随意把一个字母从一个串移到另一个串，问能否使得n个串相同。统计所有字母的个数，全部都能被n整除即可。
想法
2020/08/31 CF 1397B Power Sequence
n个数，求把他变成一个power序列的最小花费。power序列是指(a[i]=c^i,iin[0,n-1])
显然n>50以后，c=1是最优的答案，因为a[i]<=1e9，如果c!=1那么把最大的数变成第n项的代价就足够大了。
n<40的时候枚举c，寻找最小的花费，为了防止(c^i)溢出，当答案>9e18的时候结束循环即可。
2020/08/31 CF 1397C Multiples of Length
给一个数组，定义每次操作，能选择一个区间，给区间的每一个数加上区间长度的倍数，区间里的数可以选择加不同的数，只要是区间长度的倍数即可。需要在3次操作内使数组全部变为0。
想法题，首先一次操作把第一个数变为0，第二次操作把2-n这些数全都变成原来的n倍（因为区间长度=n-1，通过加上自己的n-1倍完成），第三次操作把整个序列（除了第一位）都减去原来的数的n倍（因为区间长度为n，第二步又把2-n个数都变成了原来的n倍，现在减去即可完成任务）。
2020/08/31 CF 1397D Stoned Game
两个人玩取石子游戏，一开始有n堆石子，每次可以从一堆非空石子堆取走一个，规定每个人不能取前一轮被取过的石子堆，给出石子堆情况问谁能赢？
如果最大的一堆能够大于剩下所有堆，那么先手一定能赢。否则一定会形成所有堆都是1的情况，因此总和为奇数先手赢，否则后手赢（其实这里不是很懂，是看别人的博客的）
数据结构
动态规划
图论
树
2020/09/01 牛客小白月赛27 A 巨木之森
给一棵n个结点的树，m块钱。定义从一个点出发遍历整棵树的花费是路径的边权和。
求最多能选择多少个不同的起点使得从这些起点分别遍历整棵树的花费<=m。
把一个点出发的花费转化成整棵树边权和的两倍减去最长链长度。再通过树的直径的性质维护直径的两个端点到所有点的距离即可O(1)求出对某个点来说距离他最远点的距离是多少。
TSP货郎担问题
2020/09/01 HDU-5418 Victor and World
TSP模板题
时间复杂度2^n *n^2
状压DP做法
2020/09/01 牛客小白月赛27 C光玉小镇
TSP模板题，把点挑出来，n次bfs求出任意点对之间的最短距离开始跑模板即可
时间复杂度2^n *n^2
状压DP做法
2020/09/03 ZJNU-1420 TSP问题
TSP模板题
时间复杂度2^n *n^2
2-SAT
2020/09/02 HDU-3062 Party
2-SAT模板题，两个人不能同时去婚礼。
2020/09/02 HDU-1824 Let's go home
2-SAT模板题，队长回家两个队员必须留下，队员回家队长必须留下，m对队员，一个留下，另一个则必须离开，建边跑模板即可。
2020/09/02 POJ-3207 Ikki's Story IV - Panda's Trick
2-SAT模板题
类似洛谷P3209
考虑一个有哈密顿路径的图，非圈上的边要么在圈外，要么在圈内
两条边的区间如果部分相交的话则表示这两条边不能在同侧，据此建边跑2-SAT即可
2020/09/02 HDU-1815 Building roads
2-SAT进阶题
两个中转点s1,s2，n个谷仓，每个谷仓只能选择其中一个谷仓建路，两个中转点之间建了一条边
有仇的两个谷仓不能连在同一个中转点上
有好感的两个谷仓一定要连在同一个中转点上
求一种使得任意两点之间的距离中的最大值最小的方案
二分最大距离，根据目前二分到的最大距离，如果某种连接方式会>当前二分到的最大距离
那么说明这样连边不可行
①dis[i,s1]+dis[j,s1]>DIS 若i连到s1，则j一定连到s2。 若j连到s1，则i一定连到s2
②dis[i,s1]+dis[j,s2]>DIS 若i连到s1，则j一定连到s1。 若j连到s2，则i一定连到s2
③dis[i,s2]+dis[j,s1]>DIS 若i连到s2，则j一定连到s2。 若j连到s1，则i一定连到s1
④dis[i,s2]+dis[j,s2]>DIS 若i连到s2，则j一定连到s1。 若j连到s2，则i一定连到s1
建边跑模板即可。
2020/09/02 HDU-3622 Bomb Game
2-SAT进阶题
每次给出两个点，可以选择一个点放炸弹，并且可以选择一个爆炸半径
要求n次爆炸范围不相交
求爆炸半径最小值最大是多少。
一般这种最小值最大、最大值最小基本上都是用二分
这里是二分最小半径。
两个爆炸点之间爆炸半径取多少是收益最大化的呢，显然是取两点距离的一半，否则会让最小半径变小，不利于最小值最大化
因此每次确定一个mid作为DIS
判断第i次给出的两个点和第j次给出的两个点两两之间距离的一半是否小于DIS
若是则说明这两个点不能同时选择。
与HDU1815想法相似，建边跑2-SAT即可，由于是double类型需要注意精度问题
2020/09/03 HDU-3715 Go Deeper
2-SAT进阶题
函数表达的是，如果x[a[i]]+y[b[i]]!=c[i],则i一直++，直到i>=m为止。
给定a,b,c数组，求i的最大值，二分最大值
check的时候，假设从0~当前位置上式均不成立，以此为约束条件，对c[i]=0/1/2分别讨论，根据约束条件建边，跑2-SAT模板即可。
二分出答案后+1即可，因为二分出来的答案最大的满足上式的答案，但在判断出不符合条件时i已经++了，所以需要+1