LGR-170-Div.3 简要题解

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

比赛链接：https://www.luogu.com.cn/contest/147008

虽然现在状态还是很答辩，不过 NOIP 但凡有现在一半的状态都不至于原地退役。

T1

简单模拟。

T2

这道题有点诈骗啊，要多锻炼锻炼反诈意识（

由于 pp 是质数，因此只要 bb 不为 00，那么小于 pp 的所有数都可以用 kb mod pkb\bmod p 表示出来，kk 为任意正整数。注意特判 b=0b=0 的情况。

赛时一开始没看到 pp 是质数，卡了半天。

1
2
3
4
5
6
7
void Solve()
{
    cin>>p>>a>>b>>c;
    if(b==0&&c==0) cout<<"Yes"<<endl;
    else if(b==0) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}

T3

手玩几个样例发现 gcd⁡(i,n)\gcd(i,n) 满足 gcd⁡(i,n)=gcd⁡(n−i,n)\gcd(i,n)=\gcd(n-i,n)，由异或的性质，相等的数相互抵消，最后就只剩下 gcd⁡(n,n)\gcd(n,n)，如果 2∣n2\mid n，还剩一个 gcd⁡(n2,n)\gcd(\frac{n}{2},n)。

1
2
3
4
5
6
void Solve()
{
    cin>>n;
    if(n%2==0) cout<<(n^(n/2))<<endl;
    else cout<<n<<endl;
}

T4

还是手玩几个样例，发现对于每次操作，aia_i 只有以下几种变化方式：

  • 当 aia_i 在序列 aa 中仅出现一次，那么 ai=min⁡(ai,全局mex)a_i=\min(a_i,全局 \mathrm{ mex})
  • 当 aia_i 出现多次，那么 ai=全局mexa_i=全局 \mathrm{mex}

并且在进行若干次操作后，序列 aa 中全局 mex\mathrm{mex} 为 max⁡{ai}+1\max\{a_i\}+1， 且要么所有的数互不相同，要么只有值为 mex−1\mathrm{mex}-1 的数有多个。如果为前者，则序列 aa 在之后的操作中不会改变；若为后者，则序列 aa 在一次操作后，所有值为 mex−1\mathrm{mex}-1 的数变为 mex\mathrm{mex}，其它元素不变，再进行一次操作后，又变为原样。

赛事代码写得有点石山

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
int n,m;
int a[maxn],tong[maxn];
void Solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int num=0,mex=0;
    bool flag1=true;
    while(1)
    {
        for(int i=0;i<=n;i++) tong[i]=0;
        ++num;
        mex=0;
        for(int i=1;i<=n;i++) 
        {
            if(a[i]<n) tong[a[i]]++;
            while(tong[mex]) ++mex;
        }
        bool flag=true;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=mex)
            {
                flag=false;
                break;
            }
            else if(a[i]<mex-1&&tong[a[i]]>1) 
            {
                flag=false;
                break;
            }
        }
        if(flag) 
        {
            if(tong[mex-1]==1) flag1=false;
            break;
        }
        for(int i=1;i<=n;i++) 
        {
            if(a[i]>=n) a[i]=mex;
            else if(tong[a[i]]==1) a[i]=min(mex,a[i]);
            else a[i]=mex;
        }

        if(m==num)
        {
            for(int i=1;i<=n;i++) cout<<a[i]<<" ";
            cout<<endl;
            return;
        }
    }
    if(flag1)
    {
        if(!((m-num)&1))
        {
            for(int i=1;i<=n;i++) 
            {
                if(a[i]==mex-1) cout<<a[i]+1<<" ";
                else cout<<a[i]<<" ";
            }
            cout<<endl;
        }
        else 
        {
            for(int i=1;i<=n;i++) cout<<a[i]<<" ";
            cout<<endl;
        }
    }
    else 
    {
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
    }
    
}

T5

我的构造方法：

  • 如果排列 pp 中 11 的旁边既有 22 又有 33，则 aa 中与 11 对应的位置放 44，与 33 对应的位置放 22，其它地方都放 11
  • 如果 11 的旁边有 22 没有 33，则 11 的位置放 33，其他位置都放 11
  • 否则，在 11 的位置放 22，其它位置都放 11

正确性显然。

可能要特判一下 n=2n=2 和 n=3n=3 的情况。

赛事代码仍然很石山。

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
void Solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    p[n+1]=p[0]=0;
    if(n==2) cout<<-1<<endl;
    else if(n==3)
    {
        if(p[2]==1)
        {
            for(int i=1;i<=n;i++) 
            {
                if(p[i]==3) cout<<2<<" ";
                else cout<<3<<" ";
            }
            cout<<endl;
        }
        else if(p[2]==2)
        {
            for(int i=1;i<=n;i++) 
            {
                if(p[i]==1) cout<<3<<" ";
                else cout<<1<<" ";
            }
            cout<<endl;
        }
        else
        {
            for(int i=1;i<=n;i++) 
            {
                if(p[i]==1) cout<<2<<" ";
                else cout<<1<<" ";
            }
            cout<<endl;
        }
    }
    else
    {
        for(int i=1;i<=n;i++) 
        {
            if(p[i]==1)
            {
                if((p[i-1]==2&&p[i+1]==3)||(p[i-1]==3&&p[i+1]==2))
                {
                    for(int j=1;j<=n;j++)
                    {
                        if(j==i) cout<<4<<" ";
                        else if(p[j]==3) cout<<2<<" ";
                        else cout<<1<<" ";
                    }
                    cout<<endl;
                    return;
                }
                else if(p[i-1]==2||p[i+1]==2)
                {
                    for(int j=1;j<=n;j++)
                    {
                        if(j==i) cout<<3<<" ";
                        else cout<<1<<" ";
                    }
                    cout<<endl;
                    return;
                }
                else
                {
                    for(int j=1;j<=n;j++)
                    {
                        if(j==i) cout<<2<<" ";
                        else cout<<1<<" ";
                    }
                    cout<<endl;
                    return;
                }
            }
        }
    }
}

T6

赛时有一个点 WA 了，没调出来，但是思路应该是对的。

转化下题意，相当于每个点都要在一个大于 11 的环里，且每个 SiS_i 为 11 的点所在的环的大小必须是 ll 的约数。

设 Si=1S_i=1 的位置有 numnum 个，则把 i∈[num,n],i≠n−1i\in[num,n],i\neq n-1 中的任意一个数表示为多个数相加的形式，其中每个数都是 ll 的约数，然后构造这么多个大小为这些数环就行了。

分解 ll 的时候只需要枚举到 nn 就可以了