[做題計劃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}$。