zcmimi's blog

categories/刷题记录/共658篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分最大值,然后树型dp

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_{i=1}^k a_i = x^x \mod 1000 (a_i \in \N^*)

\because 总和一定为x^x \mod 1000,并且分为k个数,

n = x^x \mod 1000

这样相当于在n-1个空位中插k-1块隔板

\therefore ans = C(n-1,k-1)

\because k \le 100,n\le 1000

\therefore我们用杨辉三角(用滚动数组,否则可能re)就可以了,但是要高精度

当然如果直接计算组合数更快

杨辉三角版:

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

就bfs

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一定是我做题太少了

看不出这是个最小割

我们将每个人看成一个点,然后如下建边:

  1. 源点向每个人连流量为其总收益的边(\sum_{j=1}^n E_{i,j})

  2. 每个人向汇点连流量为其花费的边

  3. ij连流量为E_{i,j} \times 2的边

然后用所有能赚到的利润减去最小花费就可以了

第三条,如果两个人都选,可以获得E_{i,j}的利润

如果有一个不选,会亏损E_{i,j}的利润

39/66
Search
search