AC修炼计划(AtCoder Regular Contest 166)

传送门:AtCoder Regular Contest 166 - AtCoder

一直修炼cf,觉得遇到了瓶颈了,所以想在atcode上寻求一些突破,今天本来想尝试vp AtCoder Regular Contest 166,但结局本不是很好,被卡了半天,止步于B题。不过确实,感觉AtCoder的题目还是很不错的,一改cf的很多惯性思路。

这里借用了大佬樱雪喵的题解链接,大佬的传送门如下Atcoder Regular Contest 166 - 樱雪喵 - 博客园 (cnblogs.com)

B - Make Multiples

问题陈述

给你一个整数序列 A=(A1​,…,AN​),以及正整数 a,b 和 c。

你可以对这个数列进行以下运算,次数不限,可能为零。

  • 选择一个整数 i,使得 1≤i≤N.将 Ai​ 替换为 Ai​+1。

你的目标是使数列 A 至少包含一个 a 的倍数,至少一个 b 的倍数,以及至少一个 c 的倍数。求实现这一目标所需的最少运算次数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const ll MX=0x3f3f3f3f3f3f3f3f;int n,m;
int lcm(int a,int b){return a*b/__gcd(a,b);
}
void icealsoheat(){int a,b,c;cin>>n>>a>>b>>c;vector dp(n+5,vector(10,MX));int op[]={1,a,b,lcm(a,b),c,lcm(a,c),lcm(c,b),lcm(lcm(a,c),b)};dp[0][0]=0;for(int i=0;i<n;i++){int x;cin>>x;for(int j=0;j<8;j++){for(int k=0;k<8;k++){if((j&k)==0){// dp[i+1][j|k]=min(dp[i+1][j|k],dp[i][j]+op[k])if(x%op[k]==0){dp[i+1][j|k]=min(dp[i+1][j|k],dp[i][j]);}else{dp[i+1][j|k]=min(dp[i+1][j|k],dp[i][j]+(x/op[k]+1ll)*op[k]-x);}}}}// cout<<dp[n][7]<<"\n";}cout<<dp[n][7]<<"\n";}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}
}

C - LU / RD Marking

问题陈述

有一个网格,网格中有 H 行和 W 列。

这个网格有H(W+1)条垂直边和W(H+1)条水平边,共计H(W+1)+W(H+1)条(另见输入/输出示例中的数字)。请考虑通过以下两种操作来标记这些边。

  • 操作 (1)**:选择一个正方形,在进行此操作时,其左边缘和上边缘均未标记。标记该正方形的左边缘和上边缘。
  • 操作 (2):选择一个右边和下边在执行此操作时没有标记的正方形。标出该正方形的右边和下边。

求操作(1)和操作(2)执行任意多次(可能为零)时,最终被标记的边的可能集合的数量,模为 998244353998244353。

您有 T 个测试案例需要解决。

这里要借用官方题解的图例:

由此将方块拆开找规律。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const ll MX=0x3f3f3f3f3f3f3f3f;
int n,m;
int dp[2000008];
int sum[2000008];
int kuai(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%N;b>>=1;a=a*a%N;}return ans%N;
}
void icealsoheat(){cin>>n>>m;if(n>m)swap(n,m);int ans=sum[n]*kuai(dp[2*n],m-n)%N;cout<<ans<<"\n";
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;cin>>_;dp[0]=1;dp[1]=2;for(int i=2;i<=2000005;i++){dp[i]=dp[i-1]+dp[i-2];dp[i]%=N;}sum[0]=1;for(int i=1;i<=1000000;i++){sum[i]=sum[i-1]*dp[2*i-1]%N*dp[2*i-1]%N;}while(_--){icealsoheat();}
}

D - Interval Counts

因为这题还是比较好想的所以直接上代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const ll MX=0x3f3f3f3f3f3f3f3f;
int n,m;
void icealsoheat(){cin>>n;vector<int>x;vector<int>y;x.push_back(-2e9);y.push_back(0);for(int i=1;i<=n;i++){int xx;cin>>xx;x.push_back(xx);}vector<PII>ve;for(int i=1;i<=n;i++){int xx;cin>>xx;y.push_back(xx);}ll maxx=2e9;int id=0;for(int i=1;i<=n;i++){if(y[i]==y[i-1])continue;else if(y[i]>y[i-1])ve.push_back({x[i-1]+1,y[i]-y[i-1]});else{int now=y[i-1]-y[i];while(id<ve.size()&&ve[id].second<=now){maxx=min(x[i]-1-ve[id].first,maxx);now-=ve[id].second;id++;}if(now&&id<ve.size()){ve[id].second-=now;maxx=min(x[i]-1-ve[id].first,maxx);}}}if(maxx>1e9)printf("-1\n");else printf("%lld\n",maxx);}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;// cin>>_;while(_--){icealsoheat();}
}

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

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

相关文章

Vue条件渲染

一、使用v-show条件渲染 语法格式&#xff1a; v-show"表达式" // true 或 false 当表达式的值为true的时候就显示&#xff0c;表达式值为false的时候隐藏。 下面是使用v-show实现的一个点击按钮切换显示和隐藏的小案例 &#xff1a; 值得注意的是&#xff0c;使…

Element Plus阻止 el-dropdown、el-switch等冒泡事件

最近做vue3项目&#xff0c;使用Element Plus,又遇到坑了&#xff01; 问题点&#xff1a;组件中遇到事件冒泡问题了&#xff0c;el-checkbox 中 change事件要求阻止冒泡&#xff0c;如下代码中要求点击checkbox时不调用li标签的show方法 <li click"show()">…

kafka属性说明

kafka中关于一些字段说明 groupId :标识消费者分组id&#xff0c;如果多个消费者id相同&#xff0c;就表示这几个消费者是一组&#xff0c;当一组多个消费者消费同一个topic时&#xff0c;一组中只会有一个成功消费 代码如下 这时只会有一条消息被消费

Net6 用imagesharp 实现跨平台图片处理并存入oss

项目要求&#xff1a;生成电子证书 一、模板文件在OSS中&#xff0c;直接加载 二、向模板文件添加二维码 三、向模板文件添加多行文字 四、生成二维码&#xff0c;存入本地&#xff0c; 五、向模板文件添加二维码 代码实现步骤 一、建立.net 6 API项目&#xff0c;安装N…

城市消防无人机控制系统的设计

目录 摘 要......................................................................................................................... 2 第一章 绪论.............................................................................................................…

【Java 进阶篇】JavaScript 正则表达式(RegExp)详解

JavaScript 正则表达式&#xff0c;通常简写为 RegExp&#xff0c;是一种强大的文本匹配工具&#xff0c;它允许你通过一种灵活的语法来查找和替换字符串中的文本。正则表达式在编程中用途广泛&#xff0c;不仅限于 JavaScript&#xff0c;在许多编程语言中也都有类似的实现。 …

Vue 绑定style和class

在应用界面中&#xff0c;某些元素的样式是动态的。class 与 style 绑定就是专门用来实现动态样式效果的技术。 如果需要动态绑定 class 或 style 样式&#xff0c;可以使用 v-bind 绑定。 绑定 class 样式【字符串写法】 适用于&#xff1a;类名不确定&#xff0c;需要动态指…

ETL数据转换方式有哪些

ETL数据转换方式有哪些 ETL&#xff08;Extract&#xff0c; Transform&#xff0c; Load&#xff09;是一种常用的数据处理方式&#xff0c;用于从源系统中提取数据&#xff0c;进行转换&#xff0c;并加载到目标系统中。 数据清洗&#xff08;Data Cleaning&#xff09;&am…

快手商品详情数据接口,快手商品详情API接口,快手API接口

在网页抓取方面&#xff0c;可以使用 Python、Java 等编程语言编写程序&#xff0c;通过模拟 HTTP 请求&#xff0c;获取快手网站上的商品页面。在数据提取方面&#xff0c;可以使用正则表达式、XPath 等方式从 HTML 代码中提取出有用的信息。值得注意的是&#xff0c;快手网站…

android studio 移植工程

第一步&#xff1a; 第二步&#xff1a;创建 第三步&#xff1a; 第四步&#xff1a;复制文件至替代新工程中的文件 第五步&#xff1a;修改 第六步&#xff1a;编译OK

设计模式 - 行为型模式考点篇:迭代器模式(概述 | 案例实现 | 优缺点 | 使用场景)

目录 一、行为型模式 一句话概括行为型模式 1.1、迭代器模式 1.1.1、概述 1.1.2、案例实现 1.1.3、优缺点 1.1.4、使用场景 一、行为型模式 一句话概括行为型模式 行为型模式&#xff1a;类或对象间如何交互、如何划分职责&#xff0c;从而更好的完成任务. 1.1、迭代器…

基于局部结构特征的图像匹配

目录 第一章 绪论........................................................................ 6 1.1 研究课题背景....................................................... 6 1.2 图像匹配技术国内外发展现状........................... 8 1.3 课题研究的目的......…

芯片学习记录SN74HC14DR

SN74HC14DR 芯片介绍 该设备包含六个独立的逆变器使用施密特触发器输入。每个门执行正逻辑中的布尔函数Y/A("/"表示“非”)。 引脚信息 引脚名称I/O电平功能11AI0~vcc输入21YO0~vcc输出7GND-电源14VCC-3.3v电源&#xff08;2~6V&#xff09;Y/A 推荐使用条件 参数…

微信浏览器大字体模式 按钮文字居中用line-height 显示异常

按钮文字居中用line-height 的css 在微信浏览器大字体模式&#xff0c;会导致显示错误。改成flex 居中就好了

Joe主题魔改:正文内容实现图片懒加载

引言 有个哥们问我Joe主题的正文部分&#xff0c;如何同样图片懒加载&#xff0c;于是便研究了一下。 探索过程 因为PHP语言我用的很少&#xff0c;并不擅长&#xff0c;于是我去网上搜了一下。 方案一&#xff1a;用一个叫Jquery Lazyload的JavaScript脚本&#xff0c;我尝…

Unity基础课程之物理引擎5-射线的使用方法总结

在实际游戏开发时&#xff0c;不可避免地要用到各种射线检测。即便是一个不怎么用到物理系统的游戏&#xff0c;也很可能要用到射线检测机制。换句话说&#xff0c;射线检测在现代游戏开发中应用得非常广泛&#xff0c;超越了物理游戏的范围。下面简单举几个例子。 &#xff0…

CSS网页标题图案和LOGO SEO优化

favicon图标 将网页的头名字旁边放入一个图案 想将想要的图案切成png图片 然后把png图片转换成ico图案可以借助进行访问 将语法引用到head里面 SEO译为搜索引擎优化。是一种利用搜索引擎的规则提高网站有关搜索引擎的自然排名的方式 SEO的目的是对网站进行深度的优化&…

Unity关键词语音识别

一、背景 最近使用unity开发语音交互内容的时候&#xff0c;遇到了这样的需求&#xff0c;就是需要使用语音关键字来唤醒应用程序&#xff0c;然后再和程序做交互&#xff0c;有点像智能音箱的意思。具体的技术方案方面&#xff0c;也找了一些第三方的服务&#xff0c;比如百度…

【Mybatis】基于Mybatis插件+注解,实现敏感数据自动加解密

一、介绍 业务场景中经常会遇到诸如用户手机号&#xff0c;身份证号&#xff0c;银行卡号&#xff0c;邮箱&#xff0c;地址&#xff0c;密码等等信息&#xff0c;属于敏感信息&#xff0c;需要保存在数据库中。而很多公司会会要求对数据库中的此类数据进行加密存储。 敏感数据…

C语言达到什么水平才能从事单片机工作

C语言达到什么水平才能从事单片机工作 从事单片机工作需要具备一定的C语言编程水平。以下是几个关键要点&#xff1a;基本C语言知识&#xff1a; 掌握C语言的基本语法、数据类型、运算符、流控制语句和函数等基本概念。最近很多小伙伴找我&#xff0c;说想要一些C语言学习资料&…