做题思路不清晰（[做题计划1~10] 杂题乱选）

时间2025-09-18 15:13:07分类IT科技浏览5331

导读：$\text{Case0}$: [是否自主完成][题目难度] 时间：完成细节。...

$\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}$ 。