比赛链接：Dashboard - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

B

题意：给出长度为 $n$ 的数组 $a$ ，求数组 $p$ ，使其为 $0,n-1$ 的 一个排列，且 $a_i=mex(p_1,p_2,…,p_i)-p_i$ 。

从后往前即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int a[n+2];
        for(int i=1;i<=n;i++)cin>>a[i];
        int ans[n+2];
        int mex=n;
        for(int i=n;i>=1;i--)
        {
            ans[i]=mex-a[i];
            mex=min(mex,ans[i]);
        }
        for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
    }
}

C1,C2

题意：给出一个正多边形 $n$ ，同时给出 $x$ 个点，只能在这些点之间连边，然后又给出 $y$ 个点，即可以再另选不超过 $y$ 个点使其也可以连边。求可以划出的最多的不重合的三角形的个数。

$Easy\ version:\ y=0$

选中了 $k$ 个点那么一定可以构造出 $k-2$ 个三角形；在相邻两个点之间如果隔了1个点，即标号只差为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
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x,y;
        cin>>n>>x>>y;
        int a[x+2];
        for(int i=1;i<=x;i++)cin>>a[i];
        int ans=x-2;
        sort(a+1,a+x+1);
        for(int i=2;i<=x;i++)
        {
            // cout<<a[i]<<" "<<a[i-1]<<endl;
            if(a[i]-a[i-1]==2)ans++;
        }
        if(a[1]+n-a[x]==2)ans++;
        cout<<ans<<endl;
    }
}

$Hard\ version:\ y\ !=0$

可以在两个相邻选中点之间加点。考虑如何加点最优。

  1. 一定是隔一个点选一个点最优，这样总能自然构成一个三角形，
  2. 优先在标号相差为偶数的间隔内加点，这样的话不浪费点。
  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
#include<bits/stdc++.h>
using namespace std;

bool cmp(int x,int y)
{
    if(x%2==1 && y%2==0)return 0;
    if(x%2==0 && y%2==1)return 1;
    return x<y;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,x,y;
        cin>>n>>x>>y;
        int a[x+12];
        for(int i=1;i<=x;i++)cin>>a[i];
        

        int ans=0;
        

        sort(a+1,a+x+1);
        a[x+1]=a[1]+n;
        int d[x+12];
        for(int i=1;i<=x;i++)d[i]=a[i+1]-a[i];
        sort(d+1,d+x+1,cmp);

        int v=x;
        for(int i=1;i<=x;i++)
        {
            if(y-(d[i]-1)/2>=0)
            {
                y-=(d[i]-1)/2;
                ans+=d[i]/2;
                v+=(d[i]-1)/2;
            }
            else
            {
                ans+=y;
                v+=y;
                break;
            }
        }
        ans+=v-2;
        cout<<ans<<endl;
    }
}

math