zcmimi's blog
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}的利润

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

点击跳转

f[i][j]表示前i个数选了j个最多多少

f[i][j]=\max(f[i-1][j-1]+[a[i]=j],f[i-1][j]);

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
查看原题

点击跳转

详见四边形不等式优化

最小值有单调性,可以使用四边形不等式优化

但是最大值没有

但是最大值有个性质:

一定是一直把其他石子合并到某堆石子

那么我们可以f[l][r]=\max(f[l][r-1],f[l+1,r])+S_r-S_{l-1}

相当于一直向左边的石子合并或右边

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

点击跳转

47/74
Search
search