[CF] #353(Div2)

#353 Div2



A. Infinite Sequence

給你一個等差數列問有沒有某個值


注意一下0的問題應該就沒問題了



B. Restoring Painting

給n,a,b,c,d

在3 x 3的矩陣下 每一格都只能填1~n 每一個2x2的子矩陣的和都是相同的


算出4個角落的最大最小差 因為差是固定的 且所有的值都是1~n

假設k=max-min 那(1,1+k)~(n-k,n)就是4個角落可能放的數字 最後中間直接*n



C. Money Transfers

給一個環狀的數列 合為0

定義操作為移動任意的值到旁間

問全部變成0的最少操作數


前墜和 只有和一樣的邊界才會不需要操作其他都要

所以ans= n-max(相同的前墜和個數)

D. Tree Construction


給一個二元搜尋樹的插入順序


問除了第一個點的父節點是誰



因為n到100000 直接建樹 一條鍊會變成n^2


對於每一個節點的插入 他的父節點只會有兩個可能


就是比他小或比他大的第一個 需要做的就是去尋找他的上一個和下一個數


哪個比較晚就是父節點 map的++-- 可以輕鬆找




E. Trains and Statistic

現在有一條n個站的路 對於每一站 i (除了最後一站)都有一個值ai表示他可以用一步走到i+1站到ai站

p(i,j)表示從第i站到第j站最少用的步數

問p(1 <= i < j <= n)的總和




dp

從最後面dp回來

dp[x]=min(dp[k]+n-i-(ax-k)) for ax>=k (可以一步到的就一步到 不行的就先到k)

輕鬆炸裂TLE

需要維護一個stack 我們知道跳愈大步愈好

所以stk存(i,a[i]) 且保證 stk[u].a[i] > stk[u+1].a[i]

因為放的方式從n-1->1 所以i是遞增 去二分搜 ax 搜到就是最接中繼站

nlogn解完

[CF] codeforces #291

A

給你一個正整數 x

你可以將每一位數 t 轉成 9-t
問你在不影響位數的情況下(0 = 0位數)

可以轉成的值最小是哪個

(1 ≤ x ≤ 1018)




B

你是戰場上的雷射兵

戰場上n個突襲兵

你有他們的座標跟你自己的座標(整數二維座標(x,y))

你一次可以發射一條雙向射線

問你最少要開幾槍才能擊倒所有突襲兵

(1 ≤ n ≤ 1000,  - 104 ≤ x, y ≤ 104)




C

給你n個字串

問你m個問題

每個問題都是給你字串

在n個字串中是否有一個字串與他一樣長且剛好差一個字

(字串只包含'a','b','c')

(0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105)

(子串總長度<6·105)

[CF] codeforces #292

2A.

給你一個二維座標(a,b) 問你是否可以從(0,0)走 s 步到(a,b)

一步可以從(x,y)到(x+1,y),(x-1,y),(x,y+1),(x,y-1)

( - 109 ≤ a, b ≤ 109, 1 ≤ s ≤ 2·109)




2B.

現在有n個男生跟m個女生 有一些人本來就很快樂(?

你可以在第i天的時候把編號(i%n)的男生跟編號(i%m)的女生放在一起吃晚餐

如果有其中一方快樂那另外一方也會快樂(怪怪der 真的在吃飯嗎-.-

只要他快樂他就會一直快樂,問你有沒有可能讓每一個人都快樂

(1 ≤ n, m ≤ 100)




2C.1A.

定義一個F,F(x)=將x的每一個位數拆開然後變成階層相乘

ex F(135)= 1! * 3! * 5! = 1 * 6 * 120 = 720

現在給你一個n位正整數a

請你找出一個最大的x 使得F(x)=F(a)

(1 ≤ n ≤ 15)




2D.1B.

給你一個n*m的表格

. 是可用的 *是不可用的

你可以用<,>或是^,v填滿它(必須成對)

問你是不只有一種方法填滿

如果是請輸出該種解法

(1 ≤ n, m ≤ 2000)




2E.1C.

有一隻猴子喜歡跑公園

公園是環狀的且種了n棵樹

猴子的跑法是找兩棵樹x,y 爬上x爬下x跑到y再爬上y爬下y

長度就是2h(x)+2h(y)+dis(x,y)

並且每天都有小屁孩到處跑

猴子最討厭小屁孩所以不願意有機會撞到他們

給你m天小屁孩的活動範圍

問你猴子每天最長可以跑多長

(3 ≤ n ≤ 105, 1 ≤ m ≤ 105)




1D.

給地下的樹 每一個葉子都連結到地面上

裡面住了一些蚯蚓 這些蚯蚓會住在相鄰的地方

假設a,b有住蚯蚓 a->b的路徑上都會住著蚯蚓

每天早上蚯蚓都會從離他最遠的葉子出去

q個問題 問你在抵達地面時間最長和最短差不到l的情況下 最多能有幾隻蚯蚓

(2 ≤ n ≤ 105)

(1 ≤ q ≤ 50)


1E

跟2B一樣的問題

只是要問是第幾天他們都變快樂

還有n,m變大了些Q_Q

(1 ≤ n, m ≤ 109).