Results
180/400 Rank 11
| pA | pB | pC | pD |
|---|---|---|---|
| 32 | 38 | 10 | 100 |
pA
7/25/29/39
題敘
給一棵樹，某些點已經被上了相異的顏色
每次可以取一個未被上色的點，並將其上一個相鄰點的顏色
求有幾組合法的方案模 $10^9 + 7$
想法
怪怪樹DP
看起來要求 $O(n^3)$，完全沒有想法
把 $n \leq 20$ 的暴力拿一拿就放掉了
全場只有 che AC，他超強
pB
11/14/(13)75
題敘
給一個 $n \times n$ 的表格，每一格的值都是 $1$ 或 $-1$
每次可以詢問一個矩形區間的和
最多詢問 $40000$ 次($n \leq 1000$)
求出一組 $(1,1)$ 到 $(n,n)$ 的最短路徑，使該最短路徑右下的和越大越好
若理論最佳解為 $a^*$，輸出的解為 $a$，得分為 $\frac{a}{a^* \times 0.99}$
想法
超酷的互動題，部份給分方式更酷
怪怪的 Approximation 題，超多人 claim 是蔡孟宗出的
前兩個subtask都有簡單的確定性解
無額外限制的部分我把每個橫排切成 $\min(\frac{40000}{n}, n)$ 塊
就這樣唬爛到了 13 分
據說切成好幾個小方塊可以拿更高分，LittleCubeOrz
pC
10/31/59
題敘
想法
To Be Finished
🉐🉐數奧題
pD
3/8/12/32/45
題敘
想法
裸的斜率不單調查詢不單調斜率優化
除了李超也沒有其他好作法ㄌ
開場測資燒機，不過我很晚才開這題(題敘太複雜不想開)
也沒拿到那個怪怪補償
小結
整體來說算打得還可以吧
把 pC 扣掉我會在 Rank 6
也順利進了二階
希望台大教授不要刷我><