C - Sigma Problem(AtCoder Beginner Contest 353)

题目的链接:

C - Sigma Problem (atcoder.jp)

题目:

样例:

 题目大致含意:

给你n个数,让你对这n个数进行操作,比如当前是第i个,那么让a[i] 和 后面的每个数进行相加,
例如a[i] + a[i + 1] 注意的是a[i] + a[i + 1]的结果要进行取模 同理进行操作 (a[i] + a[i + 2]) % mod 输出的结果是 把这些运算后的数 加起来 注意的是 这些加起来的数就不再进行取模操作了

分析:

本题考查的是取模的一些操作,可以先考虑先不去取模着,先把这些结果加在一起 这需要利用前缀和的思想 推导的公式是: ret += (n - i) * a[i] + (sum[n] - sum[i]); 前提是 先把前缀和给提前预处理好,然后取模 取模其实就是减去多个 mod,要去知道是哪些(a[i] + a[j]) 他们是大于1e8了 然后我再减去 就可以了 那怎么快速知道 有多少个(a[i] + a[j])是大于1e8的!可以枚举每个a[i] 然后二分找到第一个大于等于(1e8 - a[i])的数的位置 那么(n - 这个位置)就是这n个数里面和当前的a[i] 相加是大于1e8的 那么我就直接ret - 1e8*个数

代码:

// package AtCoderBeginnerContest353;import java.util.Arrays;
import java.util.Scanner;public class C {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();long mod = (long) 1e8;long ret = 0;long[] a = new long[n + 10];long[] sum = new long[n + 10];//就是二分for(int i = 1; i <= n; i ++ ) {a[i] = sc.nextLong();// 也是要利用前缀和的思想sum[i] = sum[i - 1];sum[i] += a[i];}for(int i = 1; i <= n; i ++ ) {ret += (n - i) * a[i] + (sum[n] - sum[i]);}//	System.out.println("ret = " + ret); // ret出现了问题Arrays.sort(a, 1, n + 1);
//		for(int i = 1; i <= n; i ++ ) {
//			System.out.print(a[i] + " ");
//		}for(int i = 1; i <= n; i ++ ) {int l = i, r = n + 1;long x = mod - a[i]; // 这个是要找的 找到第一个大于等于x的位置while(l + 1 < r) {int mid = l + r >> 1;if(a[mid] < x)l = mid;else r = mid;}//System.out.println("i = " + i + " l = " + l);// l + 1 是最后的答案ret -= (mod * (n - l));}System.out.print(ret);}
}

运行的结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/329098.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Stable Diffusion 3报告

报告链接&#xff1a;Stable Diffusion 3: Research Paper — Stability AI 文章目录 要点表现架构细节通过重新加权改善整流流量Scaling Rectified Flow Transformer Models灵活的文本编码器RF相关论文 引言 随着人工智能技术的飞速发展&#xff0c;文本到图像生成领域正经…

【map、set】C++用红黑树来封装map、set容器

&#x1f389;博主首页&#xff1a; 有趣的中国人 &#x1f389;专栏首页&#xff1a; C进阶 &#x1f389;其它专栏&#xff1a; C初阶 | Linux | 初阶数据结构 小伙伴们大家好&#xff0c;本片文章将会讲解map和set之用红黑树来封装map、set容器的相关内容。 如果看到最后您…

CasaOS系统玩客云安装内网穿透工具实现无公网IP远程访问

文章目录 前言1. CasaOS系统介绍2. 内网穿透安装3. 创建远程连接公网地址4. 创建固定公网地址远程访问 前言 2月底&#xff0c;玩客云APP正式停止运营&#xff0c;不再提供上传、云添加功能。3月初&#xff0c;有用户进行了测试&#xff0c;局域网内的各种服务还能继续使用&am…

kubeadm部署k8s v1.28

一、主机准备 主机硬件配置说明 作用IP地址操作系统配置k8s-master01192.168.136.55openEuler-22.03-LTS-SP12颗CPU 4G内存 50G硬盘k8s-node01192.168.136.56openEuler-22.03-LTS-SP12颗CPU 4G内存 50G硬盘k8s-node02192.168.136.57openEuler-22.03-LTS-SP12颗CPU 4G内存 50G…

C++: 多态

目录 一、多态的概念 二、多态的定义及实现 2.1虚函数 2.2虚函数的重写 2.3多态的构成条件 2.4虚函数重写的两个例外 1.协变 2.析构函数的重写 2.5虚函数重写的实质 2.6override 和 final&#xff08;C11&#xff09; 1.final 2.override 2.7重载、覆盖&#xff0…

Leetcode刷题笔记2:数组基础2

导语 leetcode刷题笔记记录&#xff0c;本篇博客记录数组基础1部分的题目&#xff0c;主要题目包括&#xff1a; 977.有序数组的平方 &#xff0c;209.长度最小的子数组 &#xff0c;59.螺旋矩阵II 知识点 滑动窗口 所谓滑动窗口&#xff0c;就是不断的调节子序列的起始位…

反射获取或修改对象属性的值

利用反射既可以获取也可以写入,首先咱们先写几个获取的例子。 一:利用反射修改各数据(利用resultField.set修改) 首先定义实体类 public class Dog {private String dogUser;private int age;把DogUser的"hahaha"改为"geggegegege" Dog dog = new Do…

Docker快速搭建Oracle服务

服务器&#xff1a;CentOS7.9 1.安装docker yum install -y docker 2. 设置镜像加速 修改 /etc/docker/daemon.json 文件并添加上 registry-mirrors 键值 阿里云的docker镜像需要自己注册账号&#xff0c;也可以不注册账号&#xff0c;直接使用下面的连接。 也可以写入多…

C语言 数组——计算最大值的函数实现

目录 计算最大值 计算最大值的函数实现 应用实例&#xff1a;计算班级最高分​编辑​编辑 返回最大值所在的下标位置 返回最大值下标位置的函数实现​编辑 一个综合应用实例——青歌赛选手评分​编辑​编辑​编辑​编辑​编辑 计算最大值 计算最大值的函数实现 应用实例&…

键盘盲打是练出来的

键盘盲打是练出来的&#xff0c;那该如何练习呢&#xff1f;很简单&#xff0c;看着屏幕提示跟着练。屏幕上哪里有提示呢&#xff1f;请看我的截屏&#xff1a; 截屏下方有8个带字母的方块按钮&#xff0c;这个就是提示&#xff0c;也就是我们常说的8个基准键位&#xff0c;我…

【蓝桥杯】

题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc.h> using llunsigned long long; #define int ll const int N2e510; int k0; std::string s; int a,b,c,d; void solve() {char op;std::cin>>op;if(opA){std::string s;for(int i1;i&l…

Kafka-偏移量(含消费者事务)

Kafka概述 1.什么是偏移量&#xff1a; 在 Kafka 中&#xff0c;每个分区的消息都会被分配一个唯一的偏移量&#xff08;offset&#xff09;。偏移量简单来说就是消息在分区中的位置标识。 偏移量从 0 开始递增&#xff0c;每条消息的偏移量都会比前一条消息的偏移量大 1。 消…

如何对Linode Windows虚拟机进行“本地”访问

大部分时候&#xff0c;IT运维工作都可以远程进行&#xff0c;只要能通过网络访问被管理的系统&#xff0c;就可以执行几乎所有任务。如果因为某些原因导致无法通过网络访问呢&#xff1f;此时可能需要亲自到达相关硬件设备旁&#xff0c;通过“本地访问”来排错。 如果这些硬…

python实现520表白图案

今天是520哦&#xff0c;作为程序员有必要通过自己的专业知识来向你的爱人表达下你的爱意。那么python中怎么实现绘制520表白图案呢&#xff1f;这里给出方法&#xff1a; 1、使用图形库&#xff08;如turtle&#xff09; 使用turtle模块&#xff0c;你可以绘制各种形状和图案…

Thinkphp内核开发盲盒商城源码v2.0 对接易支付/阿里云短信/七牛云存储

源码简介 这套系统是我从以前客户手里拿到的,100完整可用,今天测试防红链接失效了,需要修改防红API即可!前端页面展示我就不放了,懂的都懂 优点是Thinkphp开发的&#xff0c;二开容易。 源码图片 资源获取&#xff1a;Thinkphp内核开发盲盒商城源码v2.0 对接易支付/阿里云短…

苹果MacOS系统使用微软远程桌面连接Windows电脑桌面详细步骤

文章目录 前言1. 测试本地局域网内远程控制1.1 Windows打开远程桌面1.2 局域网远程控制windows 2. 测试Mac公网远程控制windows2.1 在windows电脑上安装cpolar2.2 Mac公网远程windows 3. 配置公网固定TCP地址 前言 日常工作生活中&#xff0c;有时候会涉及到不同设备不同操作系…

面了一个程序员,因为6休1拒绝了我

人一辈子赖以生存下去的主要就考虑三件事&#xff0c;职业&#xff0c;事业&#xff0c;副业&#xff0c;有其1-2都是很不错的。如果还没到40岁&#xff0c;那不妨提前想下自己可能遇到的一些情况&#xff0c;提前做一些准备&#xff0c;未雨绸缪些。 今年整体就业大环境也一般…

CDN用户平台安装说明

CDN用户平台安装说明 登录管理员系统 在”系统设置” – “高级设置” – “用户节点”中点击”添加节点” 如果所示&#xff1a; 节点名称 - 可以任意填写 进程监听端口 - 启动用户节点后&#xff0c;进程所监听的端口&#xff0c;通常是HTTP 80或者HTTPS 443&#xff0c;…

网关路由SpringCloudGateway、nacos配置管理(热更新、动态路由)

文章目录 前言一、网关路由二、SpringCloudGateway1. 路由过滤2. 网关登录校验2.1 鉴权2.2 网关过滤器2.3 登录校验2.3.1 JWT2.3.2 登录校验过滤器 3. 微服务从网关获取用户4. 微服务之间用户信息传递 三、nacos配置管理问题引入3.1 配置共享3.1.1 在Nacos中添加共享配置3.1.2 …

vue.js状态管理和服务端渲染

状态管理 vuejs状态管理的几种方式 组件内管理状态&#xff1a;通过data&#xff0c;computed等属性管理组件内部状态 父子组件通信&#xff1a;通过props和自定义事件实现父子组件状态的通信和传递 事件总线eventBus&#xff1a;通过new Vue()实例&#xff0c;实现跨组件通…