2019南昌网络赛E.Magic Master_算法日常23[23/100]

题目链接

计蒜客传送门

题意

魔法洗牌,洗完牌后进行1,2,2,2…2..操作,使得最终在John手上的牌是递减的

题解

  • 看这个题目的数据范围我们可以猜测出这题是一个找规律的题目,那我们要怎么构造这个串呢?
  • 观察题目给的M=1,发现1,2,3都间隔了一个,然后我们推测是间隔M个放置,然后再继续推测之后得到下面的规律
  • 走M次空格,第M+1次落下,第一个先填1,循环走

举例

比如N = 5, M = 4;
一开始是 1 _ _ _ _
然后走4次空格,第5次落下 变成 1 2 _ _ _
之后同理得到 1 2 _ 3 _ ==> 1 2 _ 3 4 ==> 1 2 5 3 4

实现

通过模拟链表实现走M次空格(详见代码)

复杂度分析

时间复杂度 O(T*N*M) ,接近 O(4*$10^9$) ,6s时间限制,按理1秒 2*$10^8$ 也只够跑 1.2*$10^9$ ,所以要么计蒜客评测机太快,要么数据不够强大,233

写作小收获

用转义符\来保持某些符号不成为markdown的标记符,比如我要用多个*,就要防止变成markdown的斜体

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 4e7 + 10;
int pos[N], nxt[N], pre[N];

int main() {
int T; scanf("%d", &T);
while(T--) {
int n, m, q, u, v;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) nxt[i] = i+1, pre[i] = i-1;
nxt[n] = 2; pre[2] = n;
pos[1] = 1;
int cur = 1;
for(int i=2;i<=n;i++){
for(int j=1;j<=m+1;j++) {
cur = nxt[cur];
}
pos[cur] = i;
u = pre[cur]; v = nxt[cur];
nxt[u] = v; pre[v] = u;
}
scanf("%d", &q);
while(q--) {
scanf("%d", &u);
printf("%d\n", pos[u]);
}
}
return 0;
}

每天一句叨叨

别人撞了南墙才回头,而我撞了也不回头,我要跨过去