Codeforces Round #638 (Div.2)

比赛链接 / 官方题解链接

A. Phoenix and Balance

Solution

$a=1\underbrace{00\cdots0}_\frac{n}{2}11\cdots1$，$b=0\underbrace{11\cdots1}_\frac{n}{2}00\cdots0$

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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, n;

int main(){
	for(read(T); T; T--){
		read(n);
		LL a = (1ll << n);
		for(int i = 1; i < n / 2; i++)
			a += (1ll << i);
		LL b = (1ll << (n + 1)) - 2 - a;
		printf("%lld\n", a - b);
	}
	return 0;
}

---

B. Phoenix and Beauty

Solution

‘beautiful’ 其实就是以 $k$ 为循环节。如果原有数字种类数多于 $k$，则无解，否则任选一个没有出现过的数补满 $k$ 个数构成循环节，输出即可。

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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 10005;

int T, n, k, a[N];
bool b[N];

int main(){
	for(read(T); T; T--){
		read(n, k);
		memset(b, 0, sizeof b);
		int cnt = 1, diff = 0;
		for(int i = 1; i <= n; i++){
			read(a[i]);
			if(a[i] <= a[i-1])	cnt++;
			if(!b[a[i]]){
				b[a[i]] = true;
				diff++;
			}
		}
		if(diff > k){ puts("-1"); continue; }
		int mark = 0;
		for(mark = 1; mark <= 100; mark++)
			if(!b[mark])
				break;
		vi loop;
		for(int i = 1; i <= 100; i++)
			if(b[i])
				loop.pb(i);
		for(int i = 1; i <= k - diff; i++)
			loop.pb(mark);
		printf("%d\n", (int)loop.size() * cnt);
		for(int i = 1; i <= cnt; i++)
			for(auto t: loop)
				printf("%d ", t);
		puts("");
	}
	return 0;
}

---

C. Phoenix and Distribution

Solution

排序后取前 $k$ 个字符为 $k$ 个字符串的第一个字符。

• 如果前 $k$ 个字符不全相同，那么答案就是 $s[k]$，因为可以把后面的所有字符接到 $sl$ 之后
• 如果前 $k$ 个字符全相同
  • 如果后面的字符全相同，那么平均分配到 $k$ 个字符串上
  • 如果后面的字符不全相同，那么答案就是 $s[k…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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n, k;
char s[N];

int main(){
	for(read(T); T; T--){
		read(n, k);
		scanf("%s", s+1);
		sort(s+1, s+n+1);
		bool diff = false;
		for(int i = 1; i <= k; i++){
			if(s[i] != s[1]){
				diff = true;
				break;
			}
		}
		if(diff){ putchar(s[k]); puts(""); continue; }

		diff = false;
		for(int i = k + 1; i <= n; i++){
			if(s[i] != s[k+1]){
				diff = true;
				break;
			}
		}
		if(diff){ printf("%s\n", s+k); continue; }



		putchar(s[k]);
		if(n > k){
			for(int i = 1; i <= (n - k - 1) / k + 1; i++)
				putchar(s[k+1]);
		}
		puts("");
	}
	return 0;
}

---

D. Phoenix and Science

Solution

题目可以转换为：找到一个数列 $\{x_n\}$ 满足 $x_{n-1}\leq x_n\leq2x_{n-1}$.

考虑数列 $\{2^n\}$，找到最后一个前缀和小于等于 $n$ 的位置，设 $n$ 比这个前缀和多出来了 $r$，那么只需要把 $r$ 插入到数列 $\{2^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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, n, b[40], c[40], a[40];

int main(){
	for(int i = 0; i <= 30; i++){
		a[i] = (1ll << (i + 1)) - 1;
		b[i] = 1 << i;
	}
	for(read(T); T; T--){
		read(n);
		int d = lower_bound(a+1, a+31, n) - a;
		printf("%d\n", d);
		int r = n - a[d-1], cnt = 0;
		for(int i = 1; cnt < d; i++){
			if(r < b[i]){
				printf("%d ", r - b[i-1]);
				cnt++;
				if(cnt == d)	break;
				printf("%d ", b[i] - r);
				cnt++;
				r = 2147483647;
			}
			else{
				printf("%d ", b[i] - b[i-1]);
				cnt++;
			}
		}
		puts("");
	}
	return 0;
}

---

E. Phoenix and Berries

Solution

参考博客：link

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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 505;

int n, k;
LL a[N], b[N], dp[N][N], tot;

int main(){
	read(n, k);
	for(int i = 1; i <= n; i++)
		read(a[i], b[i]);
	memset(dp, -1, sizeof dp);
	dp[0][0] = 0;
	for(int i = 0; i < n; i++){
		tot += a[i] + b[i];
		for(int j = 0; j < k; j++){
			if(dp[i][j] == -1)	continue;
			LL red = j + a[i+1];
			LL blue = tot - dp[i][j] * k - j + b[i+1];
			for(int r = 1; r <= min(a[i+1], k-1ll); r++)
				if(b[i+1] >= k - r)
					dp[i+1][(red-r)%k] = max(dp[i+1][(red-r)%k], dp[i][j] + (red-r)/k + (blue-k+r)/k + 1); 
			dp[i+1][red%k] = max(dp[i+1][red%k], dp[i][j] + red / k + blue / k);
		}
	}
	LL ans = 0;
	for(int i = 0; i < k; i++)
		ans = max(ans, dp[n][i]);
	printf("%lld\n", ans);
	return 0;
}

---

F. Phoenix and Memory

Solution

【参考官方题解】首先考虑如何求出一个合法序列：将所有线段按左端点排序，然后依次考虑每一个数字应该放在哪一个线段上，由贪心，应该放到左端点小于等于该数的线段中右端点最小的线段上——这可以通过 set 完成。

现在考虑序列是否唯一。如果不唯一的话，我们一定可以交换序列中的两数而序列仍然合法。在将线段排序后，如果我们能够交换第 $i$ 条线段上的数字 $p[i]$ 和第 $j$ 条线段上的数字 $p[j]$，那么一定有：$l[j]\leq p[i]<p[j]\leq r[i]$ 或 $l[i]\leq p[j]<p[i]\leq r[j]$，于是我们可以通过线段树完成查找。

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 vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200005;

int n, pos[N], ans[N], f[N];
struct Node{
	int l, r, id;
	bool operator < (const Node &A) const{
		return l == A.l ? r < A.r : l < A.l;
	}
}a[N];

set<pii> s;

struct segTree{
	int l, r, mx, idx;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
	if(tr[lid].mx > tr[rid].mx){
		tr[id].mx = tr[lid].mx;
		tr[id].idx = tr[lid].idx;
	}
	else if(tr[rid].mx >= tr[lid].mx){
		tr[id].mx = tr[rid].mx;
		tr[id].idx = tr[rid].idx;
	}
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].mx = tr[id].idx = 0;
	if(l == r)	return;
	build(lid, l, mid);
	build(rid, mid+1, r);
	pushup(id);
}
void modify(int id, int pos, int val){
	if(tr[id].l == tr[id].r){
		tr[id].mx = val;
		tr[id].idx = tr[id].l;
		return;
	}
	if(pos <= mid)	modify(lid, pos, val);
	else	modify(rid, pos, val);
	pushup(id);
}
pii query(int id, int l, int r){
	if(l > r)	return mp(-1, -1);
	if(tr[id].l == l && tr[id].r == r)	return mp(tr[id].mx, tr[id].idx);
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else{
		pii resl = query(lid, l, mid);
		pii resr = query(rid, mid+1, r);
		if(resl.first >= resr.first)	return resl;
		else	return resr;
	}	
}

int main(){
	read(n);
	for(int i = 1; i <= n; i++){
		read(a[i].l, a[i].r);
		a[i].id = i;
	}
	sort(a+1, a+n+1);
	int now = 0;
	for(int i = 1; i <= n; i++){
		while(now < n && a[now+1].l <= i){
			now++;
			s.emplace(mp(a[now].r, now));
		}
		while(!s.empty() && s.begin() -> first < i)
			s.erase(s.begin());
		pos[i] = s.begin() -> second;
		f[s.begin() -> second] = i;
		s.erase(s.begin());
	}
	for(int i = 1; i <= n; i++)	ans[a[pos[i]].id] = i;
	bool ok = true;
	now = 0;
	int mark1 = 0, mark2 = 0;
	build(1, 1, n);
	for(int i = 1; i <= n; i++)	modify(1, f[i], a[i].r);
	for(int i = 1; i <= n; i++){
		pii res = query(1, a[i].l, f[i]-1);
		if(res.first >= f[i]){
			ok = false;
			mark1 = a[pos[res.second]].id;
			mark2 = a[i].id;
			break;
		}
	}
	if(ok){
		puts("YES");
		for(int i = 1; i <= n; i++)	printf("%d ", ans[i]);
		return 0;
	}
	else{
		puts("NO");
		for(int i = 1; i <= n; i++)	printf("%d ", ans[i]);
		puts("");
		swap(ans[mark1], ans[mark2]);
		for(int i = 1; i <= n; i++)	printf("%d ", ans[i]);
		return 0;
	}
}