尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
AtCoder-arc227_a Fermat Point of Binary Strings 题解
Solution首先考虑distdistdist的本质是什么。显然有用的交换只有01和10。这可以看成不断移动SSS中的1。由于不交换111的相对顺序保持不变。设SSS中1的位置为s1s2⋯sns_1s_2\dotss_ns1​s2​⋯sn​TTT中1的位置为t1t2⋯tnt_1t_2\dotst_nt1​t2​⋯tn​。那么dist(S,T)∑i1n∣si−ti∣ dist(S,T)\sum_{i1}^n |s_i-t_i|dist(S,T)i1∑n​∣si​−ti​∣设A,B,C,XA,B,C,XA,B,C,X的1的位置序列分别为{ai},{bi},{ci},{xi}\{a_i\},\{b_i\},\{c_i\},\{x_i\}{ai​},{bi​},{ci​},{xi​}。题目转化为求{xi}\{x_i\}{xi​}使得∑i1n∣ai−xi∣∣bi−xi∣∣ci−xi∣ \sum_{i1}^n |a_i-x_i||b_i-x_i||c_i-x_i|i1∑n​∣ai​−xi​∣∣bi​−xi​∣∣ci​−xi​∣最小。因此ximedian⁡(ai,bi,ci)x_i\operatorname{median}(a_i,b_i,c_i)xi​median(ai​,bi​,ci​)。由于{ai},{bi},{ci}\{a_i\},\{b_i\},\{c_i\}{ai​},{bi​},{ci​}都单增求得的{xi}\{x_i\}{xi​}也单增符合题意。Code#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)usingnamespacestd;constintN4e55;intn,a[N][3];longlongtot;string s,ans;signedmain(){cinn;rep(i,0,3){cins;intcnt0;rep(j,0,n*2)if(s[j]1)a[cnt][i]j;}ans.assign(2*n,0);rep(i,0,n){sort(a[i],a[i]3);ans[a[i][1]]1;totabs(a[i][0]-a[i][1])abs(a[i][2]-a[i][1]);}couttot\nans;return0;}
RELATED

相关推荐

ExplorerPatcher:把 Windows 11 换回 Windows 10 任务栏、开始菜单与窗口切换器

ExplorerPatcher:把 Windows 11 换回 Windows 10 任务栏、开始菜单与窗口切换器

ExplorerPatcher:把 Windows 11 换回 Windows 10 任务栏、开始菜单与窗口切换器 【免费下载链接】ExplorerPatcher This project aims to enhance the working environment on Windows 项目地址: https://gitcode.com/GitHub_Trending/ex/ExplorerPatcher 你…

📅 2026/10/7 2:37:03
shadPS4 使用指南:在电脑上跑通 PS4 游戏的 6 步实操与踩坑自查

shadPS4 使用指南:在电脑上跑通 PS4 游戏的 6 步实操与踩坑自查

shadPS4 使用指南:在电脑上跑通 PS4 游戏的 6 步实操与踩坑自查 【免费下载链接】shadPS4 PlayStation 4 emulator for Windows, Linux, macOS and FreeBSD written in C 项目地址: https://gitcode.com/GitHub_Trending/sh/shadPS4 shadPS4 是一个用 C 编写…

📅 2026/10/7 2:37:03
AtCoder-arc227_b Know Your Place 题解

AtCoder-arc227_b Know Your Place 题解

Solution 我们从小到大依次枚举值 xxx 并将所有 xxx 插入序列。初始时序列为空。 设当前值为 xxx 的数出现了 yyy 次。由于目前序列里所有数都 <x<x<x&#xff0c;我们一定会在当前序列的第 xxx 位后插入 yyy 个 xxx。如果答案序列长度不够则一定无解。 模拟上述过程&…

📅 2026/10/7 2:37:03
MORE NEWS

更多资讯

📰

基于编辑距离的VB文本相似行比对工具实现

先交代个背景&#xff1a;上个月帮朋友处理两批业务导出数据&#xff0c;一份是前一天的系统快照&#xff0c;一份是后一天的&#xff0c;总共一万多行&#xff0c;行长几乎一样&#xff0c;区别就躲在某些字段里。拿Beyond Compare直接比&#xff0c;全是红的&#xff1b;拿Di…

📰

LM358运放打造纯硬件呼吸灯:从原理到调试的完整指南

1. 从一个经典需求说起&#xff1a;为什么要用LM358做呼吸灯呼吸灯这个效果&#xff0c;做过电子产品的人都不陌生——手机上的通知灯、路由器上的状态灯、笔记本的电源键&#xff0c;那种一亮一暗、像人在呼吸一样柔和渐变的光效&#xff0c;背后其实就是一个简单的模拟电路在…

📰

LM358呼吸灯电路从入门到精通:三角波振荡器原理与调试指南

1. 为什么LM358是呼吸灯入门的"黄金搭档"呼吸灯这个效果&#xff0c;很多人第一次见是在笔记本电脑的电源指示灯上——一亮一暗&#xff0c;像人在呼吸。看起来简单&#xff0c;但真动手做&#xff0c;你会发现它比"LED闪烁"复杂得多。闪烁只需要高低电平切…

📰

教育站群文件上传下载:分布式存储与负载均衡实战

做教育行业站群&#xff0c;越做到后面越会发现&#xff0c;文件上传下载这件事&#xff0c;远远不是写个MultipartFile接参那么简单。举一个真实场景&#xff1a;一套面向中小学的在线学习平台群&#xff0c;下面挂着主站、学科子站、题库站、作业站、直播回放站&#xff0c;课…

📰

Git实战:理解工作流,搞定提交、分支合并与SSH认证排坑

很多初学者学Git的时候&#xff0c;最容易犯的一个错误就是去背命令清单。git add、git commit、git push背得滚瓜烂熟&#xff0c;可真到项目里遇到提交错文件、分支合并不了、SSH认证失败&#xff0c;整个人就懵了。我当初也是这么过来的&#xff1a;本地写了好几天的代码&am…

📰

TensorFlow+CNN预测股票:从K线特征到滚动回测实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬