2022牛客多校（四）

2022牛客多校（四）

一、比赛小结

比赛链接： "蔚来杯"2022牛客暑期多校训练营4

二、题目分析及解法（基础题） A、Task Computing

题目链接：A-Task Computing

题意：

从 n n n 个任务中选 m m m 个元素 ( a 1 , a 2 , … , a m ) (a_1, a_2, \dots , a_m) (a1​,a2​,…,am​) 出来并任意排序，收益是 ∑ i = 1 m ω a i ∏ j = 0 i − 1 p a j \displaystyle \sum_{i=1}^m\omega_{a_i}\prod_{j=0}^{i-1}p_{a_j} i=1∑m​ωai​​j=0∏i−1​paj​​ ,求最大收益

题解：

对于这个复杂的多元和式，我们先比较一下双元关系，我们考虑中间相邻的两个下标 x x x 和 y y y ：

R x = ∑ i = 1 x − 1 ω a i ∏ j = 0 i − 1 p a j + ω a x ∏ j = 0 x − 1 p a j + ω a y p a x ∏ j = 0 x − 1 p a j + ∑ i = y + 1 m ω a i ∏ j = 0 i − 1 p a j \displaystyle R_x=\sum_{i=1}^{x-1}\omega_{a_i}\prod_{j=0}^{i-1}p_{a_j} + \omega_{a_x}\prod_{j=0}^{x-1}p_{a_j}+\omega_{a_y}p_{a_x}\prod_{j=0}^{x-1}p_{a_j}+\sum_{i=y+1}^{m}\omega_{a_i}\prod_{j=0}^{i-1}p_{a_j} Rx​=i=1∑x−1​ωai​​j=0∏i−1​paj​​+ωax​​j=0∏x−1​paj​​+ωay​​pax​​j=0∏x−1​paj​​+i=y+1∑m​ωai​​j=0∏i−1​paj​​

R y = ∑ i = 1 x − 1 ω a i ∏ j = 0 i − 1 p a j + ω a y ∏ j = 0 x − 1 p a j + ω a x p a y ∏ j = 0 x − 1 p a j + ∑ i = y + 1 m ω a i ∏ j = 0 i − 1 p a j \displaystyle R_y=\sum_{i=1}^{x-1}\omega_{a_i}\prod_{j=0}^{i-1}p_{a_j} + \omega_{a_y}\prod_{j=0}^{x-1}p_{a_j}+\omega_{a_x}p_{a_y}\prod_{j=0}^{x-1}p_{a_j}+\sum_{i=y+1}^{m}\omega_{a_i}\prod_{j=0}^{i-1}p_{a_j} Ry​=i=1∑x−1​ωai​​j=0∏i−1​paj​​+ωay​​j=0∏x−1​paj​​+ωax​​pay​​j=0∏x−1​paj​​+i=y+1∑m​ωai​​j=0∏i−1​paj​​

那么对于最优解里，相邻的下标一定满足

R x − R y = ( ω a x + ω a y p a x − ω a y − ω a x p a y ) ∏ j = 0 x − 1 p a j ≥ 0 R_x-R_y=(\omega_{a_x}+\omega_{a_y}p_{a_x}-\omega_{a_y}-\omega_{a_x}p_{a_y})\prod_{j=0}^{x-1}p_{a_j}\ge 0 Rx​−Ry​=(ωax​​+ωay​​pax​​−ωay​​−ωax​​pay​​)∏j=0x−1​paj​​≥0

所以我们可以按照这个关系排个偏序，那么最终答案一定是这个偏序里的一个子序列，剩下的问题 dp 可以解决

设 d p i , j dp_{i,j} dpi,j​ 表示从后往前考虑了 i i i 个任务，选择了 j j j 个任务的最优收益，初始值 d p m + 1 , 0 = 0 dp_{m+1, 0}=0 dpm+1,0​=0 转移方程为： d p i , j = max ⁡ { d p i + 1 , j , d p i + 1 , j − 1 × p i + ω i } dp_{i,j}=\max \{ dp_{i+1,j},dp_{i+1,j-1}\times p_i+\omega_i\} dpi,j​=max{dpi+1,j​,dpi+1,j−1​×pi​+ωi​}

答案为 d p 1 , m dp_{1,m} dp1,m​

代码：

#include 
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct node {
  double w, p;
  bool operator a.w * (1 - p); }
} a[maxn];
int n, m;
double dp[maxn][25];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i > a[i].w;
  for (int i = 1; i > a[i].p, a[i].p /= 10000;
  sort(a + 1, a + 1 + n);
  memset(dp, -inf, sizeof dp);
  dp[n + 1][0] = 0;
  for (int i = n; i >= 1; i--) {
    dp[i][0] = 0;
    for (int j = 0; j  1, k = 0;
    do {
      i >>= 1;
      k >>= 1;
      if ((quickpow(x, i) * quickpow(b, k) + 1) % mod == 0) k += (mod - 1 >> 1);
    } while (i % 2 == 0);
    ans = quickpow(x, i + 1 >> 1) * quickpow(b, k >> 1) % mod;
  }
  if (ans * 2 > mod) ans = mod - ans;
  return ans;
}
// 蝴蝶变换
void change(ll* a, int len) {
  static int rev[maxn];
  rev[0] = 0;
  for (int i = 0; i > 1] >> 1);
    if (i & 1) rev[i] |= len >> 1;
  }
  for (int i = 0; i  INTT , O(nlogn)
void NTT(ll* a, int len, int flag) {
  change(a, len);
  for (int h = 2; h