做题思路不清晰（[做题计划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}$           。