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

发表于 更新于 分类于 阅读次数：
2019南昌网络赛E.Magic Master_算法日常23 魔法洗牌，洗完牌后进行1,2,2,2...2..操作，使得最终在John手上的牌是递减的 走M次空格，第M+1次落下，第一个先填1，循环走 用转义符`\`来保持某些符号不成为markdown的标记符，比如我要用多个\*,就要防止变成markdown的斜体 别人撞了南墙才回头，而我撞了也不回头，我要跨过去

题目链接

计蒜客传送门

题意

魔法洗牌，洗完牌后进行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;
}

每天一句叨叨

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