热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

开发笔记:CodeForces669D

本文由编程笔记#小编为大家整理,主要介绍了CodeForces-669D相关的知识,希望对你有一定的参考价值。题目链接:http://codeforces.c
本文由编程笔记#小编为大家整理,主要介绍了CodeForces - 669D相关的知识,希望对你有一定的参考价值。


题目链接:http://codeforces.com/problemset/problem/669/D

Little Artem is fond of dancing. Most of all dances Artem likes rueda — Cuban dance that is danced by pairs of boys and girls forming a circle and dancing together.

More detailed, there are n pairs of boys and girls standing in a circle. Initially, boy number 1 dances with a girl number 1, boy number 2 dances with a girl number 2 and so on. Girls are numbered in the clockwise order. During the dance different moves are announced and all pairs perform this moves. While performing moves boys move along the circle, while girls always stay at their initial position. For the purpose of this problem we consider two different types of moves:



  1. Value x and some direction are announced, and all boys move x positions in the corresponding direction.

  2. Boys dancing with even-indexed girls swap positions with boys who are dancing with odd-indexed girls. That is the one who was dancing with the girl 1 swaps with the one who was dancing with the girl number 2, while the one who was dancing with girl number 3 swaps with the one who was dancing with the girl number 4 and so one. It‘s guaranteed that n is even.

Your task is to determine the final position of each boy.

Input

The first line of the input contains two integers n and q (2?≤?n?≤?1?000?000, 1?≤?q?≤?2?000?000) — the number of couples in the rueda and the number of commands to perform, respectively. It‘s guaranteed that n is even.

Next q lines contain the descriptions of the commands. Each command has type as the integer 1 or 2 first. Command of the first type is given as x (?-?n?≤?x?≤?n), where 0?≤?x?≤?n means all boys moves x girls in clockwise direction, while ?-?x means all boys move x positions in counter-clockwise direction. There is no other input for commands of the second type.

Output

Output n integers, the i-th of them should be equal to the index of boy the i-th girl is dancing with after performing all q moves.

Examples




Input

6 3
1 2
2
1 2



Output

4 3 6 5 2 1



Input

2 3
1 1
2
1 -2



Output

1 2



Input

4 2
2
1 3



Output

1 4 3 2
题目大意:n对男生女生顺时针围着一个圈圈在跳舞,一号男生和一号女生跳,依次类推。现在给几个指令,让男生改变他们的位置,而女生位置不变,要你求出执行完所有指令之后一号女生对应的是几号男生,二号女生对应几号男生,以此类推全部输出就行了。指令分为以下两种:
1.整体绕着这个圆圈走x步(正数为顺时针,负数为逆时针)
2.和位置数为奇数的女生跳舞的那个男生要和和位置数为偶数女生跳舞的那个男生交换以下位置,比如和一号女生跳舞的男生要和二号女生跳舞的那个男生交换位置,和3号女生跳舞的那个男生要和4号女生跳舞的那个男生交换位置,以此类推。
解题思路:这个题目看起来挺简单的,就是每次输入一个指令执行完相应的操作就行了的,可是呢,我们来看那一下范围:2?≤?n?≤?1?000?000, 1?≤?q?≤?2?000?000(n为人数,q为指令数),这么大的区间,如果我们一个一个执行操作的话,需要好多次循环,这样肯定是会超时的,所以我们想是否有什么巧妙的方法可以一次性知道他们最后的位置会怎样呢?可能先想到得应该是记录下执行了几次1操作执行了几次2操作,然后根据1操作的次数和2操作的次数来确定最后他们的位置吧,但是这样确实错的,因为先交换位置再整体移动和先整体移动在交换是不一样的,反正很乱,而且也不行,自己带几组数据试试就知道了。这时候,我们就仔细分析下两个操作的特点,第一个操作就是整体移动多少个位置,而第二个操作就是简单两个人交换位置,总人数为偶数,仔细想想我们就可以发现奇数位置的男生的相对位置压根就是不改变的,偶数位置的男生也是如此,意思就是1 3 5 7 9 ……这些男生的相对位置不会发生改变,同样2 4 6 8 ……也是如此。那题目就可以变得简单了,我们直接从开始几率1号男生和2号男生的位置就好了,就相当于记录了全部的奇数位置的男生和偶数位置的男生了,每次操作,我们对1号男生和2号男生进行更新即可,全部指令执行完毕后,我们通过1号2号男生的位置就可以填不上其他男生的位置了。思路就是这样子的,不过感觉好像不是很简单想出来那。。。。
附上AC代码:

1 #include<iostream>
2 #include
3 using namespace std;
4 int n,q,k,cnt;
5 int d[1000005];
6
7 int main()
8 {
9 scanf("%d%d",&n,&q);
10 int fir=0,sec=1; //用来记录1号男生和2号男生的位置
11 while(q--)
12 {
13 scanf("%d",&k);
14 if(k==1)
15 {
16 scanf("%d",&cnt); //整体移动cnt个位置,注意是个圈
17 fir=(fir+cnt+n)%n;
18 sec=(sec+cnt+n)%n;
19 }
20 else
21 {
22 if(fir%2==0) //交换位置,先判断两个人的相对位置
23 {
24 fir=(fir+1+n)%n;
25 sec=(sec-1+n)%n;
26 }
27 else
28 {
29 fir=(fir-1+n)%n;
30 sec=(sec+1+n)%n;
31 }
32 }
33 }
34 for(int i=0;i2
)
35 {
36 d[(fir+i)%n]=i+1; //奇数列男生位置填充
37 d[(sec+i)%n]=i+2; //偶数列男生位置填充
38 }
39 for(int i=0;i)
40 {
41 if(i==0) printf("%d",d[i]);
42 else printf(" %d",d[i]);
43 }
44 printf("
");
45 return 0;
46 }

 


















推荐阅读
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 本文深入探讨了CGLIB BeanCopier在Bean对象复制中的应用及其优化技巧。相较于Spring的BeanUtils和Apache的BeanUtils,CGLIB BeanCopier在性能上具有显著优势。通过详细分析其内部机制和使用场景,本文提供了多种优化方法,帮助开发者在实际项目中更高效地利用这一工具。此外,文章还讨论了CGLIB BeanCopier在复杂对象结构和大规模数据处理中的表现,为读者提供了实用的参考和建议。 ... [详细]
  • 本文探讨了利用Java实现WebSocket实时消息推送技术的方法。与传统的轮询、长连接或短连接等方案相比,WebSocket提供了一种更为高效和低延迟的双向通信机制。通过建立持久连接,服务器能够主动向客户端推送数据,从而实现真正的实时消息传递。此外,本文还介绍了WebSocket在实际应用中的优势和应用场景,并提供了详细的实现步骤和技术细节。 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 尽管我们尽最大努力,任何软件开发过程中都难免会出现缺陷。为了更有效地提升对支持部门的协助与支撑,本文探讨了多种策略和最佳实践,旨在通过改进沟通、增强培训和支持流程来减少这些缺陷的影响,并提高整体服务质量和客户满意度。 ... [详细]
  • 蓝桥杯算法实战:节点选取策略优化分析
    本文针对蓝桥杯算法竞赛中的节点选取策略进行了深入分析与优化。通过对比不同节点选择方法的效果,提出了基于贪心算法和动态规划的综合优化方案,旨在提高算法效率和准确性。实验结果表明,该优化策略在处理大规模数据集时表现出色,显著提升了算法性能。 ... [详细]
  • 在Android 4.4系统中,通过使用 `Intent` 对象并设置动作 `ACTION_GET_CONTENT` 或 `ACTION_OPEN_DOCUMENT`,可以从相册中选择图片并获取其路径。具体实现时,需要为 `Intent` 添加相应的类别,并处理返回的 Uri 以提取图片的文件路径。此方法适用于需要从用户相册中选择图片的应用场景,能够确保兼容性和用户体验。 ... [详细]
  • 在 Kubernetes 中,Pod 的调度通常由集群的自动调度策略决定,这些策略主要关注资源充足性和负载均衡。然而,在某些场景下,用户可能需要更精细地控制 Pod 的调度行为,例如将特定的服务(如 GitLab)部署到特定节点上,以提高性能或满足特定需求。本文深入解析了 Kubernetes 的亲和性调度机制,并探讨了多种优化策略,帮助用户实现更高效、更灵活的资源管理。 ... [详细]
  • 探索偶数次幂二项式系数的求和方法及其数学意义 ... [详细]
  • 在 Vue 项目中,为了提高页面加载速度和优化用户体验,实现图片上传前的压缩处理至关重要。本文介绍了如何通过集成第三方库和自定义组件,有效减小图片文件大小,确保在不影响图像质量的前提下,提升应用性能。 ... [详细]
  • 如何高效启动大数据应用之旅?
    在前一篇文章中,我探讨了大数据的定义及其与数据挖掘的区别。本文将重点介绍如何高效启动大数据应用项目,涵盖关键步骤和最佳实践,帮助读者快速踏上大数据之旅。 ... [详细]
  • 技术分享:深入解析GestureDetector手势识别机制
    技术分享:深入解析GestureDetector手势识别机制 ... [详细]
  • 在处理大图片时,PHP 常常会遇到内存溢出的问题。为了避免这种情况,建议避免使用 `setImageBitmap`、`setImageResource` 或 `BitmapFactory.decodeResource` 等方法直接加载大图。这些函数在处理大图片时会消耗大量内存,导致应用崩溃。推荐采用分块处理、图像压缩和缓存机制等策略,以优化内存使用并提高处理效率。此外,可以考虑使用第三方库如 ImageMagick 或 GD 库来处理大图片,这些库提供了更高效的内存管理和图像处理功能。 ... [详细]
  • 在 Windows 10 环境中,通过配置 Visual Studio Code (VSCode) 实现基于 Windows Subsystem for Linux (WSL) 的 C++ 开发,并启用智能代码提示功能。具体步骤包括安装 VSCode 及其相关插件,如 CCIntelliSense、TabNine 和 BracketPairColorizer,确保在 WSL 中顺利进行开发工作。此外,还详细介绍了如何在 Windows 10 中启用和配置 WSL,以实现无缝的跨平台开发体验。 ... [详细]
  • 本文探讨了基于点集估算图像区域的Alpha形状算法在Python中的应用。通过改进传统的Delaunay三角剖分方法,该算法能够生成更加灵活和精确的形状轮廓,避免了单纯使用Delaunay三角剖分时可能出现的过大三角形问题。这种“模糊Delaunay三角剖分”技术不仅提高了形状的准确性,还增强了对复杂图像区域的适应能力。 ... [详细]
author-avatar
wxxc
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有