Codeforces 1132D Stressful Training 题解
Codeforces 1132D Stressful Training 题解
题意
有$n$个学生打比赛,第$i$个学生的电脑的初始电量为$a_i$,每分钟使用的电量为$b_i$(即如果在一分钟的开始有$c$格电量,在下一分钟的开始,电量变为$c-b_i$)。整场比赛持续$k$分钟($1\le n\le 2\times10^5,1\le k\le 2\times10^5,1\le a_i\le 10^{12},1\le b_i\le 10^7$)。
在比赛的开始时有一个充电器。你可以选择充电器的输出电量$x$,$x$为一个非负整数,且以后不能更改。在每一分钟的开始,你可以把充电器插在任意一个学生的电脑上(如果一个电脑的用电量为$b_i$,插入了充电器后每分钟会消耗$b_i-x$格电)。每个学生的电脑的电量没有上限。充电器在一个时刻最多给一台电脑充电。
一个学生成功地完成比赛如果在比赛的过程中他的电脑的电量总是一个非负数。比赛结束时电脑的电量无关紧要。
输出充电器最小的输出电量,使得所有的学生都可以成功地完成比赛,或者输出$-1$表示不可能。
Codeforces 1249D Maximum Weight Subset 题解
Codeforces 1249D Maximum Weight Subset 题解
题意
给定一棵有$n$个结点的树和$k$,编号为$1\sim n$,结点$i$的权值为$a_i$ ($1\le n,k\le200,1\le a_i\le10^5$)。
现在请你选出一些节点,使得这些节点的权值和最大 并且 这些节点中任意两个节点的距离都$>k$。
并输出这个最大的权值。
Codeforces 903D Almost Difference 题解
Codeforces 903D Almost Difference 题解
题意
定义一个方程
给定一个有$n$个数的数组$a (1\le n\le2\times10^5,1\le a_i\le10^9)$,求出$\sum\limits_{1\le i\le j\le n}d(a_i,a_j)$。
Codeforces 337D Book of Evil 题解
Codeforces 337D Book of Evil 题解
题意
给定一个有$n$个结点的树,树上有$m (1\le m\le n\le10^5)$个结点被感染,分别是$p_1,p_2,\dots,p_m (1\le p_i\le n)$。
有一本“邪恶之书”在树上的某一个结点上,它可以感染 所有到它的距离小于等于$d (0\le d\le n-1)$的结点。
求“邪恶之书”可以在哪些结点上,使得它可以感染$p_1,p_2,\dots,p_m$这些结点。输出可能的个数。
Codeforces 587B Duff in Beach 题解
Codeforces 587B Duff in Beach 题解
题意
有一个长度为$n$的数组$a_0,a_1,\dots,a_{n-1}$和一个长度为$l$的数组$b_0,b_1,\dots,b_{l-1}$,其中$b$是由$a$得出的,满足$b_i=a_{i\bmod n}$。
给定$n,l,k (1\le n,k,n\times k\le10^6,1\le l\le10^{18})$,求子序列$b_{i_1},b_{i_2},\dots,b_{i_x}$满足以下条件的数量:
- $1\le x\le k$
- $\forall 1\le j\le x-1,\left\lfloor\frac{i_j}{n}\right\rfloor+1=\left\lfloor\frac{i_{j+1}}{n}\right\rfloor$
- $\forall 1\le j\le x-1,b_{i_j}\le b_{i_{j-1}}$,即这个子序列是非下降子序列。
输出这个数量模$10^9+7$。