Codeforces Round #851 (Div. 2) A-E

news/2024/3/29 19:03:56/文章来源:https://blog.csdn.net/a1214034447/article/details/129151614

题目链接:https://codeforces.com/contest/1788

A - One and Two

解题思路:将数组分成两半,两边二一样多就行了。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e5 + 10;int a[mx];void solve(int n)
{for (int i=1;i<=n;i++) {if (2 * a[i] == a[n]) {printf("%d\n", i);return ;}}puts("-1");
}int main() {int t;scanf("%d", &t);while (t--) {int n, x;scanf("%d", &n);for (int i=1;i<=n;i++) {scanf("%d", &x);a[i] = a[i-1] + (x==2);}solve(n);}return 0;
}

B - Sum of Two Numbers

解题思路:对于每一位数都可以拆分成x / 2和x / 2 + 1,若为奇数一边就会多出1,交替一下就行了。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e5 + 10;char a[mx];int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%s", a+1);int ans[2] = {0,0};bool id = 0;for (int i=1; a[i]; i++) {int x = (a[i] - '0') / 2;ans[id] = ans[id] * 10 + x;ans[id^1] = ans[id^1] * 10 + (a[i] - '0') - x;if (2 * x != (a[i] - '0'))id ^= 1;}printf("%d %d\n", ans[0], ans[1]);}return 0;
}

 C - Matching Numbers

解题思路:发现平均数是2*n + 1,如果n是偶数的话两边无法对称,所以无解。如果是奇数可以找几个数弄一弄发现可以构造。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e5 + 10;char a[mx];int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);if ((n & 1) == 0) {puts("NO");continue;}puts("YES");for (int i=1;i<=n/2+1;i++) {printf("%d %d\n", i, 2 * (n + 1 - i));}for (int i=1;i<=n/2;i++) {printf("%d %d\n", i + n / 2 + 1, 2 * (n + 1 - i) - 1);}}return 0;
}

D - Moving Dots

解题思路:可以发现汇成一个点的一组数他们的结构会是:

                                1->2->3->4-><-5<-6<-7

        也就是会有两个数相互靠近,其他的数都是往跟随两个数其中的一个,那么可以枚举4、5两个数作为中心的情况。假设4和5的距离是d,那么3和4的距离一定大于d,5和6的距离一定大于等于d。不然4和5不会相互移动。至于3 和6可能不往4和5移动可能向2 和7移动,但不影响4、5的作为中心成为一组贡献。所以枚举两个点,在找距离大于d的两个点。时间复杂度为O(n^2logn)。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e3 + 10;
const int mod = 1e9 + 7;int n;
int a[mx];
ll sum[mx];int main() {scanf("%d", &n);sum[0] = 1;for (int i=1;i<=n;i++) {scanf("%d", a+i);sum[i] = 2 * sum[i-1] % mod;}ll ans = 0;for (int i=1;i<=n;i++) {for (int j=i+1;j<=n;j++) {int d = a[j] - a[i];int v1 = lower_bound(a + 1, a + i, a[i] - d) - a - 1;int v2 = n + a - lower_bound(a + j, a + 1 + n, a[j] + d) + 1;ans += sum[v1] * sum[v2] % mod;}}printf("%d\n", ans % mod);return 0;
}

E - Sum Over Zero

解题思路:dp[i]表示前缀i个数最大的答案是多少。那么假设当j < i,并且sum[i] >= sum[j],j就能和i形成一段的时候,最优答案应该为, i-j+max(dp[0],dp[1],,,dp[j]),用线段树维护-j+max(dp[0],dp[1],,,dp[j]),然后枚举i即可。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 2e5 + 10;
const int mod = 1e9 + 7;int n;
int a[mx];
struct node {ll fi;int se;bool operator < (const node& A) const{if (fi == A.fi)return se < A.se;return fi < A.fi;}
}sum[mx];
ll s[mx];
int dp[mx*3];void build(int l, int r, int rt)
{if (l == r) {dp[rt] = -sum[l-1].se;return ;}int mid = (l + r) >> 1;build(lson);build(rson);dp[rt] = max(dp[rt<<1], dp[rt<<1|1]);
}void update(int l, int r, int rt, int p, int v)
{if (l == r) {dp[rt] = max(v, dp[rt]);return ;}int mid = (l + r) >> 1;if (p <= mid)update(lson, p, v);elseupdate(rson, p, v);dp[rt] = max(dp[rt<<1], dp[rt<<1|1]);	
}int query(int l, int r, int rt, int L, int R) 
{if (L<=l && R>=r) {return dp[rt];}int mid = (l + r) >> 1;if (L <= mid && R > mid)return max(query(lson, L, R), query(rson, L, R));if (L <= mid)return query(lson, L, R);return query(rson, L, R);
}int main() {scanf("%d", &n);for (int i=1;i<=n;i++) {scanf("%d", a+i);sum[i].fi = sum[i-1].fi + a[i];sum[i].se = i;s[i] = sum[i].fi;}sort(sum, sum + n + 1);build(1, n + 1, 1);int ans = 0;for (int i=1;i<=n;i++) {node temp = {s[i], i};int k = lower_bound(sum, sum + 1 + n, temp) - sum + 1;int v = query(1, n + 1, 1, 1, k) + i;//cout << k << " $ " << v << endl;//cout << sum[i].fi << " # " << sum[i].se << endl;update(1, n + 1, 1, k, max(ans, v) - i);ans = max(ans, v);}printf("%d\n", ans);return 0;
}

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

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

相关文章

Kaggle系列之识别狗的品种类别(深度残差网络模型ResNet-34)

我们来到这个比赛页面&#xff1a;https://www.kaggle.com/competitions/dog-breed-identification这个数据集的目标是Determine the breed of a dog in an image(确定图像中狗的品种)我们先下载数据集解压之后来看下(当然不手动解压&#xff0c;也可以使用)&#xff0c;这里我…

记住这12个要点,你也能打造出让HR和技术主管前一亮的前端简历

第一篇章&#xff1a;吸引HR 如果你想在众多简历中脱颖而出&#xff0c;需要注意以下几点&#xff1a; 1、突出你的亮点&#xff1a; 给你的简历一个吸引人的文件命名和头部&#xff0c;突出你的关键技能和经验。 2、采用简洁的语言&#xff1a; 用简单易懂的语言来描述你的…

笔记本cpu温度多少正常?温度过高的4个常见原因

电脑CPU指的是中央处理器&#xff0c;它与电脑运行速度的快慢存在很大关系。如果电脑的处理器温度过高&#xff0c;就会影响我们电脑的运行速度&#xff0c;甚至出现蓝屏、卡顿的情况。 那么&#xff0c;对于电脑来说&#xff0c;笔记本cpu温度多少正常&#xff1f;有什么原因…

macOS Big Sur 11.7.4(20g1220)With OpenCore 0.8.9正式版 and winPE双引导分区原版镜像

原文来源于黑果魏叔官网&#xff0c;转载需注明出处。镜像特点完全由黑果魏叔官方制作&#xff0c;针对各种机型进行默认配置&#xff0c;让黑苹果安装不再困难。系统镜像设置为双引导分区&#xff0c;全面去除clover引导分区&#xff08;如有需要&#xff0c;可以自行直接替换…

KT1025A蓝牙音频芯片_立讯KC认证FCC测试现场整改记录

目录 一、问题说明简介 测试机构立讯反馈&#xff0c;客户寄的样板进行无线KC【韩国】测试不过&#xff0c;体现在如下两点 蓝牙部分接收杂散不过 蓝牙的发射功率偏低 2.1 单独只给蓝牙部分供电的测试图片--OK 2.2 单独给整板供电--但是使用电池供电 2.3 单独给整板供电-…

关于机器人坐标系变换的笔记

ROS TFros中&#xff0c;可以通过TF Tree来进行获取 机器人不同坐标系之间的转换关系&#xff0c;命令如下&#xff1a;rosrun tf tf_echo base_link head_link1意思为&#xff0c;从源坐标系base_link&#xff0c;到目标坐标系head_link1的变换关系&#xff0c;结果如下所示。…

Crafting interpreters 中文翻译,持续修正

本书在线地址 http://craftinginterpreters.com/ 感谢作者 作者用近 4 年的时间持续创作和改进本书&#xff0c;并把其 Web 版本公开在网上。这本纸质书于今年 7 月出版&#xff0c;立刻在 Hacker News 等网络媒介上引起关注和讨论。 书中作者首先定义了一个动态类型的语言 …

棋牌类游戏测试用例怎么写?我敢打赌你绝对不知道

目录 一&#xff0e;登陆 二&#xff0e;大厅 三&#xff0e;小游戏 四&#xff0e;银行功能 五&#xff0e;其他按钮 总结感谢每一个认真阅读我文章的人&#xff01;&#xff01;&#xff01; 重点&#xff1a;配套学习资料和视频教学 一&#xff0e;登陆 1&#xff0e…

使用拦截器实现登录状态检测(以及在注册拦截器类时要使用ioc中的拦截器类)

拦截器 preHandler(HttpServletRequest request, HttpServletResponse response, Object handler) 方法在请求处理之前被调用。该方法在 Interceptor 类中最先执行&#xff0c;用来进行一些前置初始化操作或是对当前请求做预处理&#xff0c;也可以进行一些判断来决定请求是否…

【MyBatis】源码学习 04 - 从 MapperMethod 简单分析一条 SQL 的映射操作流程

文章目录前言参考目录学习笔记1、测试代码说明2、binding 包的主要功能3、获取 Mapper 接口实例过程4、SQL 语句执行流程4.1、方法调用器4.2、MapperMethod 绑定方法4.2.1、SqlCommand4.2.2、MethodSignature4.3、MapperMethod#execute前言 本文内容对应的是书本第 13 章的内容…

循环、函数、对象——js基础练习

目录 一、循环练习 1.1 取款机案例 1.2 九九乘法表 1.3 根据数据生成柱形图 1.4 冒泡排序 1.6综合大练习 二、函数 2.1 转换时间案例 三、对象 1. 遍历数组对象 2. 猜数字游戏 3. 生成随机颜色 4. 学成在线页面渲染案例 一、循环练习 1.1 取款机案例 // 准备一个…

电商项目之Feign与Dubbo技术选型

文章目录1 问题背景2 前言3 思路4 Feign与Dubbo的区别5 总结6 真实案例1 问题背景 电商项目&#xff0c;B端以consul作为注册中心。重构了一个营销服务&#xff0c;以Nacos作为注册中心。B端需要调用营销服务。关于远程调用框架&#xff0c;营销服务用了Dubbo&#xff0c;而B端…

黑马程序员-Linux网络编程-01

目录 课程链接 协议 分层模型 网络传输数据封装流程 以太网帧和ARP请求 IP协议 TCP协议 BS与CS模型对比 套接字 网络字节序 IP地址转换函数 sockaddr地址结构 socket模型创建流程 socket()和bind() listen()和accept()​ 课程链接 03-协议_哔哩哔哩_bilibili 协…

java并发笔记

文章目录HashMapput方法resize方法ConcurrentHashMapput方法initTable方法sizectl代表什么&#xff1a;扩容计数器ConcurrentHashMap的读操作会阻塞嘛AQS唤醒线程时&#xff0c;AQS为什么从后往前遍历&#xff1f;AQS为什么要有一个虚拟的head节点AQS为什么用双向链表&#xff…

万字C语言学习笔记,带你学C带你飞(四)

文章目录单链表typedef1、基础typedef2、进阶typedef共用体枚举类型1、声明枚举类型2、定义枚举变量位域位操作文件的写入与写出C语言学习笔记&#xff0c;记录所学&#xff0c;便于复习。 由于篇幅过大&#xff0c;考虑到观感&#xff0c;准备分多篇记录。学习视频链接&#x…

Vue3.x使用Echarts绘制世界地图并进行定点

Vue3.x使用Echarts绘制世界地图并进行定点 一、需求 绘制世界地图并根据返回经纬度数据进行定点将定点数据展示在世界地图内 二、解决 绘制世界地图&#xff0c;利用Echarts图表组件时间&#xff0c;需要世界地图Geojson数据的可以在资源中下载世界地图Geojson数据-Javascr…

2022FALL嵌入式大纲

Jamslade 部分内容有遗漏&#xff0c;可结合 超文本 2022FALL《嵌入式系统原理》期末复习笔记 一起观看 文章目录嵌入式系统片上系统实时系统硬实时系统软实时系统伪指令DMA传输波特率单/半双/全双工通信&#xff1b;对齐/非对齐访问地址译码代码临界区RISCBIOSUARTSPII2CWDTRO…

2.5|shell简介|Linux支持的网络协议|Linux的网络服务

shell简介shell是一种具备特殊功能的程序&#xff0c;它是介于使用者和Unix/Linux操作系统内核间的一个接口。操作计算机需要通过命令&#xff08;command&#xff09;或是程序&#xff08;program&#xff09;&#xff1b;程序需要编译器&#xff08;compiler&#xff09;将程…

东南大学研究生英语18-19秋试卷解析

写在前面 作者&#xff1a;夏日 博客地址&#xff1a;https://blog.csdn.net/zss192 本文为东南大学研究生英语上学期18-19年期末试卷解析&#xff0c;答案来源于 ChatGPT International Conference 单选题 1.A presenter is supposed to do the following in an introdu…

【数据结构趣味多】八大排序

目录 1.直接插入排序 基本思想 代码实现&#xff1a; 直接插入排序的特性总结&#xff1a; 2.希尔排序 基本思想 代码实现 &#xff08;递归实现&#xff09; 希尔排序的特性总结 3.直接选择排序 基本思想 代码实现&#xff1a; 直接选择排序的特性总结 4.堆排序 …