时间戳

首页 > 技术文章 > [CF1478] Codeforces Round #698 (Div. 2)

[CF1478] Codeforces Round #698 (Div. 2)

cjl-world 2021-01-29 09:46 原文

Codeforces Round #698 (Div. 2)

Problems

# Name
A Nezzar and Colorful Balls Submit Add to favourites img x14328
B Nezzar and Lucky Number Submit Add to favourites img x8969
C Nezzar and Symmetric Array Submit Add to favourites img x3415
D Nezzar and Board Submit Add to favourites img x796
E Nezzar and Binary String Submit Add to favourites img x150
F Nezzar and Nice Beatmap Submit Add to favourites img x77

Solutions

A Nezzar and Colorful Balls

题意：给出一个不下降序列，要求将其分成尽可能少的严格上升子序列。

引理：设不下降序列中相同值最多的值数 \(=col\) , 则 \(ans=col.\)

证明：不妨把不下降序列画成这样一张图。

假设 \(a[i]\) 最多。

  1. \(<col\) 的解都不可行：因为严格上升子序列不能同时存在 多个 \(a[i]\), 因此每个严格上升子序列至多有一个 \(a[i]\), 而 \(a[i]\) 共有 \(col\) 个，所以至少分 \(col\) 个。

  2. 可以构造出一组解使 \(ans=col\) . 如图

每个严格上升子序列选择颜色相同的方块即可。

Code:

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=256;

int n,T;
int a[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(i=1;i<=n;i++) 
			scanf("%d",&a[i]);
		int cnt=1,ans=1;
		for(i=2;i<=n;i++) {
			if(a[i]==a[i-1]) ans=max(ans,++cnt);
			else cnt=1;
		}
		ans=max(ans,cnt);
		
		printf("%d\n",ans);
	}
	return 0;
}

B Nezzar and Lucky Number

题意：Nezzar's favorite digit among 1,…,9 is d. He calls a positive integer lucky if d occurs at least once in its decimal representation.

性质 1：数较大时必存在。

性质 2：若 \(x\) 可以，\(y\) 可以，则 \(x+y\) 可以。

​ 那么对于 \(i\)

  • 要么 \(i\) 本身可以。
  • 要么枚举 \(j\) ,看是否存在 \(j,i-j\) 都可。

因此小范围打表，大范围直接判断即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=10000;

bool haved(int num,int d)
{
	while(num) {
		int x=num%10;
		num/=10;
		if(x==d) return true;
	}
	return false;
}

int T,n,d;
bool st[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i,j,x;
	
	scanf("%d",&T);
	while(T--) {
		memset(st,0,sizeof st);
		scanf("%d%d",&n,&d);
		for(i=1;i<N;i++) {
			if(haved(i,d)) st[i]=true;
			else {
				for(j=1;j<i;j++) 
					if(st[j] && st[i-j]) {
						st[i]=true;
						break;
					}
				if(j==i) st[i]=false;
			}
		}
		
		while(n--) {
			scanf("%d",&x);
			if(x>=N || (x<N && st[x])) puts("YES");
			else puts("NO");
		}
	}

	return 0;
}

C Nezzar and Symmetric Array

画数轴即可。

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N=3e5+5;

int T,n;
LL d[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(i=1;i<=2*n;i++) 
			scanf("%lld",&d[i]);
		sort(d+1,d+2*n+1);
		
		bool ans=true;
		for(i=1;i<=2*n && ans;i+=2) 
			if(d[i]!=d[i+1] || d[i]%2==1) ans=false;
		for(i=3;i<=2*n && ans;i+=2) 
			if(d[i]==d[i-2]) ans=false;
		
		LL sum=0,cur=0;
		for(i=3;i<=2*n && ans;i+=2) {
			if((d[i]-d[i-2])%(2*(i/2))) ans=false;
			cur+=(d[i]-d[i-2])/(2*(i/2));
			sum=sum+cur;
			if(sum>=d[1]/2) {
				ans=false;
				break;
			}
		}
		if(ans && (d[1]/2-sum)%n) ans=false;
		
		if(ans) puts("YES");
		else puts("NO");
	}
	return 0;
}

D Nezzar and Board

这个 D ,我做过类似的。

对 \(x\) (\(x\) 是 \(a[]\) 中的某个数) 单次变换： \(2\times a[i]-x\) 。

两次变换： \(2 \times a[j]-(2 \times a[i]-x)=x+2\times (a[j]-a[i])\)

令 \(b_{i,j}=2(a[j]-a[i])\)

若走偶数步 \(x+\sum c_{i,j} \times b_{i,j}=m, c_{i,j} \in Z\)

由贝祖定理：\(\sum c_{i,j} \times b_{i,j}\) 的取值集合为 \(\{kd|d=\gcd(b_{i,j}),k\in Z\}\)

\(d=\gcd(b_{i,j})=\gcd(b_{1,1},b_{1,2},...,b_{n,n})\)

\(=2 \times \gcd(a_{2}-a_{1},a_{3}-a_{1},...,a_{n-1}-a_{n})\)

\(=2 \times \gcd(a_{2}-a_{1},a_{3}-a_{2},...,a_{n}-a_{n-1})\)

判断是否有 \(a[i]\) 使 \(a[i]=m \: (\bmod d)\)

若走奇数步，考虑在偶数步上再添一步。

判断是否有 \(i,j\) 使 \(2\times a[j]-a[i]=m \: (\bmod d)\)

因为 \(d|2\times (a[j]-a[1])\) , 所以 \(2a_1=2a_j (\bmod d)\)

判断是否有 \(a[i]\) 使 \(2\times a[1]-a[i]=m \: (\bmod d)\)

时间 \(O(n\log n)\)

Code:

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

LL gcd(LL a,LL b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}

const int N=2e5+5;

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

inline LL mabs(LL x)
{
	if(x<0) return -x;
	else return x;
}

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%lld",&n,&m);
		for(i=1;i<=n;i++) 
			scanf("%lld",&a[i]);
		LL g=0;
		for(i=2;i<=n;i++) 
			g=gcd(g,mabs(a[i]-a[i-1]));
		g*=2;
		m=(m%g+g)%g;
		for(i=1;i<=n;i++) 
			if((a[i]%g+g)%g==m || ((2*a[1]-a[i])%g+g)%g==m) 
				break;
		if(i<=n) puts("YES");
		else puts("NO");
	}
	
	return 0;
}

E - Nezzar and Binary String

倒推的话每一步都是确定的。

具体看抽风巨巨的题解啦

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=2e5+5;

struct Node
{
	int sum,tag;
}t[4*N];

#define lc (now<<1)
#define rc (now<<1|1)

void pushup(int now)
{
	t[now].sum=t[lc].sum+t[rc].sum;
}

void Addtag(int now,int key,int l,int r)
{
	t[now].tag=key;
	t[now].sum=key*(r-l+1);
}

void pushdown(int now,int l,int r)
{
	if(t[now].tag==-1) return;
	int mid=(l+r)>>1;
	Addtag(lc,t[now].tag,l,mid);
	Addtag(rc,t[now].tag,mid+1,r);
	t[now].tag=-1;
}

void Modify(int now,int x,int y,int key,int l,int r)
{
	if(x<=l && r<=y) 
		return Addtag(now,key,l,r);
	pushdown(now,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) Modify(lc,x,y,key,l,mid);
	if(y>=mid+1) Modify(rc,x,y,key,mid+1,r);
	pushup(now);
}

int query(int now,int x,int y,int l,int r)
{
	if(x<=l && r<=y) 
		return t[now].sum;
	pushdown(now,l,r);
	int mid=(l+r)>>1,res=0;
	if(x<=mid) res+=query(lc,x,y,l,mid);
	if(y>=mid+1) res+=query(rc,x,y,mid+1,r);
	return res;
}

void Build(int now,int a[],int l,int r)
{
	t[now].tag=-1;
	if(l==r) {
		t[now].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	Build(lc,a,l,mid);
	Build(rc,a,mid+1,r);
	pushup(now);
}

int T,n,m;
PII q[N];
int s[N],f[N];
char str[N];

int main()
{
//	freopen("1.in","r",stdin);
	int i;
	int x,y,z;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n,&m);
		scanf("%s",str+1);
		for(i=1;i<=n;i++) s[i]=str[i]-'0';
		scanf("%s",str+1);
		for(i=1;i<=n;i++) f[i]=str[i]-'0';
		
		for(i=1;i<=m;i++) 
			scanf("%d%d",&q[i].first,&q[i].second);
		Build(1,f,1,n);
		
		for(i=m;i>=1;i--) {
			x=q[i].first; y=q[i].second;
			z=query(1,x,y,1,n);
			if(2*z==y-x+1) break; // NO;
			else if(y-x+1-z>z) Modify(1,x,y,0,1,n); 
			else Modify(1,x,y,1,1,n);
		}
		if(i) {
			puts("NO");
			continue;
		}
		for(i=1;i<=n;i++) 
			if(query(1,i,i,1,n)!=s[i]) break;
		if(i<=n) puts("NO");
		else puts("YES");
	}
	return 0;
}

F - Nezzar and Nice Beatmap

正解思路：每个点选择最远的点连，根据 大角对大边

\(C->A->B\)

\(CB \leq CA\) -> \(\angle A \leq \angle B\) -> \(\angle A<90^{*}\)

然而我不知道为什么就那么想用模拟褪火 qwq.

大概就是普通的模拟退火加上一些奇怪的东西。

  • \(calc()\) 在计算估价的同时求一个 \(suggest\) , 表示贡献最大（最烂）的点，下一次在 \(suggest\) 周围选择。
  • 先把点坐标按照极值大的排序，然后构造出一组较优的解 \(1,n,2,n-1,3,n-2,...\)
  • 降温系数一定要为 0.999。

Code:

#pragma GCC optimize(2)
#include<ctime>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> PLL;
typedef PLL Point;
typedef PLL Vector;

#define x first
#define y second

Vector operator-(Vector a,Vector b) { return Vector(a.x-b.x,a.y-b.y); }
LL dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; }

const int N=1e4+5;
const double INF=1e18;

int n;
Point a[N],b[N],c[N];
bool st[N];
int suggest;
void print()
{
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++) {
			if(a[i]==b[j] && !st[j]) {
				st[j]=true;
				printf("%d ",j);
				break;
			}
		}
	exit(0);	
}

double calc()
{
//	for(int i=1;i<=n;i++)
//		printf("%lld %lld\n",a[i].x,a[i].y);
//	printf("\n");
	double res=0,t,ms=-INF;
	bool flag=true;
	for(int i=2;i<=n-1;i++) {
		t=dot(a[i-1]-a[i],a[i+1]-a[i]);
		if(t<=0) {
			flag=false;
			res+=-t+1;
			if(-t+1>ms) suggest=i,ms=-t+1;
		}
	}
	if(flag) print();
//	printf("%lld\n",res);
	return res;
}

double rnd(double l,double r)
{
	return rand()*(r-l)/RAND_MAX+l;
}

LL f(int x)
{
	if(x>=n || x<=1) return 0;
	else {
		LL t=dot(a[x-1]-a[x],a[x+1]-a[x]);
		if(t>0) return 0;
		else return -t+1;
	}
}

LL add(int x,int y)
{
	static vector<int> v; v.clear();
	v.push_back(x-1); v.push_back(x); v.push_back(x+1);
	v.push_back(y-1); v.push_back(y); v.push_back(y+1);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	LL res=0;
	for(int i=0;i<(int)v.size();i++) 
		res+=f(v[i]);
	return res;
}

void SA()
{
	double cur=calc(),nw,dt;
	int x,y;
//	int cnt=0;
	for(double t=1e5;t>1e-3;t*=0.999) {
//		x=rand()%n+1,y=rand()%n+1;
//		if((++cnt)%1000==0) cur=calc();
		if(suggest==0) suggest=rand()%n+1;
		x=((suggest+(int)rnd(-t,t)+(int)rnd(-10,10))%n+n)%n+1;
		y=rand()%n+1;
	//	y=(rand()%2000+x)%n+1;
		
		if(x==y) continue;
	
		nw=cur-add(x,y);
		swap(a[x],a[y]);
		nw+=add(x,y);
		dt=nw-cur;
		if(exp(-dt/t)>rnd(0,1)) {
			cur=calc();
//			cerr<<cur<<endl;
		}
		else swap(a[x],a[y]);
	}
	random_shuffle(a+1,a+n+1);
}

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	int i;
	srand((unsigned) time(0));
	scanf("%d",&n);
	for(i=1;i<=n;i++) 
		scanf("%lld%lld",&a[i].x,&a[i].y);
	
	
	LL mn1=INF,mx1=-INF,mn2=INF,mx2=-INF;
	for(i=1;i<=n;i++) {
		mn1=min(mn1,a[i].x);
		mx1=max(mx1,a[i].x);
		mn2=min(mn2,a[i].y);
		mx2=max(mx2,a[i].y);
	}
	if(mx2-mn2>=mx1-mn1) {
		for(i=1;i<=n;i++) 
			swap(a[i].x,a[i].y);
	}
	memcpy(b,a,sizeof b); 
	sort(a+1,a+n+1);
	int hh=1,tt=n;
	for(i=1;i<=n;i++) {
		if(i&1) c[i]=a[hh++];
		else c[i]=a[tt--];
	}
//	for(i=1;i<=n;i++) 
//		printf("%lld %lld\n",a[i].x,a[i].y);
	memcpy(a,c,sizeof a);

//	for(int i=1;i<=10;i++) random_shuffle(a+1,a+n+1);
	while(clock()<1.8*CLOCKS_PER_SEC) SA();
//	SA();
	puts("-1");
	return 0;
}
// time 1

推荐阅读