摘要:
【CF961G】Partitions 題意:給出n個物品,每個物品有一個權值$w_i$,定義一個集合$S$的權值為$W(S)=|S|\sum\limits_{x\in S} w_x$,定義一個劃分的權值為$V(R)=\sum\limits_{S\in R} W(S)$。求將n個物品劃分成k個集合的所
閱讀全文
摘要:
【CF613D】Kingdom and its Cities 題意:給你一棵樹,每次詢問給出k個關鍵點,問做多干掉多少個非關鍵點才能使得所有關鍵點兩兩不連通。 $n,\sum k\le 10^5$ 題解:刷虛樹板子啦! 首先如果兩個關鍵點相鄰則無解。然后建出虛樹,進行樹形DP。設f[i]表示i子樹中
閱讀全文
摘要:
【CF429E】Points and Segments 題意:給你數軸上的n條線段$[l_i,r_i]$,你要給每條線段確定一個權值+1/-1,使得:對于數軸上的任一個點,所有包含它的線段的權值和只能是+1,-1或0。 $n\le 10^5$ 題解:首先,我們用掃描線,整個數軸被分成若干個小區間。對
閱讀全文
摘要:
【CF434D】Nanami's Power Plant 題意:有n個二次函數$y=a_ix^2+b_ix+c_i$($a_i,b_i,c_i$是整數),第i個函數要求x的取值在$[l_i,r_i]$之間且為整數。你需要確定每個函數的x的取值,使得所有函數的函數值之和最大。還有m個限制,每條限制形如
閱讀全文
摘要:
【CF434E】Furukawa Nagisa's Tree 題意:一棵n個點的樹,點有點權。定義$G(a,b)$表示:我們將樹上從a走到b經過的點都拿出來,設這些點的點權分別為$z_0,z_1...z_{l-1}$,則$G(a,b)=z_0+z_1k^1+z_2k^2+...+z_{l-1}k^{
閱讀全文
摘要:
【CF446D】DZY Loves Games 題意:一張n個點m條邊的無向圖,其中某些點是黑點,1號點一定不是黑點,n號點一定是黑點。問從1開始走,每次隨機選擇一個相鄰的點走過去,經過恰好k個黑點到達n的概率。 $n\le 500,m\le 500000,k\le 10^9$,黑點個數不超過100
閱讀全文