Codeforces Round #633 (Div.2)

比赛链接 / 官方题解链接

A. Filling Diamonds

Solution

发现一旦放置一个竖着的菱形，那么它的两边其他菱形的放置方式就固定了，所以答案就是 $n$.

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, n;

int main(){
	read(T);
	while(T--){
		read(n);
		printf("%d\n", n);
	}
	return 0;
}

---

B. Sorted Adjacent Differences

Solution

排序后从两头交叉着取数，再反转，则一定满足条件。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n;
LL a[N], b[N];

int main(){
	read(T);
	while(T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]);
		sort(a+1, a+n+1);
		int l = 1, r = n, id = 0;
		while(1){
			b[++id] = a[l];
			if(l == r)	break;
			l++;
			b[++id] = a[r];
			if(l == r)	break;
			r--;
		}
		reverse(b+1, b+id+1);
		for(int i = 1; i <= n; i++)
			printf("%lld ", b[i]);
		puts("");
	}
	return 0;
}

---

C. Powered Addition

Solution

依次考虑每个数，把它用最少的时间补成最小的不低于前一个数的数。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n;
LL a[N], power[N] = {1};

int main(){
	for(int i = 1; i <= 35; i++)
		power[i] = power[i-1] * 2;
	read(T);
	while(T--){
		LL ans = 0;
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i]);
		for(int i = 2; i <= n; i++){
			LL diff = a[i-1] - a[i];
			if(diff <= 0)	continue;
			LL tim = (LL)log2(diff) + 1;
			ans = max(ans, tim);
			a[i] += power[tim] - 1;
			for(int j = tim; j >= 1; j--)
				if(a[i] - power[j-1] >= a[i-1])
					a[i] -= power[j-1];
		}
		printf("%lld\n", ans);
	}
	return 0;
}

---

D. Edge Weight Assignment

Solution

任选一个叶节点为根，我们只需要满足条件：所有其他叶节点到根的路径上异或和为 $0$ 即可。容易证明满足这个条件后任意两个叶节点之间的路径上异或和一定为 $0$.

首先考虑最少数字：

若其他叶节点到根的距离均为偶数，那么容易知道，任意两个叶节点之间的距离一定都是偶数，所以所有边都赋值为同一个数就能满足条件；若存在到根的距离为奇数的叶节点，我们一定可以用 $1,2,3$ 这三个数赋值满足条件（$2$ 个数不可能，因为凡用 $2$ 个数满足条件的一定用 $1$ 个数就够了），因为，假想我们 $dfs$ 这棵树，只要下一个点不是叶节点就赋值 $1,2,3$ 中的一个并保证前缀异或和不为 $0$，而若下一个点是叶节点就赋值为前缀异或和，这样就能满足条件。

然后考虑最多数字：

$dfs$ 这棵树，只要下一个点不是叶节点就赋值为 $(1<<k)$，其中 $k$ 是从 $0$ 开始的某个之前没有用过的数，而若下一个点是叶节点就赋值为前缀异或和。

Code

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int n, deg[N], k;
vi edge[N];

int dis[N], cnt[N];
void dfs(int x, int f, int d){
	dis[x] = d;
	if(deg[x] != 1)	k++;
	else	cnt[f]++;
	for(auto nxt: edge[x]){
		if(nxt == f)	continue;
		dfs(nxt, x, d + 1);
	}
}

int main(){
	read(n);
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
		deg[u]++, deg[v]++;
	}
	int rt = 0;
	for(rt = 1; rt <= n; rt++)
		if(deg[rt] == 1)
			break;
	dfs(rt, 0, 0);
	bool allEven = true;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 1 && dis[i] & 1){
			allEven = false;
			break;
		}
	}
	printf(allEven ? "1 " : "3 ");
	cnt[edge[rt][0]]++;
	for(int i = 1; i <= n; i++)
		k += cnt[i] > 0;
	printf("%d\n", k - 1);
	return 0;
}

---

E. Perfect Triples

比赛时找了个假的规律，结束前2分钟交上去，于是愉快地WA了……

Solution

找规律，三元组的第一个数很容易发现规律，然后第二个数应该是——第一个数的四进制表示中，$0$ 换成 $0$，$1$ 换成 $2$，$2$ 换成 $3$，$3$ 换成 $1$，第三个数就是前两个的异或。

Code

沿用了部分比赛时的代码，所以很丑……

>folded

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T;
LL n, power[40] = {1};

inline LL lg4(LL x){
	int p = lower_bound(power, power+32, x) - power;
	if(power[p] > x)	p--;
	return p;
}

int main(){
	for(int i = 1; i <= 31; i++)	power[i] = power[i-1] * 4;
	read(T);
	while(T--){
		read(n);
		LL g = lg4(n); // start with 4^g
		LL w = 0; // which col
		w = n % 3; if(!w)	w = 3;
		LL r = 0; // which row
		r = (n - power[g] + 1) / 3; if((n-power[g]+1) % 3) r++;
		LL blo = r / 4; if(r % 4)	blo++; // which block
		LL z = r % 4; if(!z)	z = 4; // which subrow
		LL a = power[g] + (blo - 1) * 4;
		a += z - 1;
		LL b = a;
		for(int i = 0; (b >> i); i += 2){
			int x = ((b >> i) & 1) | (((b >> (i+1)) & 1) << 1);
			if(x == 1)	b ^= (1ll << i), b ^= (1ll << (i+1));
			else if(x == 2)	b ^= (1ll << i);
			else if(x == 3)	b ^= (1ll << (i+1));
		}
		LL c = a ^ b;
		printf("%lld\n", w == 1 ? a : (w == 2 ? b : c));
	}
	return 0;
}