2022ICPC济南站

K

Stack Sort

题意:给你一个长度为n的排列,设有m个栈,你需要将这n个数按出现顺序入栈,每次入栈操作从m个栈中选择一个栈从栈顶入栈。当所有元素入栈完成后,需要不断选择栈,将栈中元素弹空。需满足出栈顺序为1 2 3 ... n,问完成上述任务所需最少栈的个数为多少。

思路:遍历数组,设当前元素为x,我们就看是否存在栈顶为x+1的栈,若存在则入该栈;否则新开一个栈将x入栈。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
/*
1 4 2 5 3
1 34 2 5 
找x+1存在否 存在不存在 ++
*/
int n;
bool st[N];
void solve()
{cin>>n;for(int i=1;i<=n+1;i++) st[i]=0;int ans=0;for(int i=1;i<=n;i++){int x;cin>>x;if(st[x+1]){st[x+1]=0;st[x]=1;}else{st[x]=1;ans++;}}cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

M

Best Carry Player

题意:给定n个元素的数组a[],起始sum=0,不断执行sum+=a[i],问加法过程中的总进位次数为多少?

思路:模拟

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define PII pair<int, int>
typedef long long ll;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;using namespace std;
int n;
string a[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++){string x;cin >> x;reverse(x.begin(), x.end());a[i] = x;}string ret = "000000000000000";int ans = 0;int del = 0;for (int i = 1; i <= n; i++){for (int j = 0; j < 15; j++){int c1 = int(ret[j] - '0');int c2 = 0;if(j<a[i].size()) c2=int(a[i][j] - '0');int t = c1 + c2 + del;ret[j] = char(t % 10 + '0');if (t >= 10){ans++;del = 1;}elsedel = 0;}}cout << ans << '\n';
}
signed main()
{// freopen("input.txt","r",stdin);// freopen("output.txt","w",stdout);ios;int _t = 1;cin >> _t;while (_t--)solve();system("pause");return 0;
}

E

Identical Parity

题意:一个序列的值定义为所有数字的和,给定n,k问是否存在长度为n的排列满足所有长度为k的子段的值奇偶性都相同。

思路:当k=1时,若n=1 Yes;k=1, n不为1 No

当k为偶数时,我们可以奇偶交替的放,Yes

当k为奇数时,我们可以分成k组,每组的下标满足a, a+k, a+2k...a属于[1,k],同一组我们放相同奇偶的数。我们发现这样的序列就满足条件。

设n/k=b余c,我们将k/2个组,这些组的位置放偶数;其余k/2+1个组,这些组的位置上放奇数。那么还剩下c个数没放,判断剩下的数是否满足奇偶个数。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
void solve()
{cin>>n>>k;if(k==1){if(n==1) cout<<"Yes\n";else cout<<"No\n";}else if(k%2==0) cout<<"Yes\n";else{int tot_o=n/2,tot_j=(n+1)/2;//总的奇偶个数int k_o=k/2,k_j=k/2+1;//k组中有多少组奇数偶数int b=n/k,c=n%k;int r_o=tot_o-b*k_o,r_j=tot_j-b*k_j;//放完k组,还剩多少奇偶数没放if(r_o>=0&&r_j>=0&&r_o+r_j==c){if(r_o<=k_o&&r_j<=k_j) cout<<"Yes\n";else cout<<"No\n";}else cout<<"No\n";}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

A

Tower

题意:有n座不同高度的塔,第i座塔的高度为a[i]

你可以将其中的m座塔移除,然后进行下面的操作:

1.选择一座塔,将其高度 a[i]增加 1

2.选择一座塔,将其高度 a[i]减少 1

3.选择一座塔,将其高度 a[i]/=2,向下取整

不允许操作后塔的高度为0。问将剩余n-m座塔的高度搞成相同所需最少的操作次数。

思路:最后变成的相同高度一定是某个塔的高度不断/2的结果。所以我们可以通过枚举最后高度,来计算塔到这个高度的最小操作次数。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N];
int get(int now,int x)
{int ret=0;if(now<x) ret=x-now;else if(now==x) ret=0;else{while(now>x){if(now>x&&now/2<=x){ret+=min(now-x,1+x-now/2);break;}now/=2;ret++;}}return ret;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];set<int>s;for(int i=1;i<=n;i++){int x=a[i];s.insert(x);while(x>=2){x/=2;s.insert(x);}}int ans=1e18;for(auto x:s){vector<int>v;for(int i=1;i<=n;i++){int t=get(a[i],x);v.push_back(t);}sort(v.begin(),v.end());int tem=0;for(int i=0;i<n-m;i++)tem+=v[i];ans=min(ans,tem);}cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Frozen Scoreboard

题意:给你封榜前的情况和最终通过的题数和罚时,问最终的榜单

思路:将封榜前的过题数和罚时减去,再对封榜后的题进行二进制枚举,判断合法

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
int a[N],b[N];
struct node{char op;int x,y;int num;
}P[N];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];int nowt=0,nowcnt=0;vector<node>uk;for(int i=0;i<m;i++){char op;cin>>op;if(op=='+'){int u,v;char _;cin>>u>>_>>v;nowcnt++;nowt+=(u-1)*20+v;P[i]={'+',u,v};}else if(op=='-') {int u;cin>>u;P[i]={'-',u};}else if(op=='?'){int u,v;cin>>u>>v;P[i]={'?',u,v,i};uk.push_back({'?',u,v,i});}else P[i]={'.'};}if(nowcnt==a[i]&&nowt==b[i]){cout<<"Yes\n";for(int j=0;j<m;j++){if(P[j].op=='+') printf("+ %d/%d\n",P[j].x,P[j].y);else if(P[j].op=='-') printf("- %d\n",P[j].x);else if(P[j].op=='?') printf("- %d\n",P[j].y);else printf(".\n");}}else if(nowcnt<a[i]&&nowt<b[i]){int cnt=a[i]-nowcnt;int t=b[i]-nowt;bool f=0;for(int j=0;j<(1<<uk.size());j++){int mi=0,ma=0;for(int k=0;k<uk.size();k++){if((j>>k)&1){mi+=240+(uk[k].y-uk[k].x)*20;ma+=299+(uk[k].y-1)*20;}}if(t>=mi&&t<=ma){map<int,node>ans;int remt=t-mi;int finish=0;for(int k=0;k<uk.size();k++){if((j>>k)&1){int num=uk[k].num;int cishu=min(remt/20,uk[k].x-1);//封榜后wa了多少次ans[num].x=(uk[k].y-uk[k].x+cishu+1);remt-=cishu*20;int r1=min(remt,59ll);remt-=r1;ans[num].y=240+r1;finish++;}}if(remt==0&&finish==cnt){f=1;cout<<"Yes\n";for(int k=0;k<m;k++){if(P[k].op=='+') printf("+ %d/%d\n",P[k].x,P[k].y);else if(P[k].op=='-') printf("- %d\n",P[k].x);else if(P[k].op=='?'&&ans[k].x) printf("+ %d/%d\n",ans[k].x,ans[k].y);else if(P[k].op=='?') printf("- %d\n",P[k].y);else printf(".\n");}break;}}}if(!f) cout<<"No\n";}else cout<<"No\n";}
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;//cin>>_t;while(_t--) solve();system("pause");return 0;
}

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

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

相关文章

Flutter笔记 - 关于 fit 属性以及相关知识的总结

Flutter笔记 关于 fit 属性以及相关知识的总结 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/13434451…

任正非说:到现在我们终于可以说没有失败,但我们还不能说成功。

你好&#xff01;这是华研荟【任正非说】系列的第36篇文章&#xff0c;让我们聆听任正非先生的真知灼见&#xff0c;学习华为的管理思想和管理理念。 华研荟导语&#xff1a;今天的任正非先生讲话主要节选了他在2001-2004年的几个关于IPD、ISC的论述&#xff0c;可能大家会发现…

网络运维Day10

文章目录 SHELL基础查看有哪些解释器使用usermod修改用户解释器BASH基本特性 shell脚本的设计与运行编写问世脚本脚本格式规范执行shell脚本方法一方法二实验 变量自定义变量环境变量位置变量案例 预定义变量 变量的扩展运用多种引号的区别双引号的应用单引号的应用反撇号或$()…

Python环境安装、Pycharm开发工具安装(IDE)

Python下载 Python官网 Python安装 Python安装成功 Pycharm集成开发工具下载&#xff08;IDE&#xff09; PC集成开发工具 Pycharm集成开发工具安装&#xff08;IDE&#xff09; 安装完成 添加环境变量&#xff08;前面勾选了Path不用配置&#xff09; &#xff08;1&…

在程序中链接静态库

现在我们把上面src目录中的add.cpp、div.cpp、mult.cpp、sub.cpp编译成一个静态库文件libcalc.a。 add_library(库名称 STATIC 源文件1 [源文件2] ...) link_libraries(<static lib> [<static lib>...]) 参数1&#xff1a;指定出要链接的静态库的名字 可以是全…

基于Python+OpenCV+SVM车牌识别系统-车牌预处理系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介简介系统流程系统优势 二、功能三、系统四. 总结 一项目简介 ## PythonOpenCVSVM车牌识别系统介绍 简介 PythonOpenCVSVM车牌识别系统是一种基于计算机视…

Coding面试题之手写线程池

原理图 JDK线程池原理 实现代码 1.线程类&#xff08;PoolThread&#xff09; 这个类用于执行任务队列中的任务。 public class PoolThread extends Thread {private final Queue<Runnable> taskQueue;private boolean isStopped false;private long lastTaskTime …

详解JS的四种异步解决方案:回调函数、Promise、Generator、async/await

同步&异步的概念 在讲这四种异步方案之前&#xff0c;我们先来明确一下同步和异步的概念&#xff1a; 所谓同步(synchronization)&#xff0c;简单来说&#xff0c;就是顺序执行&#xff0c;指的是同一时间只能做一件事情&#xff0c;只有目前正在执行的事情做完之后&am…

HP惠普暗影精灵9P OMEN 17.3英寸游戏本17-cm2000(70W98AV)原装出厂Windows11-22H2系统镜像

链接&#xff1a;https://pan.baidu.com/s/1gJ4ZwWW2orlGYoPk37M-cg?pwd4mvv 提取码&#xff1a;4mvv 惠普暗影9Plus笔记本电脑原厂系统自带所有驱动、出厂主题壁纸、 Office办公软件、惠普电脑管家、OMEN Command Center游戏控制中心等预装程序 所需要工具&#xff1a;3…

【Truffle】四、通过Ganache部署连接

目录 一、下载安装 Ganache&#xff1a; 二、在本地部署truffle 三、配置ganache连接truffle 四、交易发送 除了用Truffle Develop&#xff0c;还可以选择使用 Ganache, 这是一个桌面应用&#xff0c;他同样会创建一个个人模拟的区块链。 对于刚接触以太坊的同学来说&#x…

HTML使用lable将文字与控件进行关联以获取焦点

先养养眼再往下看 注释很详细&#xff0c;直接上代码 <form action""><!-- 第一种方法:用id的方式绑定账户(文字)和输入框 --><label for"zhanghu">账户</label><input "text" id"zhanghu" name"ac…

图论13-最小生成树-Kruskal算法+Prim算法

文章目录 1 最小生成树2 最小生成树Kruskal算法的实现2.1 算法思想2.2 算法实现2.2.1 如果图不联通&#xff0c;直接返回空&#xff0c;该图没有mst2.2.2 获得图中的所有边&#xff0c;并且进行排序2.2.2.1 Edge类要实现Comparable接口&#xff0c;并重写compareTo方法 2.2.3 取…

IDEA的优化配置教程

前言 IDEA 全称 IntelliJ IDEA&#xff0c;是java编程语言开发的集成环境。IntelliJ在业界被公认为最好的java开发工具&#xff0c;尤其在智能代码助手、代码自动提示、重构、JavaEE支持、各类版本工具(git、svn等)、JUnit、CVS整合、代码分析、 创新的GUI设计等方面的功能可以…

【数据结构】深度剖析ArrayList

目录 ArrayLIst介绍 ArrayList实现的接口有哪些&#xff1f; ArrayList的序列化&#xff1a;实现Serializable接口 serialVersionUID 有什么用? 为什么一定要实现Serialzable才能被序列化&#xff1f; transient关键字 为什么ArrayList中的elementData会被transient修…

SQL 聚合函数

前言 SQL中的聚合函数是对一组值执行计算&#xff0c;并返回单个值的函数。 常用的聚合函数有&#xff1a; 函数作用AVG&#xff08;&#xff09;求平均值MAX&#xff08;&#xff09;求最大值MIN&#xff08;&#xff09;求最小值SUM&#xff08;&#xff09;求和COUNT&…

第十三章《搞懂算法:神经网络是怎么回事》笔记

目前神经网络技术受到追捧&#xff0c;一方面是由于数据传感设备、数据通信技术和数据存储技术 的成熟与完善&#xff0c;使得低成本采集和存储海量数据得以成为现实;另一方面则是由于计算能力的大幅提升&#xff0c;如图形处理器(Graphics Processing Unit&#xff0c;GPU)在神…

我在Vscode学OpenCV 色彩空间转换

文章目录 色彩【 1 】色彩空间&#xff08;色域&#xff09;&#xff08;1&#xff09;**RGB色彩空间**与xyz色彩空间的转换将 RGB 色彩空间转换为 XYZ 色彩空间将 XYZ 色彩空间转换为 RGB 色彩空间 &#xff08;2&#xff09;**CMYK色彩空间**&#xff08;3&#xff09;**HSV*…

HTML跳转锚点

跳转锚点适用于本页面和其他页面的任意标签的跳转以及JavaScript的运行 使用方法即给标签加上独一无二的id属性&#xff0c;再使用a标签跳转 如果是其他页面的标签只需加上其他页面的路径&#xff0c;eg.href"其他页面的路径#zp1" id属性的最好不要使用数字开头 <…

vue做的一个一点就转的转盘(音乐磁盘),点击停止时会在几秒内缓慢停止,再次点击按钮可以再次旋转,

先看效果&#xff1a; 代码&#xff1a;主要部分我会红线画出来 css:部分&#xff1a; 源码&#xff1a; vue部分&#xff1a; <template><div class"song-lyric"><div><div class"type"><div class"right">&l…

activiti命令模式与责任链模式

来源&#xff1a;activiti学习&#xff08;七&#xff09;——命令模式和职责链模式在activiti中的应用 文章目录 设计模式命令模式CommandHelloCommandByeCommand ReceiverInvokerClient 职责链模式AbstractHandlerConcreteHandlerAConcreateHandlerB Client activiti中很多ap…