1621 - Jumping Around【构造】【数学】

本文主要是介绍1621 - Jumping Around【构造】【数学】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意
样例
- input
- output
- 解释
思路
代码
Hit

题目大意

传送门

任务：从0出发，访问0~n各一次，可以在任意一点终止，需要用票才能从一个点到另一个点。
有三种票，跳跃长度分别为1 2 3，有a，b，c张（3<= a,b,c<=5000）并且n=a+b+c。
每张票只能用一次。输入保证有解。

样例

input

2
3 3 3
3 4 3

output

0 3 1 2 5 4 6 9 7 8
0 3 1 2 5 4 6 9 7 8 10

解释

思路

首先引入一个概念叫做同余类，以正整数m为模，则任何整数必然与0,1,2,3,…,m-1之一同余，将同余的数归为一类。
比如当m为4的时候。
{… -4 0 4 8 …}
{… -3 1 5 9 …}
{… -2 2 6 10 …}
{… -1 3 7 11 …}

首先考虑这样的一个问题：
如果只有一个a和n个b，然后就可以先跳2步，0 2 4 6 8，然后跳一个1，改变同余类，然后往回跳，结束。
引入了c，首先就把c消掉。
当c%3为0时，可以先往右调c/3个3，往右跳1步，往左跳c/3个3，往右跳1步，往右跳c/3个3，到达c/3*3+2的位置，这个时候c已经用完了。
c%3不为0的时候同理。

代码

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <math.h>
#include <stack>
using namespace std;
const int maxn = 5005;int