Codeforces Round 944 (Div. 4) 回顾

比赛回顾

赛中是AC了前四题，E答案错误，F超时。可以说是做到了最后五分钟，排名是6000多。

比赛链接

官方题解链接

题目分析

AB就直接跳过了，纯签到。

C. Clock and Strings

C题意思是给出表中两对数字，看每对数字连接的线是否相交。我的思路是只要一条线的一个端点在另一条线的区间内，切另一端在区间外即可断定这两条线是相交的。

为了更好的进行区分，我进行了排序，其中满足a<c a<b c<d。

我觉得不能直接去写，表上的数字是1到12，对于一条线，一个端点是1，另一个端点是10，其中11和12其实是在线的包围内的，所以我给所有小于6的数字加了12，区间变成了6到17，然后判断是否c在a和b之间,d在a和b之外。
但是我今天才发现我的判断语句竟然是这样的：

1
2
if((a<c&&c<b)||(a<d&&d<b)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

我究竟是怎么过了这题的所有数据，只判断了一端在区间内就过了，根本没看是否另一端是否在区间外。。。

官方题解就很有意思，他是从1到12遍历，记录一个字符串，如果碰到第一条线的端点，字符串就加一个’a’，碰到另一条线的端点，字符串就加一个’b’，这样如果答案是’abab’或者’baba’就说明有一条线的端点在另一条线区间内而且另一端点在区间外，非常巧妙。

1
2
3
4
5
6
7
8
9
10
void solve() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	string s;
	for (int i = 1; i <= 12; i++) {
		if (i == a || i == b) {s += "a";}
		if (i == c || i == d) {s += "b";}
	}
	cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n");
}

D. Binary Cut

将01数组剪切成最少的组，使能够让这些组自由组合后成为一个0全部在前面，1全部在后面的数组。

很遗憾我的AC代码被场后Hack数据卡掉了。这里思路就是相邻的1或者0分成一组，这样就分成了很多个1的组合和很多个0的组合，但是有一点需要注意，因为最终我们需要的数组是0在前1在后，所以如果有01出现的话，我们可以少分一组，比如10001我们不是分成三组1、000、1,而是1和0001两组。因为分界点只有一个，所以如果有一个01出现，答案我们减去1即可。

同样这题的官方题解也很有趣。他在判断是否有01出现时采用了位运算，而不是像我一样写丑陋的if语句。

1
2
3
4
5
6
7
8
9
10
11
void solve() {
	string s;
	cin >> s;
	int res = 1;
	bool ex = false;
	for (int i = 0; i + 1 < (int)(s.size()); i++) {
		res += (s[i] != s[i + 1]);
		ex |= (s[i] == '0' && s[i + 1] == '1');
	}
	cout << res - ex << '\n';
}

E. Find the Car

这题就是很简单的物理里的算速度的题目。给出k个路上的点，然后给出到达每个点的时间，其中设定每两点之间的速度是常数，也就是每一段路都是匀速。我们需要找到到达某一个点（不一定是给出的点）所花费的时间。但是比赛时我以为给出的时间是前一个点到下一个点的时间，所以用前缀和算的时间，样例竟然都过了。。。。注意我们要先用二分找到问的点是哪两个已知点之间。

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
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,k,q;
        cin>>n>>k>>q;
        vector<unsigned long long> a(k+1);
        for(int i=1;i<=k;i++){
            cin>>a[i];
        }
        vector<unsigned long long> b(k+1);
        vector<unsigned long long> sum(k+1);
        for(int i=1;i<=k;i++){
            cin>>b[i];
            sum[i]=sum[i-1]+b[i];
        }
        for(int i=1;i<=q;i++){
            int pos;
            cin>>pos;
            int l=1,r=k;
            while(l<r){
                int mid=(l+r)/2;
                if(a[mid]>=pos){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            
            a[0]=0;
            b[0]=0;
            sum[0]=0;
            l--;
            unsigned long long ans= 0;
            ans = b[l]+((unsigned long long)pos-a[l])*(b[r]-b[l])/(a[r]-a[l]);
            cout<<ans<<" ";
        }
        cout<<endl;
    }
    return 0;
}

F. Circle Perimeter

在笛卡尔坐标系中找到与原点的直线距离大于r小于r+1的点的个数。

因为数据很大不能纯暴力找。坐标系都是对称的，所以只需要算第一象限加y轴或者x轴然后答案x4即可。

官方题解的意思是x轴0到1遍历，先将y坐标设置为r。显然x只会越来越大，如果想要满足要求y就必须越来越小。先将y控制到点到原点距离小于r+1的高度，然后y继续减的同时ans++，直到距离小于r，x增加后继续此操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve()
{
    long long r;
    cin >> r;
    long long height = r;
    long long ans = 0;
    for(long long i = 0; i <= r; i++)
    {
        while(i*i+height*height >= (r+1)*(r+1))
        {
            height--;
        }
        long long cop = height;
        while(i*i+cop*cop >= r*r && cop > 0)
        {
            cop--;
            ans++;
        }
    }
    cout << ans*4 << endl;
}

G. XOUR

这题就是给你n个数字，如果两个数之间XOR操作后小于等于4，那么这两个数是可以换位置的。求换位后字典序最小的数列。

先把所有数字以二进制的方式看待，不难发现如果两个数XOR操作后如果小于等于4，说明除了后两位，其他位置的0或者1是完全一样的，这样才能让前面的数异或后变成0。我们需要把所有除了后两位前面位全部相同的数字分到一个组里面，这样一个组里面的数字位置是可以随意互换的。

官方题解非常巧妙地运用了C++的STL。使用了一个map，key是a[i]>>2，value是一个priority_queue，这样就可以将所有前面位一样的存在一个优先队列里面。在取数字的时候，排在队列前面的就是一个组里面字典序最小的数字。注意，优先队列默认是大根堆，所以我们需要存的是每个数的相反数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, priority_queue<int>> mp;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        mp[a[i]>>2].push(-a[i]);
    }
    for(int i = 0; i < n; i++)
    {
        cout << -mp[a[i]>>2].top() << " ";
        mp[a[i]>>2].pop();
    }
    cout << endl;
}

H. ±1

这是一个关于SAT的题目，暂时不会。