Codeforces Round 930 (Div. 2)(A,B,C,D)

比赛链接

C是个交互,D是个前缀和加二分。D还是很难写的。


A. Shuffle Party

题意:

您将得到一个数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an 。最初,每个 1 ≤ i ≤ n 1 \le i \le n 1in 对应 a i = i a_i=i ai=i 。整数 k ≥ 2 k \ge 2 k2 的运算 swap ( k ) \texttt{swap}(k) swap(k) 定义如下:

  • d d d 是不等于 k k k 本身的 k k k 的最大除数 † ^\dagger

然后交换元素 a d a_d ad a k a_k ak

假设您按此顺序对每个 i = 2 , 3 , … , n i=2,3,\ldots, n i=2,3,,n 执行 swap ( i ) \texttt{swap}(i) swap(i) 。在结果数组中查找 1 1 1 的位置。

换句话说,在执行这些操作之后,找到这样的 j j j,满足 a j = 1 a_j = 1 aj=1 † ^\dagger 如果存在整数 z z z 使得 y = x ⋅ z y = x \cdot z y=xz ,则整数 x x x y y y 的除数。

思路:

手玩一下其实比较容易看出来性质。我们只关注 1 1 1 的移动情况,一开始第 1 1 1 个位置和第 2 2 2 个位置交换位置,然后是第 2 2 2 个位置和第 4 4 4 个位置交换位置,移动路径是 1 → 2 → 4 → 8 → … 1\rightarrow2\rightarrow4\rightarrow8\rightarrow\dots 1248

思考一下为什么。因为 2 2 2 是最小的质因数,所以 x x x 第一个被后面交换的数就是 2 ∗ x 2*x 2x。换句话说就是对一个位置,我们交换的是这个位置的最大约数,反过来就是某个数最先会被它的最小倍数交换一次。

因此答案就是 ≤ n \le n n 的最大的 2 2 2 的幂。

code:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;int T,n;int main(){cin>>T;while(T--){cin>>n;cout<<(1<<(int)(log2(n)))<<endl;}return 0;
} 

B. Binary Path

题意:

您将得到一个由0和1填充的 2 × n 2 \times n 2×n 网格。设第 i i i 行与第 j j j 列的交点处的数字为 a i j a_{ij} aij 。在左上角的单元格 ( 1 , 1 ) (1, 1) (1,1) 中有一只蚱蜢,它只能向右或向下跳一个单元格。它希望到达右下角的单元格 ( 2 , n ) (2, n) (2,n)

考虑长度为 n + 1 n+1 n+1 的二进制串,它由写在路径的单元格中的数字组成,而不改变它们的顺序。

您的目标是:

  1. 通过选择任何可用的路径,查找您可以获得的字典序最小的 † ^\dagger 字符串

  2. 找出产生这个字典序最小字符串的路径数。

† ^\dagger 如果两个字符串 s s s t t t 的长度相同,则 s s s 在字典序上小于 t t t 当且仅当在 s s s t t t 不同的第一个位置,字符串 s s s 的元素比 t t t 中的对应元素小。

思路:

考虑怎样才能得到字典序最小的字符串路径。因为我们只能向下走一步,不能向上走,其他时候都是向右走,所以我们只要找到这个拐点就可以了。

考虑在第一行走的时候什么时候要拐弯。如果我们现在在 ( 1 , i ) (1,i) (1,i),那么右边和下边有三种情况。

  1. 右边是 1 1 1,下边是 0 0 0。这时必须走下边。
  2. 右边是 0 0 0,下边是 1 1 1。这时必须走右边。
  3. 右边和下边一样。这时走哪里都可以。

发现我们最保险的行走策略就是贪心地向右走,直到不得不向下走才拐弯。但是这样只能找到一种可行的行走方案。

发现我们在不得不拐弯之前可能有一段是走哪里都可以的点,有一个点就会产生一种可行的行走方案,所以我们统计一下在最保险的行走方案的拐点前面有多少走哪里都可以的拐点个数即可。

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn=2e5+5;int T,n;
string mp[3];int main(){cin>>T;while(T--){cin>>n>>mp[1]>>mp[2];mp[1]=" "+mp[1];mp[2]=" "+mp[2];int cnt=0;string str;for(int i=1;i<=n;i++){if(i==n){str=mp[1].substr(1,i)+mp[2].substr(i,n);cnt++;break;}if(mp[1][i+1]=='0'){if(mp[2][i]=='1')cnt=0;else cnt++;}else {if(mp[2][i]=='0'){str=mp[1].substr(1,i)+mp[2].substr(i,n);cnt++;break;}else cnt++;}}cout<<str<<endl<<cnt<<endl;}return 0;
}

C. Bitwise Operation Wizard

题意:

这是一个交互问题。

有一个秘密序列 p 0 , p 1 , … , p n − 1 p_0, p_1, \ldots, p_{n-1} p0,p1,,pn1 ,它是 { 0 , 1 , … , n − 1 } \{0,1,\ldots,n-1\} {0,1,,n1} 的一个排列。

您需要找到任意两个索引 i i i j j j ,使得 p i ⊕ p j p_i \oplus p_j pipj 最大,其中 ⊕ \oplus 表示 按位异或。

为此,您可以询问查询。

每个查询都具有以下形式:选择任意索引 a a a b b b c c c d d d 0 ≤ a , b , c , d < n 0 \le a,b,c,d \lt n 0a,b,c,d<n )。接下来,检验程序将计算 x = ( p a ∣ p b ) x = (p_a \mid p_b) x=(papb) y = ( p c ∣ p d ) y = (p_c \mid p_d) y=(pcpd) ,其中 ∣ | 表示 按位或。最后,您将收到 x x x y y y 之间的比较结果。换句话说,您被告知是否 x < y x \lt y x<y x > y x \gt y x>y x = y x = y x=y 。请查找任意两个索引 i i i j j j 0 ≤ i , j < n 0 \le i,j \lt n 0i,j<n ),使得 p i ⊕ p j p_i \oplus p_j pipj 在所有此类对中最大,最多使用 3 n 3n 3n 个查询。

如果有多对索引满足条件,则可以输出其中的任何一对。

思路:

先想一想 p i ⊕ p j p_i \oplus p_j pipj 的最大值是什么,不难想到应该是 n − 1 n-1 n1 的最高位二进制位和它所有低位的二进制位全部置为 1 1 1 时的数,形式化地讲,假设 n − 1 n-1 n1 的最高位二进制位是第 x x x 位,那么异或的最大值就是 2 x + 1 − 1 2^{x+1}-1 2x+11

那么我们应该怎么得到这个最大值,也不难想,首先找到一个至少最高位二进制位为 1 1 1 的数,再找到一个正好和它互补的另一个数,这样异或出来就是最大值了。因为第二个数的最高位为 0 0 0,所以这个数一定小于第一个数,再加上第一个数我们可以选择不超过 n − 1 n-1 n1 的数,因此两个数我们一定是可以找得到的。

咋找呢,发现两个相同的数 或的结果 是这个数本身,所以我们令 a = b = p i , c = d = p j a=b=p_i,c=d=p_j a=b=pi,c=d=pj,这就相当于比较 p i , p j p_i,p_j pi,pj 的大小了。因此用这种方法可以用 n − 1 n-1 n1 次比较找到最大或者最小值。我们找到 p p p 中的最大值,这个最大值至少最高位二进制位为 1 1 1,这样我们就找到了其中一个数。

然后问题来了,询问的结果返回的是或的结果,而我们需要的是异或的结果,拿我们怎么找到另一个正好互补的数呢。发现 我们找到的数和另一个数或出来的结果是 2 x + 1 − 1 2^{x+1}-1 2x+11 的所有满足条件的另一个数中,正好互补的那个数是最小的

所以我们可以先把所有满足 或的结果是最大值 的另一个数找出来,然后再在这些数里找最小值即可。

code:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;int T,n;
char st;int main(){cin>>T;while(T--){cin>>n;int idx=0;//找到n-1的位置 for(int i=1;i<n;i++){cout<<"? "<<idx<<" "<<idx<<" "<<i<<" "<<i<<endl;cin>>st;if(st=='<')idx=i;}vector<int> a;a.push_back(0);for(int i=0;i<n;i++){if(i==idx)continue;cout<<"? "<<idx<<" "<<a[0]<<" "<<idx<<" "<<i<<endl;cin>>st;if(st=='<'){a.clear();a.push_back(i);}else if(st=='=')a.push_back(i);}int idx2=a[0];for(auto x:a){cout<<"? "<<idx2<<" "<<idx2<<" "<<x<<" "<<x<<endl;cin>>st;if(st=='>')idx2=x;}cout<<"! "<<idx<<" "<<idx2<<endl;}return 0;
}

D. Pinball

题意:

有一个长度为 n n n 的一维网格。网格的第 i i i 个单元格包含字符 s i s_i si ,该字符为“<”或“>”。当弹球被放置在其中一个单元上时,它根据以下规则移动:

  • 如果弹球在第 i i i 个单元格上且 s i s_i si 是’<‘,那么弹球在下一秒钟向左移动一个单元格。如果 s i s_i si 是’>',它将向右移动一个单元格。

  • 在弹球移动后,字符 s i s_i si 被反转(比如如果 s i s_i si 曾经是’<‘,它就会变成’>',反之亦然)。

  • 弹球从左边界或从右边界离开网格时停止移动。

您需要回答 n n n独立查询。在第 i i i 个查询中,将在第 i i i 个单元格上放置一个弹球。请注意,我们总是在初始网格上放置一个弹球。

对于每个查询,计算弹球离开网格所需的秒数。可以证明,弹球总是在有限的步数内离开网格。

思路:

看视频可能会比较好理解

对傻逼二分一点好感都没有。之前调一道二分题调到凌晨三四点调不出来,中间父母一直在吵架,完全没心情想题,结果觉也没睡好,白天还要赶火车,还晕车。

先手玩一下,发现弹球向一个方向走的时候,如果箭头都是顺着它行走的方向,那么弹球就可以一直走下去,直到遇到第一个反方向的箭头(左边的小于号,右边的大于号),它就会被打回来,这时,小球之前走过的路线因为刚刚方向翻转了,小球就可以畅通无阻地走回起点,然后再向起点另一边走。而且第一个反方向的箭头也被消除了,加入到了前面那段畅通无阻的路线,等到下次再走这一边的时候就可以向右边更远的地方行走。

小球就这样来来回回地走,左边每有一个大于号,小球就会在左边被弹回来一次,同理,右边每有一个小于号,小球就会在右边被弹回来一次,弹来弹去,肯定有一边的反方向箭头不够用,然后小球就会在这边走出边界。那么在哪边走出去呢?两边各消耗了几个反方向箭头?

不妨设左边的大于号的个数为 gn \texttt{gn} gn,右边小于号的个数为 ln \texttt{ln} ln。若弹球最后从左边界弹出,说明右边的小于号很多。若:

  1. 初始方向向右,那么需要满足 l n > g n ln>gn ln>gn,这时实际会使用 g n + 1 gn+1 gn+1 个右边小于号。
  2. 初始方向向左,那么需要满足 l n > = g n ln>=gn ln>=gn,这时实际会使用 g n gn gn 个右边小于号。

其他情况就是从右边界弹出的情况,若:

  1. 初始方向向左,那么需要满足 g n > l n gn>ln gn>ln,这时实际会使用 l n + 1 ln+1 ln+1 个右边小于号。
  2. 初始方向向右,那么需要满足 g n > = l n gn>=ln gn>=ln,这时实际会使用 l n ln ln 个右边小于号。

知道了来回弹了几次,从哪个边界出去了,那么怎么计算步数呢?

我们看一下小球移动的路径,发现路径可以看成:若干个 小球从起点走到一边的反方向箭头再回到起点 的段相接,最后再加上一个从起点走出边界的段即可。而小球从起点走到某个方向的反方向箭头,然后再回到起点的长度,其实就相当于两倍的起点到这个箭头的距离。请添加图片描述

假设我们向右走,起点在 i i i,右边的第 j j j 个反方向箭头位置为 i d x j idx_j idxj,实际使用了 l n ln ln 个箭头。单个的箭头我们可以直接算,就是 i d x j − i idx_j-i idxji。如果多个箭头同时计算,相当于 ∑ k i d x k − i ∗ l n \sum_kidx_k-i*ln kidxkiln。我们可以使用前缀和维护前面的东西,这样就可以 O ( 1 ) O(1) O(1) 查询一边的多个箭头的路径。起点右边也可以这样处理(可以正着算前缀和,也可以反着算也就是后缀和 ,我是反着来算的,这样写法上比较对称),这样两边各查询一遍,再加上从起点走出边界的那段就是答案了。

不过处理出了前缀和,我们知道有一边可能用不掉所有箭头,我们需要找到实际用到的箭头的位置,查询它的前缀和才对,这就需要二分查找了。

code:

这里第47行重载了二分查找的比较函数,从而实现了自定义规则的二分查找。具体用法可以参考:讲解

这里的 [](ll val,ll ele)->bool{return ele<val;} 实现的功能 是二分查找第一个小于 v a l u e value value 的位置,然后后面 -sg-1 得到的就是最后一个大于等于 v a l u e value value 的位置。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=5e5+5;
typedef long long ll;int T,n;
char str[maxn];ll sl[maxn],sg[maxn],s1[maxn],s2[maxn];int main(){cin>>T;while(T--){cin>>n>>str+1;sl[0]=s1[0]=sg[n+1]=s2[n+1]=0;for(int i=1;i<=n;i++){sl[i]=sl[i-1]+(str[i]=='<');s1[i]=s1[i-1]+(str[i]=='<')*i;}for(int i=n;i>=1;i--){sg[i]=sg[i+1]+(str[i]=='>');s2[i]=s2[i+1]+(str[i]=='>')*(n-i+1);}//		for(int i=1;i<=n;i++)cout<<sl[i]<<" \n"[i==n];
//		for(int i=1;i<=n;i++)cout<<sg[i]<<" \n"[i==n];
//		for(int i=1;i<=n;i++)cout<<s1[i]<<" \n"[i==n];
//		for(int i=1;i<=n;i++)cout<<s2[i]<<" \n"[i==n];
//		cout<<endl;for(ll i=1,ln,gn,idx;i<=n;i++){ln=sl[n]-sl[i];//右边小于号数量 gn=sg[1]-sg[i];//左边大于号数量 if((str[i]=='>' && ln>gn) || (str[i]=='<' && ln>=gn)){//右边小于号太多了,从左边界弹出 if(str[i]=='>')ln=gn+1;//实际用到的小于号数量 else ln=gn;idx=lower_bound(sl+i,sl+n+1,ln+sl[i])-sl;cout<<(s1[idx]-s1[i]-1ll*i*ln+s2[1]-s2[i]-1ll*(n-i+1)*gn)*2+i<<" ";}else {if(str[i]=='<')gn=ln+1;//实际用到的大于号数量 else gn=ln;idx=upper_bound(sg+1,sg+i+1,gn+sg[i],[](ll val,ll ele)->bool{return ele<val;})-sg-1;cout<<(s1[n]-s1[i]-1ll*i*ln+s2[idx]-s2[i]-1ll*(n-i+1)*gn)*2+(n-i+1)<<" ";}}cout<<endl;}return 0;
}

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

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

相关文章

【Linux】从零认识进程 — 中下篇

送给大家一句话&#xff1a; 人一切的痛苦&#xff0c;本质上都是对自己无能的愤怒。而自律&#xff0c;恰恰是解决人生痛苦的根本途径。—— 王小波 从零认识进程 1 进程优先级1.1 什么是优先级1.2 为什么要有优先级1.3 Linux优先级的特点 && 查看方式1.4 其他概念 2…

目标检测的指标评估

目标检测模型的评价指标主要用于衡量模型的性能&#xff0c;特别是它在定位和识别目标方面的准确性。以下是一些常见的评价指标&#xff1a; 1. 精确度 (Precision): 表示检测到的目标中&#xff0c;正确检测到的目标所占的比例。精确度高意味着模型产生的误报&#xff08;错误…

通过jsDelivr实现Github的图床CDN加速

最近小伙伴们是否发现访问我的个人博客http://xiejava.ishareread.com/图片显示特别快了&#xff1f; 我的博客的图片是放在github上的&#xff0c;众所周知的原因&#xff0c;github访问不是很快&#xff0c;尤其是hexo博客用github做图床经常图片刷不出来。一直想换图床&…

Oracle 使用OGG(Oracle GoldenGate) 实现19c PDB与MySQL5.7 数据同步

OGG 是一种基于日志的结构化数据复制软件&#xff0c;它通过解析源数据库在线日志或归档日志获得数据的增删改变化。 OracleMysqlIP address192.168.80.100192.168.80.16DB version19.2.05.7host nametempmysql OS version&#xff1a; CentOS 7.9 一&#xff0c;Oracle 服务…

机器学习基础知识面经(个人记录)

朴素贝叶斯 特征为理想状态下的独立同分布&#xff0c;作为机器学习的重要基石和工具 由贝叶斯公式推导而来 是后验概率&#xff1a;在B发生的条件下A发生的概率。 是似然概率: 在 发生的条件下 发生的概率。 是先验概率: 发生的概率&#xff0c;而不考虑 的影响。 是…

静态综合实验

一.搭建拓扑结构 1.根据拓扑结构可以把网段分成14个网段&#xff0c;根据192.168.1.0/24可以划分出ip地址和环回地址 其中环回r1分别是 192.168.1.32/27 192.168.1.32/28 192.168.1.48/28 2.划分完后如图&#xff1a; 二.配置IP地址 注意&#xff1a;为了避免错误&#…

vulnhub prime1通关

目录 环境安装 1.信息收集 收集IP 端口扫描 目录扫描 目录文件扫描 查找参数 打Boss 远程文件读取 木马文件写入 权限提升 方法一 解锁密钥 方法二&#xff1a; linux内核漏洞提权 总结 环境安装 Kali2021.4及其prime靶机 靶机安装&#xff1a;Prime: 1 ~ Vul…

今天聊聊新零售

一、什么是新零售&#xff1f; 2016年&#xff0c;在杭州举行的“云栖大会”上&#xff0c;马云发表了讲话&#xff0c;首次提出了“新零售”这一概念。 1.1 新零售概念 新零售&#xff0c;英文是New Retailing&#xff0c;新零售是对人货场的重构。人是消费者、销售人员、…

Python 从0开始 一步步基于Django创建项目(3)使用Admin site管理数据模型

本文内容建立在《Python 从0开始 一步步基于Django创建项目&#xff08;2&#xff09;创建应用程序&数据模型》的基础上。 Django提供的admin site&#xff0c;使得网站管理员&#xff0c;能够轻松管理网站的数据模型。 本文首先创建‘管理员账户’&#xff0c;即超级用户…

Linux:Jenkins全自动持续集成持续部署(3)

在上一章部署好了之后&#xff0c;还需要点击一下才能进行部署&#xff0c;本章的效果是&#xff1a;当gitlab上的代码发生了变化后&#xff0c;我们不需要做任何事情不需要去点击构建按钮&#xff0c;Jenkins直接自动检测变化&#xff0c;然后自动去集成部署Linux&#xff1a;…

利用免费 GPU 部署体验大型语言模型推理框架 vLLM

vLLM简介 vLLM 是一个快速且易于使用的 LLM&#xff08;大型语言模型&#xff09;推理和服务库。 vLLM 之所以快速&#xff0c;是因为&#xff1a; 最先进的服务吞吐量 通过 PagedAttention 高效管理注意力键和值内存 连续批处理传入请求 使用 CUDA/HIP 图快速模型执行 量…

C#,图论与图算法,用于检查给定图是否为欧拉图(Eulerian Graph)的算法与源程序

1 欧拉图 欧拉图是指通过图(无向图或有向图)中所有边且每边仅通过一次通路, 相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph), 具有欧拉通路而无欧拉回路的图称为半欧拉图。 对欧拉图的一个现代扩展是蜘蛛图,它向欧拉图增加了可以连接的存在点。 这给…

vue3对openlayers使用(加高德,天地图图层)

OpenLayers认识 WebGIS四大框架&#xff1a; Leaflet、OpenLayers、Mapbox、Cesium OpenLayers 是一个强大的开源 JavaScript 地图库&#xff0c;专注于提供可嵌入网页的交互式地图体验。作为一款地理信息系统&#xff08;GIS&#xff09;的前端开发工具&#xff0c;OpenLaye…

docker 和K8S知识分享

docker知识&#xff1a; 比如写了个项目&#xff0c;并且在本地调试没有任务问题&#xff0c;这时候你想在另外一台电脑或者服务器运行&#xff0c;那么你需要在另外一台电脑或者服务器配置相同的软件&#xff0c;比如数据库&#xff0c;web服务器&#xff0c;必要的插件和库等…

使用 chezmoi vscode, 管理你的 dotfiles

什么是 dotfiles In Unix-like operating systems, any file or folder that starts with a dot character (for example, /home/user/.config), commonly called a dot file or dotfile. 任何以 . 开头去命名的文件或者目录都可以称为 dotfile, 在 Unix-like 系统一般用的比较…

Mysql数据库深入理解

目录 一、什么是数据库 二、Mysql基本架构图 1.Mysql客户端/服务器架构 2.客户端与服务器的连接过程 3.服务器处理客户端请求 4.一条查询SQL执行顺序 4.1连接器 4.2查询缓存 4.3解析器 4.4执行器 4.4.1预处理阶段 4.4.2优化阶段 4.4.3执行阶段 5.一条记录如何存…

使用 Flink + Faker Connector 生成测试数据压测 MySQL

博主历时三年精心创作的《大数据平台架构与原型实现&#xff1a;数据中台建设实战》一书现已由知名IT图书品牌电子工业出版社博文视点出版发行&#xff0c;点击《重磅推荐&#xff1a;建大数据平台太难了&#xff01;给我发个工程原型吧&#xff01;》了解图书详情&#xff0c;…

VMware Workstation Pro 17虚拟机超级详细搭建(含redis,nacos,docker)(一)

今天从零搭建一下虚拟机的环境&#xff0c;把nacos&#xff0c;redis等微服务组件还有数据库搭建到里面&#xff0c;首先看到的是我们最开始下载VMware Workstation Pro 17 之后的样子&#xff0c;总共一起应该有三部分因为篇幅太长了 下载地址 : VMware - Delivering a Digit…

Mora: Enabling Generalist Video Generation via A Multi-Agent Framework

目录 论文地址&#xff1a;Mora: Enabling Generalist Video Generation viaA Multi-Agent Framework github地址&#xff1a;https://github.com/lichao-sun/Mora 一、摘要 &#xff08;1&#xff09;Mora 的主要特点&#xff1a; &#xff08;2&#xff09;Mora的应用场景…

Qt/C++通用跨平台Onvif工具/支持海康大华宇视华为天地伟业等/云台控制/预置位管理/工程调试利器

一、前言 在安防视频监控行业&#xff0c;Onvif作为国际标准&#xff0c;几乎主要的厂商都支持&#xff0c;不仅包含了国内的厂商&#xff0c;也包括主要的国际厂商&#xff0c;由于有了这个标准的存在&#xff0c;使得不同设备不同安防平台之间&#xff0c;能够接入各个厂家的…