Codeforces Global Round 9 A~F补题

发表于 更新于 分类于 阅读次数：

Codeforces Global Round 9，掉到了1791

A.Sign Flipping

很简单，正负轮流就好

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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=105,inf=0x3f3f3f3f,mod=1000000007;
int a[maxn];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(i&1)
                a[i]=-abs(a[i]);
            else
                a[i]=abs(a[i]);
        }
        for(int i=1;i<=n;i++)
            cout<<a[i]<<' ';
        cout<<endl;
    }
    return 0;
}

B.Neighbor Grid

还是先判断是否有解，贪心构造

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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=305,inf=0x3f3f3f3f,mod=1000000007;
int a[maxn][maxn];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n,m;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]>4)
                    ok=0;
                else if((i==1||i==n)&&(j==1||j==m)&&a[i][j]>2)
                    ok=0;
                else if((i==1||i==n||j==1||j==m)&&a[i][j]>3)
                    ok=0;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if((i==1||i==n)&&(j==1||j==m))
                    a[i][j]=2;
                else if(i==1||i==n||j==1||j==m)
                    a[i][j]=3;
                else
                    a[i][j]=4;
            }
        cout<<(ok?"YES":"NO")<<endl;
        if(ok)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                    cout<<a[i][j]<<' ';
                cout<<endl;
            }
        }
    }
    return 0;
}

C.Element Extermination

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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=3e5+10,inf=0x3f3f3f3f,mod=1000000007;
int a[maxn];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        cout<<(a[1]<a[n]?"YES":"NO")<<endl;
    }
    return 0;
}

D.Replace by MEX

题意

给你$n$个范围在$[0,n]$区间内的整数，你可以进行最多$2n$次如下操作，使用数组的$MEX$替换数组的任意一个元素。请输出一种得到非递减序列的方案。

思路

尝试构造$0,1,2\dots n-1$的序列，设下标从$0$开始，每个位置与下标相等的点为确定点，当每个点都为确定点时，构造完毕。只需要将每次得到的$MEX$填入对应的下标，即可得到新的确定点（因为$MEX$一定不在数组中），当得到的$MEX$为$n$时要特判，找到一个不为确定点的元素并替换。

代码

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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=1005,inf=0x3f3f3f3f,mod=1000000007;
int n,a[maxn];
int MEX[maxn];
int mex()
{
    for(int i=0;i<=n;i++)
        if(!MEX[i])
            return i;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int fix=0;
        memset(MEX,0,sizeof(MEX));
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            MEX[a[i]]++;
            if(a[i]==i)
                fix++;
        }
        vector<int>ans;
        while(fix<n)
        {
            int now=mex();
            if(now==n)
            {//找到一个未确定的点替换
                for(int i=0;i<n;i++)
                {
                    if(a[i]!=i)
                    {
                        MEX[a[i]]--;
                        MEX[a[i]=now]++;
                        ans.push_back(i+1);
                        break;
                    }
                }
            }
            else{
                MEX[a[now]]--;
                MEX[a[now]=now]++;
                fix++;
                ans.push_back(now+1);
            }
        }
        cout<<ans.size()<<endl;
        for(auto &x:ans)
            cout<<x<<' ';
        cout<<endl;
    }
    return 0;
}

E.Inversion SwapSort

题意

给你长度为$n$的序列$a$，你要将$a$中所有逆序对的下标对做一个排列形成操作序列，当你按次序交换每一个下标后，$a$是按非递减排好序的。

思路

令$pos[x]=i$表示元素$x$的当前下标为$i$。先考虑对于一个排列$p$该如何操作：第$i$轮将第$i$大的元素移到第$i$位。记在当前第$i$位的元素为$q_i$，因为$[i+1,n]$区间元素已经归位，当前因为$q_i$而形成的逆序对（即逆序对的第二个数值为$i$）为数值$q_i+1,q_i+2,\dots i$与$q_i$构成的逆序对。这时依次交换$(pos[q_i+1],i),(pos[q_i+2],i),\dots,(pos[i],i)$即可使$i$移动到第$i$位且[1,i-1]位每个元素相对大小不变。

PS：依次交换$(pos[q_i+1],i),(pos[q_i+2],i),\dots,(pos[i],i)$相当于从$[q_i,i]$依次用$x-1$替换$x$，并最终将$i$填入$i$，相当于$[1,i-1]$区间的大于$q_i$的部分全部减1，相对大小不变，逆序对也不发生变化。

当数组中出现了数值相等情况时，更改元素的值，令后面的元素大于前面的元素，不影响答案。

代码

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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define int ll
const int maxn=1e5+10,inf=0x3f3f3f3f,mod=1000000007;
struct BinaryIndexedsTree
{
    int n;
    ll c[maxn],sum[maxn];//c维护差分数组,sum维护i*c[i]的前缀和
    inline int lowbit(int x)
    {
        return x & (-x);
    }
    void build(int *a,int n)//a是原数组,n是元素个数
    {
        this->n=n;
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            add(i,a[i]-a[i-1]);//构建差分c数组
    }
    void add(int k,ll val)//修改:a[k]加上val,直接在c数组上操作
    {
        for(int i=k;i<=n;i+=lowbit(i))//从叶子一直更新到父节点
            c[i]+=val,sum[i]+=val*(k-1);//每个节点都加上val
    }
    void radd(int l,int r,ll val)//区间更新
    {
        add(l,val);//把l之后所有的点都更新一遍
        add(r+1,-val);//因为r之后的点是不用更新的,但是多更新了,所以要每个点都-val；
    }
    ll query(int k)//查询:c[i]前缀和的前缀和,即a[i]的前缀和
    {//节点i的长度为lowbit(i)
        ll ret=0;
        for(int i=k;i;i-=lowbit(i))
            ret+=k*c[i]-sum[i];
        return ret;
    }
} bit;
int a[maxn],pos[maxn];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    vector<pii>ans;
    vector<int>v;
    map<int,int>mp;
    int n;
    cin>>n;
    bit.build(a,n);
    for(int i=1;i<=n;i++)
        cin>>a[i],v.push_back(a[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++)//离散化
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    for(int i=1;i<=n;i++)
        bit.radd(a[i],a[i],1);
    for(int i=1;i<=n;i++)
    {//变为一个n的排列
        mp[a[i]]++;
        a[i]=bit.query(a[i]-1)+mp[a[i]];
        pos[a[i]]=i;
    }
    for(int i=n;i>=1;i--)
    {//尝试将当前最大的归位
        for(int j=a[i]+1;j<=i;j++)
        {
            int p1=pos[j],p2=i;
            pos[a[p1]]=p2;
            pos[a[p2]]=p1;
            swap(a[p1],a[p2]);
            ans.push_back(make_pair(p1,p2));
        }
    }
    cout<<ans.size()<<endl;
    for(auto &x:ans)
        cout<<x.first<<' '<<x.second<<endl;
    return 0;
}

F. Integer Game

一道交互题

题意

两个人在玩一个游戏，B有三堆数量不同的石子$a,b,c$，A每次给B石子任意个，B可以将这些石子合并到任意一堆，但不能连续合并到相同一堆。如果其中有两堆石子数量相同，则A胜；若超过1000次A仍未胜出，则B胜出。

思路

可以发现，当三个数构成等差数列且最大堆无法操作时，A必胜。
所以我们尽量创造这种情况，假设$a<b<c$，得到$y$的那一堆会变为最大

  1. 若B将$y$加在$a$上，解得$y=2c-b-a$
  2. 若B将$y$加在$b$上，解得$y=2c-b-a$
  3. 若B选择加在$c$上，则无解

所以我们又要创造前置情况：B无法对最大的堆进行操作，即将第一个$y$设为一个很大的数，任意一堆合并后都会变为最大。

因此，A在三步内必胜
1.给出一个很大的数
2.给出$2c-b-a$
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
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
//#define int ll
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    ll pre=1000000000,a[4],x;
    for(int i=1;i<=3;i++)
        cin>>a[i];
//    sort(a,a+3);
    cout<<"First"<<endl;
    int cnt=0;
    cout<<pre<<endl;
    cout.flush();
    while(cin>>x&&x)
    {
        a[x]+=pre;
        if(cnt==0)
            pre=3*max({a[1],a[2],a[3]})-a[1]-a[2]-a[3];
        else
            pre=(max({a[1],a[2],a[3]})-min({a[1],a[2],a[3]}))>>1;
        cout<<pre<<endl;
        cout.flush();
        cnt++;
    }
    return 0;
}