The 3rd Universal Cup. Stage 14: Harbin

• 連結：https://qoj.ac/contest/1817
• 時間：2024 Oct 27, 02:00-07:00
• 團隊：ネクロマンサー (SorahISA)
• 成績：6 / 13, Penalty 774, dirt 0% ( A B C D E F G H I J K L M )

沒看計分板以為 I 是水題就 AC 了，結果看了記分板之後才發現是測資太爛 + 自己不會估複雜度！？

A. Build a Computer

Tags:

請構造一個至多 $100$ 個點的自動機，該自動機需要且只能 accept $[L,R]$ 間數字沒有前導零的二進位表示法。

• 舉例來說，當 $(L,R)=(3,5)$ 時，自動機需要且只能接受 $11,100,101$ 這三個字串。

• $1\le L\le R\le 10^6$，你構造的圖只能有一個起點和一個終點，且不能有環

待補

B. Concave Hull

Tags: convex hull

給定 $n$ 個點，求其所有不是 convex 的 simple polygon 的最大面積 $\times 2$。

• 多筆測資、$\sum n\le 200000$、$|x_i|,|y_i|\le 10^9$、沒有三點共線

待補

C. Giving Directions in Harbin

水題，跳過

D. A Simple String Problem

Tags:

題目

• 測資

待補

E. Marble Race

Tags:

題目

• 測資

待補

F. 1D Galaxy

Tags:

題目

• 測資

待補

G. Welcome to Join the Online Meeting!

Tags:

題目

• 測資

待補

H. Subsequence Counting

Tags:

題目

• 測資

待補

I. A Brand New Geometric Problem

Tags:

題目

• 測資

待補

J. New Energy Vehicle

Tags: greedy

你在一維數線上開車，出發點是座標 $0$，有 $n$ 個油箱分別能裝 $a_1,\dots ,a_n$ 公升的油。有 $m$ 個加油站，第 $j$ 個加油站在座標 $x_j$ 處，並能夠幫你加滿第 $t_j$ 個油箱。你的車每行駛 $1$ 單位距離需要消耗 $1$ 公升的油，問最遠可以開到哪裡（用完油剛好到加油站也可以加油並繼續行駛）。

• 多筆測資、$\sum n\le 200000$、$\sum m\le 200000$、$a_i,x_j\le 10^9$

待補

K. Farm Management

Tags:

給定 $n$ 個工作 $({\ell }_i,r_i,w_i)$ 跟時間 $m$，請找到一個 schedule $⟨t⟩$ 使得

• ${\sum }_{i=1}^n{t}_i=m$ 且 $t_i$ 是整數
• ${\ell }_i\le t_i\le r_i$
• ${\sum }_{i=1}^n{w}_i\cdot t_i$ 收益最大

你可以將至多一個工作修改成 $(0,m,w_i)$，求收益最大值。

• $n\le 10^5$、$m\le 10^{11}$、$w_i\le 10^6$、${\ell }_i\le r_i\le 10^6$、$\sum {\ell }_i\le m\le \sum r_i$

待補

L. A Game On Tree

Tags:

題目

• 測資

待補

M. Weird Ceiling

Tags: math

求

$$\sum _{i=1}^n\frac{n}{\max \{k:k\le i\wedge n\mathrm{mod}k=0\}}$$

• 測資數量 $\le 1000$、$n\le 10^9$

$\mathcal{O}(\sqrt{n})$ 枚舉因數即可。