ICPC2020小米網絡選拔賽第一場復盤

第一次組隊打ICPC，可能任務分配上還有待優化

但是有個團隊，感覺安心好多。

我們有三個人，開始是分開來，每人看三題

djn看ABC，jyf看DEF，我看GHI，JK沒人看

我開始只來得及看了GH，但是發現都不太可做

【G - Tree】

給出兩個長為n的序列

構造一顆無根樹，滿足第一個序列為樹的拓撲序，第二個序列為樹的先中后序遍歷。

輸出一種可能的建樹方案，無法構造輸出NO

序列n長度<2e5

【H-Grouping】

給出一個數字n，2n個整數。

將其隨機分為n組，每組兩個數。將兩個數作差得到n個權重，求n個權重的方差得到一個w值。

不同分組方式的w值取平均對998244353取模得到答案.

大約過了半小時

好多隊伍ak了，簽到題出來了

CI，DJK都是過了500多個隊伍的

甚至ABF都過了200多個隊伍

先是djn跟我說C很簡單，我開始調C（她看了A和C,B沒看完）

【C-Smart】

給出一個字符串

統計有多少組連著的w，計算個數

因為題意看錯了，字符串可以隨機，WA了兩次才過掉

然后jyf跟我說I題暴力超時了，然后開始做I題

他看了D和E，F沒看

【I-Walking】

給出一個矩陣，每個點只能向特定方向走一步

求多少個點能走出矩陣

很簡單就是一個剪枝，從邊界開始向內枚舉，每次打標記O（mn）就行了

但是開始constCE了一次，后來stringRE了一次。

【D-Router】

給出n個點m條邊的無向圖，求每次刪除點i后剩余的圖分為幾個聯通塊。n<3e5

第一個想法是并查集，每次除了有i的邊都合并，但是很明顯TLE了。

然后發現可以最開始統計有幾個集合，然后每次刪除與i相連的邊，判斷哪些點在環上就不增加，否則增加一個強連通分量。然而tarjan打不來，沒寫出來。

【J-Matrix】

給出一個nm的矩陣，每次選一個ab的子矩陣減1，判斷能否讓原矩陣全部為0，nm<1e6

二維差分可以O(1)計算子矩陣的和，然后去枚舉就行了？

【F-Design】

一直沒看到題面，但是好像A了好多人

快結束的時候，才看到的A題

【A-Intelligent】

給出一個序列，選出一個無序子集，讓里面的數互為倍數，求最大的子集，n的范圍2e5

就還是用dp 數組排序之后dp[i]=max(dp[i的因數]+1，dp[i / i的因數]+1）因數枚舉到根號i

【B-Robot】

沒看題

【E-Network】

沒看題

【K-Sqrt】

沒看題

一共11題，4題沒看，2題看了個寂寞，看的5題里面過了4題樣例，2個AC。

網絡

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。