链接

https://ac.nowcoder.com/acm/contest/9985/B

题意

给定 $n,m$，定义一种序列，构造方法如下：

1. 在 $[1,n]$ 中任意选择 $m$ 次，得到了 $m$ 个整数（显然数字可能相同）;
2. 将选出的 $m$ 个数字排序之后得到一个序列 $a_1,a_2,\dots ,a_m$

定义一个序列的贡献为 $max{a}_1,a_2,\dots ,a_m-min{a}_1,a_2,\dots ,a_m$，求所有不同的序列的贡献和。

链接

https://ac.nowcoder.com/acm/contest/12606/I

题意

记 $d_{u,v}$ 为节点 $u$ 到节点 $v$ 的最短距离，$t_u$ 为节点 $u$ 的权值，对树上任意节点 $u$ 求 $\sum _{v=1}^n[d_{u,v}\ast (t_u+t_v)]$。

链接

https://loj.ac/p/6010

题意

给定一个由 $n$ 行数字组成的数字梯形如下方所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

1. 从梯形的顶至底的 $m$ 条路径互不相交；
2. 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交；
3. 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

按照规则 $1$，规则 $2$，和规则 $3$ 计算出的最大数字总和并输出，每行一个最大总和。

链接

https://loj.ac/p/6122

题意

给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。

除起点城市外，任何城市只能访问一次。

对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。

链接

https://ac.nowcoder.com/acm/contest/9986/H

题意

有一张 $n$ 个点 $m$ 条边的图，每条边连接点 $u_i,v_i$，边权为 $w_i$。他想进行 $q$ 次操作，有如下两种类型：

1. 修改第 $x$ 条边为连接点 $y,z$，边权为 $t$；
2. 查询只用编号在 $[l,r]$ 范围内的边，得到的最小生成树权值是多少。

数据范围：

$1\le n\le 200,1\le m\le 30000,1\le q\le 30000,1\le u_i,v_i\le n,1\le w_i\le 100000$。

$1\le x\le m,1\le y,z\le n,1\le t\le 100000$。

链接

https://atcoder.jp/contests/abc194/tasks/abc194_e

题意

定义 $mex(x_1,x_2,\dots ,x_k)$ 为在 $x_1,x_2,\dots ,x_k$ 中未出现的最小自然数。

求 $\underset{i=0}{\overset{n-m}{min}}[mex(a_{i+1},a_{i+2},\dots ,a_{i+m})]$。

数据范围：

• $0\le m\le n\le 1.5\ast {10}^6$
• $0\le a_i<n$

链接

https://atcoder.jp/contests/abc194/tasks/abc194_f

题意

求 $1\sim n$ 中十六进制表示中严格有 $k$ 个不同的数（$0\sim 9,a\sim f$）的个数（不包含前导 $0$）。

链接

https://atcoder.jp/contests/abc145/tasks/abc145_f

题意

$n\ast m$ 的二维白色网格，$H_i$ 表示第 $i$ 列底端往上 $H_i$ 格需涂成黑色。

每次操作可以选择一段水平方向连续的网格涂黑。

现在可以至多改变 $k$ 列的 $H$ 值，求最小操作数使需涂黑的网格涂黑。

链接

https://ac.nowcoder.com/acm/contest/13168/G

题意

有 $n$ 篇文章，第 $i$ 篇文章中的概率为 $a_i$，定义 $i$ 篇文章中 $j$ 篇的生产指数为 $j^{j/i}$。

现在可以自己选择投哪几篇文章，求生产指数的最大期望。