第二周训练
第二周
2-SAT：
Problems - Virtual Judge //n^2建图（枚举前后重叠），跑tarjian；
[HNOI2010] 平面图判定 - 洛谷 //判断相交条件
if(x1>y1)swap(x1,y1);
if(x2>y2)swap(x2,y2);
if(x1>x2)swap(x1,x2),swap(y1,y2);
if(x1<x2 && x2<y1 && y2>y1){
add(i,j+m); //i内j外
add(i+m,j); //i外j内
add(j+m,i); //j外i内
add(j,i+m); //j内i外
}
https://codeforces.com/problemset/problem/27/D //和上一题一样
[USACO11JAN] The Continental Cowngress G - 洛谷 //模版题
[POI2001] 和平委员会 - 洛谷 //模版
https://vjudge.net/problem/UVA-1146 //暴力建图，二分答案；
[NOI2017] 游戏 - 洛谷 //暴力枚举二进制，为A,B包括 选C
[PA2010] Riddle - 洛谷 //前缀优化建边
https://codeforces.com/problemset/problem/587/D //二分+前缀优化建图
[POI2011] KON-Conspiracy - 洛谷 //推贡献即可
[ARC069F] Flags - 洛谷 //好题，线段树优化建图+二分，为前面一题的加强版
树形dp：
[HAOI2015] 树上染色 - 洛谷 //套路题
[NOIP2006 提高组] 金明的预算方案 - 洛谷 //树上依赖背包可做，枚举也可做
二叉苹果树 - 洛谷 //和上一题相同思路
[CEOI2017] Chase - 洛谷 //通过两条路径确定ans
树的直径：
树的直径 - 洛谷 //模版，掌握两种方法：正权，负权
[SDOI2013] 直径 - 洛谷 //需要知道几个性质：最大相同直径必定相交；只有某一条直径上的分支的长度相同才可能成为另外一条直径
[SDOI2011] 消防 - 洛谷 //贪心的考虑直径即可
[APIO2010] 巡逻 - 洛谷 //两次dfs
[AGC001C] Shorten Diameter - 洛谷 //树的直径，枚举中点
Tree Destruction - 洛谷 //先删除直径外的点，再删直径上的点（不妨想一下如果直径上的边权都不同呢？如何解决，显然我们有一个n^2的做法，就是区间dp）
重建道路 - 洛谷 //直接定义状态转移就好了。
有线电视网 - 洛谷 //定义状态：节点i有j个转播点的最大值即可；最后答案从后面枚举根节点的数量。
“访问”美术馆 - 洛谷 //定义状态节点i具有j代价的最大数量，二进制优化背包选取，将代价转化为边。对叶子节点特判，注意加min优化一下，否则TLE；
for(int j=min(n,sz[u]); j>=0; j--){
for(int k=0; k<=min(j-w,sz[v]); k++){
if(v==0){
f[u][j]=max(f[u][j-w-k]+f[v][k]+w/5,f[u][j]);
}else{
f[u][j]=max(f[u][j-w-k]+f[v][k],f[u][j]);
}
}
}
线性基：
【模板】线性基 - 洛谷 //模版题，有贪心，高斯消元的做法。如果学过线性代数的基础解系会很快理解。
[BJWC2011] 元素 - 洛谷 //贪心线性基，可以从任何子集的异或和不为0可以得出。所以我们可以利用线性基异或不为0的性质来贪心实现；为什么不能枚举二进制上每一位为1的最大值呢？线性基实际上做的就是这样的事情，只不过线性基考虑了一个数与子集异或后的情况。
Problem - 3949 //子集异或第K小，首先我们得排除0的一个情况，其次我们有一种直觉，2^k,k是线性基的个数。简单的证明一下，考虑第i个与i-1个；首先i的出现肯定是i及其后面的子集；i-1的出现同样；那么对于i和i-1构成的数，可以通过异或抵消；所以我们的自觉是正确的。注意需要使用高斯消元求得线性基
[TJOI2008] 彩灯 - 洛谷 //求方案数，模版题
[CQOI2013] 新Nim游戏 - 洛谷 //利用nim结论，贪心求线性基；
总结：本周出去打了icpc南京区域赛，落下几天的进度，同时被课程作业逼迫，故更新较慢。但是沉淀了一下，个人的提升还是挺大滴。下周出一个线性基的专题讲解，同时讲一下最近正在做的一个springboot项目的开发经验。