Codeforces Round #702 (Div. 3) 题解

本场链接:Codeforces Round #702 (Div. 3)

A. Dense Array

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 55;
int a[N];

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		forn(i,1,n)	scanf("%d",&a[i]);
		
		int res = 0;
		forn(i,1,n - 1)
		{
			int minv = min(a[i],a[i + 1]),maxv = max(a[i],a[i + 1]);
			while(maxv > 2 * minv)	minv *= 2,++res;
		}
		printf("%d\n",res);
	}
	return 0;
}

B. Balanced Remainders

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

int c[3];

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n,x;scanf("%d",&n);
		c[0] = c[1] = c[2] = 0;
		forn(i,1,n)	scanf("%d",&x),++c[x % 3];
		int res = 0;
		while(c[0] != n / 3 || c[1] != n / 3 || c[2] != n / 3)
		{
			if(c[0] > n / 3)	res += c[0] - n / 3,c[1] += c[0] - n / 3,c[0] = n / 3;
			if(c[1] > n / 3)	res += c[1] - n / 3,c[2] += c[1] - n / 3,c[1] = n / 3;
			if(c[2] > n / 3)	res += c[2] - n / 3,c[0] += c[2] - n / 3,c[2] = n / 3;
		}
		printf("%d\n",res);
	}
	return 0;
}

C. Sum of Cubes

思路

枚举\(b\),由范围可以知道\(1 \leq b \leq 10^4\).\(a\)可以求一个立方根.如果用浮点数的话需要额外处理边界一些其他值来避免精度问题.我写的是整数二分.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	


int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		ll x;scanf("%lld",&x);
		bool ok = 0;
		for(ll b = 1;b <= min(x,10000ll);++b)
		{
			ll a3 = x - b * b * b;
			if(a3 < 0)	break;
			ll l = 1,r = 10000;
			while(l < r)
			{
				ll mid = l + r >> 1;
				if(mid * mid * mid >= a3)	r = mid;
				else l = mid + 1;
			}
			if(l * l * l == a3)
			{
				ok = 1;
				break;
			}
		}
		if(ok)	puts("YES");
		else puts("NO");
	}
	return 0;
}

D. Permutation Transformation

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	

const int N = 105;
int son[N][2],a[N],depth[N],idx;

int build(int l,int r)
{
	if(l > r)	return 0;
	if(l == r)	return l;
	int root = 0,maxv = 0;
	forn(i,l,r)
	{
		if(a[i] > maxv)
		{
			maxv = a[i];
			root = i;
		}
	}
	son[root][0] = build(l,root - 1),son[root][1] = build(root + 1,r);
	return root;
}

void dfs(int u)
{
	if(son[u][0])	depth[son[u][0]] = depth[u] + 1,dfs(son[u][0]);
	if(son[u][1])	depth[son[u][1]] = depth[u] + 1,dfs(son[u][1]);
}

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		forn(i,1,n)	scanf("%d",&a[i]),son[i][0] = son[i][1] = 0;
		
		int root = build(1,n);
		depth[root] = 0;
		dfs(root);
		
		forn(i,1,n)	printf("%d ",depth[i]);puts("");
	}
	return 0;
}

E. Accidental Victory

思路

首先次序无所谓,可以先给所有人排序.其次枚举到第\(i\)个人检查他是否可以获胜的时候,他一是可以直接吃掉所有在他左边的人的分,也就是说对于\(i\)来说他的权应该是\(s[i]\)前缀和,那么现在的问题就是\(s[i]\)是否大于等于\(a[i+1]\),如果是的话\(i\)还可以继续吃掉\(a[i+1]\)往下走,拿到\(a[i+1]\)的分值等价于把现在的分换成\(s[i + 1]\).接着可以发现\(i\)是否能吃烂分吃掉最后一个人,可以等价于:\(i\)能吃掉\(a[i + 1]\)的分,且从\(i+1\)开始一直能吃到\(n\)的烂分.这个可以后缀与和向前递推.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	
#define forr(i,x,n)	for(int i = n;i >= x;--i)

typedef pair<int,int> pii;
#define x first
#define y second

const int N = 2e5+7;
pii a[N];
bool win[N];
ll s[N];

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		forn(i,1,n)	scanf("%d",&a[i].x),a[i].y = i;
		sort(a + 1,a + n + 1);
		
		forn(i,1,n)	s[i] = s[i - 1] + a[i].x;
		forn(i,1,n)	win[i] = (s[i] >= a[i + 1].x);win[n] = 1;
		forr(i,1,n - 1)	win[i] &= win[i + 1];		
		vector<int> res;
		forr(i,1,n)	if(win[i])	res.push_back(a[i].y);
		
		sort(res.begin(),res.end());
		printf("%d\n",(int)res.size());
		for(auto& v : res)	printf("%d ",v);puts("");
	}
	return 0;
}

F. Equalize the Array

思路

枚举每个数\(C\)表示我想把所有数出现次数拉到C.那么对于所有出现次数小于\(C\)的数来说,我都必须一个一个删除他们.对于出现次数大于\(C\)的数我可以只删其中的\(i-C\)个,其中\(i\)表示的是出现次数为\(i\)的某个数对应的出现次数.

简单来说:需要维护每个数的出现次数,每个数出现次数的出现次数.分别记为cntc_cnt.对于\(<C\)的部分,必须全部删除,这个求的是有多少个数字,对于\(>C\)的部分,可以删除$(i-C) * \(出现次数为\)i$的数的种类数.分别前缀和维护就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)	
#define forr(i,x,n)	for(int i = n;i >= x;--i)

const int N = 2e5+7;
int cnt[N],a[N];
int c_cnt_kind[N],c_cnt_num[N];
ll s_c_cnt_kind[N],sj_c_cnt[N],s_c_cnt_num[N];
set<int> st[N];
vector<int> val;

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n;scanf("%d",&n);
		forn(i,0,n)	cnt[i] = 0,sj_c_cnt[i] = 0,st[i].clear(),
		c_cnt_kind[i] = 0,c_cnt_num[i] = 0,s_c_cnt_num[i] = 0,s_c_cnt_kind[i] = 0;
		
		val.clear();
		forn(i,1,n)	scanf("%d",&a[i]),val.push_back(a[i]);
		sort(val.begin(),val.end());
		val.erase(unique(val.begin(),val.end()),val.end());
		forn(i,1,n)	a[i] = lower_bound(val.begin(),val.end(),a[i]) - val.begin() + 1,++cnt[a[i]];
		
		forn(i,1,n)	st[cnt[a[i]]].insert(a[i]);
		forn(i,1,n)	c_cnt_kind[i] = (int)st[i].size(),
					++c_cnt_num[cnt[a[i]]];
		forn(i,1,n)	s_c_cnt_kind[i] = s_c_cnt_kind[i - 1] + c_cnt_kind[i],
					s_c_cnt_num[i] = s_c_cnt_num[i - 1] + c_cnt_num[i],
					sj_c_cnt[i] = sj_c_cnt[i - 1] + c_cnt_kind[i] * i;	
		
		ll res = n;		
		forr(C,1,n)
		{
			ll cur = s_c_cnt_num[C - 1];
			cur += sj_c_cnt[n] - sj_c_cnt[C];
			cur -= C * (s_c_cnt_kind[n] - s_c_cnt_kind[C]);
			res = min(res,cur);
		}
		printf("%lld\n",res);
	}
	return 0;
}

G. Old Floppy Drive

思路

对\(a\)求前缀和.考虑分情况:如果一轮就可以拿到\(x\),那么直接在里面lower_bound就可以拿到了.否则一轮结束不了的,看总和是否是正的,如果不是那么无论走多少轮都是无用功.最后一种情况就是找一组\((i,k)\),满足有\(s[i] + k * sum >= x\).并且\(i+k*n-1\)是最小的.显然应该先让\(k\)取到最小值,所以先用最大的\(s[i]\)求出\(k\)的最小值记作\(kmin\),其次要找一个最小的\(i\)使得\(s[i] >= x - kmin * sum\).可以发现如果有\(s[i] > j\)且\(i < j\),那么\(j\)的存在是没有意义的,所以可以对\(s[i]\)求一个前缀max记作premax,由于premax是具有单调性的,所以可以二分求解.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n)	for(int i = n;i >= x;--i)

typedef pair<ll,int> pli;
#define x first
#define y second

const int N = 2e5+7;
int a[N],premax[N];
ll s[N];

bool cmp(int x,int y)
{
	return s[x] < y;
}

int main() 
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int n,m;scanf("%d%d",&n,&m);
		forn(i,1,n)	s[i] = 0,premax[i] = 0;
		forn(i,1,n)	scanf("%d",&a[i]),s[i] = s[i - 1] + a[i];
		
		ll sum = s[n];
		premax[1] = 1;
		forn(i,2,n)	premax[i] = (s[premax[i - 1]] < s[i] ? i : premax[i - 1]);
		forn(i,1,m)	
		{
			int x;scanf("%d",&x);
			int p = lower_bound(premax + 1,premax + n + 1,x,cmp) - premax;
			if(p == n + 1)
			{
				if(sum <= 0)	printf("-1 ");
				else
				{
					ll kmin = (x - s[premax[n]] + sum - 1) / sum;
					p = lower_bound(premax + 1,premax + n + 1,x - kmin * sum,cmp) - premax;
					printf("%lld ",p - 1 + kmin * n);
				}
			}
			else printf("%d ",p - 1);
		}
		puts("");
	}
	return 0;
}
上一篇:BZOJ5415 [NOI2018] 归程


下一篇:第四十七章:forn组件