$\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}$，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541473.html
標籤：其他