首页 > 其他分享 >CF1794C Scoring Subsequences题解

CF1794C Scoring Subsequences题解

时间:2023-05-14 14:35:36浏览次数:41  
标签:dots Scoring frac CF1794C 题解 times leq int include

文中 \(a\) 为题目中给的 \(a\)。

如果我们要求 \(a_1, a_2, a_3, \dots, a_m\) 的结果,

那么我们可以把 \(a\) 数组从后往前依次除以 \(i\),\(i\) 从 \(1\) 到 \(n\),

即为 \(\frac{a_1}{m},\frac{a_2}{m - 1},\frac{a_3}{m - 2},\dots,\frac{a_{m - 1}}{2},\frac{a_m}{1}\),并将其保存在数组 \(s\) 中。

因为 \(a_1 \leq a_2 \leq a_3 \leq \dots \leq a_m\),且 \(\frac{1}{i}\) 单调递增,所以 \(s_1 \leq s_2 \leq s_3 \dots \leq s_m\)。

那么我们自然而然地可以想到,每一次的结果就是末尾的几个数字的乘积(因为 \(s\) 越大越好),即 \(s_k \times s_{k + 1} \times \dots \times s_m\)。

那么 \(k\) 取多少呢?

我们只取对自己有利的部分,所以当 \(s_k \geq 1\) 且 \(s_{k - 1} < 1\) 时,我们可以达到最大值 \(ans = s_k \times s_{k + 1} \times \dots \times s_m\)。

因为 \(s\) 单调不下降,所以可以使用二分来得出要保留的数字 \(m - k\)。

对每一个 \(m\) 进行操作,\(1 \leq m \leq n\)。

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

C++代码

/*******************************
| Author:  SunnyYuan
| Problem: C. Scoring Subsequences
| Contest: Codeforces Round 856 (Div. 2)
| URL:     https://codeforc.es/contest/1794/problem/C
| When:    2023-03-06 08:30:32
| 
| Memory:  256 MB
| Time:    2500 ms
*******************************/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n, a[N];

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int i = 1; i <= n; i++) {
		int l = -1, r = i + 1;
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			if (a[i - mid + 1] >= mid) l = mid;
			else r = mid;
		}
		cout << l << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	while (T--) solve();

	return 0;
}

标签:dots,Scoring,frac,CF1794C,题解,times,leq,int,include
From: https://www.cnblogs.com/PlayWithCPP/p/17399253.html

相关文章

  • CF371D题解
    思路:定义一个权值并查集,权值保存这个集合还可以存下多少水。如果这个集合可以存放的水已经小于要装入的水,就将这个集合与下一个集合合并。否则,直接把这个集合可以存放的水减去要装入的水的体积。代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;......
  • CF1799B Equalize by Divide题解
    本蒟蒻学习了jiangly大佬的思想,来发一个题解。大致题意:给定一个\(n\)个元素的数组\(a\),每次可以选择\(a[i]\)和\(a[j]\),然后使\(a[i]=\lceil\frac{a_i}{a_j}\rceil\),如果最后可以使数组中的所有元素都相等,那么输出Yes,并输出每一个操作\(i,j\);否则输出No。本人不......
  • CF1728A Colored Balls: Revisited题解
    去我的Blog观看修改时间:2022/9/11修改了格式与标点修改时间:2022/9/13修改了个别不严谨的语句题目大意有\(n\)种颜色的球,颜色为\(i\)的球为\(cnt_i\)个(\(cnt_1+cnt_2+\dots+cnt_n\)为奇数)。每次从球堆中取出\(2\)个颜色不相同的球,问最后可能剩下哪种颜色的球(输出任意......
  • 常见问题解决 --- python必备技能 换源
    源是什么源是编程开发或则是操作系统要使用的第三方依赖软件应用市场,源又从何而来,其实源来自其他的源的克隆,或者是源提供者自己收集,编译,又或者作者的上传为什么要换源这些源往往都在国外,国内以为你懂的原因无法直接访问或者特别慢怎么换Windows下python永久换源方式有两种:修......
  • 常见问题解决 --- pip报错【WARNING: Retrying (Retry(total=4, connect=None, read=N
    问题现象【WARNING:Retrying(Retry(total=4,connect=None,read=None,redirect=None,st】解决方法:出现该错误信息是因为pip源连接证书验证失败,增加参数 --trusted-host例如pipinstallmatplotlib-ihttp://mirrors.aliyun.com/pypi/simple--trusted-hostmirrors.al......
  • 【题解】ars[A001]相控阵
    Link→模拟赛T1一道简单好想小可爱题。首先我们很容易得到一个结论,就是若想使总作用力最大,那么五个核弹中一定会有四个反应关系去对总作用力产生贡献。证明的话:五个核弹相当于一个五元环,不同模式相当于对点进行染色,我们不妨规定两种模式分别染色为红和蓝。因为边数\(n\)......
  • P8430 题解
    前言题目传送门!更好的阅读体验?比较妙的交互题。思路题意就是每次可以询问\([l,r]\)的括号子序列是否为合法,\((n-1)\)次询问后,需要求出整个括号序列。括号序列,自然想到栈。考虑每次进行一个\([\text{top},i]\)的询问。如果是合法,那么\(a_{\text{top}}=\text{LEFT},a......
  • CF543D 题解
    前言题目传送门!更好的阅读体验?比较有趣的换根DP。思路FirstDFS按照换根DP套路,先钦定\(1\)为首都(即根节点),并计算。显然是树形DP。设\(dp_{u}\)表示以\(u\)为根的子树全部满足的方案数。对于一条树边\((u,v)\):如果\((u,v)\)修,就意味着\(v\)对应子树的所......
  • ABC254F 题解
    前言题目传送门!更好的阅读体验?这题trick就是更相减损术:\(\gcd\{a_1,a_2,a_3,\cdots,a_n\}=\gcd\{a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}\}\)。思路有了这个trick之后这题就好做了。并不需要其他题解一样画表格,化简式子就行,过程并没有难点。\[\begin{a......
  • UVA12096 题解
    这道题虽然被评黄,但个人感觉不止普及组难度,而且是一道很有价值的题目。题解区里全是\(O(n^2logn)\)的STL大法,我来发一篇\(O(n^2)\)哈希做法。目前0ms喜提最优解。这道题是codeforcesgym的题目,本质上就是模拟栈中集合插入,复制,相加,取交集,取并集的过程。注意,这些集合都是......