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

AtCoder Beginner Contest 426 实况记录 + A-D 题解

省流:只有 \(1000\) 分,遗憾离场。

这篇文章用来警示大家不要在比赛中犯相同的错误。

A. OS Versions

AI 出来解释一下 \(\texttt{newer than}\) 翻译成“更新”何意味?

请判断版本 \(X\) 与版本 \(Y\) 是否相同或更新。

噢,原来是要 \(X\)\(Y\) 更(四声)新。

语法题,会写条件语句就行。

B. The Odd One Out

语法题,找不同。

C. Upgrade Required

唐得离谱了。

内心 OS:前缀和?差分?

然后发现不对劲。

注意到一共就 \(n\) 台电脑,那就用桶记录数量,每次暴力更新就行。前面归零的桶直接不管,每个桶只被暴力归零一次,时间复杂度 \(O(n)\)

这是入门题啊,我在想什么???

真的怒了!

D. Pop and Insert

很快发现性质:要通过形如 00111111000\(ABA\) 型子串进行线性计算。无非就是把 \(AB\) 推出去,然后再塞回来或把 \(BA\) 推出去,然后塞回来,又或是把两边的 \(A\) 推出去再塞回来,分别用式子计算取最小值就可以了!

不知道为什么写了那么久……

请输入文字
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5; 
int n, a[N], tot, b[N]; 
string s;
void solve() {cin >> n >> s; int cnt1 = 0, cnt0 = 0; tot = 0;  for(auto v : s) cnt1 += (v == '1'), cnt0 += (v == '0'); //cnt1,cnt0分别是1的总数和0的总数int tmp = 1;  for(int i = 1; i < n; i++) {if(s[i] == s[i - 1]) {++tmp; }else {a[++tot] = tmp;  b[tot] = s[i - 1] - '0'; tmp = 1; }}a[++tot] = tmp, b[tot] = s[n - 1] - '0'; int minn = INT_MAX; if(tot == 1) {puts("0"); } else if(tot == 2) {printf("%d\n", min(cnt1, cnt0)); } else {for(int i = 3; i <= tot; i++) {int tmp1 = 0, tmp0 = 0; if(b[i] == 1) {tmp1 += a[i] + a[i - 2], tmp0 += a[i - 1];if(minn > (cnt0 - tmp0) * 2 + cnt1) {minn = (cnt0 - tmp0) * 2 + cnt1; //cout << i<<' '<<minn << endl; }minn = min(minn, cnt0 + (cnt1 - tmp1 + a[i - 2]) * 2); minn = min(minn, cnt0 + (cnt1 - tmp1 + a[i]) * 2);  }else { //mid = 1tmp1 += a[i - 1], tmp0 += a[i] + a[i - 2];if(minn > (cnt1 - tmp1) * 2 + cnt0) {minn = (cnt1 - tmp1) * 2 + cnt0; //cout << i<<' '<<minn << endl; } minn = min(minn, cnt1 + (cnt0 - tmp0 + a[i - 2]) * 2); minn = min(minn, cnt1 + (cnt0 - tmp0 + a[i]) * 2); }}printf("%d\n", minn); }return; 
} 
int main(){int t; cin >> t; while(t--) {solve(); }return 0;
} //AC 100
http://www.hskmm.com/?act=detail&tid=24488

相关文章:

  • 提示词攻击如何防范(2025):从 Indirect Prompt Injection 到 RAG 供应链的分层防御实战
  • 【STM32项目开源】基于STM32的智能养殖场环境监测系统 - 详解
  • 前端学习教程-Axios
  • 『回忆录』返校前夜 230102
  • 断更
  • 前端学习教程-环境配置
  • TypeScript - Ref
  • 20251004 qmd 弱化规约(未完成)
  • 深入解析:人工智能专业术语详解(C)
  • 2025.10.4模拟赛
  • 黄金替罪羊
  • P5301 [GXOI/GZOI2019] 宝牌一大堆
  • 10.4 2025多校冲刺CSP模拟赛2 改题记录
  • 【比赛记录】2025CSP-S模拟赛58
  • 回忆有感
  • 框架高效的系统的演进如何塑造人工智能的深层语义分析能力
  • 『回忆录』高二上第一次月考——压力下的崛起,意料外的突破
  • AutoCAD 2025安装包下载 CAD免费下载 永久免费激活 附详细安装教程
  • 微分和积分的区别
  • 202509_QQ_secret
  • 4 对拍杂谈
  • Matlab R2024b下载及详细安装教程,附永久免费Matlab安装包
  • Luogu P1966
  • 题解:P14036 [PAIO 2025] Rooks
  • 2025/8/26
  • 27 考研初试时间大约是什么时候?
  • 数据结构 - 跳表 Skip List
  • 06. 定时器
  • NOIP之前的复健记录
  • Linux 命令行安装达梦数据库