Codeforces Round #698 (Div. 2) 题解 全部6题

目录
  • A. Nezzar and Colorful Balls
  • B. Nezzar and Lucky Number
  • C. Nezzar and Symmetric Array
  • D. Nezzar and Board
  • E. Nezzar and Binary String
  • F. Nezzar and Nice Beatmap

div2 传送门
div1 传送门

A. Nezzar and Colorful Balls

大意：给一个单调不减序列，要给每个数染色使得同一种颜色组成的序列单调上升，求染色数最小值

因为对一种颜色 \(color_i\) 来说，每种数字只能有一个数字染 \(color_i\) 颜色（比如很多个 "2" 中只能有 1 个 "2" 染成红色），所以有多少个相同的数字就对应需要多少种颜色，答案自然是出现频次最多的数字的个数

#include 
using namespace std;
const int N=200010; typedef long long ll;
signed main(){
	int T; scanf("%d",&T);
	while(T--){
		int n; scanf("%d",&n);
		int pre=-1,now=0,ans=0; // pre是前
		for(int i=0;i

B. Nezzar and Lucky Number

大意：判断一个数是否能被表示为若干（十进制表示下）含有数码 d 的数字之和

我的代码太生草了（

首先可以猜到，很大的数字可以转换成 \(\overline{dX}\) 和 \(d\) 的组合。比如 \(d=7\) 时，取一个 \(\ge 70\) 的数 \(n\)，由于 \(70,71,...,76\) 构成了模 7 的剩余系（说人话：\(n\) 一定与 \(70,71,...,76\) 其中一个数同余），我们就可以将 \(n\) 表示为 \(\overline{7M}+\tfrac{n-\overline{7M}}7\times 7\)（\(M=n\bmod 7\)，可以证明 \(\tfrac{n-\overline{7M}}7\) 一定是个非负整数）

这样，我们只要考虑 \(n 的情况了。为了节省时间，当然是怎么简单怎么来了，直接上暴力（我写的记忆化搜索，不清楚不记忆化行不行）

#include 
using namespace std;
const int N=200010; typedef long long ll;
int ans[10][100];
bool calc(int d,int n){
	if(n>=d*10)return 1;
	if(n

C. Nezzar and Symmetric Array

大意：a 是一个长度 \(2n\)、对称的、数字互不相同的数列，对称意味这每个数都能找到对应的相反数。\(d_i=\sum_{j=1}^{2n}|a_i-a_j|\)，已知数列 d 问是否存在数列 a

先对 \(d_i\) 排个序

如果原数列 \(a\) 是 4 个数 \(A,-A,B,-B\)，\(0，那么 \(A\) 对应的 \(d\) 值是 \(2A+2B\)，\(B\) 对应的 \(d\) 值是 \(4B\)。这样我们大致得知一个结论，一个数的 \(d\) 值就是有多少个数绝对值比它小 * 它的绝对值 + 剩下的数绝对值之和

根据上述结论，我们又可以得到三个推论，\(a_i=-a_j\Rightarrow d_i=d_j\)（或者说 \(d_i\) 是两个两个出现的），\(d_i\) 是偶数，任意 4 个 \(d_i\) 不相等（因为数列 a 互不相等）

如果上面都成立，我们就可以把长度为 \(2n\) 的 \(d_i\) 简化成长度为 \(n\) 的数列 \(e_i=\dfrac 1 2 d_{2i}\)，那么 \(a_i\) 也可以去掉那些负数的部分留下正数的部分

（\(e_i\) 为有多少个数比 \(a_i\) 小 * \(a_i\) + 剩下的数之和，其中 \(a_i\) 已经去掉负数了）

然后我们发现，\(e_n\) 其实就是 \(n\) 倍 \(a_n\)，而 \(e_{n-1}-a_n\) 其实就是 \(n-1\) 倍 \(a_{n-1}\)，\(e_{n-2}-a_n-a_{n-1}\) 其实就是 \(n-2\) 倍 \(a_{n-2}\)，依次类推，我们可以计算出所有 \(a_i\)

#include 
using namespace std;
const int N=200010; typedef long long ll;
ll a[N],d[N],e[N];
#define GG {puts("NO"); return;}
void solve(){
	int n; scanf("%d",&n);
	for(int i=1;i<=n*2;i++)
		scanf("%lld",d+i);
	sort(d+1,d+n*2+1);
	for(int i=1;i<=n*2;i++){
		if(d[i]%2!=0)GG;
		if(i%2==1){
			if(d[i]!=d[i+1])GG;
			if(i!=1 && d[i]==d[i-2])GG;
		}
	}
	for(int i=1;i<=n;i++)e[i]=d[i*2]/2;
	ll sum=0;
	for(int i=n;i>=1;i--){
		if((e[i]-sum)%i!=0)GG;
		a[i]=(e[i]-sum)/i;
		sum+=a[i];
	}
	if(a[1]<=0)GG;
	puts("YES");
}
signed main(){
	int T; scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}

D. Nezzar and Board

大意：初始黑板上有 \(n\) 个数，你可以从中取两个数 \(x,y\) 并把 \(2x-y\) 写在黑板上。问给定数字 \(k\) 是否能被写在黑板上

从几何（？）的角度思考，（或者瞎*b试一试就可以看出）\(2x-y\) 其实就是 \(y\) 关于 \(x\) 对称的点

假设一开始只有两个数 \(x,y\)，不断对称对称，就会出现相邻间隔为 \(|x-y|\) 的很多数。或者说，\((n-x) \equiv 0 \pmod {|x-y|}\) 的任意整数 \(n\) 都能被表示出来了

如果一开始有三个数 \(x,y,z\)，会发生什么呢？根据欧几里得算法，（哦细节就不说了，总之就是——）会出现间隔为 \(\gcd(|x-y|,|x-z|)\) 的很多数。这样，三个数 \(x,y,z\) 可以简化成两个数 \(x,x+\gcd(|x-y|,|x-z|)\)，不断这么操作，再多的数也都只剩两个数了

以上仅考虑数字之间互不相同的情况，相同情况要特殊处理

//#pragma GCC optimize(3)
#include 
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define fi first
#define se second
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
//int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;} typedef double lf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)!=1)exit(0); return x;} typedef pair pii; template void operator<<(vector &a,T b){a.push_back(b);}
const ll mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;}
#define int ll
int a[N];
void Solve(){
	int n=read(),k=read();
	repeat(i,0,n){
		a[i]=read();
	}
	int d=-1;
	sort(a,a+n);
	repeat(i,0,n-1)
	if(a[i]!=a[i+1]){
		if(d!=-1)d=__gcd(d,a[i+1]-a[i]);
		else d=a[i+1]-a[i];
	}
	if(d==-1){
		puts(k==a[0]?"YES":"NO");
	}
	else{
		puts((k-a[0])%d==0?"YES":"NO");
	}
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}

E. Nezzar and Binary String

大意：给01字符串s,f，初始字符串为s，每次断言区间 \([l_i,r_i]\) 都是0或都是1，然后修改这个区间的x个字符，x严格小于区间长度的一半，最后断言字符串=f。问是否可以让所有断言都成立

考虑倒着操作，即从f出发，先修改区间再断言。这样的操作就是唯一的，即修改区间内出现次数少的所有字符

维护区间赋值和区间求和考虑用线段树

//#pragma GCC optimize(3)
#include 
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define fi first
#define se second
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
//int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;} typedef double lf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)!=1)exit(0); return x;} typedef pair pii; template void operator<<(vector &a,T b){a.push_back(b);}
const ll mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;}
// #define int ll
int in[N]; 
struct seg{
	#define U(x,y) (x+y)
	#define a0 0
	void toz(ll x){z=x,state=1;}
	void toa(){a=z*(r-l+1),z=0,state=0;}
	ll a,z; bool state;
	int l,r; seg *lc,*rc;
	void init(int,int);
	void up(){a=U(lc->a,rc->a);}
	void down(){
		if(!state)return;
		if(ltoz(z); rc->toz(z);}
		toa();
	}
	void update(int x,int y,ll k){
		if(x>r || y=r){toz(k); down(); return;}
		down();
		lc->update(x,y,k);
		rc->update(x,y,k);
		up();
	}
	ll query(int x,int y){
		if(x>r || y=r)return a;
		return U(lc->query(x,y),rc->query(x,y));
	}
}tr[N*2],*pl;
void seg::init(int _l,int _r){
	l=_l,r=_r; state=0; z=0;
	if(l==r){a=in[l]; return;}
	int m=(l+r)>>1;
	lc=++pl; lc->init(l,m);
	rc=++pl; rc->init(m+1,r);
	up();
}
void init(int l,int r){
	pl=tr; tr->init(l,r);
}
// 以上为线段树板子
char s1[N],s2[N];
pii op[N];
void Solve(){
	int n=read(),q=read();
	scanf("%s%s",s1,s2);
	repeat(i,0,n)
		in[i]=s2[i]=='1';
	repeat(i,0,q)op[i]={read()-1,read()-1};
	init(0,n-1);
	repeat_back(i,0,q){
		int l=op[i].fi,r=op[i].se,len=r-l+1;
		int cnt=tr->query(l,r);
		if(len%2==0 && cnt==len/2){
			puts("NO");
			return;
		}
		tr->update(l,r,cnt>len/2);
	}
	repeat(i,0,n)
	if(tr->query(i,i)!=(s1[i]=='1')){
		puts("NO");
		return;
	}
	puts("YES");
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}

F. Nezzar and Nice Beatmap

大意：平面 \(n\) 个点，求连接这 \(n\) 个点的路径（折线）使得形成的所有夹角小于 90 度

一看到范围 5000，立刻往 \(O(n^2)\) 方向考虑。很快啊，发现如果连了 \(AB\)，那么过 \(B\) 做垂线后，平面被垂线分成两个半平面，下一个要连的点必须要在包含 \(A\) 的半平面中

如果所有点都在这个Yes的半平面中就完美了。还真的可以这样，我们只要让B为距离A最远的点即可（连过的点都删了）

问题解决

//#pragma GCC optimize(3)
#include 
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define fi first
#define se second
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
//int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;} typedef double lf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)!=1)exit(0); return x;} typedef pair pii; template void operator<<(vector &a,T b){a.push_back(b);}
const ll mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;}
#define int ll
struct vec{
	int x,y; vec(){} vec(int x,int y):x(x),y(y){}
	vec operator-(const vec &b){return vec(x-b.x,y-b.y);}
	vec operator+(const vec &b){return vec(x+b.x,y+b.y);}
	void operator+=(const vec &b){x+=b.x,y+=b.y;}
	void operator-=(const vec &b){x-=b.x,y-=b.y;}
	vec operator*(lf k){return vec(k*x,k*y);}
	bool operator==(vec b)const{return x==b.x && y==b.y;}
	int sqr(){return x*x+y*y;}
	void output(){printf("%lld %lld\n",x,y);}
}a[N];
bool vis[N];
void Solve(){
	int n=read();
	repeat(i,0,n)a[i].x=read(),a[i].y=read();
	vis[0]=1; int p=0; printf("1 ");
	repeat(i,0,n-1){
		int dis2=-1,rec;
		repeat(j,0,n)if(!vis[j]){
			if(dis2<(a[p]-a[j]).sqr()){
				dis2=(a[p]-a[j]).sqr();
				rec=j;
			}
		}
		p=rec; vis[p]=1;
		printf("%lld ",p+1);
	}
	puts("");
}
signed main(){
	//freopen("data.txt","r",stdin);
	int T=1; // T=read();
	repeat(ca,1,T+1){
		Solve();
	}
	return 0;
}
比赛题解

相关

标签

一品网 冀ICP备14022925号-6