【noip2005】篝火晚会 题解报告(→_→)

传送门:!点我传送!

首先,毫无疑问,即使是在毫无思路的情况下,我们也应先把期待的序列求出,个人想法只是一个遍历加一些奇怪的判断,在此过程中,我们可以十分轻易的拿到“-1”答案的分值。在求出期待序列后,我们再对其分析。

明显地 ,当一个人到达了他想在的位置后,就永远不需要再挪动了,而且每个人到达它想在的位置的代价必定为1(最赖皮情况就是每次两两交换),因此,当目标序列确定时,不在位人数即为这种情况下的解

当然由于题目是绕着篝火以圆的方式排列,所以并无所谓的起始点。意思就是我们要把每个点当做起始点,再依次与期待序列进行比较,找出最少不在位人数(answer)。

30%

暴力解法就是直接暴搜所有情况,找出最小答案输出,时间复杂度应是起始点个数*队列长度O(n^2),期待得30%的点。

100%

以下要说的方法是我在一篇博文中看到的。30%的方法中,我把每种情况都枚举,这是没必要的。在目标环中,如果一些元素的相对位置与原环中的相同,我就可以让两个环中的这些元素对齐,此时若这些元素的个数为k,则代价m=N-k。明显地,找出最长的一组就可以让代价最小。

要找最长的相对位置相同的串,也就是找最长的递增且权值之差等于序号之差的序列,DP可行,加入优化可以到O(nlogn)。

当然还有一种简单的方法,如果a和b的相对位置与序号的相对位置和c和d的相对位置与序号的相对位置相同,并无法确定a、b、c、d相对位置是否都与序号的相对位置相同。但是我如果知道a与其序号位置、b与其序号位置、c与其序号位置、d与其序号位置的差值都相等,就一定有a、b、c、d与序号的相对位置相等。因此用f[i]存储目标环中权值与序号差值为i的数的个数,最后找出最大值maxx,N-maxx即为解。同样要反向做一次。时空复杂度皆为O(N)。注意:所考虑的1,2,3,4,5,6,7,8和1,8,7,6,5,4,3,2(例)在题目中是同种情况


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int MAX = 50000;

int f[200000];
int a[50100];

int num[2][50100];
int w[50100], ji[50100], n;

int main(void)
{

    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        a[i] = n-i+2;
        scanf("%d%d", &num[0][i], &num[1][i]);
    }
    a[1] = 1;
    w[1] = 1; i = 1; ji[1] = 1;
    int k = num[0][1], fa = 1;
    while (i<n)
    {
       
        if (i == n-1)
        {
            int sd = 1;
            for (j = 0; j <= 1; j++)
            {
                if (num[j][k] != fa) continue;
                if (ji[num[1-j][k]] != 1) continue;
                sd = 0;
                w[++i] = k;
                ji[k] = 1;
            }
            if (sd)
            {
                printf("-1\n");
                return 0;
            }
            continue;
        }
       
        int mas = 1;
       
        for (j = 0; j <= 1; j++)
        {
            if (num[j][k] != fa) continue;
            if (ji[num[1-j][k]]) break;
            mas = 0;
            w[++i] = k;
            fa = k;
            k = num[1-j][k];
            ji[w[i]] = 1;
        }
        if (mas)
        {
            printf("-1\n");
            return 0;
        }
    }
   
    int maxx = -1;
    for (i = 1; i <= n; i++)
    {
        int forward, back;
        if (w[i] >= i)
        {
            forward = w[i]-i;
            back = (i-w[i]+n)%n;
        } else
        {
            back = i-w[i];
            forward = (w[i]-i+n)%n;
        }
        f[MAX+forward]++;
        f[back]++;
        maxx = maxx < f[MAX+forward] ? f[MAX+forward] :maxx;
        maxx = maxx < f[back] ? f[back] :maxx;
       
    }
   
    memset(f,0,sizeof(f));
    for (j = 1; j <= n; j++)
    {
        int forward, back;
        i = a[j];
        if (w[j] >= i)
        {
            forward = w[j]-i;
            back = (i-w[j]+n)%n;
        } else
        {
            back = i-w[j];
            forward = (w[j]-i+n)%n;
        }
        f[MAX+forward]++;
        f[back]++;
        maxx = maxx < f[MAX+forward] ? f[MAX+forward] :maxx;
        maxx = maxx < f[back] ? f[back] :maxx;
       
    }
    printf("%d", n-maxx);

    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注