当前位置: 首页 > news >正文

速通ACM省铜第十六天 赋源码(Sigma Cubes和Find Permutation 2和Rotate and Sum Query) - 教程

目录

引言:

Sigma Cubes(水题)

        题意分析:

        逻辑梳理:

        代码实现:

Find Permutation 2(水题)

        题意分析

        逻辑梳理

        代码实现

Rotate and Sum Query(主要)

        题意分析

        逻辑梳理

        代码实现

结语:


引言:

        昨天没有更新速通ACM省铜,是因为昨天事比较多,去搞ICPC区域赛的一些信息什么的一些事情了,就耽搁了,搞完时候已经9点多了,就没招了,所以昨天就没有打题和写博客,那么,今天我又复苏了,桀桀桀

        今天呢,我们不讲CF的题,因为今天正巧有atcoder abc的比赛,那我就打打那个,来讲讲这场比赛的题,这场比赛我就开出了ABC三道题,AB是纯水题,C感觉有点意思,D拼尽全力无法战胜了

        因为这是新的竞赛平台,那我就先放一个链接,这是今天这场比赛的链接UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 425) - AtCoder

        那么,我们就进入今天的算法讲解吧————————>

                ​​​​​​​        ​​​​​​​        ​​​​​​​        

Sigma Cubes(水题)

        按照惯例,先看题目

        题意分析:

        题目链接在这里A - Sigma Cubes

        不想跳转的可看下图

        这题题目要求很简单,就是给你一个数,然后通过运算题目给的式子来运算出结果,然后输出就可以了

        题目到这里就梳理完了,那么我们来看看这题逻辑的梳理方面


        逻辑梳理:

        逻辑其实也很简单,题目都告诉你奇数就-这个奇数的3次发,偶数就+ 这个偶数的3次方,那只需要判断一下就好啦,这跟之前讲的那道水题一样简单

        那么我们来看代码实现       


        代码实现:

        这里就直接放代码啦

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
long long n;
long long ans;
int main()
{cin >> n;for (int i = 1; i <= n; i++){if (i % 2)ans -= pow(i, 3);elseans += pow(i, 3);}cout << ans << endl;return 0;
}

        那么这题就讲完啦,是不是很水,我们来看下一题

Find Permutation 2(水题)

        我们先来看题目

        题意分析

        题目链接在这里B - Find Permutation 2

        不想跳转的可看下图

        这题的题目就是也很简单,就是给你一个数组a,然后问你存不存在满足条件的p数组,如果存在就输出Yes,然后再输出p数组,否则就输出No即可

        那什么样的数组满足条件呢,就是a数组中不是-1的那些元素的位置与p数组中同样位置的地方,这俩个的值要一样,然后p数组中刚好1-N的每个数都存在

        这就是题目的意思,接下来我们来梳理一下题目的逻辑


        逻辑梳理

        能否找到满足条件的p其实很简单,就是a数组里面不要有重复的非-1元素,不然就无法满足p数组能有1-n的数

        然后判断完能否创建后,接下来就是数据的填充,那么可以从小到大,也可以从大到小

        就是如果一个数没访问过且a[i]是-1,那么就输出没访问过的数,如果a[i]是具体的值,那么就输出a[i]就好啦,那么接下来,题目的逻辑梳理完啦,我们就进入代码的实现环节


        代码实现

        代码方面没什么好说的,毕竟这也是一道水题,就直接放代码啦

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;
int a[20];
int vis[20];
int main()
{cin >> n;int xixi = 0;for (int i = 1; i <= n; i++){cin >> a[i];if (a[i] != -1){if (vis[a[i]])xixi = 1;vis[a[i]] = 1;}}if (xixi)cout << "No" << endl;else{cout << "Yes" << endl;int ge = 0;for (int i = n; i > 0; i--){if (!vis[i]){ge = i;break;}}for (int i = 1; i <= n; i++){if (!vis[a[i]]){cout << ge << " ";ge--;while (vis[ge])ge--;}elsecout << a[i] << " ";}cout << endl;}return 0;
}

        那么,这题就讲完啦,是不是也很水,我们接着来看下一题

Rotate and Sum Query(主要)

        这题就是这篇博客最主要的部分了,前面俩题我感觉还是很水的,这题还是有点意思的,那么,我们来看题目吧

        题意分析

        题目链接在这里C - Rotate and Sum Query

        不想跳转的可看下图

        这题的题意很简单,就是给你一个相当于队列吧,然后告诉你有2种操作,让你选择

        1操作是让前c个元素出队再入队

        2操作是输出现在队列下标i到j的总和

        这就是这个题目的意思了,接下来,我们来看一下题目逻辑的梳理

        逻辑梳理

        首先看数据范围,如果开队列,出队,入队,算值都一个个操作,那么,时间复杂度肯定会超时

        所以我用的方法是先用数组装下原始的队列,然后再算出前缀和

        前缀和要算俩次,这样每种情况下队列的值都可以通过前缀和来算出来了

        那么下标方面我们要怎么操作呢,我们可以运算下标的变化值,然后通过下标的变化值,来算出各种情况下的值

        那么下标的变化值我们如何来求呢,很简单,如图,如果是出队一个进队一个,那么队列就变成了这个样子,那i,j的左右下标变化也都加了一

        通过这个图一个就能知道,下标的变化值的式子为L=(L+c)%n

        那么,逻辑就梳理完啦,接下来,我们进入代码的实现环节


        代码实现

        这题主要也是思维方面比较巧妙,思维想到了,代码实现自然就不难了,这里就直接展示AC码啦

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n, q;
long long a[200010];
long long sum[400010];
int main()
{cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];sum[i] = sum[i - 1] + a[i];}for (int i = n + 1; i <= 2 * n; i++)sum[i] = sum[i - 1] + a[i - n];int k, L = 0;while (q--){cin >> k;if (k == 1){int l;cin >> l;L = (L + l) % n;}else{int l, r;cin >> l >> r;cout << sum[r + L] - sum[l + L - 1] << endl;}}return 0;
}

        那么这题也讲解完啦

结语:

        今日算法讲解到此结束啦,希望对你们有所帮助,谢谢观看,如果觉得不错可以分享给朋友哟。当然也可以关注一下,有什么看不懂的可以评论问哦

http://www.hskmm.com/?act=detail&tid=29485

相关文章:

  • Linux操作系统扫盲汇总
  • ABC round 427
  • 卸载驱动模块,内核崩溃排查调试记录
  • 详细介绍:游戏引擎以及游戏开发
  • springboot大学校园旧物捐赠网站(代码+数据库+LW) - 详解
  • DropLoRA 论文浅读:通过动态子空间学习突破 LoRA 的性能瓶颈
  • python基础知识
  • switch语句的简单应用
  • 操作系统CPU和内核思维导图总结
  • defold游戏引擎与lua(teal)编程语言
  • 03 数值类型拓展
  • python如何引用变量的名称
  • Python GIL与No-GIL技术详解
  • fuse.js前端搜索简单使用的三个案例
  • 题解:AT_abc288_h [ABC288Ex] A Nameless Counting Problem
  • 2025 年 CBN 砂轮源头厂家最新推荐榜单:专业实力与客户满意度全景解析及选购指南
  • JDK安装和卸载
  • Python定义一个User类的基本写法
  • 10.12 CSP-S模拟30 改题记录
  • 编译GreatSQL with RocksDB引擎
  • ubuntu源码编译指定版本make
  • 【LeetCode】274. H 指数
  • python之多态
  • Linux安装JDK1.8 tomcat MariaDB(MySQL删减版)
  • Ubuntu系统部署Anaconda环境及Python语言的详细流程
  • python之继承
  • RK3568+MCU实时机器人解决方案 - 教程
  • 做题记录 #2
  • 深度学习开源书籍的技术解析
  • Nginx怎么去做负载均衡?