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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深度学习十大算法之长短时记忆网络(LSTM)

一、长短时记忆网络&#xff08;LSTM&#xff09;的基本概念 长短时记忆网络&#xff08;LSTM&#xff09;是一种特殊类型的循环神经网络&#xff08;RNN&#xff09;&#xff0c;主要用于处理和预测序列数据的任务。LSTM由Hochreiter和Schmidhuber于1997年提出&#xff0c;其…

41-Vue-webpack基础

webpack基础 前言什么是webpackwebpack的基本使用指定webpack的entry和output 前言 本篇开始来学习下webpack的使用 什么是webpack webpack: 是前端项目工程化的具体解决方案。 主要功能&#xff1a;它提供了友好的前端模块化开发支持&#xff0c;以及代码压缩混淆、处理浏览…

海康威视-AIOT的业务转型

海康威视的转型和定位为智能物联网&#xff08;AIoT&#xff09;解决方案和大数据服务的提供商。 公司不仅仅聚焦于其核心的视频监控业务&#xff0c;而且正在积极拓展到新的技术领域和市场。通过专注于物联感知、人工智能、大数据等技术的创新&#xff0c;对未来技术发展方向的…

golang import引用项目下其他文件内函数

初始化项目 go mod init [module名字] go mod init project 项目结构 go mod 文件 代码 需要暴露给外界使用的变量/函数名必须大写 在main.go中引入&#xff0c;当前项目模块名/要引用的包名 package mainimport (// 这里的路径开头为项目go.mod中的module"project/…

微信小程序----猜数字游戏.

目标&#xff1a;简单猜字游戏&#xff0c;系统随机生成一个数&#xff0c;玩家可以猜8次&#xff0c;8次未猜对&#xff0c;游戏结束&#xff1b;未到8次猜对&#xff0c;游戏结束。 思路和要求&#xff1a; 创建四个页面&#xff0c;“首页”&#xff0c;“开始游戏”&#…

hadoop基本概念

一、概念 Hadoop 是一个开源的分布式计算和存储框架。 Hadoop 使用 Java 开发&#xff0c;所以可以在多种不同硬件平台的计算机上部署和使用。其核心部件包括分布式文件系统 (Hadoop DFS&#xff0c;HDFS) 和 MapReduce。 二、HDFS 命名节点 (NameNode) 命名节点 (NameNod…

STM32 | Systick定时器(第四天)

STM32 第四天 一、Systick定时器 1、定时器概念 定时器:是芯片内部用于计数从而得到时长的一种外设。 定时器定时长短与什么有关???(定时器定时长短与频率及计数大小有关) 定时器频率换算单位:1GHZ=1000MHZ=1000 000KHZ = 1000 000 000HZ 定时器定时时间:计数个数…

Django缓存(二)

一、视图缓存 Django的缓存可以设置缓存指定的视图,具体方式使用django.views.decorators.cache.cache_page, 方法有2种方式: 装饰器:以方法以装饰器的方式使用 from django.views.decorators.cache import cache_page@cache_page(60 * 15,cache="default") def…

CRC计算流程详解和FPGA实现

一、概念 CRC校验&#xff0c;中文翻译过来是&#xff1a;循环冗余校验&#xff0c;英文全称是&#xff1a;Cyclic Redundancy Check。是一种通过对数据产生固定位数的校验码&#xff0c;以检验数据是否存在错误的技术。 其主要特点是检错能力强、开销小&#xff0c;易于电路实…

【prompt六】MaPLe: Multi-modal Prompt Learning

1.motivation 最近的CLIP适应方法学习提示作为文本输入,以微调下游任务的CLIP。使用提示来适应CLIP(语言或视觉)的单个分支中的表示是次优的,因为它不允许在下游任务上动态调整两个表示空间的灵活性。在这项工作中,我们提出了针对视觉和语言分支的多模态提示学习(MaPLe),以…

“架构(Architecture)” 一词的定义演变历史(依据国际标准)

深入理解“架构”的客观含义&#xff0c;不仅能使IT行业的系统架构设计师提升思想境界&#xff0c;对每一个积极的社会行动者而言&#xff0c;也具有长远的现实意义&#xff0c;因为&#xff0c;“架构”一词&#xff0c;不只限于IT系统&#xff0c;而是指各类系统(包括社会系统…

python(django)之流程接口管理后台开发

1、在models.py中加入流程接口表和单一接口表 代码如下&#xff1a; from django.db import models from product.models import Product# Create your models here.class Apitest(models.Model):apitestname models.CharField(流程接口名称, max_length64)apitester model…

C#,图论与图算法,计算图(Graph)的岛(Island)数量的算法与源程序

1 孤岛数 给定一个布尔矩阵,求孤岛数。一组相连的1形成一个岛。例如,下面的矩阵包含5个岛: 在讨论问题之前,让我们先了解什么是连接组件。无向图的连通分量是一个子图,其中每两个顶点通过一条路径相互连接,并且不与子图外的其他顶点连接。 所有顶点相互连接的图只有一个…

java数据结构与算法基础-----字符串------正则表达式---持续补充中

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 目前校招的面试&#xff0c;经常会遇到各种各样的有关字符串处理的算法。掌…

【docker系列】深入理解 Docker 容器管理与清理

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

JVM——运行时数据区

前言 由于JAVA程序是交由JVM执行的&#xff0c;所以我们所说的JAVA内存区域划分也是指的JVM内存区域划分&#xff0c;JAVA程序具体执行的过程如下图所示。首先Java源代码文件会被Java编译器编译为字节码文件&#xff0c;然后由JVM中的类加载器加载各个类的字节码文件&#xff0…

解决win10安装软件提示Microsoft Store界面

解决方法 1. 打开设置&#xff0c;找到应用 2. 应用与功能&#xff0c;选择任何来源

Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路:出该二叉树的 最底层 最左边 节点的值找出深度最大的第一个结点(左结点先遍历) 方法一…

【数据挖掘】实验5:数据预处理(1)

实验5&#xff1a;数据预处理&#xff08;1&#xff09; 一&#xff1a;实验目的与要求 1&#xff1a;熟悉和掌握数据预处理&#xff0c;学习数据清洗、数据集成、数据变换、数据规约、R语言中主要数据预处理函数。 二&#xff1a;实验内容 【缺失值分析】 第一步&#xff1…

java selenium 元素点击不了

最近做了一个页面爬取&#xff0c;很有意思被机缘巧合下解决了。 这个元素很奇怪&#xff0c;用xpath可以定位元素&#xff0c;但是就是click()不了。 试过了网上搜的一些办法&#xff1a; //尝试一 WebElement a_tag driver.findElement(By.xpath("xxx")); a_tag…