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

$\text{Case0}$:

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

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

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

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

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

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

$\color{red}\text{Case3}$: $\color{blue}\text{CF1600E}$

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

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

$\color{red}\text{Case4}$: $\color{blue}\text{CF1600F}$

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

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

$\color{green}\text{Case5}$: $\color{orange}\text{CF1601A}$

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

$\color{green}\text{Case6}$: $\color{purple}\text{CF1601D}$

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

2022.12.9 21:14
线段树有时候最小值是 $\color{green}\text{负无穷}$，但我的程序询问还是建树时有些地方都用的 $\text{0}$ 为初始值。$\color{red}\text{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}\text{int}$，好，又忘记开 $\color{green}\text{long long}$ 了。
改完之后 $\color{red}\text{TLE On test #8/60}$

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

$\color{green}\text{Case7}$: $\color{purple}\text{P5782}$

2022.12.11 15:05
2-SAT模板题。$\color{red}\text{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}\text{Case2.5}$: $\color{purple}\text{P1224}$

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

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

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

$\color{blue}\text{#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}\text{TLE 75pts}$。（在某些点上速度快了很多，多过一个点，少过一个点）

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

G！

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

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

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

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

$\color{grey}\text{Case9}$: $\color{purple}\text{CF1601E}$

$\color{red}\text{Case10}$: $\color{green}\text{P1613}$

2022.12.5
$\color{green}\text{AC}$。