Vjudge contest 424196

Problem A

关于这道题目你发现你不需要考虑的是分割之后具体的面积是多少，我们可以用叉积计算之后暂时不除以 \(2\) ，最后判断一下奇偶性就可以了。

考虑这样的话我们就可以直接对于一个右（这里的左右实际上就是凸包上点的遍历顺序）端点，把其左端点的值存入一个桶里，发现桶内只需要存 \(x_i\) 的奇偶性， \(y_i\) 的奇偶性， \(pre_i\) 的奇偶性。

然后对于根据桶内数据求出来的面积的奇偶性判断是否可行，然后加几个特判就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int n,sum=0,res=0;
int pre[N],cnt[2][2][2];
struct Point{int x,y;}a[N];
signed main(){
	freopen("integral.in","r",stdin);
	freopen("integral.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) scanf("%lld%lld",&a[i].x,&a[i].y);
	a[0]=a[n];
	for(int i=0;i<=n;++i) a[i].x&=1,a[i].y&=1;
	for(int i=1;i<=n;++i) pre[i]=(pre[i-1]^(a[i].x&a[i-1].y)^(a[i].y&a[i-1].x));
	if(pre[n]) return printf("0\n"),0;
	for(int i=1;i<n;++i){
		for(int c=0;c<2;++c){
			for(int d=0;d<2;++d){
				for(int e=0;e<2;++e){
					int tmp1=((c&a[i].y)^(d&a[i].x)),tmp2=(pre[i]^e);
					if((tmp1^tmp2)==0){
						res+=cnt[c][d][e];
						// if(cnt[c][d][e]) printf("%d %d %d %d\n",i,c,d,e);
					}
				}
			}
		}
		cnt[a[i-1].x][a[i-1].y][pre[i-1]]++;
		// printf("%lld\n",res);
	}
	printf("%lld\n",res-1);
	return 0;
}

Problem B

是不是可以二分？他的答案序列是满足单调性的。

不对，有点问题。??????????????????????????????????????

首先可以确定的是，如果在已知我们当前操作步数的情况下，每一个数最多只会被操作一次。

神 \(\text{zkdxl}\) 给了我一点提示，就是要将倍数和 \(\text{lcm}\) 分开考虑。

感觉可以这样，每一个数开一个堆，然后每一次从堆顶取出两个（真实）数量最小的数，将其变成两者的 \(\text{lcm}\) ，但是这样貌似并不能处理倍数的情况。

那我们就开两个堆，一个存储所有的数，一个存储存在有的数是其倍数的数。然后两个一起搞，哪个小就从哪一个中取。

你发现你有两种策略，有倍数的数连向其倍数，没有倍数的数连向一个巨大的 \(\text{lcm}\) 。你发现两种策略必然只会选取一个，然后就分别处理两种策略然后扫一遍求一下答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,A=1e6+5;
int n,a[N],cnt[A],res[N],sum=0;
vector<int> bag1,bag2;
int main(){
	// freopen("equal.in","r",stdin);
	// freopen("equal.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=n;++i) cnt[a[i]]++;
	for(int i=1;i<A;++i){
		if(!cnt[i]) continue;
		for(int j=i+i;j<A;j+=i)
		if(cnt[j]){bag1.push_back(cnt[i]);break;}
		bag2.push_back(cnt[i]),sum++;
	}
	sort(bag1.begin(),bag1.end());
	sort(bag2.begin(),bag2.end());
	for(int i=0;i<=n;++i) res[i]=sum;
	for(int i=0,tmp=0;i<(int)bag1.size();++i)
	tmp+=bag1[i],res[tmp]=min(res[tmp],sum-i-1);
	for(int i=0,tmp=0;i<(int)bag2.size();++i)
	tmp+=bag2[i],res[tmp]=min(res[tmp],sum-i);
	for(int i=1;i<=n;++i) res[i]=min(res[i],res[i-1]);
	for(int i=0;i<=n;++i) printf("%d ",res[i]);
	return printf("\n"),0;
}

Problem C

易证个屁得，当 \(w\) 表示矩形宽度， \(x\) 表示矩形左下角的横坐标时函数 \(f(w,x)\) 是单峰的，然后三分套三分即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,L,R,Ltop,Rtop,Lbot,Rbot;
struct Point{double x,y;}a[N*3];
struct Rectangle{double x1,y1,x2,y2,S;};
int nxt(int x){return (++x>n?x-n:x);}
int pre(int x){return (--x<1?x+n:x);}
double cal(int u,int v,double x){
	return a[u].y+(a[v].y-a[u].y)*(x-a[u].x)/(a[v].x-a[u].x);
}
pair<double,double> find(double x){
	int res1,res2,res3,res4;
	int l=Lbot,r=Rbot;
	// printf("---%lf\n",x);
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].x<=x) r=mid-1,res1=mid;
		else l=mid+1;
	}
	// printf("%d\n",res1);
	l=Lbot,r=Rbot;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].x>=x) l=mid+1,res2=mid;
		else r=mid-1;
	}
	// printf("%d\n",res2);
	l=Ltop,r=Rtop;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].x<=x) l=mid+1,res3=mid;
		else r=mid-1;
	}
	// printf("%d\n",res3);
	l=Ltop,r=Rtop;
	while(l<=r){
		int mid=(l+r)>>1;
		if(a[mid].x>=x) r=mid-1,res4=mid;
		else l=mid+1;
	}
	// printf("%d\n",res4);
	double tmp1=min(cal(res1,res1-1,x),cal(res2,res2+1,x));
	double tmp2=max(cal(res3,res3+1,x),cal(res4,res4-1,x));
	return make_pair(tmp1,tmp2);
}
Rectangle f(double x,double w){
	pair<double,double> tmp1=find(x),tmp2=find(x+w);
	Rectangle t;t.x1=x,t.x2=x+w;
	t.y1=max(tmp1.first,tmp2.first);
	t.y2=min(tmp1.second,tmp2.second);
	t.S=w*(t.y2-t.y1);
	return t;
}
Rectangle g(double w){
	double Lx=a[L].x,Rx=a[R].x-w;
	while(Rx-Lx>1e-6){
		// printf("w:%lf x:%lf %lf\n",w,Lx,Rx);
		double Mid1x=2*Lx/3+Rx/3,Mid2x=Lx/3+2*Rx/3;
		Rectangle tmp1=f(Mid1x,w),tmp2=f(Mid2x,w);
		// printf("%lf %lf\n",Mid1x,tmp1.S);
		// printf("%lf %lf\n",Mid2x,tmp2.S);
		if(tmp1.S<tmp2.S) Lx=Mid1x;
		else Rx=Mid2x;
	}
	return f(Lx,w);
}
void solve(){
	L=R=1;
	for(int i=1;i<=n;++i){
		scanf("%lf%lf",&a[i].x,&a[i].y);
		a[i+n]=a[i];
	}
	for(int i=1;i<=n;++i){
		if(a[i].x<a[L].x) L=i;
		if(a[i].x>a[R].x) R=i;
	}
	Lbot=R,Rbot=L;
	while(a[Lbot].x==a[pre(Lbot)].x) Lbot=pre(Lbot);
	while(a[Rbot].x==a[nxt(Rbot)].x) Rbot=nxt(Rbot);
	if(Lbot>Rbot) Rbot+=n;
	Ltop=L,Rtop=R;
	while(a[Ltop].x==a[pre(Ltop)].x) Ltop=pre(Ltop);
	while(a[Rtop].x==a[nxt(Rtop)].x) Rtop=nxt(Rtop);
	if(Ltop>Rtop) Rtop+=n;
	// printf("%d %d %d %d\n",Lbot,Rbot,Ltop,Rtop);
	double Lw=0,Rw=a[R].x-a[L].x;
	while(Rw-Lw>1e-6){
		// printf("w:%lf %lf\n",Lw,Rw);
		double Mid1w=2*Lw/3+Rw/3,Mid2w=Lw/3+2*Rw/3;
		Rectangle tmp1=g(Mid1w),tmp2=g(Mid2w);
		// printf("%lf %lf\n",Mid1w,tmp1.S);
		// printf("%lf %lf\n",Mid2w,tmp2.S);
		if(tmp1.S<tmp2.S) Lw=Mid1w;
		else Rw=Mid2w;
	}
	Rectangle res=g(Lw);
	printf("%lf %lf %lf %lf\n",res.x1,res.y1,res.x2,res.y2);
}
int main(){
	freopen("easy.in","r",stdin);
	freopen("easy.out","w",stdout);
	while(~scanf("%d",&n)) solve();
}

Problem D

很有意思的一道构造题。

你发现对于一个位置 \(i\) ，其后面的位置 \([i+1,n-1]\) ，如果已经正好填满了 \([0,n-i-2]\) ，那么你可以通过持续操作这个位置 \(i\) 来使得 \(n-i-1\) 到达这个位置。

因此我们可以通过上述操作来获得整个序列的逆序。

然后对于如何将逆序转换成顺序，这个随便手玩一下就知道了？然后就行了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,p[N];
vector<int> opt;
int main(){
	cin>>n;
	for(int i=0;i<n;++i) scanf("%d",&p[i]);
	for(int i=n-1;i>=0;--i){
		while(p[i]!=n-i-1){
			opt.push_back(i);
			swap(p[i],p[(i+p[i])%n]);
		}
	}
	for(int i=n-2;i>=0;--i){
		for(int j=p[i];j>=1;--j){
			opt.push_back(i);
			swap(p[i],p[(i+p[i])%n]);
		}
	}
	printf("%d\n",(int)opt.size());
	for(int i=0;i<(int)opt.size();++i)
	printf("%d\n",opt[i]);
	// for(int i=0;i<n;++i) printf("%d ",p[i]);
	// printf("\n");
	return 0;
}

Problem E

过于毒瘤，之后有时间再补上。

Vjudge contest 424196

原文：https://www.cnblogs.com/Point-King/p/14456975.html