John is not only a magic master but also a shuffling master.
Famous though he is, he likes interacting with his fans by playing a game with his fantastic shuffling skills.
The game shows as follows:
He first shows a deck of pokers contains NNcards indexed 1,2,\dots ,N1,2,…,N and all the cards are the same. He notes that the side contains numbers as the front side and the other side as the back. Later he selects one of his fans to choose a positive integer MM that is not greater than 1010. After that, he will shuffle the cards purposefully and put it on the desktop. Note that at this moment the front sides of the cards are facing to the desk.
Then, the selected fans should perform the following steps until there is no card on the desk.
- Place the card on the top of the piles to John's hand. If there are already some cards in his hand, put it on the top of them.
- If there remain cards on the desk:
(a) Put a card from the top of the piles to the bottom of it.
(b) Execute the step (aa) of MM times.
(c) Go to step 11.
Next, it is time to witness the miracle.
John will continually overturn the cards on his hand top to bottom, and we will find that the cards are always in decreasing order.
One day, one of John's fans, Tom, a smart JBer, understands the key to this magic. He turns to you and comments that the key to that magic is the shuffling John did previously. For any number MM, he will turn the cards in a specific order after the shuffling. As you are not as smart as Tom, you should find the index of the KKth cards from the top of the piles after the shuffling.
Input
The first line contain a positive integer T (1\le T \le10)T(1≤T≤10) – the number of test cases.
For each test cases, the first line contain a positive integer N (1 \le N \le 40000000)N(1≤N≤40000000) , indicating the numberof cards.
The second line contain a positive integer M (1\le M \le 10)M(1≤M≤10) – the number the fans select.
The third line contain an integer Q (1 \le Q \le 100)Q(1≤Q≤100) – indicating that there are QQ questions.
Next, there are QQ lines, each with an integer K (1 \le K \le N)K(1≤K≤N) – representing a query.
Output
For each query, you should output the index of the KKth cards from the top of the piles after the shuffling.
样例输入复制
1
5
1
2
2
3
样例输出复制
5
2样例解释
Sample description - The indexs of the cards after the shuffling are: 1~5~2~4~31 5 2 4 3 (Left is top)
双端队列或者链表倒着模拟即可。
纪念我的指针为啥会TLE
2ms通过服气（大佬做法）
#include<bits/stdc++.h>
int main(void)
{
int t;
scanf("%d",&t);
while (t--)
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for (int i=0;i<q;++i)
{
int k;
scanf("%d",&k);
int old=n,pos=k,now=n;
while (pos>1)
{
if (pos<=(m+1))
{
--now;
pos-=m+1;
while (pos<=0) pos+=now;
}
else
{
now=old-(pos/(m+1));
pos%=(m+1);
if (pos==0) ++now,pos=m+1;
}
old=now;
}
printf("%d\n",n-old+1);
}
}
return 0;
}#include<bits/stdc++.h>
using namespace std;
const int N=4e7+10;
int a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
deque<int>Q;
int n,m;
scanf("%d%d",&n,&m);
for(int i=n; i>=1; i--)
{
Q.push_front(i);
if(i==1) break;
for(int j=1; j<=m; j++)
{
int t=Q.back();
Q.pop_back();
Q.push_front(t);
}
}
for(int i=1; i<=n; i++)
{
a[i]=Q.front();
// cout<<a[i]<<endl;
Q.pop_front();
}
int q;
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
}
数组模拟链表
#include<iostream>
using namespace std;
const int MAXN =50000005;
int a[MAXN];
int pre[MAXN];
int nxt[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
if(n==1)
{
for(int i=1; i<=q; i++)
{
int x;
scanf("%d",&x);
printf("%d\n",1);
}
continue;
}
pre[n]=-1;
nxt[n]=-1;
int be=n;
int en=n;
int num=1;
for(int i=n-1;i>=1;i--)
{
nxt[en]=i;
pre[i]=en;
nxt[i]=-1;
en=i;
if(i==1) break;
num++;
int M=m%num;
if(M==0)
continue;
int f=be;
int t=1;
while(t<M)
{
f=nxt[f];
t++;
}
nxt[en]=be;
pre[be]=en;
be=nxt[f];
pre[be]=-1;
en=f;
nxt[en]=-1;
//cout<<num<<"*"<<f<<" "<<be<<" "<<en<<endl;
}
int j=n;
while(be!=-1)
{
a[j--]=be;
be=nxt[be];
}
for(int i=1; i<=q; i++)
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
return 0;
}
指针TLE
#include<iostream>
using namespace std;
const int MAXN =50000005;
int a[MAXN];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
if(n==1)
{
for(int i=1; i<=q; i++)
{
int x;
scanf("%d",&x);
printf("%d\n",1);
}
continue;
}
f=new Node;
r=new Node;
Node *s=new Node;
s->data=n;
f->next=s;
r=s;
int num=1;
for(int i=n-1; i>=1; i--)
{
//cout<<i<<" "<<num<<endl;
s=new Node;
s->data=i;
r->next=s;
r=s;
if(i==1)
break;
num++;
int M=m%num;
if(M==0)
continue ;
int temp=0;
Node *p=f;
while(temp<M)
{
p=p->next;
temp++;
}
r->next=f->next;
r=p;
f->next=p->next;
//cout<<f->next->data<<"*"<<r->data<<endl;
}
r->next=NULL;
Node *p=f->next;
int j=n;
while(p!=NULL)
{
a[j--]=p->data;
p=p->next;
}
delete p,f,r,s;
for(int i=1; i<=q; i++)
{
int x;
scanf("%d",&x);
printf("%d\n",a[x]);
}
}
return 0;
}
标签：le,Magic,Contest,int,scanf,next,--,2019,cards From： https://blog.51cto.com/u_14932227/6041985