noip模拟37

\(\color{white}{\mathbb{燕子来时青尚在，木荫遥看杏花菲，名之以：杏红}}\)

考场发现 \(t2\) 基本上是原题，\(t3\) 的套路见过，\(t4\) 像是并查集之类的算法，\(t1\) 是个扩欧，总之感觉今天的题非常可做

先写 \(t3\) 打完二进制分组，过了大样例，然后也没测时间也没对拍开始写 \(t2\)，很快也过了大样例，然后推 \(t1\)，像是个三分，打完稍调一下也过了大样例。

发现时间还有两个半小时，觉得良心出题人前三题都给了大样例，估计不用对拍了吧，于是开始想 \(t4\)

想了一个小时复杂度大概对了，半个小时码完，再写个暴力挂上对拍

发现还有将近一个小时，开始喝水上厕所(一度以为有生之年可以AK了)

最后考完发现两题都挂了，发现 \(t1\) 有个三分的细节写错了，\(t3\) 是位运算弄错了，总共挂了 135 的分……

还是得认真检查……

A. 数列

很明显是扩欧，然后要求一组解使得 \(abs(x)+abs(y)\) 最小，这个是单峰函数，写了个三分，但是左右 \(mid\) 写错了

更简单的做法是令 \(a < b\)，那么求通解的时候 \(x\) 每次跨度大，\(y\) 跨度小，所以当 \(abs(x)\) 小的时候一定答案最小

代码实现

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5+5;

int n,a,b,g,x,y,p[maxn],ans,xx,yy,ax,ay;

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

int gcd(int a,int b){

	return b==0?a:gcd(b,a%b);

}

void exgcd(int a,int b){

	if(!b){

		x=1;

		y=0;

		return ;

	}

	exgcd(b,a%b);

	int k=y;

	y=x-a/b*y;

	x=k;

	return ;

}

int calc(int k){

	return abs(xx+k*ax)+abs(yy-k*ay);

}

int solve(int val){

	if(val%g){

		puts("-1");

		exit(0);

	}

	xx=x*val/g;

	yy=y*val/g;

	int l=-1e9,r=1e9,lastl=0,lastr=0,cnt=0;

	while(l<r){

		int lmid=(r-l+1)/3+l;

		int rmid=l+r-lmid;

//		cout<<l<<" "<<r<<" "<<lmid<<" "<<rmid<<endl;

		if(calc(lmid)<calc(rmid))r=rmid;

		else l=lmid;

		if(l==lastl&&r==lastr)cnt++;

		else lastl=l,lastr=r,cnt=0;

		if(cnt>=2)break;

	}

	int mn=0x3f3f3f3f3f3f3f3f;

	for(int i=l-1;i<=r+1;i++){

		mn=min(mn,calc(i));

	}

	return mn;

}

signed main(){

//	freopen("array.in","r",stdin);

//	cout<<gcd(12,18);

	n=read();

	a=read();

	b=read();

	g=gcd(a,b);

//	cout<<g<<endl;

	exgcd(a,b);

	ax=b/g;

	ay=a/g;

//	cout<<x<<" "<<y<<endl;

	for(int i=1;i<=n;i++){

		p[i]=read();

	}

	for(int i=1;i<=n;i++){

		ans+=solve(abs(p[i]));

	}

	cout<<ans;

	return 0;

}

B. 数对

类似与队长快跑，只不过这道题无序，按 \(min(a_i,b_i)\) 排序即可

C. 最小距离

二进制拆分写错+卡常挂成零分

一定注意 \((1<< pos ) \& x\) 的值不是 \(1\)！！！！

正解是记录每个点更新的源点或者次短路

代码实现

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=4e5+5;

const int maxm=1e6+5;

int n,m,x,y,w,hd[maxn],cnt,dis[maxn],a[maxn],k,ans[maxn],col[maxn];

bool vis[maxn];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

struct Edge{

	int nxt,from,to,val;

}edge[maxm];

void add(int u,int v,int w){

	edge[++cnt].nxt=hd[u];

	edge[cnt].to=v;

	edge[cnt].val=w;

	edge[cnt].from=u;

	hd[u]=cnt;

	return ;

}

struct Node{

	int dis,id;

	Node(){}

	Node(int x,int y):dis(x),id(y){}

	bool operator < (const Node & x)const{

		return dis>x.dis;

	}

};

priority_queue<Node>q;

void dij(){

	memset(dis,0x3f,sizeof dis);

	memset(vis,0,sizeof vis);

	for(int i=1;i<=k;i++){

		col[a[i]]=i;

		q.push(Node(0,a[i]));

		dis[a[i]]=0;

	}

	while(!q.empty()){

		int u=q.top().id;

		q.pop();

		if(vis[u])continue;

		vis[u]=true;

		for(int i=hd[u];i;i=edge[i].nxt){

			int v=edge[i].to;

			if(dis[v]>dis[u]+edge[i].val){

				dis[v]=dis[u]+edge[i].val;

				col[v]=col[u];

				q.push(Node(dis[v],v));

			}

		}

	}

	return ;

}

signed main(){

//	freopen("distance.in","r",stdin);

//	freopen("my.out","w",stdout);

	n=read();

	m=read();

	k=read();

	memset(ans,0x3f,sizeof ans);

	for(int i=1;i<=k;i++){

		a[i]=read();

	}

	for(int i=1;i<=m;i++){

		x=read();

		y=read();

		w=read();

		add(x,y,w);

		add(y,x,w);

	}

	dij();

	for(int i=1;i<=cnt;i++){

		if(col[edge[i].from]!=col[edge[i].to]){

			ans[col[edge[i].from]]=min(ans[col[edge[i].from]],edge[i].val+dis[edge[i].from]+dis[edge[i].to]);

			ans[col[edge[i].to]]=min(ans[col[edge[i].to]],edge[i].val+dis[edge[i].from]+dis[edge[i].to]);

		}

	}

	for(int i=1;i<=k;i++){

		printf("%lld ",ans[i]);

	}

	return 0;

}

D. 真相

这种题一看类似于图论

按照真假拆点建图后发现分成多个块，每个块的结尾都是 \(1\) 类节点

那么一种思路是枚举每个结尾点，统计所有与其相同的节点的真话总数，判断是否满足即可，这个可以预处理优化成 \(O(n)\)

代码实现

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+5;

int t,n,a[maxn],val[maxn],pos[maxn],val1[maxn],tot,w[maxn],sumtot,sum1[maxn],sum2[maxn];

bool vis[maxn];

char c[5];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

void work(){

	int op=0;

	for(int i=1;i<=n;i++){

		op^=a[i];

	}

	if(op==0)puts("consistent");

	else puts("inconsistent");

	return ;

}

void pre(){

	for(int j=1;j<=tot;j++){

		int p=pos[j];

		int op=0;

		while(!vis[p-1]){

			p--;

			if(!p)p=n;

			if(vis[p])break;

			op^=a[p];

			val[j]+=(!op);

		}

		val[j]++;

		p=pos[j],op=1;

		while(!vis[p-1]){

			p--;

			if(!p)p=n;

			if(vis[p])break;

			op^=a[p];

			val1[j]+=(!op);

//			cout<<p<<" "<<a[p]<<" "<<op<<endl;

		}

//		cout<<val[j]<<" "<<val1[j]<<endl;

	}

	return ;

}

bool solve(){

	for(int i=1;i<=n;i++){

		sum1[w[i]]+=val[i];

		sum2[w[i]]+=val1[i];

		sumtot+=val1[i];

	}

	for(int i=1;i<=tot;i++){

		int sum=sumtot-sum2[w[i]]+sum1[w[i]];

		if(sum==w[i])return true;

	}

	int sum=0;

	for(int i=1;i<=tot;i++){

		sum+=val1[i];

	}

	for(int i=1;i<=tot;i++){

		if(sum==w[i])return false;

	}

	return true;

}

void init(){

	for(int i=1;i<=n;i++){

		a[i]=vis[i]=val[i]=val1[i]=sum1[i]=w[i]=sum2[i]=0;

	}

	tot=sumtot=0;

	return ;

}

int main(){

//	freopen("shuju.in","r",stdin);

//	freopen("my1.out","w",stdout);

	t=read();

	while(t--){

		init();

		n=read();

		for(int i=1;i<=n;i++){

			scanf("%s",c+1);

			if(c[1]=='$')pos[++tot]=i,vis[i]=true,w[tot]=read();

			else if(c[1]=='-')a[i]=1;

			else a[i]=0;

		}

		if(!tot){

			work();

			continue;

		}

		pre();

		if(solve())puts("consistent");

		else puts("inconsistent");

	}

	return 0;

}

\(\color{white}{\mathbb{花褪残红青杏小，燕子来时，绿水人家绕。}}\)

巴特西

noip模拟37

A. 数列

B. 数对

C. 最小距离

D. 真相

最新文章

热门文章