noip模拟61

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

A. 交通

考虑转化问题.

把边之间的禁止关系转化成点之间的.

还有一种思路.

发现每个边的出边和入边只能选一个.

所以可以选择固定一个点的出边/入边,然后删边判定就行了.

A_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=3e6+21,mod=998244353;

ll m,n,ans;
ll fa[N],vis[N];
struct Graph{
	ll ts; ll head[N];
	struct I { ll u,v,col,nxt; } e[N<<1];
	inline void add(ll u,ll v,ll opt){
		e[++ts].u=u,e[ts].v=v,e[ts].nxt=head[u],
		head[u]=ts,e[ts].col=opt;
	}
}A,B;
inline ll find(ll x){ return x==fa[x] ? x : fa[x]=find(fa[x]); } 
inline ll ksm(ll a,ll b,ll c){
	a%=c; ll res=1;
	for(;b;b>>=1,a=a*a%c) if(b&1) res=res*a%c;
	return res%c;
}
signed main(){
	File(a);
	n=read(); ll u,v,a,b,c,d; A.ts=1;
	for(int i=1;i<=2*n;i++) u=read(),v=read(),A.add(u,v,1),A.add(v,u,0);
	for(int u=1;u<=n;u++){
		a=A.head[u],b=A.e[a].nxt,c=A.e[b].nxt,d=A.e[c].nxt;
		if(A.e[a].col==A.e[b].col) B.add(a-(a&1),b-(b&1),0),B.add(c-(c&1),d-(d&1),0);
		else if(A.e[a].col==A.e[c].col) B.add(a-(a&1),c-(c&1),0),B.add(b-(b&1),d-(d&1),0);
		else if(A.e[a].col==A.e[d].col) B.add(a-(a&1),d-(d&1),0),B.add(b-(b&1),c-(c&1),0);
	}
	for(int i=2;i<=A.ts;i+=2) fa[i]=i;
	for(int i=1;i<=B.ts;i++){
		u=B.e[i].u,v=B.e[i].v;
		if(find(u)!=find(v)) fa[find(u)]=find(v);
	}
	for(int i=2;i<=A.ts;i+=2) if(!vis[find(i)]) ans++,vis[find(i)]=1;
	printf("%lld\n",ksm(2,ans,mod));	
	exit(0);
}

B. 小P的单调数列

一开始就应该推性质而不是莽干的.

做不出来的时候思维就应该发散一下.

由于越取平均数答案越小,其实序列有一个最多只有两段的性质.

也就是说答案要么只有单增的一段,要么就是一段单增,一段单减.

B_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=1e5+21;

lf ans;
ll m,n,cnt;
ll val[N],lsh[N],ans1[N],ans2[N];
struct Bit_Array{
	ll res; ll c[N<<2];
	inline void update(ll x,ll w){
		for(;x<=n;x+=lbt(x)) c[x]=max(c[x],w);
	}
	inline ll query(ll x){
		res=0; for(;x>0;x&=(x-1)) res=max(res,c[x]); return res;
	}
	inline void clr(){ Fill(c,0); }
}bit;
signed main(){
	File(b);
	n=read();
	for(int i=1;i<=n;i++) lsh[i]=val[i]=read();
	sort(lsh+1,lsh+1+n),cnt=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++){
		val[i]=lb(lsh+1,lsh+1+cnt,val[i])-lsh;
		ans1[i]=bit.query(val[i]-1)+lsh[val[i]];
		bit.update(val[i],ans1[i]);
	}
	bit.clr();
	for(int i=n;i>=1;i--){
		ans2[i]=bit.query(val[i]-1)+lsh[val[i]];
		bit.update(val[i],ans2[i]);
	}
	for(int i=1;i<=n;i++) ans1[i]=max(ans1[i],ans1[i-1]);
	for(int i=n;i>=1;i--) ans2[i]=max(ans2[i],ans2[i+1]);
	for(int i=1;i<=n;i++){
		ans=max(ans,1.0*ans1[i]);
		ans=max(ans,1.0*(ans1[i]+ans2[i+1])/2);
	}
	printf("%.3lf\n",ans);
	exit(0);
}

C. 矩阵

很显然是构造题.

由于两点之间即可确定一条线.

所以可以转化成只让前两行和前两列被消成 \(0\).

C_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=1e3+21;

ll m,n,cntx,cnty,cntz;
ll x[N],y[N],z[N*3];
ll w[N][N];
signed main(){
	File(c);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			w[i][j]=read();
		}
	}
	x[1]=w[2][2]-w[1][1],z[N]=-w[2][2];
	for(int i=2;i<=n;i++) z[N+1-i]+=-x[i]-w[i][1],x[i+1]+=-(z[N+1-i]+w[i+1][2]);
	for(int j=2;j<=m;j++) z[N+j-1]+=-y[j]-x[1]-w[1][j],y[j+1]+=-(z[N+j-1]+w[2][j+1]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			if(w[i][j]+x[i]+y[j]+z[j-i+N]) puts("-1"),exit(0);
	}
	cout<<n+m+(m-1-(1-n)+1)<<endl;
	for(int i=1;i<=n;i++) cout<<1<<' '<<i<<' '<<x[i]<<endl;
	for(int j=1;j<=m;j++) cout<<2<<' '<<j<<' '<<y[j]<<endl;
	for(int i=1-n;i<=m-1;i++) cout<<3<<' '<<i<<' '<<z[N+i]<<endl;
	exit(0);
}

D. 花瓶

没见过二维斜率优化,枯了.

考场上想了斜率优化,但是写的是一维的,发现这个东西很离奇,于是就死了.

不应该拘束于已经学过的东西.

D_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long int
	#define ull unsigned ll
	#define lf double
	#define lbt(x) (x&(-x))
	#define mp(x,y) make_pair(x,y)
	#define lb lower_bound 
	#define ub upper_bound
	#define Fill(x,y) memset(x,y,sizeof x)
	#define Copy(x,y) memcpy(x,y,sizeof x)
	#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
	inline ll read() {
		ll res=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
		return cit?res:-res;
	}
} using namespace BSS;

const ll N=5e3+21;

ll m,n,ans;
ll val[N],stk[N],sum[N];
ll dp[N][N];
struct I { ll pre,id; } p[N];
inline bool comp(I i,I j){ return i.pre==j.pre ? i.id<j.id : i.pre<j.pre; } 
inline ll caly(ll j,ll k){ return dp[j][k]; }
inline lf slope(ll j,ll ka,ll kb){ return sum[ka]==sum[kb] ? 1e15 : 1.0*(caly(j,ka)-caly(j,kb))/(sum[ka]-sum[kb]); }
signed main(){
	File(d);
	n=read(); ll l,r,id;
	for(int i=1;i<=n;i++){
		val[i]=read(),p[i].pre=p[i-1].pre+val[i],p[i].id=i;
		sum[i]=p[i].pre;
	}
	sort(p+1,p+1+n,comp);
	for(int j=1;j<=n;j++){
		l=1,r=0;
		for(int k=1;k<=n;k++){
			id=p[k].id; if(id>=j) continue;
			while(l<r and slope(j,stk[r],stk[r-1])<=slope(j,id,stk[r])){
				r--;
			}
			stk[++r]=id;
		}
		for(int i=n;i>=1;i--){
			id=p[i].id; if(id<=j) continue;
			while(l<r and (slope(j,stk[l+1],stk[l])>=(sum[id]-sum[j]))){
				l++;
			}
			dp[id][j]=max(caly(j,stk[l])+(sum[id]-sum[j])*(sum[j]-sum[stk[l]]),(sum[id]-sum[j])*sum[j]);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[n][i]);
	}
	printf("%lld\n",ans);
	exit(0);
}

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

Java教程

noip模拟61

A. 交通

B. 小P的单调数列

C. 矩阵

D. 花瓶

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯