第一周训练

第1周

树形dp：

[POI2013] LUK-Triumphal arch - 洛谷

[USACO08JAN] Cell Phone Network G - 洛谷 //相邻点

战略游戏 - 洛谷 //覆盖边

[POI2014] HOT-Hotels - 洛谷 //实际上这个是考虑每个节点，根据每个相邻节点不同分支进行考虑

[USACO17DEC] Barn Painting G - 洛谷 //dp方案数，乘法原理

[HNOI2014] 米特运输 - 洛谷 //这个思路挺巧妙，考虑结果的规律，然后进行筛选，注意哈希冲突。

[蓝桥杯 2021 省 A] 左孩子右兄弟 - 洛谷 dfs即可

[POI2014] FAR-FarmCraft - 洛谷好题，分类讨论一下，发现贪心选择安装时间长的即可

[蓝桥杯 2018 国 A] 采油 - 洛谷模拟考虑一下即可，由于可以随便空运于是我们可以考虑

[ZJOI2007] 时态同步 - 洛谷统计以该节点为根的子树的最大值即可。

[HAOI2009] 毛毛虫 - 洛谷 //树的直径

[POI2011] DYN-Dynamite - 洛谷 //二分+树形dp，转化为最小点集覆盖

[USACO12FEB] Nearby Cows G - 洛谷 //两遍dfs，第一遍预处理，第二遍计算结果

四边形不等式优化DP

石子合并（弱化版） - 洛谷 //石子合并+四边形不等式优化

2-SAT:

将或问题转化为必然后续问题；

下面有几个点需要知道：

1.同一条链必然存在反链；所以如果a同时取0和1，那么将在同一个联通块中；

2.选择某条链的点，其后续节点一定选上；这个后续节点都选上实际上是拓扑排序的体现；

【模板】2-SAT - 洛谷

SAT模版：

 #include<iostream>#include<cstring>using namespace std;const int N=2*1e6+10;int h[N], e[N], ne[N], idx; //邻接表int dnf[N],stak[N];bool instak[N];int low[N],id[N],cnt;int times;int top;void add(int a, int b) //添加边{e[idx] = b, ne[idx] = h[a], h[a] = idx++;}void tarjan(int u){dnf[u]=low[u]=++times;instak[u]=true;stak[++top]=u;for(int i=h[u]; ~i; i=ne[i]){int v=e[i];if(!dnf[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(instak[v]){low[u]=min(low[u],dnf[v]);}}if(dnf[u]==low[u]){++cnt;int y;do{y=stak[top--];instak[y]=false;id[y]=cnt;}while(y!=u);}}int main(){std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int n,m;cin>>n>>m;memset(h,-1,sizeof h);while(m--){int i,j,a,b;cin>>i>>a>>j>>b;i--;j--;add(2*i+!a,2*j+b);add(2*j+!b,2*i+a);}for(int i=0; i<2*n; i+=2){if(!dnf[i+1]){tarjan(1+i);}if(!dnf[i]){tarjan(i);}}for(int i=0; i<n; i++){if(id[2*i]==id[2*i+1]){cout<<"IMPOSSIBLE"<<endl;return 0;}}cout<<"POSSIBLE"<<endl;for(int i=0; i<n; i++){if(id[2*i]<id[2*i+1])cout<<"0"<<' ';else cout<<"1"<<' ';}return 0;}

tarjian

关于讨论为什么是 low[u]=min(low[u],dnf[v]);

而不是 low[u]=min(low[u],low[v]);

https://www.luogu.com/article/g5rh9ro2

981div3（切6题）

https://codeforces.com/contest/2033/problem/A //模拟即可

https://codeforces.com/contest/2033/problem/B //注意到只需要主对角线，记录主对角线的最小值即可

https://codeforces.com/contest/2033/problem/C //注意到对称的关系，当不相等时交换有效，对于i-1，如果存在贡献就切断，同时swap，将这个swap的影响给到i+1，因为当i和i+1同时调换时，相当于原本的关系。最后影响传递到中间的值。

https://codeforces.com/contest/2033/problem/D //贪心求出能选i就选i，线性处理即可

https://codeforces.com/contest/2033/problem/E //注意到交换两个数最多使得4个数不再处理；然后根据数与数之间的一一对应关系，可以知道直接交换即可；

F不太清楚结论，裴波拉契序列k倍数循环；

https://codeforces.com/contest/2033/problem/G //一开始以为向下走消耗体力，用了离线查询+两颗线段树查询区间最大值；