jjzjj

牛牛的猜球游戏

月半流苏 2024-06-27 原文

PS:如果读过题了可以跳过题目描述直接到题解部分

暂无提交链接

题目

题目描述

牛牛和牛妹在玩猜球游戏,牛牛首先准备了 10 个小球,小球的编号从 0~9。首先,牛牛把这 10 个球按照从左到右编号为 0,1,2,3...9 的顺序摆在了桌子上,接下来牛牛把这 10 个球用 10 个不透明的杯子倒扣住。

牛牛接下来会按照一定的操作顺序以极快的速度交换这些杯子。

换完以后他问牛妹你看清楚从左到右的杯子中小球的编号了么?

由于牛妹的动态视力不是很好,所以她跑来向你求助。你在调查后发现牛牛置换杯子其实是有一定原则的。

具体来讲,牛牛有一个长度大小为 n 的操作序列。

操作序列的每一行表示一次操作都有两个非负整数 a,b,表示本次操作将会交换从左往右数第 a 个杯子和从左往右数第 b 个杯子(a 和 b 均从 0 开始数)。请注意是换杯子,而不是直接交换 a 号球和 b 号球。

牛牛和牛妹一共玩了 m 次猜球游戏,在每一轮游戏开始时,他都将杯子中的小

球重置到从左往右依次为 0,1,2,3...9 的状态。

然后在第 i 轮游戏中牛牛会按照操作序列中的第 l[i] 个操作开始做,一直做到第 r[i] 个操作结束(l 和 r 的编号从 1 开始计算)。

由于你提前搞到了牛牛的操作序列以及每一次游戏的 l,r。请你帮助牛妹回答出牛牛每一轮游戏结束时,从左至右的杯子中小球的编号各是多少。

输入格式

首先输入一行两个正整数 n,m,表示操作序列的长度以及进行游戏的次数。

接下来 n 行每行两个非负整数 a,b,表示交换左数第 a 个杯子和左数第 b 个杯子。(a,b 均从 0 开始数起)

接下来 m 行每行两个正整数 l,r 表示该轮游戏中牛牛从第 l 个操作开始做,一直做到第 r 个操作结束。(l 和 r 的编号从 1 开始计算)

输出格式

对于每一轮游戏,输出一行 10 个非负整数,表示从左至右每一个杯子中小球,输出的整数之间用空格隔开,行末不允许有多余空格。

样例

输入

5 3

0 1

1 2

2 3

0 1

9 0

1 5

5 5

3 5

输出

9 1 3 0 4 5 6 7 8 2

9 1 2 3 4 5 6 7 8 0

9 0 3 2 4 5 6 7 8 1

 数据范围

对于 30% 的测试数据,保证 1≤n,m ≤500

对于 60% 的测试数据,保证 1≤n, m≤4×10^4

对于 60% 以外另 10% 的数据,保证输入的 a,b∈ {0,1,2}

对于 100% 的测试数据,保证 1≤n,m≤10^5, 0≤a,b≤ 9 , 1≤l≤r≤n

题解

写这道题的题解主要是想纪念一下我的第一道被卡常卡掉的题。

但毕竟还是一道题解,所以我还是把我的思路大概讲一下。

这道题最暴力的方法当然是暴力,但肯定会T掉,所以我们需要进行优化。

其他题解很多都是用的回滚莫队,但我没有(说实话是我不会

我的想法是既然一个数可以交换,那么它无论这次操作之前或是之后的操作对它当前操作的相对位移都是没有影响的。

所以我用数组 p[i][j] 表示第 i 次操作相对没操作之前的数 j 的相对位移,取向右为正。

这样在取 l 到 r 次操作中间的时候只需要把第 r 次操作与第 l-1 次操作相减就好了。

具体的相减办法,我们可以找一下规律:

以样例为例

Ap0

1

23456789
00000000000
11-100000000
B22-1-10000000
33-1-1-1000000
430-2-1000000
C5307-100000-9

我们以 l=3,r=5 的样例为例。

我们通过观察会发现 A+B 是操作后的数值,而 A+B+(C-B)=A+C 则是其所在的位置。

代码实现

//牛牛的猜球游戏
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int a[100010],b[100010];
int l,r;
int w[15];
int p[100010][15];

void kd(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<1)+(x<<3)+(nt^'0');
	}
}

int main(){
	register int i,j;
	kd(n);
	kd(m);
	for(i=0;i<=9;++i){
		w[i]=i;
		p[0][i]=0;
	}
	for(i=1;i<=n;++i){
		kd(a[i]);
		kd(b[i]);
		swap(w[a[i]],w[b[i]]);
		for(j=0;j<=9;++j){
			p[i][w[j]]=j-w[j];
		}
	}
	for(i=1;i<=m;++i){
		kd(l);
		kd(r);
		for(j=0;j<=9;++j){
			w[j+p[r][j]]=j+p[l-1][j];
		}
		for(j=0;j<=9;++j){
			printf("%d ",w[j]);
		}
		printf("\n");
	}
	return 0;
}

有关牛牛的猜球游戏的更多相关文章

  1. ruby - 我需要从 facebook 游戏中抓取数据——使用 ruby - 2

    修改(澄清问题)我已经花了几天时间试图弄清楚如何从Facebook游戏中抓取特定信息;但是,我遇到了一堵又一堵砖墙。据我所知,主要问题如下。我可以使用Chrome的检查元素工具手动查找我需要的html-它似乎位于iframe中。但是,当我尝试抓取该iframe时,它​​是空的(属性除外):如果我使用浏览器的“查看页面源代码”工具,这与我看到的输出相同。我不明白为什么我看不到iframe中的数据。答案不是它是由AJAX之后添加的。(我知道这既是因为“查看页面源代码”可以读取Ajax添加的数据,也是因为我有b/c我一直等到我可以看到数据页面之后才抓取它,但它仍然不存在)。发生这种情况是因为

  2. python - Ruby 或 Python 的 3d 游戏引擎? - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。要求我们推荐或查找工具、库或最喜欢的场外资源的问题对于StackOverflow来说是偏离主题的,因为它们往往会吸引自以为是的答案和垃圾邮件。相反,describetheproblem以及迄今为止为解决该问题所做的工作。关闭9年前。Improvethisquestion是否有适用于这些的3d游戏引擎?

  3. ruby - 使用 Ruby 编写 Unity 游戏 - 2

    所以我看到unity支持c#、JS和Boo。我可以学习其中一个,但我想制作一个“编译器”或类似的东西,让我可以编写ruby​​代码并输出JS代码或制作一个可以被Unity编译器读取的层。这有可能吗?我愿意在这方面投入很多时间并且有相当多的经验。 最佳答案 如果您的问题实际上是“我如何将Ruby编译为JavaScript”,那么这更容易回答:Opal:RubytoJavaScriptcompiler但是,学习其中一种受支持的语言会更好。当运行的是用另一种语言解释的代码时,很难调试“您的”代码。

  4. 【Unity游戏破解】外挂原理分析 - 2

    文章目录认识unity打包目录结构游戏逆向流程Unity游戏攻击面可被攻击原因mono的打包建议方案锁血飞天无限金币攻击力翻倍以上统称内存挂透视自瞄压枪瞬移内购破解Unity游戏防御开发时注意数据安全接入第三方反作弊系统外挂检测思路狠人自爆实战查看目录结构用il2cppdumper例子2-森林whoishe后记认识unity打包目录结构dll一般很大,因为里面是所有的游戏功能编译成的二进制码游戏逆向流程开发人员代码被编译打包到GameAssembly.dll中使用il2ppDumper工具,并借助游戏名_Data\il2cpp_data\Metadata\global-metadata.dat

  5. Unity游戏开发:背包系统的实现 - 2

    背包是游戏中经常使用的一个组件,它负责管理玩家在游戏中所获得的道具。一个完整的背包系统应当具有将物品放置进背包、对背包内物品进行管理和使用背包内物品等功能。而往往一个背包系统的逻辑关系较为复杂,如果把所有功能都放在一个脚本中实现会使代码显得十分冗杂且缺乏逻辑。所以在背包系统的设计过程中,我们常将其分解为数据、逻辑和UI三部分分别来进行完成。一、UI设计以CottonPuzzle中的背包设计为例,我们需要有物品展示栏、物品切换按键和物品提示信息等部分。在Canvas中创建ItemHolder,在ItemHolder中创建LeftButton和RightButton控制物品的左右切换、Slot来控

  6. 仍在积极维护的 Ruby 游戏框架? - 2

    关闭。这个问题不符合StackOverflowguidelines.它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。关闭7年前。Improvethisquestion我发现很难调查使用Ruby进行游戏编程的选项。其他帖子和文章中提到的几个包装器和框架不再维护或使用。Gosu/Ruby似乎仍然活跃:官方论坛上的讨论一直很稳定。是否还有其他积极维护的ruby​​游戏框架?编辑:我发现使用MacRuby进行大量游戏开发。

  7. ruby - 基于 OOP 的文本游戏中的优雅命令解析 - 2

    我正在玩用Ruby编写MUD/文本冒险(请不要笑)。谁能给我任何关于解析输入文本的优雅的、基于oop的解决方案的建议?我们在这里谈论的只是“把魔杖放在table上”更复杂的事情。但是一切都需要柔软;我想稍后轻松地扩展命令集。我目前的想法,稍微简化一下:每个项目类别(盒子、table、房间、播放器)都知道如何识别“属于”它的命令。游戏类理解一种特定于领域的语言,涉及诸如“将对象X移入对象Y”、“显示对象X的描述”等Action。游戏类询问房间中的每个项目是否识别输入命令。先说是赢。然后它将控制传递给项目类中处理命令的方法。此方法重新表述DSL中的命令,将其传递回游戏对象以实现它。必须有一

  8. ruby - 此修改后的二十一点游戏的最佳获胜策略是什么? - 2

    问题有没有可以保持的最佳值(value),这样我才能赢得尽可能多的比赛?如果是这样,那是什么?编辑:是否可以为给定的限制计算出确切的获胜概率,而与对手的所作所为无关?(自大学以来,我还没有做过概率和统计)。我有兴趣将其作为与模拟结果进行对比的答案。编辑:修复了我算法中的错误,更新了结果表。背景我一直在玩改进的二十一点游戏,其中对标准规则进行了一些相当烦人的规则调整。我已将与标准二十一点规则不同的规则斜体化,并为不熟悉的人添加了二十一点规则。修改二十一点规则正是两个人类玩家(经销商无关)每个玩家面朝下发两张牌双方玩家_ever_都不知道对手纸牌的_any_的值在_both_完成手牌之前,

  9. ruby-on-rails - 选择 Ruby on Rails 作为基于浏览器的在线游戏平台 - 2

    对于类似Travian的在线策略游戏,我有一些(我认为)非常棒的想法。有些内容我还没有想通,还有一些我还不知道的挑战。这是一个相当大的项目,对于(还)不是熟练的Web开发人员的人来说可能太重了。我还是想试一试,但我在选择平台时遇到了麻烦。世界上的“规模”最近被抛得一团糟,我看到RubyonRails因规模不佳而受到抨击,所以我来这里是为了得到一些答案。我喜欢RubyonRails,无论是Ruby还是Rails。我当然不是这方面的专家,但我喜欢使用它。我之前也使用过Python+Django,也使用过PHP(我不喜欢它。)理想情况下,假设每个服务器有7000名玩家,大概每秒要处理大量数据

  10. U3D游戏开发工程师正确入行姿势指南 - 2

    2021年,游戏圈上演了一场精彩绝伦的抢人大战。在上海游戏圈,年薪百万的人越来越多了。据多名HR估算,在上海,过去一年TA、引擎、美术等稀缺岗位拟的薪资涨幅大概在20%-30%左右。某位圈内知名资深游戏猎头对此发出感叹:“50K的数值策划、角色原画;70K的技术美术;80K的技术总监...他们的年薪总包都接近百万,就连应届生入行的薪资也水涨船高,这要是放在以往都是不敢想象的”。以往含年薪、期权等的年总包收入上百万元,起码得是总监级别。如今工作五六年的人从广深跳到上海游戏公司,年薪能从50-70万跃上100万元,拿百万年薪的游戏从业者越来越多了上海游戏圈近年发展迅速,既有颇具发展潜力的中生代F4

随机推荐