首页 > 其他分享 >CF125D 题解

CF125D 题解

时间:2024-02-01 22:36:28浏览次数:29  
标签:ch int 题解 公差 add CF125D 等差数列

思路

首先可以发现前三个数中的两个数一定为一个等差数列中,所以我们对于前三个数枚举哪两个数是一个等差数列中的,设这两个数的差为 \(w\),在原数列中找到一个最长的公差为 \(w\) 的等差数列,记为 \(A\),剩下的数记为 \(B\),此时有三种可能。

  1. \(|B|=0\),此时可以知道原数组就是等差数列,此时我们可以把 \(B\) 当成最后一个数即可。
  2. \(|B|\leq 2\),通过题意可知 \(B\) 也为等差数列,直接输出即可。
  3. \(|B|>2\),此时答案不一定不存在,有可能在 \(A\) 中选择一些数到 \(B\) 后能使 \(B\) 成为等差数列,为了仍满足 \(A\) 为等差数列,所以我们取出的这段数一定要为 \(A\) 的后缀,然后插入进 \(B\) 中,这个过程可以用set来维护,但是我们想要快速维护 \(B\) 是否为等差数列仍需要知道序列的公差,所以我们可以枚举公差,而有效的公差只有 \(B\) 的最后两位的差和 \(A\) 与 \(B\) 最后两位的差。

代码

#include<bits/stdc++.h>
#define mm 600010
using namespace std;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int n,a[mm];
int A[mm],B[mm];
int num1,num2;
set<int> s;
bool vis[mm];
void check(int w)//将A的后缀插入到B中
{
    s.clear();int add=0;
    for(int i=2;i<=num2;i++)if(a[B[i]]-a[B[i-1]]!=w) ++add;
    for(int i=1;i<=num2;i++)s.insert(B[i]);
    for(int i=num1;i>=0;i--)
    {
        if(add==0)
        {
            if(i==0)
            {
                printf("%d\n",a[1]);
                for(int j=2;j<=n;j++) printf("%d ",a[j]);printf("\n");
                exit(0);
			}
            for(int j=1;j<=i;j++)printf("%d ",a[A[j]]),vis[A[j]]=true;printf("\n");
            for(int j=1;j<=n;j++)if(!vis[j])printf("%d ",a[j]);printf("\n");
            exit(0);
        }
        if(i==0) break;
        int X=A[i];
        s.insert(X);
        auto it=s.lower_bound(X);
        auto it1=it;it1--;auto pre=it1;
		auto it2=it;it2++;auto nxt=it2;
        if(it==s.begin())
        {
            if(a[*nxt]-a[*it]!=w) ++add;
            continue;
		}
        if(it==s.end())
        {
            if(a[*it]-a[*pre]!=w) ++add;
            continue;
        }
        if(a[*nxt]-a[*pre]==w){add+=2;continue;}
        if(a[*it]-a[*pre]!=w && a[*nxt]-a[*it]!=w) ++add;
        else if(a[*it]-a[*pre]==w && a[*nxt]-a[*it]==w) --add;
        //插入一个数,动态维护B是否为等差数列
    }
}
void work(int sta,int w)
{
    num1=num2=0;
    for(int i=1;i<sta;i++) B[++num2]=i;
    for(int i=sta;i<=n;i++)
        if(a[i]-a[A[num1]]==w || i==sta) A[++num1]=i;
        else B[++num2]=i;
    if(num2==0)
    {
        for(int i=1;i<num1;i++) printf("%d ",a[A[i]]);printf("\n");
        printf("%d\n",a[A[num1]]);
        exit(0);
    }//情况1
    if(num2<=2)
    {
        for(int i=1;i<=num1;i++) printf("%d ",a[A[i]]);printf("\n");
        for(int i=1;i<=num2;i++) printf("%d ",a[B[i]]);printf("\n");
        exit(0);
    }//情况2
    check(a[B[num2]]-a[B[num2-1]]);
    check(a[B[num2]]-a[A[num1]]);
    check(a[A[num1]]-a[B[num2]]);
    //情况3
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    work(1,a[2]-a[1]),work(1,a[3]-a[1]),work(2,a[3]-a[2]);//枚举哪两个数在同一个等差数列中
    puts("No solution");
}

标签:ch,int,题解,公差,add,CF125D,等差数列
From: https://www.cnblogs.com/noipwen/p/18001885

相关文章

  • mozhe靶场: WebShell文件上传漏洞分析溯源(第5题) 题解(使用哥斯拉)
    哥斯拉由java编写,可以在linux上使用.个人认为比冰蝎好用,用冰蝎连不上这个靶场,但是哥斯拉可以连的上.github搜哥斯拉就能下载首先登陆后台,弱口令adminadmin点击添加文章,尝试上传一句话木马(一句话木马可以点击哥斯拉的生成)webshell.asp<%evalrequest("pass")%>......
  • P3356 火星探测题解
    part1费用流建图比较显然,把车的数量当成流量,把捡到的石头数量当成费用。然后跑最大费用最大流。因为费用是针对点而不是边,所以要拆点,每个点分为入点和出点。对于向下走,向右走建边:从起点的出点向终点的入点连边,容量为\(inf\),费用为\(0\)。对于每一个格子,如果当前格子是石头......
  • AT_abc243_g [ABC243G] Sqrt 题解
    可设\(f_i\)为以\(i\)开头的方案数,由于最后由于操作数很多所以不用考虑还剩多少次操作,显然可得状态转移方程\(f_i=\sum\limits_{j=1}^{\sqrti}f_j\),时间复杂度\(O(T+X\sqrtX)\),空间复杂度\(O(X)\),无法接受。考虑如何更优,可以发现在\(T\)次询问中,每次可以直接转移,因此......
  • UVA12032 题解
    题意原题面一堆废话,其实这道题很简单。\(T\)组数据,每组数据给定你一个长度为\(n\)的序列\(a_1...a_n\),在定义\(a_0\)为\(0\)的情况下,假设\(k\)为你的力量系数,在\(\foralli\inn\)时\(a_i-a_{i-1}\lek\),且在按顺序\(1-n\)进行判断时,如果\(a_i-a_{i-1}=k\)......
  • 一般图最小匹配 题解
    首先进行排序,显然只有排序后相邻两个元素匹配才有可能成为答案。我们设\(b_i=a_i-a_{i-1}\),则问题转化为:在\(b\)数组中选\(m\)个数(显然一个\(b\)),两两不能相邻,求这些数和最小值。就和这道题一模一样了,使用反悔贪心。具体的,我们可以将所有\(b_i\)放进小根堆里,每次取出......
  • PMP-6.8 控制资源--问题解决
    一、控制资源基础内容 0.涉及领域:资源管理计划资源管理计划为如何使用、控制和最终释放实物资源提供指南。1.控制资源阶段需参照文档(1)问题日志问题日志用于识别有关缺乏资源、原材料供应延迟,或低等级原材料等问题。(2)经验教训登记册在项目早期获得的经验教训可......
  • CF1753D 题解
    因为最后要找的是“腾出空位”的最小代价。所以不妨把“障碍的移动”转化为“空位的移动”。令\(f_{x,y}\)为:使得\((x,y)\)为空,至少需要多少代价。下面来找转移方程,显然转移方程与空格子移动有关。所以观察空格子移动的规律。若当前格子\((x,y)\)为L。以\((x,y+1)\)......
  • P7031 [NWRRC2016] Anniversary Cake 题解
    作者还在想,居然没什么人写红题题解???咳咳。言归正传。本题没有想象中的那么复杂,咱分类讨论就行了。·若在属于蛋糕的平面直角坐标系中,两支蜡烛的横、纵轴不同,就会有多种切法。如图:           这样,我们随便找一种情况输出就行,反正有SpecialJudge......
  • A+B problem 题解
    先把一个单项式理解为:符号,系数的绝对值,字母,指数。为了方便操作,一口气读完整个字符串(数组),然后去扫描。因为如果第一项为整数的话没有符号,判一判。读入系数的绝对值像快读。如果有\(\texttt{^}\)这个符号,读一下之后的指数。由于只有三个字母,所以可以复制粘贴,不用写冗余的......
  • CEIT算法训练-双指针部分题解(T1-3)
    AnagramSearch题意简述两个字符串\(s\)和\(t\)相似的定义为:\(s\)可以打乱之后重新排列成为\(t\)。题目给出\(a\)和\(b\),问\(a\)中有多少子串(连续的一段)与\(b\)相似。同时,\(a\)中还含有\(?\)字符,他可以等价于任何字符(可以变成任何字符)解题思路实际上,根据题......