ABC347 C~D~?（更新中）

Portal:https://atcoder.jp/contests/abc347/tasks

ABC347只过了\(A,B\)，再创新低，。。。遂来补题

C - Ideal Holidays

题意简述

输入\(n,a,b,d_1,d_2,…,d_n\)，表示在Atcoder国每周分为\(a\)天休息日和\(b\)天工作日，现在有\(n\)个事件，第\(i\)个事件落在第\(d_i\)日。我忘了今天是这一周的第几天，需要你输出这\(n\)个事件是否有可能全部落在休息日。

分析

一开始是对\(n\)个日期取模\(a+b\)然后再求极差\(k\)，如果\(k<a\)就Yes，否则No……

然后就\(WA\)了一个点。见下：

2 5 1
5 6

\(2\)个事件：\(\{5,6\}\)，\(5\)天休息日，\(1\)天工作日。本应输出Yes，但是输出了No。这是因为对\(5\)和\(6\)取模\(6\)分别得\(5\)和\(0\)，所以只判断极差是不行的。应该把所有\(d[i]\)取模后的结果存在\(d\)中，从小到大排序，然后把两个日期之间的天数（包括\(d[1]+a+b-d[n]\)）求最大值。因为\(d[i]\)取值范围是\([0,a+b)\)，所以如果两个天数之间差距\(\geq b\)（工作日的天数），就说明这些日期都能安排在休息日。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a,b,d[200010];
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>d[i];
		d[i]%=(a+b);
	}
	sort(d+1,d+1+n);
	int maxx=INT_MIN;
	for(int i=2;i<=n;i++){
		maxx=max(maxx,d[i]-d[i-1]-1);
	}
	maxx=max(maxx,d[1]+a+b-d[n]-1);
	if(maxx>=b) cout<<"Yes\n";
	else cout<<"No\n";
}

D - Popcount and XOR

题意简述

给你非负整数\(a,b,C\)，构造出非负整数\(X,Y\)满足下列条件：

• \(0 \leq X < 2^{60}\)
• \(0 \leq Y < 2^{60}\)
• \(\operatorname{popcount}(X) = a\)
• \(\operatorname{popcount}(Y) = b\)
• \(X \oplus Y = C\)

\(popcount(X)\)表示\(X\)二进制表示中\(1\)的个数。
\(\oplus\)表示按位异或。

分析

这个题难度其实并不高，但因为赛时跟C鏖战太久并且吃了\(4\)次罚时还没\(A\)，所以思路乱了。第二天一想就出来了。

设\(k\)为\(C\)中\(1\)的个数，\(x,y\)分别为\(X,Y\)中，放在\(C\)值为\(1\)的位置上的\(1\)的个数。则有下列关于\(x,y\)的方程组：

\(\begin{cases} a-x=b-y\\ x+y=k \end{cases}\)

则有\(\begin{cases} x=\frac{a-b+k}{2}\\ y=k-x \end{cases}\)

那么我们总结了部分输出No的情况：

• \((a-b+k)\ mod\ 2\neq 0\)（注意负数\(mod\ 2\)可能等于\(-1\)）；
• \(x<0,y<0,x\geq a或y\geq b\)。

根据目前的结果，我们可以进行构造了，\(0\leq i<60\)，\(cnt0\)和\(cnt1\)分别表示到目前\(s[i]=0和1\)的个数。详见代码。

需要注意的是还有一种输出No的情况，也就是构造完，\(a\)个\(1\)或者\(b\)个\(1\)没有用完。比如\(a=60,b=60,c=2^{60}-1\)，不会被前面的步骤筛查出来，但是发现\(X\)和\(Y\)中一共只能用\(60\)个\(1\)，\(a\)和\(b\)没有用完。所以需要定义\(cnt\)来记录填了多少\(1\)，每构造完一个就判断如果\(cnt<a\)（如果构造的是\(Y\)就判断\(cnt<b\)）就输出No。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
signed main(){
	cin>>a>>b>>c;
	bitset<70> s(c),A,B;
	int k=s.count();
	int dx=a-b+k;
	if(dx%2!=0){
		cout<<"-1\n";
		return 0;
	}
	int x=dx/2,y=k-x;
	if(x<0||y<0||x>a||y>b){
		cout<<"-1\n";
		return 0;
	}
	int cnt=0;
	for(int i=0,cnt0=0,cnt1=0;i<60;i++){
		if(s[i]==0){
			if(cnt0<a-x) A[i]=1,cnt++;
			cnt0++;
		}else{
			if(cnt1<x) A[i]=1,cnt++;
			cnt1++;
		}
	}
	if(cnt<a){
		cout<<"-1\n";
		return 0;
	}
	cnt=0;
	for(int i=0,cnt0=0,cnt1=0;i<60;i++){
		if(s[i]==0){
			if(cnt0<b-y) B[i]=1,cnt++;
			cnt0++;
		}else{
			if(cnt1>=x) B[i]=1,cnt++;
			cnt1++;
		}
	}
	if(cnt<b){
		cout<<"-1\n";
		return 0;
	}
	cout<<A.to_ullong()<<" "<<B.to_ullong()<<"\n";
	return 0;
}

\([To\ be\ continued?]\)

不行太菜了，必须多练了