[做题计划1~10] 杂题乱选

$ ext{Case0}$:

[是否自主完成][题目难度]
时间：
完成细节。

$color{red} ext{Case1}$: $color{purple} ext{P1117 [NOI2016] 优秀的拆分}$

2022.12.1 killed[不会，但大概懂了]
技巧：二分，hash
TIP：用 $color{green} ext{hash}$ 作为变量名会CE

$color{red} ext{Case2}$: $color{blue} ext{P2464 [SDOI2008] 郁闷的小 J}$

2022.12.6
对每种书开一棵平衡树。用 $color{green} ext{hash}$ 或 $color{green}
ext{map}$ 离散化
16：52->40pts

2022.12.7 21:27
读入问题，把读入的int型变量定义成了 $color{green} ext{char}$。关键用的时候 $color{green} ext{char}$ 又变回了 $color{green} ext{int}$，在不炸 $color{green} ext{爱斯科码}$ 时是不会有问题的。$color{green} ext{6}$。

$color{red} ext{Case3}$: $color{blue} ext{CF1600E}$

2022.12.8 15:09
设计了DP状态，$f(L,R,lim)$ 表示这个序列左右两边能否选，价值即为其是否能达到取奇数个。
空间是 $n^2$ ，所以用的搜索， $color{red} ext{TLE On test #48/50}$。
然后尝试用 $color{green} ext{map}$ 记忆化， $color{red} ext{TLE On test #32/50}$。
或许 $color{green} ext{hash}$ 还会再快一点，但我不想试了。

2022.12.8 15:24
原来是结论题，具体可以看题解。
发现只有50个点，或许我原来的方法其实可以卡过去？

$color{red} ext{Case4}$: $color{blue} ext{CF1600F}$

2022.12.8 15:48 $color{green} ext{拉姆齐定理}$

2022.12.8 16:06
根据$color{green} ext{拉姆齐定理}$，每48人中必定有5个人互相认识或不认识。直接暴力即可。
比较神奇的是 $2 imes 48^5$ 会 $color{red} ext{TLE On test #27/30}$ ，还得小优化一下（指每次递增地搜索，复杂度 $2 imes 48!div(48-5)!$ ），然后就快的飞起 $color{green} ext{AC In 140ms/1000ms}$。
这种搜索小习惯还是要养成。

$color{green} ext{Case5}$: $color{orange} ext{CF1601A}$

2022.12.8 20:38
对每个二进制进行单独处理，统计出每一位有几个，看看这一位是不是答案的倍数，
复杂度 $30 imes n$ ，$color{green} ext{AC In 139ms/2000ms}$

$color{green} ext{Case6}$: $color{purple} ext{CF1601D}$

2022.12.8 21:51
贪心+ $color{green} ext{DP}$
思路目前是按一定顺序 对登山者进行排序，然后 $color{green} ext{DP}$ 设计 $dp[ ext{max}(q[i].a,q[i].s)][i]= ext{max}(dp[ ext{max}(q[i].a,q[i].s)][i],dp[j][i-1]+1),(jle q[i].s)$
然后想到线段树优化。结果打挂了。下次调吧。$color{red} ext{WA On test #2/60}$

2022.12.9 21:14
线段树有时候最小值是 $color{green} ext{负无穷}$，但我的程序询问还是建树时有些地方都用的 $ ext{0}$ 为初始值。$color{red} ext{WA On test #4/60}$。

2022.12.9 21:22

bool cmp1(node A,node B){return A.s*A.a<B.s*B.a;}

乍一看，这只是一份人畜无害的排序代码，但是乘法在离散化之后还会炸 $color{green} ext{int}$，好，又忘记开 $color{green} ext{long long}$ 了。
改完之后 $color{red} ext{TLE On test #8/60}$

2022.12.9 21:51
怀疑 $color{green} ext{map}$ 慢了，自己打个 $color{green} ext{hash}$ 离散化。不出意外，稳定发挥，链式前向星挂了。
$color{green} ext{AC In 1860ms/2000ms}$

$color{green} ext{Case7}$: $color{purple} ext{P5782}$

2022.12.11 15:05
2-SAT模板题。$color{red} ext{WA 35pts}$。

2022.12.11 16:13

W CODE

else if(bk[u])low[u]=min(low[u],dfn[v]);

C CODE

else if(bk[v])low[u]=min(low[u],dfn[v]);

$color{grey} ext{Case2.5}$: $color{purple} ext{P1224}$

2022.12.13 15:26
尝试暴力 $O(n^2d)$ 。$color{red} ext{TLE 75pts}$。
尝试随机化。 $color{red} ext{RE}$。

发现问题:
$color{blue} ext{#1}$

Wcode
printf("%d %d
",min(sui[i],sui[j]),max(sui[i],sui[j]));
Ccode
printf("%lld %lld
",min(sui[i],sui[j]),max(sui[i],sui[j]));

$color{blue} ext{#2}$

Wcode
for(int i=1;i<=1000;i++)swap(sui[rand()],sui[rand()]);
Ccode
for(int i=1;i<=1000;i++)swap(sui[rand()%n+1],sui[rand()%n+1]);

修改问题后：$color{red} ext{TLE 75pts}$。（在某些点上速度快了很多，多过一个点，少过一个点）

随机化+大数据摆烂（输出”-1″)。$color{red} ext{TLE+WA 70pts}$。

G！

突然发现 $k$ 的范围只有 $ ext{2}$ 和 $ ext{3}$。
2022.12.15
不会。

$color{green} ext{Case8}$: $color{blue} ext{P2738 [USACO4.1]篱笆回路Fence Loops}$

2023.1.8 15:31
这题主要烦在建图。
我们发现每个篱笆都有左右两个端点，但是有些篱笆共用端点，而共用的端点只能算一个。我们发现共用的端点所连接的篱笆编号完全一致，所以可以利用集合的互异性，用 bitset 表示每个点连接的篱笆，共用的点会自动去重。

然后就是找无向图中的最小环。 这里用的是 $ ext{Floyd}$ 。
但我也有自己的想法：枚举每条边，求包括这条边的最小环，那么只需要割断这条
边，求两个端点的最小距离，再加上这条边的长度即可。

$color{grey} ext{Case9}$: $color{purple} ext{CF1601E}$

$color{red} ext{Case10}$: $color{green} ext{P1613}$

2022.12.5
$color{green} ext{AC}$。