CF1032G Chattering

2022-09-22 20:02:43 字數 947 閱讀 8279

cf1032g chattering

容易發現,這道題用倍增。(秒掉題目演算法,被實現卡掉。。。)

再撕烤,是區間跳區間,那麼其實更新的是端點,那麼維護什麼就很顯然。

用st表維護一個從當前點開始 \(2^i\) 秒能跳到的左右端點,再用一個st表維護一個區間內能跳到的左右的最遠點,然後用後者更新前者。

最後一直倍增跳就完了。

時空 \(o(n \log n)\)

#include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 3e5+10;

ll n, m, log[maxn], val[maxn], lb[maxn], rb[maxn], lt[21][maxn], rt[21][maxn];

struct st_biao

void build(ll *now, ll n, ll _type)

ll qmin(ll l, ll r)

} stl, str;

int main()

for (ll i = 1; i <= 3*n; i++)

for (ll i = 0; i <= log[3*n]; i++) rt[i][3*n] = 3*n, lt[i][1] = 1;

for (ll i = 1; i <= 3 * n; i++)

stl.build(lt[0], 3*n, -1), str.build(rt[0], 3*n, 1);

for (ll i = 1; i <= log[3*n]; i++)

}for (ll j = n+1; j <= 2*n; j++)

printf("%lld ", ans + 1);

}return 0;

}

CF1032D Solution

題目連結 可以分兩類討論 a b 點間的最短路徑,經過函式與不經過函式,其中不經過函式的情況曼哈頓距離即可。 可得在只能經過格點的情況下,點 a 到函式 f 最短距離的點 x 值與 y 值中一定有一項與 a 相等。 也就是如左圖,點 a 到直線的最短距離一定為 ad 與 ac 的最小值, b 同理。...

CF1450G

給定字串 s ,保證不存在t r y g u b,即字符集 mathbf 為 20 給定常數 k frac ,你可以執行以下操作 假定經過若...

CF526G

給定一棵樹 t ,有 q 次詢問,每次給定兩個數 x y ,在樹上選出 y 條鏈,使得其並可以構成一個包含 x 的連通塊。 n q le 5...