热门标签 | 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 }

 


















推荐阅读
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 本文介绍了SIP(Session Initiation Protocol,会话发起协议)的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]
  • 问题场景用Java进行web开发过程当中,当遇到很多很多个字段的实体时,最苦恼的莫过于编辑字段的查看和修改界面,发现2个页面存在很多重复信息,能不能写一遍?有没有轮子用都不如自己造。解决方式笔者根据自 ... [详细]
  • 长期从事ABAP开发工作的专业人士,在面对行业新趋势时,往往需要重新审视自己的发展方向。本文探讨了几位资深专家对ABAP未来走向的看法,以及开发者应如何调整技能以适应新的技术环境。 ... [详细]
  • 使用TabActivity实现Android顶部选项卡功能
    本文介绍如何通过继承TabActivity来创建Android应用中的顶部选项卡。通过简单的步骤,您可以轻松地添加多个选项卡,并实现基本的界面切换功能。 ... [详细]
  • 入门指南:使用FastRPC技术连接Qualcomm Hexagon DSP
    本文旨在为初学者提供关于如何使用FastRPC技术连接Qualcomm Hexagon DSP的基础知识。FastRPC技术允许开发者在本地客户端实现远程调用,从而简化Hexagon DSP的开发和调试过程。 ... [详细]
  • 从CodeIgniter中提取图像处理组件
    本指南旨在帮助开发者在未使用CodeIgniter框架的情况下,如何独立使用其强大的图像处理功能,包括图像尺寸调整、创建缩略图、裁剪、旋转及添加水印等。 ... [详细]
  • 管理UINavigationController中的手势返回 - Managing Swipe Back Gestures in UINavigationController
    本文介绍了如何在一个简单的闪存卡片应用中实现平滑的手势返回功能,以增强用户体验。 ... [详细]
  • 题目描述:给定一组学生和课程,每个学生可以参加多个课程。任务是判断是否可以从这些学生中选出一个由 P 名学生组成的委员会,满足以下条件:每名学生代表不同的课程,且每个课程都有代表。时间限制:20000/10000 MS (Java/Others),内存限制:65536/32768 K (Java/Others)。 ... [详细]
  • Encountering frequent mismatches during Terraform apply operations, particularly with resource attributes. ... [详细]
  • 一个转子曲线面积问题及其反问题的解答
    曾经解答过这样一个问题,从该ID的最后一次登录时间、该ID显示的专业信息,误以为是新闻里某个想不开的同学,不安了一阵子。经确认是我多虑了,不过把问题答案还是写出来。之后就收到一堆要求帮忙算 ... [详细]
  • iOS snow animation
    CTSnowAnimationView.hCTMyCtripCreatedbyalexon1614.Copyright©2016年ctrip.Allrightsreserved.# ... [详细]
  • 此更新支持将 Cognito User Pools 作为 API Gateway 授权器的类型 ... [详细]
  • 一、MATLAB常用的基本数学函数abs(x):纯量的绝对值或向量的长度angle(z):复数z的相角(Phaseangle)sqrt(x)࿱ ... [详细]
  • Quora问题探讨:26岁开始转行做开发是否太迟? ... [详细]
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社区 版权所有