首页 > 其他分享 >P1667 数列

P1667 数列

时间:2023-10-09 20:47:37浏览次数:39  
标签:le 数列 int P1667 置换 lt 操作 我们

原题

可能更好的阅读体验

区间操作的维护看起来很麻烦,考虑转为点操作的维护。题目中的 \(\sum_{i=l}^r a_i\) 启发我们用前缀和。那么我们考虑每次操作会对前缀和数组 \(s\) 造成怎样的变化。设操作区间为 \([l,r]\),按照题意,会把 \(a_{l-1}\) 和 \(a_{r+1}\) 加上 \(S\),\(a_l\) 和 \(a_r\) 减去 \(S\),那么对于 \(s\) 数组的影响即是把 \(s_{l-1}\) 加上 \(S\),\(a_r\) 减去 \(S\)。

接下来我们考虑 \(S\) 的取值,\(S=\sum_{i=l}^r a_i=s_r-s_{l-1}\),然后我们把这个带过去可得:\(s_{l-1}=s_{l-1}+s_r-s_{l-1}=s_r,s_r=s_r-(s_r-s_{l-1})=s_l\)。

然后就发现这其实就是交换操作。

接下来考虑,我们的目标是使得序列 \(a\) 中所有子段和 \(\gt 0\),容易发现这就是让序列 \(a\) 中所有数都 \(\gt 0\),也就是使前缀和序列 \(s\) 单调递增。

所以,我们的问题转化为了:每次操作可选择一对 \(l,r(1\le l\lt r\lt n)\),然后 \(swap(s_l,s_r)\)。求使得序列 \(s\) 单调递增的最小操作次数。

那这就是个经典问题了,可以用找置换环的方式解决,具体来说,我们记 \(s\) 升序排序之后得到的数组为 \(s'\),记 \(pos_i\) 表示数 \(i\) 在 \(s'\) 中出现的位置。那么我们每次从一个没有访问过的位置开始搜,不断令 \(i=pos_{s_i}\),直到找到一个置换环,即 \(i\) 已经被访问过了,就退出,并令置换环个数 cnt++

最终答案就是 \(n-1-cnt\)。不懂这里的置换环操作以及答案由来的选手可以自行搜索“置换环”进行了解。至于为什么是 \(n-1\) 而不是 \(n\),是因为我们每次选择的 \(r\) 必须 \(\lt n\),所以 \(s_n\) 一定是永远都不能参与操作的,直接排除它就好了。

最后的最后,我们来考虑判断无解情况,首先如果 \(s\) 中有相等的数的话就一定不能满足“递增”,于是无解,以及如果出现了 \(s_i\le 0\) 的话也一定无解,因为如果有 \(s_i\le 0\),那么我们把 \(s\) 排完序之后一定有 \(s_1\le 0\),即 \(a_1\le 0\),不满足条件,故无解。

以上这些判断可以合并成:

sort(s+1,s+n);
    for(re int i=1;i<=n;i++)
        if(s[i]<=s[i-1]){
            puts("-1");
            return 0;
        }

然后这题就做完了。

\(\text{Code:}\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=100100;
int n,a[N],s[N],b[N],mx=-1e18;
unordered_map<int,int>mp;
bitset<N>vis;
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
signed main(){
    n=read();
    for(re int i=1;i<=n;i++)
        a[i]=read(),b[i]=s[i]=s[i-1]+a[i];
    sort(s+1,s+n);
    for(re int i=1;i<=n;i++)
        if(s[i]<=s[i-1]){
            puts("-1");
            return 0;
        }
    for(re int i=1;i<n;i++)mp[s[i]]=i;
    int cnt=0;
    for(re int i=1;i<n;i++){
        if(vis[i])continue;
        int j=i;
        while(!vis[j]){
            vis[j]=1;
            j=mp[b[j]];
        }
        cnt++;
    }
    cout<<n-1-cnt;
    return 0;
}

标签:le,数列,int,P1667,置换,lt,操作,我们
From: https://www.cnblogs.com/MrcFrst-LRY/p/17753088.html

相关文章

  • 斐波那列数列的讲解过程
    python案例解释的有点不好,多多包含deff1(n):ifn<=2:return1;else:returnf1(n-1)+f1(n-2)#print(f1(6))"""示例1解释一下他是如何等8的,递归不是直接返回值再去传递给自身函数,比如n=4的时候,那么f1(4-1)+f1(4-2)=f1(3)+f1(2)不是......
  • 算法:打印斐波那契数列的前30项(JS)
    打印斐波那契数列的前30项提示:斐波那契数列的前两项是1,其他项是之前两项之和1functionfibonacciIterative(n){2if(n<=0){//如果输入的n小于等于0,表示输入错误,返回错误提示3return"输入错误,请输入正整数";4}5leta=1;//初始化......
  • P3901 数列找不同 【莫队】
    P3901数列找不同莫队:一种离线处理的优化暴力解法,时间复杂度在n*n^(1/2),会被卡常数,但是极为简单推荐视频:莫队算法点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inta[N];intpos[N];structnode{ intl,r,k;}t[N];strings......
  • 关于斐波那契数列 - 2 (平方的和)
    令斐波那契数列的第\(i\)项定义为\(b_i\)。再令\(f_n=\underset{i=1}{\overset{n}{\sum}}b^2_i\)结论:\(f_n=b_n\timesb_{n+1}\)首先,不难发现,该结论对于\(n=1\)和\(n=2\)一定是成立的\[f_1=1=1\times1\]\[f_2=1+1=2=1\times2\]......
  • 关于斐波那契数列 - 1
    令斐波那契数列第\(i\)个为\(F_i\)\(F_0=0,F_1=1,F_2=1\…\…\)结论:\(F_n^2=F_{n-1}F_{n+1}-(-1)^n\)不难发现,这一结论对于\(n=1\)显然是成立的接下来,运用数学归纳法若该结论对于\(n=k-1\)成立则\(F_{k-1}^2=F_{k-2}F_{k}-(-1)^{k......
  • 「高等数学」1.2 数列的极限
    数列极限的定义数列概念:如果按照某一法则,对每个\(n\in\mathbf{N_{+}}\),对应着一个确定的实数\(x_n\),这些实数按照下标\(n\)从小到大排列得到的一个序列\[x_1,x_2,x_3,\dots,x_n,\dots\]就叫做数列,简记为数列\(\left\{x_n\right\}\).数列中的每一个数......
  • 以下是一个复杂的 C 语言代码示例,展示了如何使用递归函数来计算斐波那契数列: ```c #i
    以下是一个复杂的C语言代码示例,展示了如何使用递归函数来计算斐波那契数列:#include<stdio.h>//递归函数计算斐波那契数列intfibonacci(intn){if(n<=1){returnn;}returnfibonacci(n-1)+fibonacci(n-2);}intmain(){intnum;......
  • 数列
    起因坐车两小时准备来道简单的数列题,然后发现不会做()时隔两个月再回来看看((然后和数列求导放缩的一起写了待我写完政治(虚弱题目设数列{\(a_n\)}的前n项和\(S_n=pn^2+qn\).若\(a_1^2\)+\(a_3^2\)\(\leq\)10,求\(a_3\)+\(a_4\)+\(a_5\)的最大值,并求此时\(p\)、\(q\)的值.解法......
  • [Резюме] 基础数列分块
    Preface分块可以\(O(n\sqrt{n})\)解决不能用线段树解决的问题,即不能快速合并区间信息的问题,是很多高级算法与数据结构的基础。本篇只是作者基础入门的一些感受,例题为\(\text{LOJ}[6277,6285]\),下一步计划学习莫队算法,这里有学习总结。Content0如何分块?考虑将标准块大小定......
  • 二阶差分——进行一个等差数列的加
    一般的差分用于对一段区间进行加减,但如果在该区间内加减的是一段等差数列呢?对于一段区间[l,r],加一段首项为s,末项为e的等差数列。其公差d=(s-e)/(r-l+1)为简化问题讨论,先假设这段区间都为0。原数组:0000000添加后的数组:0046800第一次差分:00422-8......