2020.07.20【省選B組】模拟

T1：題解待更新

T2：首先p肯定全部分給流量最多的一條邊，是以現在就是求流量最多的一條邊的最小值。注意這個值可以是小數。

接下來我們先算出最大流，然後就可以二分答案，限制每一條邊的流量不能超過mid，在做一遍最大流。若最大流沒有發生改變則目前mid是合法的。這樣就做完這題了。

T3：首先可以想到把x軸和y軸分開考慮。

因為每一個數各個位置的乘積最終一定隻包含2、3、5、7這四個質因子，是以我們可以先把1~n中隻包含2、3、5、7質因子的數都篩選出來，這樣的數不多。

然後設num[i]表示各位乘積為i的數的個數，這個可以用數位dp求。設f[i][c2][c3][c5][c7][0/1]表示到第i位，2、3、5、7的指數分别為c2、c3、c5、c7，目前是否有頂到上限的方案數。轉移顯然。注意0和1的差別，具體做法就是在初始化的時候把所有長度的數字都考慮進去，然後在dp時強制下一位隻能填1~9即可。

再求出了num之後，我們下一步就是要求num[i]*num[j]的前k大。這個可以用堆來實作。首先我們把num[1]*num[1]、num[1]*num[2]……num[1]*num[s]都加入堆中，堆中的每一個元素還要記錄下num的兩個下标（設為f1、f2）。加下來操作k次，每次取出堆頂，然後将num[f1]*num[f2+1]加入堆中。至于為什麼這樣是對的，我們可以了解成我們固定了每一個num[f1]，然後要在所有num[f1]*num[f2]中選出最大值來。至此這題就做完了。