CF1971 (CF Round 944 Div.4) A-G 题解

发表于 更新于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 9 分钟

A

题意：输入两个整数，分别输出其最小值与最大值。

题解：使用 min() 与 max()。

1
2
3
4
5
6
7
8
9
10
11
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int x,y;
        cin>>x>>y;
        cout<<min(x,y)<<" "<<max(x,y)<<endl;
    }
}

B

题意：输入一个仅由小写字母构成的字符串，输出由同样字母构成的但与原字符串不同的字符串，否则报告不可能做到。

题解：除非其由完全相同的字母构成（包括单个字母），否则都为可以做到的；交换任意不同的字母即可。

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
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string x;
        cin>>x;
        int i=0;
        int len=x.length();
        int flag=1;
        if(len==1) 
        {
            cout<<"NO"<<endl;
            continue;
        }
        while(x[i]==x[i+1]&&i<len)
        {
            i++;
            if(i==len-1) flag=0;
        }
        if(flag==0) cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            for(int j=0;j<len;j++)
            {
                if(j<len-1&&x[j]!=x[j+1]) 
                {
                    cout<<x[j+1]<<x[j];
                    j++;
                }
                else cout<<x[j];
            }
            cout<<endl;
        }
    }
}

C

题意：你有一个时钟（刻度由 1 至 12），选择任意不同的四个刻度 a,b,c,da,b,c,d，连接为线段 abab 与 cdcd，请你判断其是否相交。

题解：abab 一定将时钟分为两部分，判断 c,dc,d 是否分别在时钟的不同部分。易得：如果是，则其相交；否则反之。不妨令 a<ba<b ，判断 cc 或 dd 是否属于 (a,b)(a,b)，另一者是否不属于 (a,b)(a,b) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a>b) swap(a,b);
        if((c>a&&c<b)&&((d>b&&d<=12)||d<a)) cout<<"YES"<<endl;
        else if((d>a&&d<b)&&((c>b&&c<=12)||c<a)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

D

题意：输入一个 0101 串，需要将其分段后重新组合，使得所有 00 在 11 前面，试问最少的分段次数。

题解：如果可以找到一个子段，使得其本身的所有 00 在 11 前面，便可以减少一次分段次数；其他的都只需要简单地把 00 和 11 分开即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string x;
        cin>>x;
        int cnt=1;
        int flag=0;
        for(int i=0;i<x.length()-1;i++)
        {
            if(x[i]!=x[i+1]) cnt++;
            if(x[i]=='0'&&x[i+1]=='1') flag=1;
        }
        cout<<cnt-flag<<endl;
    }
}

E

题意：你在一段路上开车，由于不同的路段的限速不一样，所以你在不同路段的行驶速度不同，但仍在同一路段上保持匀速行驶。给出道路总长 nn ， kk 段不同限速的路段，当你到达该路段尽头时的行驶距离（距离起点）aia_i 与 行驶时间（距离开始时，即 0min0 min 时）bib_i，保证数组 a,ba,b 严格递增且 ak=na_k=n。询问 qq 次：当汽车行驶距离（距离起点）为 did_i 时，其行驶时间（距离开始时，即 0min0 min 时）为多少？（向下取整）

题解：考虑二分法，二分求出 did_i 所在路段，答案为已行驶完的路段所用时间 + 该路段已行驶距离 / 该路段速度。

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
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,k,q;
        cin>>n>>k>>q;
        int a[k+5]={0},b[k+5]={0};
        for(int i=1;i<=k;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=k;i++)
        {
            cin>>b[i];
        }
        int d[q+5];
        for(int i=1;i<=q;i++)
        {
            cin>>d[i];
            int l=0,r=k;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(a[mid]>d[i])
                {
                    r=mid-1;
                }
                else 
                {
                    l=mid+1;
                }
            }
            if(a[r]==d[i])
            {
                cout<<b[r]<<" ";
            }
            else
            {
                cout<<b[r]+(d[i]-a[r])*(b[r+1]-b[r])/(a[r+1]-a[r])<<" ";
            }
        }
        cout<<endl;
    }
}

F

题意：给出正整数 rr，找到在平面直角坐标系中的整数坐标点，使得其与 (0,0)(0,0) 的距离大于等于 rr 且严格小于 r+1r+1，找出这样的点的数量。

题解：首先，距离为 [r,r+1)[r,r+1) 的所有点构成一个圆环，其四分之一圆弧上的整数点一定占总数的四分之一，我们只用考虑其四分之一圆弧即可。以第二象限的圆弧为例，容易发现若以位于 Y 轴的整数点为起点，其它整数点都在其左下方。因圆弧宽度为 11，容易发现：不存在一个点，在符合要求的点左方 22 格仍符合要求；不存在一个点，在符合要求的点下方 22 格仍符合要求；若一个符合要求的点左方 11 格和下方 11 格都没有符合要求的点，则其左下方 11 格的点应符合要求。故我们可以考虑以位于 Y 轴的整数点为起点，依次向其左方、下方或左下方寻找符合要求的点，直到位于 X 轴的整数点为止。

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
int r;
int cnt;
list <pair<int,int>> lst;
void bfs(int x,int y)
{
    cnt++;
    lst.pop_front();
    int flag=0;
    if((x-1)*(x-1)+y*y>=r*r&&(x-1)*(x-1)+y*y<(r+1)*(r+1)&&y!=0)
    {
        lst.push_back(make_pair(x-1,y));
        flag=1;
    }
    if(x*x+(y-1)*(y-1)>=r*r&&x*x+(y-1)*(y-1)<(r+1)*(r+1)&&(y-1)!=0)
    {
        lst.push_back(make_pair(x,y-1));
        flag=1;
    }
    if(flag==0&&(x-1)*(x-1)+(y-1)*(y-1)>=r*r&&(x-1)*(x-1)+(y-1)*(y-1)<(r+1)*(r+1)&&(y-1)!=0)
    {
        lst.push_back(make_pair(x-1,y-1));
    }
    if(lst.size()==0) return;
    else bfs(lst.front().first,lst.front().second);
}
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cnt=0;
        cin>>r;
        lst.push_back(make_pair(0,r));
        bfs(0,r);
        cout<<cnt*4<<endl;
    }
}

G

题意：给出有 nn 个元素的数组 aa，你可以交换 aia_i 与 aja_j 当且仅当 ai XOR aj<4a_i\ XOR\ a_j<4，XORXOR 指按位异或。请交换任意元素后，使得其字典序最小，求出字典序最小的数组。

题解：由异或的定义易得：当且仅当 aia_i 与 aja_j 除了最后 22 位（二进制下）其它位数皆相同时，ai XOR aj<4a_i\ XOR\ a_j<4 成立。所以将数据中满足该条件的数据归为一组，在该组中任意交换，使得字典序最小。可以使用 map 与优先队列（priority_queue）实现；注意优先队列默认从大至小排序。时间复杂度 O(nlogn)O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int a[n+5];
        map<int,priority_queue<int>>mp;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mp[a[i]>>2].push(-a[i]);//a[i]>>2返回a[i]右移2位（二进制下）后的数字，即忽略最后2位后进行分组排序
        }
        for(int i=1;i<=n;i++)
        {
            cout<<-mp[a[i]>>2].top()<<" ";
            mp[a[i]>>2].pop();
        }
        cout<<endl;
    }
}