CCF- CSP202112-2序列查询新解 简单分段+满分题解_ccf202112_2-程序员宅基地

技术标签: 算法  c++  ccf  CCF-CSP  

CCF- CSP202112-2序列查询新解 简单分段+满分题解

题目链接:202112-2序列查询新解

思路:

  • 数据最大范围为109,因此需要采用long long类型
  • 分析样例序列A,我们可以对序列A进行预处理:设置a[0]=0,a[n+1]=N
  • 为降低时间复杂度,我们选择遍历序列A,对序列A中的区间进行分段处理
  • 分别枚举序列A的每个段,选定左右端点,左端点为a[i-1],右端点为a[i]-1,注意第i个段的f(i)值为i-1
  • 首先判断左右端点的g(i)值,如果值相等,将两者直接归为一个段,长度为right-left+1;如果值不等,说明该段内的g(i)值不相等,我们需要对该段再次分段,将g(i)值相等的点分为一个段
  • 当再次分段时,我们需要优先处理端点值,将端点值处理为可以整除r的值,便于后续计算
  • 处理左端点时,如果left%r!=0我们需要+(r-left%r)%r,注意%r,因为当前左端点可能刚好可整除r,此时只需要+0;比如5%3=2,我们需要将5更新为6,则需要+2;
  • 处理右端点时,我们需要-right%r;比如5%3=2,我们需要将5更新为3,则需要-2
  • 参考样例3,我们需要对右端点进行特判,当其可以整除r时,不应该放在当前段内,对该点进行单独处理:sum+=labs(r__/r-i+1);
  • 处理完该段的左右端点后,我们得到规整的段,即左端点和右端点都可以整除r,便于将该段分成更小的单位段,单位段的段长为r

具体代码如下:

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long  LL;
const int M = 1e5+10;
LL a[M];
LL n,N;
int main()
{
    
    cin>>n>>N;
    LL r = N/(n+1);//得到r值
    //输入序列A,a[0]默认为0
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[++n]=N;//将N加入到序列A中
    
    LL sum = 0;
    for(int i=1;i<=n;i++)
    {
    
        LL left = a[i-1];//该段区间的左端点
        LL right = a[i]-1;//该段区间的右端点,注意-1
        
        LL l_ = left/r;//判断左右两端点之间的距离,决定计算方式
        LL r_ = right/r;
        //如果左端点与有端点除以r的值相等,即该段区间的g(i)相等
        if(l_==r_)
        {
    
            //当前区间的长度为right-left+1;
            //由于g(i)值相等,f(i)值相等,则可以直接求解该段区间的sum
            //注意第i段区间的,f(i)值为i-1
            sum+=labs(l_-i+1)*(right-left+1);
        }
        //如果不想等,说明该区间内g(i)的值不想等,需要再次分段
        else
        {
    
            
            sum+=(r-left%r)%r*labs(l_-i+1);//处理左边部分,当left%r!=0时,我们优先处理该部分
            sum+=(right%r)*labs(r_-i+1);//同理处理右边部分,当right%r!=0时,我们优先处理该部分,使得剩下的区间端点都可以整除r
            LL l__ = left+(r-left%r)%r;//更新左端点,比如5%3=2,我们需要将5更新为6,则需要+2,即+(r-left%r)%r,注意%r,因为当前端点可能刚好可整除r
            LL r__ = right - right%r;//更新右端点,比如5%3=2,我们需要将5更新为3,则需要-2,直接 -right%r
            //参考样例3,我们需要对右端点进行特判,当其可以整除r时,不应该放在当前段内
            if(r__%r==0)
            {
    
                sum+=labs(r__/r-i+1);//对最右一个端点进行特判
            }
            //将该区间分为r长度的单位段,进行处理,只需要满足<=r__-1
            while(l__<=r__-1)
            {
    
                sum+=r*labs(l__/r-i+1);//每个单位段的长度为r
                l__+=r;//跳到下一个单位段
                
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_53641110/article/details/126862925

智能推荐

react router 配置404页面_react router 404-程序员宅基地

文章浏览阅读7.3k次,点赞3次,收藏7次。react router 配置404页面使用Vue相关的技术栈2年左右了,在路由管理上一直用的比较得心应手,现在的项目使用react开发,路由自然也就切换到了react router,所用版本为react router 4在Vue router配置中,我们可以很简单的配置出404页面使用通配符 * 号匹配所有路由,并将此配置放在数组的最末端,当前面的路由都匹配不上时,就会匹配到 * 号,然后..._react router 404

[蓝桥杯][2017年第八届真题]青蛙跳杯子_青蛙跳杯子-第八届蓝桥省赛-c组-程序员宅基地

文章浏览阅读168次。题目链接:青蛙跳杯子解题思路: 从第一个空杯子开始宽搜,每次前进1、2、3步判断每次的状态是否合法,如果合法就放入队列。#include<bits/stdc++.h>#define x first#define y second#define mem(h) memset(h,-1,sizeof h)#define mcp(a,b) memcpy(a,b,sizeof b)using namespace std;typedef long long LL;typedef uns_青蛙跳杯子-第八届蓝桥省赛-c组

电子信息工程专业保研:从211到北大软微保研面试经验分享(含通信原理面试真题)_电子信息保研北大-程序员宅基地

文章浏览阅读9.4k次,点赞28次,收藏158次。2021保研面试经验分享(含真题)保研经历:夏令营面试经验:预推免面试经验:资料下载保研经历:本人211电子信息工程专业,2020年保研至北京大学硕士。以下为一些高校面试经验\面试真题。整理不易,欢迎点赞收藏~,感谢!夏令营:北大信科计算机系、浙大工程师学院、东南大学网安学院、华科国光国家重点实验室、中科大科学岛、北理工电信学院、山东大学电信学院预推免:北大软微、清华深圳电子通信项目、复旦通信系、中科院计算机学院学硕夏令营面试经验:第一面:北大信科计算机系当时为了去名校报的直博,电子信息工程跨_电子信息保研北大

基于JDK7 NIO2的高性能web服务器实践之二(转)-程序员宅基地

文章浏览阅读75次。前一篇博客,我简单提了下怎么为NIO2增加TransmitFile支持,文件传送吞吐量是一个性能关注点,此外,并发连接数也是重要的关注点。不过JDK7中又一次做了简单的实现,不支持同时投递多个AcceptEx请求,只支持一次一个,返回后再投递。这样,客户端连接的接受速度必然大打折扣。不知道为什么sun会做这样的实现,WSASend()/WSAReceive()一次只允许一个还是可以理解..._jlong_to_ptr

Codeforces 574A Bear and Elections 思维题 暴力/优先队列-程序员宅基地

文章浏览阅读141次。题源:http://codeforces.com/problemset/problem/574/A思路:更多像是个思维题吧,数据量不大,完全可以暴力,暴力的代码不放了,每次找出队列里面的最大值,然后-1,然后第一项+1。直到最大的一项是第一个元素。。自己做的时候用了堆,按num从大到小排序,若相等,id小的在后面,可以用于判断是不是还有和1一样大的。自己这次写题解的时候也不知道自己当时怎么..._bear and elections

Java ip地址查询,根据ip接口获得ip所在省市区,邮编,运营商等_java如何通过ip地址获得运营商的ldns-程序员宅基地

文章浏览阅读5.0k次。互联网有很多接口可以实现通过ip查询到具体的位置,如下:通过淘宝IP地址库获取IP位置1. 请求接口(GET):http://ip.taobao.com/service/getIpInfo.php?ip=[ip地址字串]2. 响应信息:(json格式的)国家 、省(自治区或直辖市)、市(县)、运营商3. 返回数据格式:{"code":0,"data":{"ip":"210.75..._java如何通过ip地址获得运营商的ldns

随便推点

如何模拟用户登录爬取知乎_sso 爬取-程序员宅基地

文章浏览阅读842次。**如何模拟用户登录爬取知乎**import requests# 可以读取本地的cookie送给requeststry: import cookielib # Python2中叫cookielibexcept: import http.cookiejar as cookielib # Python3中叫做cookiej..._sso 爬取

SAP:SMARTFORM打开WORD文档出错,或无法编辑_sap smartform 报错-程序员宅基地

文章浏览阅读2.8k次,点赞2次,收藏5次。SAP760或者750都会出现这类问题:无法拖拽或编辑,出现这样的问题是因为SAP版本与本机中的office不兼容导致的解决办法:1.安装SAP插件:插件存在个人资源中,可自取2.程序函数增强:SE24:CL_COS_UTILITIES对于该对象中的方法:IS_S4H增加如下代码: method is_s4h. validate_gv_s4h( ). if gv_s4h-public_cloud_on = abap_true. rv_is_s4h = abap_sap smartform 报错

【数字图像处理】——BMP文件的简单操作_hxlbmpfile.h-程序员宅基地

文章浏览阅读1.6k次,点赞5次,收藏15次。1、在 VC 环境下 – 建立动态库工程,录入 HXLBMPFILE 类,建立相应动态库,将整个类作为动态库输出。输出 HXLBMPFILE.dll/lib 。可参考动态库如何建立录入 hxlbmpfile.h 文件,包含 HXLBMPFILE 类 的定义#pragma once#include"stdio.h"#include"math.h"#include"windows.h"#..._hxlbmpfile.h

前端之路从此启程____ _.-' \ / \ / \ / `.___ ( .--.)\/(,.--. `-. ,',-程序员宅基地

文章浏览阅读862次,点赞10次,收藏3次。一楼镇图## _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ...____ _.-' \ / \ / \ / `.___ ( .--.)\/(,.--. `-. ,',-. \ / ,-.`. ) ( / \ / \ )

模电(一)半导体基础_模电中va是什么-程序员宅基地

文章浏览阅读2k次,点赞9次,收藏25次。模拟电子电路之半导体基础【概念-本征半导体-杂质半导体-PN结】_模电中va是什么

python小作业4代码(简单循环语句的应用)_智力捕鱼python-程序员宅基地

文章浏览阅读1.6k次,点赞5次,收藏10次。任务一:水仙花数判断程序任务内容:水仙花数是一个三位整数,如153是一个水仙花数,是因为该数的百位的立方、十位的立方、个位的立方之和等于该数本身。程序编写要求:使用for语句完成;统计水仙花数个数的值请保存到变量中,并要求自动进行统计。代码:print("所有三位数中的水仙花数如下所示:")count=0for i in range(100,1000): a = i//10..._智力捕鱼python

推荐文章

热门文章

相关标签