【二分or双指针】CF856div2 C. Scoring Subsequences

布满荆棘的人生 2024-03-22 10:36 58阅读 0赞

感觉对CF的套路题稍微有点感觉了

考虑特殊条件性质就好了....

[Problem - C - Codeforces][]

题意：

定义一个序列的分数为s1\*s2\*s3\*..../d!

给定一个序列，问对于1<=k<=n，设a1~ak这个序列中的这么多个子序列中分数最大的为m，问这些子序列中分数为m的最长子序列的长度

![e732aefd4071428eadf6915d50567500.png][]

思路：

对题中的条件一点点分析就好了

子序列：考虑将其特殊化，化成子段

递增：考虑从末尾开始取子段

s1\*s2\*s3\*....\*sk/d!：计算贡献，往前取子段，当a\[l\]<r-l+1的时候贡献变小，因此这个可以作为l的条件

所以综上，双指针就可以解决

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    int n;
    int a[mxn];
    
    void solve(){
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int l=1;
    	vector<int> v;
    	for(int r=1;r<=n;r++){
    		while(l<r&&a[l]<r-l+1) l++;
    		v.push_back(r-l+1); 
    	}
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1794/problem/C
[e732aefd4071428eadf6915d50567500.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e9acae09ed3344d4aff357c680bd4887.png

发表评论取消回复

表情：

评论列表（有 0 条评论，58人围观）

还没有评论，来说两句吧...

相关阅读

相关【双指针合并序列】CF731div3 B C

woc了好不容易补完div3，结果一点了，没时间写题解了，留着明天写吧，反正题是补完的，所以，我滴任务完成辣！双指针可以保证两个序列合并时相对位置不变！在合并过程中循环次数

深碍√TFBOYSˉ_/ 2024年03月27日 13:34/ 0 赞/ 74 阅读

相关 CF723div2 vp

哈哈，我是弱智哈哈，我是弱智哈哈，我是弱智谢谢你xcpc，让我认识到我就是个什么都不会的dinner ![cafe464664a699c7748235ab1488

小鱼儿/ 2024年03月26日 15:51/ 0 赞/ 77 阅读

相关【二分+贪心】CF1665 C

[Problem - C - Codeforces][] 题意： ![acbe9c1d054143bb8090042f525333b9.png][] ![557b7c06

比眉伴天荒/ 2024年03月23日 21:45/ 0 赞/ 29 阅读

相关【二分答案】CF1661 C

[Problem - C - Codeforces][] 题意： ![b7962e76b90c402e95ec6324c654b1fa.png][] 思路：在chec

小咪咪/ 2024年03月22日 20:25/ 0 赞/ 42 阅读

相关【sorting+双指针+数学】CF845div2 C. Quiz Master

和我一开始想的不太一样一开始想的也是排序，然后双指针，但是我想的双指针是l=1,r=n的，因为我没注意到极差尽可能小这个条件可以转化为区间长度最短其实就是尺取法，然后合

系统管理员/ 2024年03月22日 15:30/ 0 赞/ 5 阅读

相关 CF869div2 C. Almost Increasing Subsequence

[Problem - C - Codeforces][] 题意： ![967e89b3f5584dafb5a3e8b721e277fc.png][] 思路：关注特殊点

落日映苍穹つ/ 2024年03月22日 11:33/ 0 赞/ 31 阅读

相关【构造】CF851div2 C. Matching Numbers

[Problem - C - Codeforces][] 题意：有1~2\n的一个排列，进行数与数之间两两匹配，问如何组合可以使n个数对 ai+bi排列起来是一个连续序

àì夳堔傛蜴生んèń/ 2024年03月22日 11:02/ 0 赞/ 72 阅读

相关【二分or双指针】CF856div2 C. Scoring Subsequences

感觉对CF的套路题稍微有点感觉了考虑特殊条件性质就好了.... [Problem - C - Codeforces][] 题意：定义一个序列的分数为s1\s2\s3

布满荆棘的人生/ 2024年03月22日 10:36/ 0 赞/ 59 阅读

相关 CF#692 div2

A 从后往前找连续)最长长度判断是否大于n/2即可 B 一个数字只会出现1-9，而1-9的最小公倍数为7560 所以你最多自增7560个数后必能找到符合条件的数，所以暴力模拟

缺乏、安全感/ 2022年12月29日 06:47/ 0 赞/ 177 阅读

相关 CF572_Div2_F

题意 [http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_pr

╰半夏微凉°/ 2021年10月29日 13:32/ 0 赞/ 295 阅读