Joint examination of six provinces 2017

Sushi restaurant

Maximum weighted closed subgraph

Because the weight of each point is calculated only once , Consider transforming it into a graph

Map each section [l,r] towards [l+1,r] And [l,r-1] Even the edge , The point weight is the interval delicious value , Every interval [i,i] The point weight is the interval delicious value -c, Finally, each kind of sushi is connected to the point representing this kind of sushi , The point is m*id^2

In this picture , Selected a point , We must choose the successor of this point , Maximize point weight

Is the maximal weighted closed subgraph

Connect the punctual weight node with S Connecting edges means selecting this point , Negative point weight node and T Edge building means that this point is not selected , In order to meet the conditions, we need to let S,T Disconnected , The minimum cut is enough

final exam

Maintain the prefix and number of students at a certain time , Greater than the prefix sum of a certain time , Less than the prefix sum of a certain time , Enumeration is enough

Combinatorial number problem

all ik+r stay modk Congruence in the sense of , Therefore, it is considered that f[i][j] Express election i Items in modk The remainder is j The answer

Every time you choose or not , so

Matrix optimization times recursion can

  Meeting is greeting

1. Extend Euler's theorem

The establishment condition is k>m

2. Power of light speed

In index a And modulus mod In the same case , Let the maximum modulus be b, Preprocessing a Of 1-√b Result of the power , In pretreatment k*√b（k<=√b) Result , You can find it directly every time

seek

You know , The maximum number of changes per location √mod Time , Because after that mod=1 The following result is 0, Save this √mod The second answer

It is found that the base number is c, But the modulus will change , But the number of modules is very small , Preprocess the power of light speed of each module , You can query directly every time

Segment tree is used to maintain interval and , Every time you make a change, make a violent change to every point , Because there will be no edge after a certain number of modifications

Break up is a wish

probability dp, Find the best pull x This state can represent all situations of playing , Order dp[x] Indicates the optimal pull x After the second pull

Yes    , It means if you choose the right , The minimum number of times is x-1, otherwise x+1

Make x=n, Yes

Therefore, the difference between the two maintenance items is found , Make del[i]=dp[i]-dp[i-1]

And found that del You can deduce

So because dp[k]=k,dp It can also be deduced

​​​​​​