牛客网多校第4场 J Hash Function 【思维+并查集建边】

题目链接：戳这里

学习博客：戳这里

题意：

有n个空位，给一个数x，如果x%n位数空的，就把x放上去，如果不是空的，就看(x+1)%n是不是空的。

现在给一个已经放过数的状态，求放数字的顺序。（要求字典序最小

解题思路：

用一个优先队列。如果序列里的x的位子就是x%n，证明这个数是最开始就放好的。加入优先队列。

每次出一个最小元素。把它填入位子a，然后用并查集把a和a+1合并，看看现在a的祖先能不能被加入队列。

用优先队列维护很容易想到，关键是怎么维护选出的数的位置，这里用并查集建边很巧妙的解决了这个问题。

附ac代码：

 1 #include<iostream>

 2 #include<algorithm>

 3 #include<stdio.h>

 4 #include<string.h>

 5 #include<string>

 6 #include <cmath>

 7 #include <vector>

 8 #include <queue>

 9 using namespace std;

10 typedef long long ll;

11 const ll mod = 1e9 + 7;

12 const int maxn = 2e6 + 10;

13 int pre[maxn];

14 int nu[maxn];

15 int ans[maxn];

16 bool vis[maxn];

17

18 struct nod

19 {

20     int pos;

21     int val;

22     nod(){};

23     nod(int x, int y)

24     {

25         pos = x;

26         val = y;

27     }

28     bool friend operator < (nod a, nod b)

29     {

30         return a.val > b.val;

31     }

32

33 };

34 void init(int n)

35 {

36     for(int i = 0; i <= n; ++i)

37         pre[i] = i;

38 }

39 int find(int x)

40 {

41     if(pre[x] == x) return x;

42     else return pre[x] = find(pre[x]);

43 }

44 int main()

45 {

46     int t;

47     scanf("%d", &t);

48     int n;

49     while(t--)

50     {

51         int cnt = 0;

52         int len = 0;

53         scanf("%d", &n);

54

55         priority_queue<nod>q;

56         memset(vis, 0, sizeof(vis));

57         init(n);

58         for(int i = 0; i < n; ++i)

59         {

60             scanf("%d", &nu[i]);

61         }

62         for(int i = 0; i < n; ++i)

63         {

64             if(nu[i] == -1) continue;

65             ++cnt;

66             if(nu[i] % n == i)

67             {

68                 q.push(nod(i, nu[i]));

69                 vis[i] = 1;

70             }

71         }

72

73         while(!q.empty())

74         {

75             nod u = q.top(); q.pop();

76             ans[++len] = u.val;

77             int to = pre[find(u.pos)] = find((u.pos + 1) % n);

78             if(vis[to] || nu[to] == -1 || find(nu[to]%n) != to) continue;

79             q.push(nod(to, nu[to]));

80             vis[to] = 1;

81         }

82         if(len != cnt)

83         {

84             puts("-1");

85             continue;

86         }

87

88         for(int i = 1; i <= len; ++i)

89         {

90             if(i > 1) printf(" ");

91             printf("%d", ans[i]);

92         }

93         printf("\n");

94     }

95 }

巴特西

牛客网多校第4场 J Hash Function 【思维+并查集建边】

最新文章

热门文章