noip模拟37

本文主要是介绍noip模拟37，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

期望得分：100+10+15+0=125
实际得分：100+10+10+0=120

T1

签到题，扩欧，然后三分，或者直接\(O(1)\)出解

T2

队长快跑微弱加强版，区别在于这道题需要排序

发现若\(a_i< b_j\)且\(a_j> b_i\)，则\(i\)一定在\(j\)之前，反之则\(i\)在\(j\)之后

剩下的两种情况怎么排都相同

想到这里就是队长快跑了，，，线段树优化\(dp\)

然而考场上只打了\(O(2^nn^2n!)\)，，，

T3

若没有终点是特殊点这个限制就是多源最短路，加上限制后考虑怎么改多源最短路

考虑跑\(dij\)时记录每个点是由哪个特殊点拓展的

发现对于一条边两端的点\(i\)和点\(j\)，假设\(i\)和\(j\)是由不同的特殊点\(p_i，p_j\)拓展的，若\(p_i\)的最短距离经过了边\((i,j)\)，那么\(p_i\)的距离最短特殊点一定是\(p_j\)

跑完\(dij\)后枚举每条边计算答案就行了

T4

如果没有第一种话，那么先随便确定一个人的真假，那么整个环的真假就确定了，直接判断是否矛盾

考虑加入第一种话，发现第一种话将环分成若干个不同的序列，同样的，确定序列中一个人的真假，整个序列就确定了

预处理出每段以说第一种话的人结尾的序列，在这个人分别说真话和假话时序列中说真话人的数量

然后枚举所有第一种话，分别判断其为真时是否不矛盾

代码

T1

#include<bits/stdc++.h>
using namespace std;
namespace STD
{
	#define rr register 
	typedef long long ll;
	const ll inf=LONG_LONG_MAX;
	const int N=1e5+4;
	int n,a,b;
	ll ans;
	int x[N];
	int read()
	{
		rr int x_read=0,y_read=1;
		rr char c_read=getchar();
		while(c_read<'0'||c_read>'9')
		{
			if(c_read=='-') y_read=-1;
			c_read=getchar();
		}
		while(c_read<='9'&&c_read>='0')
		{
			x_read=(x_read<<1)+(x_read<<3)+(c_read^48);
			c_read=getchar();
		}
		return x_read*y_read;
	}
	int exgcd(int a_e,int b_e,ll &x_e,ll &y_e)
	{
		if(b_e==0)
		{
			x_e=1;
			y_e=0;
			return a_e;
		}
		int gcd=exgcd(b_e,a_e%b_e,x_e,y_e);
		int temp=x_e;
		x_e=y_e;
		y_e=temp-a_e/b_e*y_e;
		return gcd;
	}
	void deal(int val)
	{
		ll p,q;
		int gcd=exgcd(a,b,p,q);
		if(val%gcd)
		{
			printf("-1\n");
			exit(0);
		}
		p=val/gcd*p;
		q=val/gcd*q;
		int l=0,r=1e9;
		ll x1,x2,x3;
		ll temp=inf;
		while(l<r)
		{
			int mid=(l+r)>>1;
			x1=abs(p-(mid-1)*1ll*(b/gcd))+abs(q+(mid-1)*1ll*(a/gcd));
			x2=abs(p-mid*1ll*(b/gcd))+abs(q+mid*1ll*(a/gcd));
			x3=abs(p-(mid+1)*1ll*(b/gcd))+abs(q+(mid+1)*1ll*(a/gcd));
			if(x1>=x2&&x2<=x3)
			{
				ans+=x2;
				return;
			}
			if(x1>x3)
				l=mid+1;
			else r=mid;
		}
		l=0,r=1e9;
		while(l<r)
		{
			int mid=(l+r)>>1;
			x1=abs(p+(mid-1)*1ll*(b/gcd))+abs(q-(mid-1)*1ll*(a/gcd));
			x2=abs(p+mid*1ll*(b/gcd))+abs(q-mid*1ll*(a/gcd));
			x3=abs(p+(mid+1)*1ll*(b/gcd))+abs(q-(mid+1)*1ll*(a/gcd));
			if(x1>=x2&&x3>=x2)
			{
				ans+=x2;
				return;
			}
			if(x1>x3)
				l=mid+1;
			else r=mid;
		}
	}	
};
using namespace STD;
int main()
{
	n=read(),a=read(),b=read();
	for(rr int i=1;i<=n;i++) x[i]=read();
	for(rr int i=1;i<=n;i++)
		deal(abs(x[i]));
	printf("%lld\n",ans);
}

T2

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1000011;
struct tree{
	int l,r;
	int sum;
	int maxa;
	int lazy;
}tre[6*N];
struct pot_{
	int a,b,w;
	int ab;
	friend bool operator<(pot_ a,pot_ b)
	{
		return a.ab<b.ab;
	}
}pot[N];
int jud[N];
int n;
int lsh[N],sl;
int f[N];
int maxx;
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s;
}
void update(int i)
{
	if(tre[i<<1].sum>tre[i<<1|1].sum)
	{
		tre[i].sum=tre[i<<1].sum;
		tre[i].maxa=tre[i<<1].maxa;
	}
	else
	{
		tre[i].sum=tre[i<<1|1].sum;
		tre[i].maxa=tre[i<<1|1].maxa;
	}
	return;
}
void build(int i,int l,int r)
{
	tre[i].l=l;
	tre[i].r=r;
	if(l==r)
	{
		if(jud[l])
			tre[i].maxa=l;
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	return;
}
void pushdown(int i)
{
	tre[i<<1].sum+=tre[i].lazy;
	tre[i<<1|1].sum+=tre[i].lazy;
	tre[i<<1].lazy+=tre[i].lazy;
	tre[i<<1|1].lazy+=tre[i].lazy;
	tre[i].lazy=0;
	return;
}
void insert(int i,int x,int val)
{
	if(tre[i].lazy)
		pushdown(i);
	if(tre[i].l==tre[i].r)
	{
		tre[i].sum=max(val,tre[i].sum);
		return;
	}
	int mid=(tre[i].l+tre[i].r)>>1;
	if(mid>=x)
		insert(i<<1,x,val);
	else
		insert(i<<1|1,x,val);
	update(i);
	return;
}
void insert1(int i,int l,int r,int val)
{
	if(tre[i].lazy)
		pushdown(i);
	if(tre[i].l>=l&&tre[i].r<=r)
	{
		tre[i].sum+=val;
		tre[i].lazy+=val;
		return;
	}
	int mid=(tre[i].l+tre[i].r)>>1;
	if(mid>=l)
		insert1(i<<1,l,r,val);
	if(mid<r)
		insert1(i<<1|1,l,r,val);
	update(i);
	return;
}
tree query(int i,int l,int r)
{
	if(tre[i].lazy)
		pushdown(i);
	if(tre[i].l>=l&&tre[i].r<=r)
		return tre[i];
	tree ans1,ans2;
	ans1.sum=ans1.maxa=ans2.sum=ans2.maxa=0;
	int mid=(tre[i].l+tre[i].r)>>1;
	if(mid>=l)
		ans1=query(i<<1,l,r);
	if(mid<r)
		ans2=query(i<<1|1,l,r);
	return ans1.sum<ans2.sum?ans2:ans1;
}
void lsh_()
{
	sort(lsh+1,lsh+sl+1);
	int x=unique(lsh+1,lsh+sl+1)-lsh;
	for(int i=1;i<=n;i++)
	{
		pot[i].a=lower_bound(lsh+1,lsh+x,pot[i].a)-lsh;
		pot[i].b=lower_bound(lsh+1,lsh+x,pot[i].b)-lsh;
		pot[i].ab=pot[i].a+pot[i].b;
		jud[pot[i].a]=1;
		maxx=max(maxx,max(pot[i].a,pot[i].b));
	}
	return;
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		lsh[++sl]=pot[i].a=read();
		lsh[++sl]=pot[i].b=read();
		pot[i].w=read();
	}
	lsh_();
	sort(pot+1,pot+n+1);
	build(1,1,maxx);
	maxx=0;
	for(int i=1;i<=n;i++)
	{
		if(pot[i].a<pot[i].b)
		{
			tree ans=query(1,1,pot[i].a);
			ans.sum+=pot[i].w;
			f[i]=ans.sum;
			insert(1,pot[i].a,ans.sum);
			ans=query(1,pot[i].a+1,pot[i].b);
			ans.sum+=pot[i].w;
			f[i]=max(f[i],ans.sum);
			insert1(1,pot[i].a+1,pot[i].b,pot[i].w);
		}
		else
		{
			tree ans=query(1,1,pot[i].b);
			ans.sum+=pot[i].w;
			insert(1,pot[i].a,ans.sum);
			f[i]=ans.sum;
		}
		maxx=max(maxx,f[i]);
	}
	cout<<maxx<<endl;
	return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
const int N=200011;
struct tu{
	int x;
	long long d;
	friend bool operator<(tu a,tu b)
	{
		return a.d>b.d;
	}
}a,b;
struct qxxx{
	int v,next;
	long long w;
}cc[2*N];
bool jud[N];
int p[N];
int first[N],cnt;
int fm[N];
int n,m,num;
long long d[N];
long long ans[N];
priority_queue<tu> dui;
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s;
}
void qxx(int u,int v,int w)
{
	cc[++cnt].v=v;
	cc[cnt].w=w;
	cc[cnt].next=first[u];
	first[u]=cnt;
	return;
}
inline long long min_(long long a,long long b)
{
	return a<b?a:b;
}
void dij()
{
	memset(d,0x7f,sizeof(d));
	for(int i=1;i<=num;i++)
	{
		a.x=p[i];
		d[a.x]=0;
		dui.push(a);
		fm[a.x]=p[i];
	}
	while(dui.size())
	{
		a=dui.top();
		dui.pop();
		if(jud[a.x])
			continue;
		jud[a.x]=1;
		for(int i=first[a.x];i;i=cc[i].next)
			if(d[cc[i].v]>d[a.x]+cc[i].w)
			{
				d[cc[i].v]=d[a.x]+cc[i].w;
				fm[cc[i].v]=fm[a.x];
				b.x=cc[i].v;
				b.d=d[cc[i].v];
				dui.push(b);
			}
	}
	return;
}
signed main()
{
	int x,y,z;
	n=read();
	m=read();
	num=read();
	for(int i=1;i<=num;i++)
		p[i]=read();
	for(int i=1;i<=m;i++)
	{
		x=read();
		y=read();
		z=read();
		qxx(x,y,z);
		qxx(y,x,z);
	}
	dij();
	memset(ans,0x7f,sizeof(ans));
	for(int i=1;i<=n;i++)
		for(int j=first[i];j;j=cc[j].next)
			if(fm[i]!=fm[cc[j].v])
			{
				x=fm[i],y=fm[cc[j].v];
				long long k=d[cc[j].v]+cc[j].w+d[i];
				ans[x]=min_(ans[x],k);
				ans[y]=min_(ans[y],k);
			}
	for(int i=1;i<=num;i++)
		printf("%lld ",ans[p[i]]);
	return 0;
}

T4

#include<bits/stdc++.h>
using namespace std;
const int N=100011;
struct wd{
	int sl;
	char kd;
}pot[N];
struct ary{
	int l,r;
	int num[2];
}ary[N];
bool jud[N];
int jud1[N][2];
int n;
int sum;
int wzq,wz,sl;
vector<int> vct;
inline int read()
{
	int s=0;
	char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+(ch^48);
		ch=getchar();
	}
	return s;
}
inline char readc()
{
	char ch=getchar();
	while(ch!='+'&&ch!='-'&&ch!='$')
		ch=getchar();
	return ch;
}
void solve(int x)
{
	ary[x].num[0]=0;
	for(int i=ary[x].r-1;i>=ary[x].l;i--)
	{
		if((jud[i+1]&&pot[i].kd=='+')||(!jud[i+1]&&pot[i].kd=='-'))
			jud[i]=1,ary[x].num[0]++;
		else
			jud[i]=0;
	}
	ary[x].num[1]=1;
	jud[ary[x].r]=1;
		for(int i=ary[x].r-1;i>=ary[x].l;i--)
	{
		if((jud[i+1]&&pot[i].kd=='+')||(!jud[i+1]&&pot[i].kd=='-'))
			jud[i]=1,ary[x].num[1]++;
		else
			jud[i]=0;
	}
	if(!jud1[pot[ary[x].r].sl][0])
	{
		jud1[pot[ary[x].r].sl][0]=1;
		jud1[pot[ary[x].r].sl][1]+=ary[x].num[1]-ary[x].num[0];
		vct.push_back(pot[ary[x].r].sl);
	}
	else
		jud1[pot[ary[x].r].sl][1]+=ary[x].num[1]-ary[x].num[0];
	sum+=ary[x].num[0];
	return;
}
void init()
{
	memset(jud,0,sizeof(jud));
	memset(jud1,0,sizeof(jud1));
	if(vct.size())
		vct.clear();
	sum=0;
	sl=0;
	return;
}
int main()
{
	int t=read();
	while(t--)
	{
		init();
		n=read();
		int num=0;
		for(int i=1;i<=n;i++)
		{
			pot[i].kd=readc();
			if(pot[i].kd=='$')
			{
				num++;
				pot[i].sl=read();
				
			}
		}
		if(!num)
		{
			bool jd=0;
			jud[1]=1;
			for(int i=1;i<n;i++)
			{
				if(jud[i]==1&&pot[i].kd=='+')
					jud[i+1]=1;
				else if(!jud[i]&&pot[i].kd=='+')
					jud[i+1]=0;
				else if(jud[i]&&pot[i].kd=='-')
					jud[i+1]=0;
				else
					jud[i+1]=1;
			}
			if(jud[n]==1&&pot[n].kd=='+'||jud[n]==0&&pot[n].kd=='-')
				jd=1;
			else
				jd=0;
			if(!jd)
			{
				jud[1]=0;
				for(int i=1;i<n;i++)
				{
					if(jud[i]==1&&pot[i].kd=='+')
						jud[i+1]=1;
					else if(!jud[i]&&pot[i].kd=='+')
						jud[i+1]=0;
					else if(!jud[i]&&pot[i].kd=='-')
						jud[i+1]=1;
					else
						jud[i+1]=0;
				}
				if(!jud[n]&&pot[n].kd=='+'||jud[n]&&pot[n].kd=='-')
					jd=1;
				else
					jd=0;
			}
			if(jd)
				printf("%s\n","consistent");
			else
				printf("%s\n","inconsistent");
		}
		else
		{
			for(int i=1;i<=n;i++)
				if(pot[i].kd=='$')
				{
					wzq=i;
					break;
				}
			memcpy(pot+n+1,pot+1,sizeof(wd)*wzq);
			wz=n+wzq;
			int qd=wzq+1;
			for(int i=wzq+1;i<=wz;i++)
				if(pot[i].kd=='$')
				{
					ary[++sl].l=qd;
					ary[sl].r=i;
					qd=i+1;
				}
			for(int i=1;i<=sl;i++)
				solve(i);
			bool jd=0;
			for(int i=0;i<vct.size();i++)
				if(vct[i]==sum+jud1[vct[i]][1])
				{
					jd=1;
					break;
				}
			bool jd1=1;
			for(int i=0;i<vct.size();i++)
				if(vct[i]==sum)
					jd1=0;
			if(jd||jd1)
				printf("%s\n","consistent");
			else
				printf("%s\n","inconsistent");
		}
	}
	return 0;
}

这篇关于noip模拟37的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

noip模拟37

T1

T2

T3

T4

代码

T1

T2

T3

T4

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯