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

CSP-S模拟28

T1:挑战(challenge)

思路:

说是签到题(但是疑似没有T2简单?好吧,其实这题也不难,只是我傻而已)

只需要把所有的矿车挪到有矿车的最后一列,贪心和dp都可以,我写的dp。不难发现dp有两种状态转移过来,如下图,取最小值就好了。最后的答案就是到最后一列的值减去最前一列的值,若最前一列两个都是要加一。因为直接做差求出来的是从最前列的某个格到最后列的某个格的最小值,但是若最前列两个都是的话,那得先把两个合并成一个,所以要加一。

image

代码:

$code$
#include<iostream>
using namespace std;
const int N=2e5+5;
int T,dp[N][2],n;string s[2];
int main(){
//	freopen("challenge.in","r",stdin);
//	freopen("challenge.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){int minn=1e9,maxn=-1;cin>>n>>s[0]>>s[1];s[0]=' '+s[0];s[1]=' '+s[1];for(int i=1;i<=n;i++){if(s[1][i]=='*'||s[0][i]=='*') maxn=max(maxn,i),minn=min(minn,i);for(int j=0;j<=1;j++) dp[i][j]=min(dp[i-1][j]+1+(s[1-j][i]=='*'),dp[i-1][1-j]+2);}cout<<(min(dp[maxn][0],dp[maxn][1])-min(dp[minn][0],dp[minn][1])+(s[0][minn]==s[1][minn]))<<'\n';}return 0;
}

T2:染色(color)

思路:

显然,从前往后便利,统计每种颜色出现的次数,若某一时刻不符合要求,就将该时刻的\(B\)(一定是\(B\))与最后面的\(R\)交换即可。当蓝色的次数多于红色时,显然无解。

我是弱智,多测没清空,但是为什么样例能过啊喂?!

代码:

$code$
#include<iostream>
using namespace std;
const int N=2e5+5;
int T,n,s[N],cnt0,cnt1,num0,num1,ans,pos[N],mk[N];char ch;
int main(){
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;ans=cnt0=cnt1=num0=num1=0;for(int i=1;i<=n;i++){cin>>ch;if(ch=='R') s[i]=1,cnt1++,pos[cnt1]=i;else s[i]=0,cnt0++;	}if(cnt0>cnt1){cout<<-1<<'\n';continue;}for(int i=1;i<=n;i++){if(s[i]==1) num1++;else num0++;if(num0>num1){for(int j=cnt1;j>=1;j--){if(pos[j]!=-1){swap(s[pos[j]],s[i]),ans++;pos[j]=-1;break;}}num0--,num1++;}}cout<<ans<<'\n';}return 0;
}/*
3
3
RBB
9
RBBRBBRRR
12
BBBBBBRRRRRR*/

T3:海(summer)

思路:

题外话: 不知道为什么海的文件名是summer。以及突然想起来《她的山她的海》还有那句“陈景深,喜欢山还是喜欢海?”,“喜欢__”(自己猜)。完了,不小心说多了......

我们可以求出\(f_i\)表示使用\(i\)次魔法最多能摧毁多少根柱子。显然,每次使用魔法的区间都包含全局最大值是不劣的,于是我们可以根据全局最大值将原序列分为若干段,求出每一段的长度\(len_i\)。于是,问题幻化为:给定一个序列\(len\),每次可以选择一个或相邻两个数,求\(i\)次操作后选择的和最大为多少。然后就跟此题相似了(虽然我没做)。

代码:

$code$
#include<iostream>
#include<queue>
using namespace std;
const int N=5e5+5;
int n,m,maxn=-1,sum,cnt,tot,vis[N],f[N],h[N],lst=1,a;priority_queue<pair<int,pair<int,int> > > q;
struct node{int len,lst,nxt;}p[N];
int main(){
//	freopen("summer.in","r",stdin);
//	freopen("summer.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++) cin>>h[i],maxn=max(maxn,h[i]);for(int i=1;i<=n;i++){if(h[i]==maxn){sum++;p[++cnt].len=i-lst;p[cnt].lst=cnt-1;p[cnt].nxt=cnt+1;lst=i+1;}}p[++cnt].len=n+1-lst;p[cnt].lst=cnt-1;p[cnt].nxt=0;for(int i=1;i<cnt;i++) q.push({p[i].len+p[i+1].len,{i,i+1}});while(!q.empty()){auto u=q.top();q.pop();int x=u.second.first,y=u.second.second;if(vis[x]||vis[y]) continue;vis[x]=vis[y]=1;f[tot+1]=f[tot]+u.first+1;tot++;p[p[x].lst].nxt=p[y].nxt;p[p[y].nxt].lst=p[x].lst;//合并两个区间 q.push({p[p[x].lst].len+p[p[y].nxt].len,{p[x].lst,p[y].nxt}});p[x]={0,0,0};p[y]={0,0,0};}while(tot<sum) f[tot+1]=f[tot]+1,tot++;while(m--){cin>>a;int b=lower_bound(f+1,f+1+tot,a)-f;cout<<b<<' ';}return 0;
}
/*
6 3
3 1 2 3 2 3
2 5 6*/

T4:

一如既往地没有T4,别问,问就是不会,而且T4太长了。

后言:

一段歌词
天地大还有这酒家
待她笑颜如花 笔墨山河入画
金戈铁马且不敌你灼灼风华
身影恣意潇洒 四海为家
抵不过他一缕牵挂
一肆酒家
http://www.hskmm.com/?act=detail&tid=27445

相关文章:

  • 形式化验证提升RSA性能与部署效率
  • AI元人文的硅基实现可行性Ai研究报告
  • 利用linux系统自带的cron 定时备份数据库,不需要写代码了
  • centos服务器实时备份
  • 666
  • P14150 不动鸣神,恒常乐土
  • python本地生成验证码图片
  • CentOS 7 一键安装 vsftpd 并创建可登录 FTP 用户 test - 教程
  • 【完结】-固态硬盘ssd
  • 破解工地防盗难题:如何利用国标GB28181视频平台EasyCVR实现视频监控统一管理?
  • autogen论文解读 - Sun
  • 高效仿真:功耗与散热攻略
  • Vue的nextTick函数作用
  • #6515. 「雅礼集训 2018 Day10」贪玩蓝月
  • 公告
  • 车企数据治理平台化实战:从数据孤岛到全链路治理的架构演进
  • 磁盘的管理
  • 完整教程:Java中的缓存机制与分布式缓存实现!
  • jsconfig.json-vscode或cursor ctrl点击@路径,快速到达
  • C# 弃元模式:从语法糖到性能利器的深度解析
  • 2025钣金加工厂家最新推荐榜:精密工艺与定制服务口碑之选
  • python查询数据信息,分析前了解表格结构
  • 减少磁盘延迟的方法
  • AutoCAD 2025 CAD 安装包中文永久免费免激活破解版下载 附图文安装教程
  • nmcli修改ip地址
  • 静态库与动态库:开发者必知的底层逻辑与实践技巧
  • 从C到pwn入门
  • 基于MATLAB的三轴航天器姿态控制的仿真
  • golang基础语法(四) 数组 - 教程
  • for循环s.length()-1,s为空时的一直执行循环的问题