首页 > 其他分享 >CF573E Bear and Bowling 题解

CF573E Bear and Bowling 题解

时间:2024-08-06 21:29:41浏览次数:12  
标签:ch frac int 题解 Bear cdot int64 tot CF573E

Description

  • 给定一个长度为 \(n\) 的序列 \(a_{1\dots n}\)。
  • 你要求一个 \(a\) 的子序列 \(b_{1\dots m}\)(可以为空),使得 \(\sum_{i=1}^m ib_i\) 的值最大。
  • \(n \le 10^5\),\(|a_i| \le 10^7\)。

Solution

有一个显然的 dp 是设 \(f_{i,j}\) 表示前 \(i\) 个数,选 \(j\) 个数的最大值,转移即为:\(f_{i,j}=\max\left\{f_{i-1,j},f_{i-1,j-1}+j\cdot a_i\right\}\),由于这题时限很大并且 \(n\) 很小,所以这个能过。。。

考虑优化。

有一个结论是对于每个 \(i\),都存在一个分界点 \(k_i\),使得对于 \(\forall j<k_i\),\(f_{i,j}=f_{i-1,j}\),对于 \(j\geq k_i\),\(f_{i,j}=f_{i-1,j-1}+j\cdot a_i\)。

证明就考虑设 \(g_{i,j}=f_{i,j}-f_{i,j-1}\),那么 \(f_{i,j}=f_{i-1,j}\) 的充分必要条件为 \(f_{i-1,j}\geq f_{i-1,j-1}+j\cdot a_i\),即 \(\frac{g_{i-1,j}}{j}\geq a_i\)。

通过观察可以发现 \(\frac{g_{i,j}}{j}\) 对于 \(j\) 单调不增,那么不妨假设 \(\frac{g_{i-1,j}}{j}\) 单调不增,考虑归纳证明 \(g_i\) 也满足条件。

设 \(k\) 为满足 \(\frac{g_{i-1,j}}{j}<a_i\) 的最小的 \(j\),则对于 \(j\in [0,k-1]\),\(g_{i,j}=g_{i-1,j}\)。同时 \(g_{i,k}\) 变为 \(k\cdot a_i\),所以 \(\frac{g_{i,k}}{k}=a_i\leq \frac{g_{i,k-1}}{k-1}\)。

对于 \(j>k\),\(g_{i,j}=g_{i-1,j-1}+a_i\),所以对于 \(j>k\) 满足 \(\frac{g_{i,j}}{j}\geq \frac{g_{i,j+1}}{j+1}\) 的条件为:

\[\begin{aligned} \frac{g_{i-1,j-1}+a_i}{j}&\geq\frac{g_{i-1,j}+a_i}{j+1}\\ g_{i-1,j-1}&\geq\frac{j}{j+1}\cdot g_{i-1,j}-\frac{1}{j+1}\cdot a_i\\ g_{i-1,j-1}-\left(\frac{j}{j+1}\cdot g_{i-1,j}-\frac{1}{j+1}\cdot a_i\right)&\geq 0\\ \end{aligned} \]

又因为:

\[\begin{aligned} LHS\geq&\frac{j-1}{j}\cdot g_{i-1,j}-\frac{j}{j+1}\cdot g_{i-1,j}+\frac{1}{j+1}\cdot a_i\\ =&\frac{j\cdot a_i-g_{i-1,j}}{j(j+1)}\\ \geq& 0 \end{aligned} \]

所以结论得证。

然后就可以从前往后枚举 \(a_i\),维护 \(g\) 数组,每次相当于是在某个位置插入和将某个后缀区间加某个数,并且需要快速找到分界点,可以用平衡树维护。

时间复杂度:\(O(n\log n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n;
int64_t a[kMaxN];

struct FHQTreap {
  int tot = 0, rt, ch[kMaxN][2], rd[kMaxN], sz[kMaxN];
  int64_t val[kMaxN], rnk[kMaxN], tag1[kMaxN], tag2[kMaxN];
  std::mt19937 rnd;

  int newnode(int64_t x, int64_t y) {
    val[++tot] = x, rnk[tot] = y;
    ch[tot][0] = ch[tot][1] = tag1[tot] = tag2[tot] = 0, rd[tot] = rnd();
    sz[tot] = 1;
    return tot;
  }

  FHQTreap() {
    tot = 0, rnd.seed(std::random_device{}());
    rt = newnode(-1e18, 1);
  }

  void pushup(int x) {
    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
  }

  void addtag(int x, int64_t v1, int64_t v2) {
    val[x] += v1, rnk[x] += v2, tag1[x] += v1, tag2[x] += v2;
  }

  void pushdown(int x) {
    if (ch[x][0]) addtag(ch[x][0], tag1[x], tag2[x]);
    if (ch[x][1]) addtag(ch[x][1], tag1[x], tag2[x]);
    tag1[x] = tag2[x] = 0;
  }

  int merge(int x, int y) {
    if (!x || !y) return x + y;
    pushdown(x), pushdown(y);
    if (rd[x] < rd[y]) {
      ch[x][1] = merge(ch[x][1], y), pushup(x);
      return x;
    } else {
      ch[y][0] = merge(x, ch[y][0]), pushup(y);
      return y;
    }
  }

  void split(int x, int v, int &a, int &b) { // a : >= v, b : < v
    if (!x) return void(a = b = 0);
    pushdown(x);
    if (val[x] >= rnk[x] * v) {
      a = x, split(ch[x][1], v, ch[a][1], b);
    } else {
      b = x, split(ch[x][0], v, a, ch[b][0]);
    }
    pushup(x);
  }

  void ins(int64_t x) {
    int a, b;
    split(rt, x, a, b);
    if (b) addtag(b, x, 1);
    rt = merge(merge(a, newnode(x * (sz[a] + 1), sz[a] + 1)), b);
  }

  int64_t getval(int x) {
    if (!x) return 0;
    pushdown(x);
    int64_t ret = std::max<int64_t>(val[x], 0);
    return ret + getval(ch[x][0]) + getval(ch[x][1]);
  }
} t;

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    t.ins(a[i]);
  }
  std::cout << t.getval(t.rt) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:ch,frac,int,题解,Bear,cdot,int64,tot,CF573E
From: https://www.cnblogs.com/Scarab/p/18346015

相关文章

  • CF1920D题解
    题面这里不再赘述了,直接搬个链接。InLuoguInCodeforces思路存储一共两种操作:要么在末尾加一个数xxx,要么把整一段复制......
  • NSSCTF靶场题解(6)
    站在小白的视角上,写了在写题目的wp方面更多是想体现题目思考的逻辑和细节,更多是写给同样新手小白的内容,解题方面为什么从这一步到下一步的,很助于培养思考题目的逻辑思维,尽我所能把细节阐释到位,有些地方可能理解说辞不是特别到位,如果有问题就麻烦各位大佬师傅指点~这次题解库收......
  • 题解:CF257C View Angle
    题目传送门题意平面上有\(n\)个点。从原点引出两条射线,将平面分成两个部分,使其中一个部分覆盖所有的点。求这个部分与原点所夹的角的最小度数。思路既然一个部分覆盖了所有的点,那么另一个部分就一个点都没覆盖,那么要让这个部分最优,这两条射线一定经过两个中间没有任何点的点......
  • 【题解】暑假集训CSP提高模拟14
    目录Rank&挂分A.BA题目内容部分分10pts10+20pts正解思路代码B.BB题目内容部分分5pts正解思路代码C.BCD.BDRank&挂分T4暴搜后来改了记搜,不知道哪里锅了,挂5pts。A.BA题目内容现在有\(m\)块烙板,\(n\)张饼,第\(i\)张饼需要烙\(a_i\)个单位时间,一张饼一个单位时刻只能......
  • 2024MX-MF-DAY1-text题解
    T1【题目描述】有\(n\)个人按编号从\(1\)到\(n\)坐成一圈,即第\(i\in[1,n]\)个人右边是\(i+1\),第\(n\)个人右边的人是\(1\)。初始,每个人手上有\(m\)个球。随后,\(n\)个人按编号从小到大的顺序依次执行如下操作:把自己手中的球分成数量相同且尽可能多的三份,......
  • AkSoundSeedAir.dll修复指南:游戏音频问题解决与预防技巧
    AkSoundSeedAir.dll是一个与声音引擎相关的动态链接库(DynamicLinkLibrary,简称DLL)文件,尤其与Wwise(AudiokineticWwise)声音设计和游戏音效中间件有关。Wwise是一个广泛应用于游戏开发的声音引擎,用于处理游戏中的音频和音效,AkSoundSeedAir.dll就是Wwise的一部分,用于实现声音处理......
  • 花园改造 题解
    题目id:9989题目描述小\(X\)开始改造她的环形的花园了,具体来说她要在花园的环上种满\(n\)棵树。她现在有\(3\)种树:种子、小树苗和大树。每个位置上种不同的树会产生不同的满意度,具体来说在第\(i\)个位置,种种子会产生\(a_i\)的满意度,种小树苗会产生\(b_i\)的满意度,种大树会产生\(c......
  • [AGC005B] Minimum Sum 题解
    题目传送门看到这道题很多人用单调栈,其实用笛卡尔树本质差不多,但是思维难度更小。不知道笛卡尔树的同学可以看这里简单说来,笛卡尔树的一个子树可以代表一个区间,且左子树上点的下标小于根节点,右子树上点的坐标大于根节点。这道题要求所有子区间的\(\texttt{min}\)值之和,其实......
  • 迟钝的舞会 题解
    题目id:1329题目描述牛是公认的笨拙的舞者。然后,约翰发现富有音乐细胞的母牛能产更多的奶。因此,他把他的整圈的牛都拉进了舞蹈培训班,包括所有的公牛(因为跳舞的时候得一男一女-_-)。这些牛正好有\(n\)头是公的,有\(n\)头是母的。在第一堂课开始之前,舞蹈老师想将他们分成一对一对的(......
  • 08-04 题解
    08-03题解A根据题目的提示,发现所有数的积是不变的(\(gcd(a,b)*lcm(a,b)=a*b\)),所以差大和大简易证明设\(g=gcd(a,b)\),则\(a=a'g,\)\(b=b'g\),\(lcm(a,b)=a'b'g\)\(gcd(a,b)+lcm(a,b)=g(1+a'b')\)\(a+b=g(a'......