如何評價2022年第十三屆藍橋杯省賽？
匿名使用者2022-04-09 00:00:14已經被官方自己評價了，笑死
明天藍橋杯省賽就開始了，這就是山東負責人對於線上作弊的態度！_嗶哩嗶哩_bilibili
匿名使用者2022-04-09 13:53:10謝邀，人在家裡，剛下考場
真噁心啊，多方面的噁心到我了，首先這破系統擱著裝卡牌大師是吧，切一次頁面給一次警告切一次頁面給一次警告，組委會是讓大家直接在答題框裡寫答案是吧，切到DevC++裡剛寫完一題就喜提3次警告，考完40多次警告，贈我一張黃牌。不是我說你都錄屏了還搞這j8東西幹嘛？考生不得看題？不得在Dev裡除錯程式碼？一直給警告，我校都有人因為這個直接交卷了，無語
還有這破題，或許我水平低，沒資格評價這題，但你們是真噁心啊，題型突然變了，好，為了防止有人作弊對填空題，okok。但你們這題的難度和模擬賽一樣嗎，我請問？所有的模擬賽加一起有這張八道程式設計的題難嗎？模擬賽好像騙傻子一樣，卷點 +29。8 * N money，到正賽不裝了，我就是來騙錢的，絕
一個無線滑鼠的事咋整整不明白，一會說可以用，一會又不行，最後臨考試的前一天說不能用，必須用有線滑鼠，要不就觸控板，你是真e啊，還好小區沒封，我臨時出門買的，那些封小區，家裡沒有線滑鼠的咋整？嗯用觸控板？
最後簡單說一下題吧，答主某強省C++A組，感覺-300 了
填空 ：
A： 全場唯一想明白的題，拿紙比劃一下就行，443
B：不會，考前看了一下簡單博弈論，異或啥的，但這題一眼不會，感覺慢慢推太費時間，萬一推錯了就血虧，交卷前蒙了個 VLLV
程式設計：
C ：高精度加法 + 高精度乘法，但是我寫著寫著就亂了，直接不想寫高精度了，交了發暴力
D：沒找出規律，交了發暴力（因為異或的算術符優先順序沒整明白還卡了我好久才調好cao）
E：純純不會，輸出樣例了，看學校群裡說是求逆元？考前就沒整明白逆元，不會認了
F：想打個模擬來著，邊界情況太多了，沒寫明白，就沒交
G：交了發貪心+暴力，貪心的策略明顯不對，不過能過樣例，懶得再調了，交了
H：感覺是個大模擬，剛開始用pair套pair的陣列存斜率，長度和價值，後來排序搞亂了，就重寫了個結構體，過程好像沒錯，最後輸出次序那裡死活調不好，心態崩了，感覺前面過程都是對的，就結果調不明白，因為有相同次序，我就搞了個偏移量，給我害了
I：用算數基本定理寫了發，如果一個數的質因子個數小於等於2且質因子的次數都大於等於2，就yes，反之則no，紙上推了下，感覺應該對，就交了，反正過樣例了，能騙幾分是幾分把
J：隨便模擬了一下，能過樣例，但我自己都能寫出這個模擬過不了的資料，直接交了，能不能騙到分看天意了
藍橋杯？騙錢杯！！
更一下 水了個省三。。。以後的人可以作參考，寫到我這種程度都可以水個強省省三。。。就是學校好像不給報銷省三了！草！
Once2022-04-09 14:20:14先說結論：線上監考比較混亂，題目（A組）對普通選手非常不友好。
先說題目
本人打了兩年藍橋杯，拿了兩屆國一。這幾年藍橋杯一直在努力提升自己的含金量，主要體現在題目難度顯著加大，一等獎也不隨便亂髮。這幾年拿國一的人，可以說都是ACM/OI圈子裡的老面孔了。
而這次的藍橋杯省賽，明顯感覺藍橋杯想把自己打造成大學裡的CSP/NOIP，以至於題目出的有點過火。我的觀點是，藍橋杯畢竟已經是一個每年幾十萬人參加的大型賽事，論受眾比ICPC/CCPC之類的要廣得多，命題，尤其是省賽的命題，更應該照顧絕大部分選手的參賽體驗。所以我認為比較合理的設計可能應該更靠近天梯賽那種，年年第一道Hello World只要來了就能拿分，前八道題對演算法設計都沒什麼太高的要求。
而今年的題目完全是以對標區域賽/NOIP的標準在造，對競賽知識的儲備要求非常高，大多數選手應該做的非常痛苦。比方說E題蝸牛爬樹，背景是一個簡單的機率期望遞推，機率論學的好的同學應該都能想想。但是最後輸出時用了模意義下的逆元。非專業競賽選手肯定是沒見過用逆元輸出有理數的；哪怕能理解，也不太可能自己發明出快速冪求逆元的演算法然後把這道題A了。所以這題的最大難點儼然成了輸出答案。又比如說B題，出題人放這個位置應該是認為這題很簡單，確實，從競賽選手角度來說就是一個暴力dfs，基礎得不能再基礎。可是有多少大學生學過博弈論呢？這就導致擅長博弈的選手做的索然無味，不熟悉博弈的選手題目都看不明白。一套好的題目應該兼顧知識儲備和分析推理，對於這種大眾化的比賽，應該更偏向於分析推理，而非知識儲備。所以我認為這幾題完全可以改一下背景使得更多的人可以有更好的參賽體驗。
此外就是資料範圍上下手相當狠，一共八道程式設計題沒有一道能透過直接模擬AC。我做下來的感覺就是彷彿回到高中在打NOIP。這場省賽隨便抽個三道題出來都能組一套難度不小的NOIP題（以三年前的標準），最後幾題放到省選也不算簽到題。更何況程式碼量和處理細節都不少，就算想出來也不是很敢寫，寫完了也還得寫對拍。可是這四小時的比賽是留不出多少對拍的時間的，最後只能硬著頭皮交了。
I題數的拆分這題我是開出來也寫完的，個人感覺難度是ACM金牌題。
此題不難想到要透過分解質因數去分析各個質因數的次數。顯然，如果某個質因數的次數為1，那麼答案一定為no。因為一個質因數最後可以分成兩半分別放到
和
裡面去。假設這個質因數的次數為
，那麼問題大概轉化為一個不定方程的形式
。因為
是任意的，所以我們不難想到可以去令
，
。因為
對於任意的
都是有非負整數解的（這個結論曾經出現在NOIP2017《小凱的疑惑》中），所以我們就能證明，答案為yes的充要條件是所有質因子的次數大於1。
那麼接下來的問題是給
分解質因數了。因為
是1e18的範圍加上1e5組多測，所以Pollard-Rho也不是很好使（這玩意沒板子也寫不對）。所以需要對問題進行進一步分析。透過分類討論，可以確定，如果答案是yes，
一定滿足以下三種情況之一：
是完全平方數；
是完全立方數；
最小的質因子小於等於
![\sqrt[5]{n}](https://img.heatask.com/upload/website_attach/NW2WGgB5NG-YhdmaBULQmznRFzXTCcFnyl7WMMFibe1+inOfn3o9HM5ghKBXYu=P5puZ+yhSZb0fM.jpeg)
。
第三點的證明如下。如果
不是完全平方數也不是完全立方數，那麼可以對
進行分類討論：
只有一種不同質因子。那麼顯然次數大於等於4。如果剛好等於4的話，不滿足
不是完全平方數的前提，所以次數應該大於等於5，因此
最小的質因子小於等於
。
有超過兩種不同的質因子。因為每種質因子的次數都大於1，所以
至少有四個質因子。接下來繼續分類：1）
有大於等於5個質因子，直接得證；2）
有剛好4個質因子，那麼
，不滿足
不是完全平方數。
判斷完全平方數和完全立方數都可以在
的複雜度內完成。而對於情況3，我們只需要
的複雜度就能找出最小的質因子，隨後遞迴判斷即可。
如果預處理出
以內的所有素數的話，那麼複雜度就是
。
【挖坑，慢慢更】
一個人2022-04-09 15:50:51
櫻落三千2022-04-09 17:25:40寫一篇
不靠譜的部分題解
，組別是A組C++。
文中可能有些地方說的是不對的，可能程式碼也有點問題，建議僅作參考。
A題 裁紙刀
題面
做法
先橫著剪，再豎著剪，發現可以在 n * m + 3 次操作後完成裁剪，直覺上感覺就是最少的，至於是不是最少的不知道怎麼證明。
於是賽場上直接交了個 443。
B題 滅鼠先鋒
題面
做法
推導了一會兒得出 LLLV 的結果，不放心又打了個表驗證，發現果然是 LLLV。
程式碼
#include
using namespace std；
int a［2］［4］；
bool dfs（） {
bool all1 = true；
for（int i = 0； i < 2； i++） {
for（int j = 0； j < 4； j++） {
if（！a［i］［j］） all1 = false；
}
}
if（all1） return true；
bool res = false；
for（int i = 0； i < 2； i++） {
for（int j = 0； j < 4； j++） {
if（！a［i］［j］） {
a［i］［j］ = 1；
if（！dfs（）） res = true；
if（j < 4 && ！a［i］［j + 1］） {
a［i］［j + 1］ = 1；
if（！dfs（）） res = true；
a［i］［j + 1］ = 0；
}
a［i］［j］ = 0；
}
}
}
return res；
}
int main（） {
a［0］［0］ = 1；
cout << dfs（）；
a［0］［0］ = 0；
a［0］［1］ = 1；
cout << dfs（）；
a［0］［1］ = 0；
a［0］［0］ = a［0］［1］ = 1；
cout << dfs（）；
a［0］［0］ = a［0］［1］ = 0；
a［0］［1］ = a［0］［2］ = 1；
cout << dfs（）；
a［0］［1］ = a［0］［2］ = 0；
}
C題 求和
題面
做法
題目要我們求這個式子
，可以寫成
的形式，對於後半部分，做一個字首和就可以在 O（1） 的時限內完成計算，因此對於整個式子就可以在 O（n） 的時限內完成計算。
具體看程式碼。
程式碼
#include
#define ll long long
using namespace std；
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
ll n， res = 0， tmp = 0；
cin >> n；
vector
for（int i = 0； i < n； i++） {
cin >> a［i］；
res += a［i］ * tmp；
tmp += a［i］；
}
cout << res；
return 0；
}
D題 選數異或
題面
做法
維護 f［i］ 表示第 i 個位置左邊第一個 A［j］ 的值為 A［i］ ^ x 的下標 j，這樣有一個性質是 a［i］ ^ a［f［i］］ = x。
比如樣例中，i = 3 處， 3 ^ 1 = 2，而 2 這個數字在 3 位置左邊第一次出現是在 2 位置。因此 f［3］ = 2。
這樣，對於每個詢問 ［l， r］，若滿足
![\max_{i = l}^{r}\{f[i]\} \ge l](https://img.heatask.com/upload/website_attach/2+ujze_xcGzJQd36vj7V3e9U0ddqPfzL5yqjPOho3eqrRniqdmfp1PKs=sSH1t8VzI5OyGm6D9L+DurIoNDrdfoWc=f8bdxg=FFcPlmJD9L+lmrIpfVrdFdA1v9p2.jpeg)
，則該區間記憶體在兩個數的異或為 x。
如何求解 f［i］？從左到右掃一遍，用 pos［x］ 記錄數字 x 當前最右出現的位置。則對於 A［i］，f［i］ = pos［A［i］ ^ x］，同時更新 pos［A［i］］ = i。對於 A［i］ ^ x 不存在的情況，令 f［i］ = 0 即可。
還有需要解決的問題是快速求解
![\max_{i = l}^{r}\{f[i]\}](https://img.heatask.com/upload/website_attach/aCiDrOCKpXlzH29ycBVtYA6z8CDvsO7pdp=DprA5AyeS0lB_B6TQWobm3emAofh-MNh4qVn2hxJPIRIN_vMSBBfjV+FtTC0NJIURpJn0hxJP+PINjkyRW.jpeg)
的值，我們需要一個支援區間 max 的資料結構，可以使用線段樹，ST表……等各種方式維護。
程式碼中我使用了線段樹，預處理時間複雜度 O（nlogn），單次詢問 O（logn），總的時間複雜度為 O（（n + q） logn）。
程式碼
#include
using namespace std；
const int N = 100000， M = 20；
int st［（N + 1） << 2］， pos［1 << M］， Left［N + 1］；
void pull（int i） {
st［i］ = max（st［i << 1］， st［i << 1|1］）；
}
void build（int i， int tl， int tr） {
if（tl == tr） {
st［i］ = Left［tl］；
return；
}
int mid = （tl + tr） >> 1；
build（i << 1， tl， mid）；
build（i << 1 | 1， mid + 1， tr）；
pull（i）；
}
int qry（int i， int tl， int tr， int l， int r） {
if（tl >= l && tr <= r） {
return st［i］；
}
int mid = （tl + tr） >> 1；
if（mid >= r） {
return qry（i << 1， tl， mid， l， r）；
} else if（mid + 1 <= l） {
return qry（i << 1 | 1， mid + 1， tr， l， r）；
} else {
return max（qry（i << 1， tl， mid， l， r）， qry（i << 1 | 1， mid + 1， tr， l， r））；
}
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
int n， q， x；
cin >> n >> q >> x；
for（int i = 1； i <= n； i++） {
int v；
cin >> v；
Left［i］ = pos［v ^ x］；
pos［v］ = i；
}
build（1， 1， n）；
for（int i = 1； i <= q； i++） {
int l， r；
cin >> l >> r；
if（qry（1， 1， n， l， r） >= l） cout << “yes\n”；
else cout << “no\n”；
}
return 0；
}
E題 爬樹的甲殼蟲
題面
做法
這題我的做法非常笨，已經知道了有更簡潔的做法。
令 f［i］ 表示從 i 出發到達 n 的期望次數，則容易得到。
![f[i - 1] = p[i] * (f[0] + 1) + (1 - p[i]) * (f[i] + 1)](https://img.heatask.com/upload/website_attach/+lPuU5=b2tHDkMVG7=kLw4eNTEvm6FSiKJ5uTcsmjqwPV59oqcIzwxyyaU_Htdy+pbtOYtR2iyoHZhS5rwd_Pxyg7WVKZbSv2RhvNgz23hn17g_E_bPBnZM4ZaMr7a1HqAuCvXGfqOazZhamrwd_Pxyg7WVKZbSv+ahvNgz23hn17g_E_ZzAT.jpeg)
維護 a［i - 1］，b［i - 1］，含義是
![f[0] = a[i - 1] \times f[i - 1] + b[i - 1]](https://img.heatask.com/upload/website_attach/NW2WGgB5NG-YhdmaBULQmznRFzXTCcFnyl7WMMFibe1+inPUP1soCYnh3V7UNa5lB3uX+yplNveuRvpIyq4XI_JECrBcvcCS9ugQ5dPlOv5Ws8jf-uPSL+nh2CAFCuKn_4=KM.jpeg)
。
這樣，把第二個式子中的 f［0］ 代入第一個式子。可以解得 f［i - 1］ 關於 f［i］ 的表示式
![f[i - 1] = (f[i] - p[i] \times f[i] + 1 +p[i] \times b[i - 1]) / (1 - p[i] \times a[i - 1])](https://img.heatask.com/upload/website_attach/znrURfeVI4Qrwn-k=bnazKmVu6cpdw_3ijbUjPcqs6m0xmojFl13zBWYCumr2HC_SPfek3Cuvfs0vNWPFl1HTvSg=1C+DRidGzqixEymUfdGShJz55m7sI0aJCDXwmXKTlaixEw2-01pC+hZ+ErcSC1bl+Lpi5K_PFMwEdPbIEahXBibFlEqTvm6Ltrre8D3T=RiRHC6Be40vNBzFl1GiJZYvgeXhMzxs6HieDrPWF52XBVxu.jpeg)
可以寫成以下形式：
![f[i - 1] = c \times f[i] + d \\ c = (1 - p[i]) / (1 - p[i] \times a[i- 1]) \\ d = (1 + p[i] \times b[i - 1]) / (1 - p[i] \times a[i - 1]) \\](https://img.heatask.com/upload/website_attach/fiU511GvNc9_Ij1gK0cs8Hoi84MUO5VLJGN5HYMjb_RwJkhFowqx8SSQ4hAxakQNoqzNs4GEvnVxIzw_eaB=rioPfHWxakQNoqnzs4SEvnVxno9Rp5B=1TY-4gxdbAEN0pEXvUXWH7UhUZpWhUQREkMl3UKQPUsxpROBZx6lvnVkodpNUuIs9W8Z44AxakJB0pDYvUXwvnIQodpNUh7OdyTo4gxe7PsV17jYsgxaK+tqno9wfU7OeCSSVxPh0Z1VIfESvUXWH7s-oekQgk+REjrl3U6zthUfhWCmN-lovnVYenpNwPQRxUYOLY3x2htJoqZzH-=SsdEwzqKQ1Sp=1T8T3UXkb.jpeg)
進而有
![f[0] = a[i - 1] \times c \times f[i] + a[i - 1] \times d + b[i - 1] \\ a[i] = a[i - 1] \times c \\ b[i] = a[i - 1] \times d + b[i -1] \\](https://img.heatask.com/upload/website_attach/+KxKR5+rc4f2dvJE+JQ9e2kv+sc911VWKhPKjceD36B=eBv46NZy0Pk2VgrM2HQLeBX6E3zGcELwJxbP7sV5-u-qKcyvq1MLpCbmS4mAhzIqZRXsSJYAzkT8rVw2q1EFhOpZkj6GdEP0RyFNPPz4eZ4D6j8yqPUhwlA=xVggiELsK_ONPP-MnwYErVymq1EFhOpZxVgOw4PyRyAT6NZyeUl=8QmMh-QLpCbmS4mAhzIqYiFNPP0AzkH8+TC6wMkFhOwbxV4OwK0=NVpm7s4M0Uk2VgrMh-N3+hvMRjLaw4PPQRA-6NZyeUl=4kC6xBsFhO2M3X+Bi.jpeg)
由於
![f[0] = a[n] \times f[n] + b[n]](https://img.heatask.com/upload/website_attach/HVnyiXwtwaNezI1K4aGFAe8jE+U-Oitv2=XygD-R8h7ngrhas=lZxG8z2mfwPg0Sm2rztVawqn6xjl9q3bKUFPzEF5uh6PaIZ57ET5zYhgvnLEvKs=lVG.jpeg)
且
![f[n] = 0](https://img.heatask.com/upload/website_attach/9CGNmCC3VrQeAZO+Ck9TGk1IFOxISdl5mpINLpAgMYmnBJaXy4vrHM1c3wIKTb2QFUdQ9.jpeg)
，因此
![b[n]](https://img.heatask.com/upload/website_attach/Iuw42jhFNcyh6U2=K46O4_Wxet2w4R9p6dO400zwb_p-7aiRoWHe56WSxhBxf.jpeg)
就是最終的答案。
程式碼
#include
using namespace std；
typedef long long ll；
const ll P = 998244353；
ll qpow（ll a， ll n） {
ll res = 1；
while（n） {
if（n & 1） res = res * a % P；
a = a * a % P；
n >>= 1；
}
return res；
}
ll inv（ll x） {
return qpow（x， P - 2）；
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
int n；
cin >> n；
vector
for（int i = 1； i <= n； i++） {
ll x， y；
cin >> x >> y；
p［i］ = x * inv（y） % P；
}
vector
a［0］ = 1， b［0］ = 0；
for（int i = 1； i <= n； i++） {
ll c = （1 - p［i］） * inv（（1 - p［i］ * a［i - 1］） % P） % P；
ll d = （1 + p［i］ * b［i - 1］） % P * inv（（1 - p［i］ * a［i - 1］） % P） % P；
a［i］ = （a［i - 1］ * c % P + P） % P；
b［i］ = （（a［i - 1］ * d + b［i - 1］） % P + P） % P；
}
cout << b［n］ << ‘\n’；
return 0；
}
F題 青蛙過河
題面
做法
感謝評論區老哥指正原錯誤表述
先思考題意，考慮過河的一條路徑，發現如果一條路徑能過河，那麼同樣也可以從這條路徑從河對岸過來。因此轉化題意為：找到 2x 條過河路徑。
什麼是過河路徑呢？相當於是 {p1， p2， p3， p4。。。pk} 這樣一個位置序列，任意相鄰的 pi 距離小於等於小青蛙的跳躍能力。每次選擇這樣的一條路徑，相應位置上的 h［i］ 減去1。對於一個跳躍能力 k，如果能選出 2x 條路徑，那麼就說明有解。
使用二分答案的方法。很顯然這裡 k 越大越有能力“能完成題目所要求的事情”，因此二分是正確的，對小青蛙的跳躍能力 k 二分。
對於一個小青蛙的跳躍能力 k，如何判定呢？這個東西可以看成一個網路流模型（但我們並不採用【流】的演算法去求解它），0 位置是源點，n 位置是匯點，詢問最大流量。
考慮到本題的特殊性質，我使用了貪心演算法去模擬這樣一個流的過程。我也說不清我是怎麼實現的，直接看程式碼吧。（也許我的實現是錯的吧）
程式碼
#include
using namespace std；
typedef long long ll；
const ll INF = （ll）2e9；
int n；
ll x；
vector
bool check（int jump） {
ll cnt = 0；
vector
for（int i = 0； i < n； i++） h［i］ = H［i］；
h［n］ = h［0］；
queue
Q。push（make_pair（h［0］， 0））；
for（int i = 1； i <= n； i++） {
while（！Q。empty（） && i - Q。front（）。second > jump） Q。pop（）；
int now = 0；
while（！Q。empty（） && now < h［i］） {
int v = min（Q。front（）。first， h［i］ - now）；
now += v；
Q。front（）。first -= v；
if（Q。front（）。first == 0） Q。pop（）；
}
Q。push（make_pair（now， i））；
if（i == n） cnt = now；
}
return cnt >= 2 * x；
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
cin >> n >> x；
H。resize（n）；
H［0］ = INF；
for（int i = 1； i < n； i++） {
cin >> H［i］；
}
int l = 1， r = n；
while（l < r） {
int mid = （l + r） / 2；
if（check（mid）） r = mid；
else l = mid + 1；
}
cout << l << ‘\n’；
return 0；
}
G題 最長不下降子序列
題面
做法
考慮如果我們把一段區間修改成一個相同的數字，會修改成什麼樣的數字？
對於每個 i，我們把它右邊 ［i + 1， i + k］ 範圍內全部修改成 a［i］，這樣一定比把這段區間 ［i + 1， i + k］修改成其他數字更優（嚴格來說應該是不劣）。
那麼修改後的最長非降子序列長度 = 以 i 為結尾的最長非降子序列長度 + 在 i + k 位置，暫時把 a［i + k］ 改成 a［i］ 後，以 i + k 位置為起點的最長非降子序列長度 + （k - 1）。我們把每個位置 i 的結果算出來，取 max 即可。
我們稱前者為 f［i］， 後者為 g［i］［j］（g［i + k］［a［i］］）。二者都可以用線段樹維護，具體看程式碼（我說不清楚我是怎麼做的）。
程式碼
感謝評論老哥提供的 hack 資料，以下是也許修復了錯誤的程式碼
#include
using namespace std；
const int N = （int）1e5；
int st［（N + 5） << 2］；
void init（int i， int tl， int tr） {
st［i］ = 0；
if（tl == tr） return；
int mid = （tl + tr） >> 1；
init（i << 1， tl， mid）；
init（i << 1 | 1， mid + 1， tr）；
}
void pull（int i） {
st［i］ = max（st［i << 1］， st［i << 1 | 1］）；
}
void upd（int i， int tl， int tr， int p， int v） {
if（tl == tr） {
st［i］ = max（st［i］， v）；
return；
}
int mid = （tl + tr） >> 1；
if（mid >= p） upd（i << 1， tl， mid， p， v）；
else upd（i << 1 | 1， mid + 1， tr， p， v）；
pull（i）；
}
int qry（int i， int tl， int tr， int l， int r） {
if（tl >= l && tr <= r） {
return st［i］；
}
int mid = （tl + tr） >> 1；
if（mid >= r） {
return qry（i << 1， tl， mid， l， r）；
} else if（mid + 1 <= l） {
return qry（i << 1 | 1， mid + 1， tr， l， r）；
} else {
return max（qry（i << 1， tl， mid， l， r）， qry（i << 1 | 1， mid + 1， tr， l， r））；
}
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
int n， k；
cin >> n >> k；
vector
map
vector
for（int i = 0； i < n； i++） {
cin >> a［i］；
b［i］ = a［i］；
}
sort（b。begin（）， b。end（））；
b。erase（unique（b。begin（）， b。end（））， b。end（））；
for（int i = 0； i < n； i++） {
a［i］ = lower_bound（b。begin（）， b。end（）， a［i］） - b。begin（）；
}
init（1， 0， n）；
for（int i = 0； i < n； i++） {
f［i］ = qry（1， 0， n， 0， a［i］） + 1；
upd（1， 0， n， a［i］， f［i］）；
int r = min（n - 1， i + k）；
gv［r］。push_back（a［i］）；
}
init（1， 0， n）；
int ans = 0；
for（int i = n - 1； i >= 0； i——） {
//
if（i == k - 1） {
ans = max（ans， qry（1， 0， n， 0， n） + k）；
}
//
for（auto v ： gv［i］） {
g［make_pair（i， v）］ = qry（1， 0， n， v， n） + 1；
}
invf［i］ = qry（1， 0， n， a［i］， n） + 1；
upd（1， 0， n， a［i］， invf［i］）；
}
for（int i = 0； i < n； i++） {
int r = min（n - 1， i + k）；
ans = max（ans， f［i］ + g［make_pair（r， a［i］）］ + r - i - 1）；
}
cout << ans << ‘\n’；
return 0；
}
H題 掃描遊戲
題面
做法
對每個物品極角排序，棒的長度足夠碰到的物品丟進 set ，然後使用 lower_bound 找到離棒最近的一個元素。
這題就是需要讓我們模擬一下這個過程，但是我賽場上看錯題了，看成了棒逆時針旋轉，得知是順時針旋轉後，非常痛苦。
因為不太會計算幾何，我的程式碼寫得非常混亂非常醜陋，感覺把方向改一改是對的，不過我也不確定有沒有其他 bug。
程式碼
#include
using namespace std；
typedef long long ll；
inline int to（ll x， ll y） {
if（y > 0 || （x > 0 && y == 0）） return 0；
else return 1；
}
struct Point {
ll x， y， z， id；
bool operator<（const Point& P2） const {
if（x * P2。y - P2。x * y == 0） return id < P2。id；
else return x * P2。y - P2。x * y > 0；
}
bool operator==（const Point& P2） const {
return x * P2。y - P2。x * y == 0 && id == P2。id；
}
}；
bool cmp（Point A， Point B） {
return A。x * A。x + A。y * A。y > B。x * B。x + B。y * B。y；
}
int cross（Point A， Point B） {
return A。x * B。y - B。x * A。y；
}
bool sameRank（Point A， Point B） {
return to（A。x， A。y） == to（B。x， B。y） && cross（A， B） == 0；
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
int n， rank = 0， add = 0；
ll L；
cin >> n >> L；
ll nowx = 0， nowy = L；
vector
vector
set
for（int i = 0； i < n； i++） {
Point pnt；
cin >> pnt。x >> pnt。y >> pnt。z；
pnt。id = i；
if（pnt。x == 0 && pnt。y == 0） {
if（rank == 0） rank = 1， add = 0；
else add += 1；
res［i］ = rank；
L += pnt。z；
// ！！！
pnt。y = L；
solved。push_back（pnt）；
} else {
p［to（pnt。x， pnt。y）］。push_back（pnt）；
}
}
rank += add；
add = 0；
sort（p［0］。begin（）， p［0］。end（）， cmp）；
sort（p［1］。begin（）， p［1］。end（）， cmp）；
bool tag；
do {
tag = false；
while（！p［0］。empty（）） {
if（L * L >= p［0］。back（）。x * p［0］。back（）。x + p［0］。back（）。y * p［0］。back（）。y） {
s［0］。insert（p［0］。back（））；
p［0］。pop_back（）；
} else {
break；
}
}
while（！p［1］。empty（）） {
if（L * L >= p［1］。back（）。x * p［1］。back（）。x + p［1］。back（）。y * p［1］。back（）。y） {
s［1］。insert（p［1］。back（））；
p［1］。pop_back（）；
} else {
break；
}
}
int nowP = to（nowx， nowy）；
Point tmp；
tmp。x = nowx， tmp。y = nowy， tmp。z = -1， tmp。id = -1；
auto nxt = s［nowP］。lower_bound（tmp）；
if（nxt ！= s［nowP］。end（）） {
if（solved。empty（） || ！sameRank（*nxt， solved。back（））） {
rank += add + 1；
add = 0；
} else {
add += 1；
}
solved。push_back（*nxt）；
res［nxt->id］ = rank；
L += nxt->z；
nowx = nxt->x， nowy = nxt->y；
s［nowP］。erase（nxt）；
tag = true；
} else {
if（nowP == 0） {
tmp。x = -1， tmp。y = 0；
} else {
tmp。x = 1， tmp。y = 0；
}
nowP ^= 1；
auto qwq = s［nowP］。lower_bound（tmp）；
if（qwq ！= s［nowP］。end（）） {
if（solved。empty（） || ！sameRank（*qwq， solved。back（））） {
rank += add + 1；
add = 0；
} else {
add += 1；
}
solved。push_back（*qwq）；
res［qwq->id］ = rank；
L += qwq->z；
nowx = qwq->x， nowy = qwq->y；
s［nowP］。erase（qwq）；
tag = true；
} else {
if（nowP == 0） {
tmp。x = -1， tmp。y = 0；
} else {
tmp。x = 1， tmp。y = 0；
}
nowP ^= 1；
auto tvt = s［nowP］。lower_bound（tmp）；
if（tvt ！= s［nowP］。end（）） {
if（solved。empty（） || ！sameRank（*tvt， solved。back（））） {
rank += add + 1；
add = 0；
} else {
add += 1；
}
solved。push_back（*tvt）；
res［tvt->id］ = rank；
L += tvt->z；
nowx = tvt->x， nowy = tvt->y；
s［nowP］。erase（tvt）；
tag = true；
}
}
}
}while（tag）；
for（int i = 0； i < n； i++） {
cout << res［i］ << ‘ ’；
}
return 0；
}
I題 數的拆分
題面
做法
思考後發現，取 y1 = 2，y2 = 3，足夠表示所有情況了。問題轉變為 n 能否被表示為一個平方數和一個立方數的乘積。
對於單個數字。列舉 1e18 以內所有的立方數（只有 1e6 個），如果它（稱為 p）能夠整除 n ，且n/p 是一個平方數，那麼答案是 yes。
這樣我們能夠在 1e6 規模的運算次數後算出一個 n 的答案，進一步考慮最佳化。若 n 能夠被表示為一個平方數和一個立方數的乘積，則這個立方數和平方數，必然有一個小於
。也就是說列舉立方數只需要列舉到 1e3，列舉平方數需要列舉到 4e4 這樣子就足夠了。
然後我就不會做了，我只做了 30％ 的部分分數。
// 歷史版本（錯誤的說法，使用Pollard-Rho演算法的時間複雜度是不對的）：
據說使用一些質因數分解演算法可以解決這道題。
分解質因數 - OI Wiki
// 歷史版本
// 學完正解後的版本：
歷史版本假了，在瞎說。
正解在這個回答下有人已經說清楚了。
// 學完正解後的版本
部分分程式碼
#include
using namespace std；
typedef long long ll；
bool check2（ll x） {
ll v = sqrt（x）；
if（（v + 1） * （v + 1） <= x） v += 1；
if（v * v > x） v -= 1；
return v * v == x；
}
const ll N = （ll）1e6；
ll num［N + 5］， sq［N + 5］；
bool check3（ll x） {
ll v = lower_bound（num + 1， num + N + 1， x） - num；
return num［v］ == x；
}
int main（） {
ios：：sync_with_stdio（false）；
cin。tie（0）；
cout。tie（0）；
for（ll i = 1； i <= N； i++） {
num［i］ = i * i * i；
sq［i］ = i * i；
}
int T；
cin >> T；
while（T——） {
ll n；
cin >> n；
bool tag = false；
ll z = sqrt（n） + 1；
for（int i = 1； num［i］ <= z； i++） {
if（n % num［i］ == 0 && check2（n / num［i］）） {
tag = true；
break；
}
}
if（！tag） {
for（int i = 1； sq［i］ <= z； i++） {
if（n % sq［i］ == 0 && check3（n / sq［i］）） {
tag = true；
break；
}
}
}
if（tag） cout << “yes\n”；
else cout << “no\n”；
}
return 0；
}
J題 推導部分和
題面
分析
不會做，聽說有一些和這個很像的題，不過賽場上沒時間做了，也沒有思考，也沒有做過原題，有空去補一補吧。。。
更新做法
E - Range Sums
在 atcoder 上有一道做法與本題一樣的題目。
令字首和陣列 sum［i］ 表示 a［1］ + a［2］ + 。。。 + a［i］ 的值。對於一個 ［l， r， s］，相當於給出了 sum［r］ - sum［l - 1］ = s 的資訊。建一個森林，每個 ［l， r ，s］ 相當於在點 l - 1 和點 r 之間連了一條表示 sum［r］ - sum［l - 1］ = s 的邊（程式碼實現上連兩條值互為相反數的有向邊更為合適）。
對於詢問 ［l， r］，有解當且僅當 r 與 l - 1 同一棵樹上時。對於每一棵樹，任意指定一個根節點，假設它（root）的值（sum［root］）為 0，從它開始 dfs 求出每個點（v）的值（sum［v］），這個過程透過預處理來實現。對於是否在同一棵樹上，可以用給每個節點染色的方式實現。
之後的每次詢問，只要判斷它們是否顏色相同，若相同則答案為 sum［r］ - sum［l - 1］，否則無解。
上一篇:新手會計如何提高自己的工作效率？
下一篇：大家有遇到過哪些奇葩的人嗎？
