Codeforces Round 913 (Div. 3) (A-G)
后天就是 I C P C ICPC ICPC杭州站了,今天把之前做的 d i v 3 div3 div3题补一下,打完这场杭州站这赛季除了 E C F i n a l EC\,\,Final ECFinal就结束了,以后应该要多打 c f cf cf比赛练习保持手感,争取下赛季冲一下金牌。
感觉这个 d i v 3 div3 div3的难度还不错,正常状态应该能做到差一题 A K AK AK,思维含量还没有太高,适合我这种fw选手。
A. Rook
题面
题意:一个空的国际象棋棋盘,给你车的初始位置,问你挪动一步这个车可以到达哪些位置。
S o l u t i o n : Solution: Solution:按行按列输出即可,注意初始的点不要输出。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t;
char chr,ch;
void solve(){chr=getchar();while(chr<'a'||chr>'z')chr=getchar();ch=getchar();while(ch<'0'||ch>'9')ch=getchar();n=ch-'0';for(int i=1;i<=8;i++){if(i==n)continue;printf("%c%d\n",chr,i);}for(int i=1;i<=8;i++){if('a'+i-1==chr)continue;printf("%c%d\n",'a'+i-1,n);}
}
int main(){read(t);while(t--)solve();return 0;
}
B. YetnotherrokenKeoard
题面
题意:一个奇怪的键盘,按小写 b b b是删掉目前已经打的最后一个小写字母,按大写 B B B是删掉目前已经打的最后一个大写字母(如果没有则不删,打 b / B b/B b/B不会打出来字符只会删掉字符),给出键盘按下的顺序,求最后打出的内容。
S o l u t i o n Solution Solution:个人做法是从头开始记录目前最后一个小写、大写字母的位置,然后遇到 b / B b/B b/B就删除那个位置的字符,并更新目前最后一个小写、大写字母的位置,写的比较麻烦。赛后看题解发现倒序维护 b / B b/B b/B的数量,遇到大小写直接删除是最快的最方便的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t,len,l[N],L[N],p,P,lst[N],LST[N];
char s[N];
void solve(){scanf("%s",s);len=strlen(s);p=P=0;lst[0]=LST[0]=-1;for(int i=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z'){if(s[i]=='B'){if(P){s[L[P]]=0;P--;}s[i]=0;}else L[++P]=i;}else{if(s[i]=='b'){if(p){s[l[p]]=0;p--;}s[i]=0;}else l[++p]=i;}}for(int i=0;i<len;i++){if(s[i]!=0)putchar(s[i]);}puts("");
}
int main(){read(t);while(t--)solve();return 0;
}
C. Removal of Unattractive Pairs
题面
题意:对于一个字符串可以进行的操作是删掉相邻两个不相同的字符,问最后最少剩下几个字符。
S o l u t i o n Solution Solution:之前做过类似结论的题,对于出现最多的字符的出现次数 t t t,如果 t ≤ ⌊ l e n 2 ⌋ t\le\lfloor\frac{len}{2}\rfloor t≤⌊2len⌋,则不会剩下字符,否则剩下字符数为 t − ( t − ⌊ l e n 2 ⌋ ) t-(t-\lfloor\frac{len}{2}\rfloor) t−(t−⌊2len⌋)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t;
int cnt[30];
char s[N];
void solve(){read(n);for(int i=0;i<=26;i++)cnt[i]=0;for(int i=1;i<=n;i++){s[i]=getchar();while(s[i]<'a'||s[i]>'z')s[i]=getchar();cnt[s[i]-'a']++;}int m=0;for(int i=0;i<=26;i++){if(cnt[i]>m)m=cnt[i];}if(m<=n-m){if(n&1)puts("1");else puts("0");}else printf("%d\n",m-n+m);
}
int main(){read(t);while(t--)solve();return 0;
}
D. Jumping Through Segments
题面
题意:一个坐标轴上有 n n n条线段,从原点 0 0 0开始移动 n n n次,每次移动到第 i i i条线段上,这些移动的最大距离 ≤ k \le k ≤k,求 k k k的最小值。
S o l u t i o n Solution Solution:二分 k k k,判断 k k k是否可行我们通过一个贪心的思想来模拟。
首先对于当前位置 n o w now now,判断其在目标线段的左侧还是右侧,如果在左侧则要向左移动,在右侧则要向右移动,这两种情况是等价的我们以向右移动为例子。
如果向右移动到目标线段的左侧,发现还可以继续移动,这时我们就维护一个 l , r l,r l,r,代表目前可以向左、右走的多余距离。例如上述情况我们的 l = 0 , r = l=0,r= l=0,r=剩余的移动距离。
每当我们移动距离 k k k发现仍然到不了目标线段时,此时就要用到这个多余距离来判断能否通过上一步剩余的距离来使我们移动到目标线段。
对于当前位置正好在目标线段的情况,向左向右的多余距离分别为该位置到左右端点的距离。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t,l[N],r[N];
bool check(int x){int now=0,suml=0,sumr=0,movl=0,movr=0;for(int i=1;i<=n;i++){int cnt=0;if(now<l[i]){cnt=l[i]-now;movr=min(r[i]-l[i],x-cnt);if(movr<0){if(sumr+movr<0)return false;}sumr+=movr,sumr=min(sumr,r[i]-l[i]),suml=0;now=l[i];}else if(now>r[i]){cnt=now-r[i];movl=min(r[i]-l[i],x-cnt);if(movl<0){if(suml+movl<0)return false;}suml+=movl,suml=min(suml,r[i]-l[i]),sumr=0;now=r[i];}else{suml=min(x+suml,now-l[i]),sumr=min(x+sumr,r[i]-now);}}return true;
}
void solve(){read(n);for(int i=1;i<=n;i++)read(l[i]),read(r[i]);int le=0,ri=1e9,mid=0;while(le<ri){int mid=le+ri>>1;if(check(mid))ri=mid;else le=mid+1;}printf("%d\n",ri);
}
int main(){read(t);while(t--)solve();return 0;
}
E. Good Triples
题面
题意:给你 n n n 问你有多少组 ( a , b , c ) (a,b,c) (a,b,c)使得 a + b + c = n a+b+c=n a+b+c=n 并且 a , b , c a,b,c a,b,c的每个位数的和等于 n n n的位数的和。
S o l u t i o n : Solution: Solution:很显然每一位不能有进位,以为数字和相等,所以对每一位都是独立考虑,各个位之间的方案数乘起来即是答案。
对于每一位的答案,赛时是通过观察样例前几个得到的答案,其实推也很好推,不想推一个一个写也写出来了,答案就是 0 + 1 + ⋯ + i 0+1+\dots+i 0+1+⋯+i,对于这一位为 i i i。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t,a[]={1,3,6,10,15,21,28,36,45,55};
void solve(){read(n);ll s=1;while(n){s*=1ll*a[n%10];n/=10;}printf("%lld\n",s);
}
int main(){read(t);while(t--)solve();return 0;
}
F. Shift and Reverse
题面
题意:对于一个序列,你可以做两种操作,第一种是把最后一个放到最前面,第二种是把整个序列倒序,问最少用几次操作可以把数列变为从小到大的。不能变则输出 − 1 -1 −1。
S o l u t i o n Solution Solution:如果把这个序列当成循环序列,不难发现第一种操作没有改变序列,第二种操作只是改变了顺序和倒序,因此如果序列最开始不是顺序或逆序,则不能变为有序数列。
对于可以改变的序列,我们要找到序列的起始点,再分别判断先改变位置再倒序和先倒序再改变位置哪个更优,输出操作次数最少的那个即可。
赛时有点困想出来的时候还有 5 5 5分钟,再加上想出来的方法比较麻烦所以就没做这个题,实际上直接倍长数组就比较方便。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const ll mod = 998244353;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
int n,t,a[N<<1];
void solve(){read(n);for(int i=1;i<=n;i++)read(a[i]),a[i+n]=a[i];int b=1,s=1,now=0,ans=n<<1;for(int i=2;i<=n*2;i++){if(a[i]>a[i-1])b++,s=1;else if(a[i]<a[i-1])s++,b=1;else s++,b++;if(s>=n||b>=n){now=i-n+1;if(s>=n)ans=min(ans,min(1+n-now+1,now));if(b>=n)ans=min(ans,min(n-now+1,2+now-1));}}if(ans!=n*2)printf("%d\n",ans);else puts("-1");
}
int main(){read(t);while(t--)solve();return 0;
}
G. Lights
题面
题意:你有 n n n个灯,有开有闭,想把这些灯全关了,但是灯有个性质是每按一次灯 i i i开关,灯 a i a_i ai的开关也会被按一次,问你最少多少次能把这些灯全关了,不能全关输出 − 1 -1 −1。
S o l u t i o n Solution Solution:把 i i i和 a i a_i ai连出一条边,就会获得一个 n n n个点 n n n条边的一张图,这个图会由若干棵基环树组成,对于每棵树我们先处理他的叶子节点,随后删掉叶子节点,最后剩下一个环,在这个环上我们每次操作都是动偶数个灯,因此如果环上有奇数个灯开着那么就无法全部关闭,输出 − 1 -1 −1。对于环上有两种情况,一种是从起点开始关,一种是从起点的下一个点开始关,这个起点可以随意设置,因为环上是等价的,选出这两种情况关闭数量最少的一个进行关灯即可。
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}x=s*w;
}
const int N = 2e5 + 100;
int T,n,cd[N],e[N],a[N],cc[N];
void solve(){read(n);for(int i=1;i<=n;i++){char chr=getchar();while(chr!='0'&&chr!='1')chr=getchar();cc[i]=cd[i]=chr&15;}vector<set<int> > s(n+1);queue<int> p;int ans=0;for(int i=1,x;i<=n;i++){read(x);e[i]=x;s[x].insert(i);}for(int i=1;i<=n;i++)if(s[i].size()==0)p.push(i);while(!p.empty()){int i=p.front();p.pop();if(cd[i]==1){s[e[i]].erase(i);cd[i]^=1,cd[e[i]]^=1;a[++ans]=i;if(s[e[i]].size()==0)p.push(e[i]);}else{s[e[i]].erase(i);if(s[e[i]].size()==0)p.push(e[i]);}}for(int now=1;now<=n;now++){if(cd[now]){vector<int> c;int sum=1;if(cd[now])c.push_back(1);for(int i=e[now];i!=now;i=e[i]){sum++;if(cd[i])c.push_back(sum);}if(c.size()&1){puts("-1");return ;}int s1=0,s2=c[0]+sum-c[c.size()-1];for(int i=1;i<c.size();i++){if(i&1)s1+=c[i]-c[i-1];else s2+=c[i]-c[i-1];}int st=now;if(s2<=s1)st=e[now];for(int i=st;;i=e[i]){if(cd[i]){a[++ans]=i;cd[i]^=1,cd[e[i]]^=1;}if(e[i]==st)break;}}}printf("%d\n",ans);for(int i=1;i<=ans;i++)printf("%d ",a[i]);puts("");return ;
}
int main(){read(T);while(T--)solve();return 0;
}
相关文章:
Codeforces Round 913 (Div. 3) (A-G)
后天就是 I C P C ICPC ICPC杭州站了,今天把之前做的 d i v 3 div3 div3题补一下,打完这场杭州站这赛季除了 E C F i n a l EC\,\,Final ECFinal就结束了,以后应该要多打 c f cf cf比赛练习保持手感,争取下赛季冲一下金牌。 感觉这…...

CSS——sticky定位
1. 大白话解释sticky定位 粘性定位通俗来说,它就是相对定位relative和固定定位fixed的结合体,它的触发过程分为三个阶段 在最近可滚动容器没有触发滑动之前,sticky盒子的表现为相对定位relative【第一阶段】, 但当最近可滚动容…...

Redis hash表源码解析
1、 整体数据结构 链式hash解决hash冲突、采用渐进式hash来完成扩容过程。 /** 哈希表节点*/ typedef struct dictEntry {// 键void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下个哈希表节点,形成链表struct dictEntry *next;} dictEntry;…...

dll动态链接库【C#】
1说明: 在C#中,dll是添加 【类库】生成的。 2添加C#的dll: (1)在VS中新建一个Windows应用程序项目,并命名为TransferDll。 (2)打开Windows窗体设计器,从工具箱中为窗体…...
Linux 系统设置cpu频率
source_code: https://github.com/emagii/cpufrequtils cpufreq-set - A small tool which allows to modify cpufreq settings.(修改内存频率的工具) cpufreq-set allows you to modify cpufreq settings without having to type e.g. “/sys/devices…...

git基本概念
一、版本控制概念 1.1 什么是版本控制 1.1.1 手动管理文件版本 1.1.2 版本控制软件 概念:版本控制软件是一个用来记录文件发生的变化,以便将来查阅特定版本修订情况的系统,有时也叫“版本控制系统”。通俗的理解就是把手工管理文件版本的方…...
多个HTML属性
在HTML中,属性用于提供有关HTML元素的附加信息。在这篇文章中你将学习多个HTML属性,它们可以增强网站的视觉吸引力。 接下来开始吧!🚀 Accept 属性 您可以将accept属性与<input>元素(仅用于文件类型ÿ…...

基于运算放大器的电压采集电路
一、运算放大器 运放推导的两个重要概念:虚短、虚断。 1、差分放大器 以差分放大器为例进行推导分析。 虚断–运放的"-“端、”“端的引脚电流接近为0; 根据基尔霍夫电流定律可知:iR1iRF,iR2iR3; iR1(Ui1-(V-…...

数字图像处理(实践篇) 十六 基于分水岭算法的图像分割
目录 一 分水岭算法 二 利用OpenCV实现分水岭算法的过程 三 实践 一 分水岭算法 基于任何灰度图像都可以视为地形表面,其中高强度表示山峰和山丘,而低强度表示山谷。首先,开始用不同颜色的水(标签)填充每个孤立的山…...
快速学习PyQt5的高级自定义控件
Pyqt5相关文章: 快速掌握Pyqt5的三种主窗口 快速掌握Pyqt5的2种弹簧 快速掌握Pyqt5的5种布局 快速弄懂Pyqt5的5种项目视图(Item View) 快速弄懂Pyqt5的4种项目部件(Item Widget) 快速掌握Pyqt5的6种按钮 快速掌握Pyqt5的10种容器&…...

Python中读写(解析)JSON文件的深入探究
目录 一、引言 二、如何读取JSON文件 三、如何写入JSON文件 四、如何解析JSON字符串 五、错误处理和异常处理 六、使用第三方库提高效率 七、总结 一、引言 在Python中,我们经常使用JSON(JavaScript Object Notation)格式来存储和传输…...
我获取股票和期货数据的常用函数
记录一下获取数据所使用的函数,以防止遗忘和方便查找。 # 获取掘金的数据 # 需要打开并登陆掘金终端 def get_data_juejin(symbol"bu2112",start"2021-8-1",end"2021-8-30 23:00:00",frequency"1800s",fields"eob,sy…...
高并发场景下的httpClient使用优化技巧
1. 背景 我们有个业务,会调用其他部门提供的一个基于http的服务,日调用量在千万级别。使用了httpclient来完成业务。之前因为qps上不去,就看了一下业务代码,并做了一些优化,记录在这里。 先对比前后:优化…...
用php上传图片到阿里云oss
如果你想自动创建目录并将文件上传到新的目录下,你可以使用阿里云 OSS 的 createObject 方法来实现。下面是更新后的示例代码: php <?php require_once __DIR__ . /vendor/autoload.php; // 引入 SDKuse OSS\OssClient; use OSS\Core\OssException;…...
服务器适合哪些使用场景_Maizyun
服务器适合哪些使用场景 在当今的数字化时代,服务器作为互联网基础设施的核心组件,被广泛应用于各种场景。本文将探讨服务器适合哪些使用场景。 一、Web服务器 Web服务器是服务器中最常见的一种,用于托管和运行网站。它负责处理来自客户端…...

发布“最强”AI大模型,股价大涨,吊打GPT4的谷歌股票值得投资吗?
来源:猛兽财经 作者:猛兽财经 谷歌在AI领域的最新进展,引发投资者关注 在谷歌-C(GOOGL)谷歌-A(GOOG)昨日发布了最新的AI大模型Gemini后,其股价就出现了大幅上涨,更是引发了投资者的密切关注&a…...

年度工作总结怎么写?掌握这些年终总结万能公式,让你的报告出彩无比!
光阴似箭,日月如梭,时间总是不疾不徐地向前奔去,转眼就来到了2023年的最后一个月,12月一到,上班族和打工人又要开始忙活工作总结的事情~ 工作总结,不仅是一年工作的回顾,更是未来规划的起点。你…...
常用Nmap脚本
端口扫描类脚本 Nmap是一款非常流行的端口扫描工具,它可以帮助渗透测试工程师识别目标网络上开放的端口,并提供有关这些端口的详细信息。Nmap还提供了一系列基于脚本的功能,这些脚本可以扩展Nmap的功能,使其能够更深入地探测目标网…...

在pom.xml中添加maven依赖,但是类里面import导入的时候报错
问题: Error:(27, 8) java: 类TestKuDo是公共的, 应在名为 TestKuDo.java 的文件中声明 Error:(7, 23) java: 程序包org.apache.kudu不存在 Error:(8, 23) java: 程序包org.apache.kudu不存在 Error:(9, 23) java: 程序包org.apache.kudu不存在 Error:(10, 30) jav…...
【NEON】学习资料汇总
一、资料链接 Guide : http://www.heenes.de/ro/material/arm/DEN0018A_neon_programmers_guide_en.pdf csdn博文1,基础案例: https://blog.csdn.net/kakasxin/article/details/103912832? csdn博文2,内部函数: ht…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...