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

布满荆棘的人生 2024-03-22 10:36 75阅读 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 条评论，75人围观）

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

相关阅读

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

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

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

相关 CF790 div4 F(双指针） H（逆序对）

乐，被div4薄纱了没想到把所有出现次数>=k的数放一个数组里然后双指针还有H，连逆序对都没看出来，嘻感觉以后还是写写div4算了，写什么div2啊，caibi

- 日理万妓/ 2024年03月27日 10:24/ 0 赞/ 80 阅读

相关【二进制枚举+双指针】CF828div2 C. Flexible String

原来Brute Force就是枚举 Brute Force！ [Problem - C - Codeforces][] 题意： ![7141b563d11346efa

深碍√TFBOYSˉ_/ 2024年03月22日 19:17/ 0 赞/ 78 阅读

相关【差分】CF862div2 C

[Problem - C - Codeforces][] 题意： ![0f5f6ec576ec4ff191478dc5d04be692.png][] ![c8f8ba05

川长思鸟来/ 2024年03月22日 17:26/ 0 赞/ 56 阅读

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

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

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

相关 CF869div2 C. Almost Increasing Subsequence

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

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

相关【构造】CF851div2 C. Matching Numbers

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

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

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

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

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

相关 CF#692 div2

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

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

相关 POJ 3061 Subsequence 题解法一：二分 + 遍历法二：双指针

题目链接 > https://vjudge.net/problem/POJ-3061 一、二分+遍历利用二分的思想来解决，复杂度O(n \ log(n))

末蓝、/ 2022年09月02日 05:14/ 0 赞/ 18 阅读