noip模拟74(待补)

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

A. 自然数

线段树二分在之前的题目中出现过，但是我是用别的方法写的.

所以这个题在我这里就死了.

固定左端点应该是能想到的，因为这样的套路很多，但是自己没想到，不应该.

A_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long 
	#define ull unsigned ll
	#define lf long 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 w=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
		return cit?w:-w;
	}
} using namespace BSS;

#define ls (x<<1)
#define rs (x<<1|1)
const ll N=1e6+21,W=2e5+21;

ll m,n,ans;
ll vis[N],val[N],lst[N],nxt[N];
struct I { ll sum,lzy,maxw; } tr[N<<2];
auto getval=[](ll 
x,ll w,ll l,ll r){ 
	tr[x].sum=(r-l+1)*w,tr[x].lzy=w,tr[x].maxw=w;
};
auto spread=[](ll x,ll l,ll r){
	ll &lzy=tr[x].lzy,mid=(l+r)>>1;
	if(~lzy) getval(ls,lzy,l,mid),getval(rs,lzy,mid+1,r),lzy=-1;
};
auto pushup=[](ll x){ 
	tr[x].sum=tr[ls].sum+tr[rs].sum;
	tr[x].maxw=max(tr[ls].maxw,tr[rs].maxw); 
};
void change(ll x,ll l,ll r,ll ql,ll qr,ll w){
	if(l>=ql and r<=qr) return getval(x,w,l,r),void();
	ll mid=(l+r)>>1; spread(x,l,r);
	if(ql<=mid) change(ls,l,mid,ql,qr,w);
	if(qr>mid) change(rs,mid+1,r,ql,qr,w);
	pushup(x);
}
ll qsum(ll x,ll l,ll r,ll ql,ll qr){
	if(l>=ql and r<=qr) return tr[x].sum;
	ll mid=(l+r)>>1,res=0; spread(x,l,r);
	if(ql<=mid) res+=qsum(ls,l,mid,ql,qr);
	if(qr>mid) res+=qsum(rs,mid+1,r,ql,qr);
	pushup(x); return res;
}
ll qmax(ll x,ll l,ll r,ll ql,ll qr){
	if(ql>qr) return -1;
	if(l>=ql and r<=qr) return tr[x].maxw;
	ll mid=(l+r)>>1,res=0; spread(x,l,r);
	if(ql<=mid) res=max(res,qmax(ls,l,mid,ql,qr));
	if(qr>mid) res=max(res,qmax(rs,mid+1,r,ql,qr));
	pushup(x); return res;
}
ll qpos(ll x,ll l,ll r,ll ql,ll qr,ll w){
	if(l==r) return tr[x].maxw>=w ? l : -1;
	ll mid=(l+r)>>1,res; spread(x,l,r);
	if(l>=ql and r<=qr){
		if(tr[ls].maxw>=w) res=qpos(ls,l,mid,ql,qr,w);
		else res=qpos(rs,mid+1,r,ql,qr,w);
		pushup(x); return res;
	}
	if(ql<=mid and tr[ls].maxw>w) res=qpos(ls,l,mid,ql,qr,w);
	else res=qpos(rs,mid+1,r,ql,qr,w);
	pushup(x); return res;
}
void build(ll x,ll l,ll r){
	tr[x].lzy=-1;
	if(l==r) return ; ll mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
}
signed main(){
	File(mex);
	n=read();  ll now=0,x,y;
	for(ll i=1;i<=n;i++) val[i]=read();
	for(ll i=1;i<=n;i++){
		if(val[i]>n) { change(1,1,n,i,i,now); continue; }
		if(vis[val[i]]) lst[i]=vis[val[i]],nxt[vis[val[i]]]=i; 
		vis[val[i]]=i; while(vis[now]) now++; change(1,1,n,i,i,now);
	}
	for(ll i=n;i>=1;i--){
		if(val[i]>n) continue;
		if(!nxt[i]) nxt[i]=n+1;
	}
	for(ll i=1;i<=n;i++){
		ans+=qsum(1,1,n,i,n);
		if(val[i]>n or qmax(1,1,n,i+1,n)<val[i]) continue;
		now=qpos(1,1,n,i+1,n,val[i]);
		if(now>0) change(1,1,n,now,nxt[i]-1,val[i]);
	}
	printf("%lld\n",ans),exit(0);
}

B. 钱仓

签到题，贪心乱写.

由于博主比较智障，直接糊了个线段树.

B_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long 
	#define ull unsigned ll
	#define lf long 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 w=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
		return cit?w:-w;
	}
} using namespace BSS;

#define ls x<<1
#define rs x<<1|1
const ll N=2e5+21,inf=1e15;

ll m,n,pc,ans,minpos,minval;
ll o[N];
struct I { ll w,c,len,lc,llen; } tr[N<<2];
auto getval=[](ll x,ll c,ll len)->void{
	tr[x].c+=c,tr[x].len+=len,tr[x].w=tr[x].len-tr[x].c;
	tr[x].lc+=c,tr[x].llen+=len;
};
void update(ll x,ll l,ll r,ll ql,ll qr,ll c,ll len){
	if(l>=ql and r<=qr) return getval(x,c,len)/*,cout<<l<<' '<<r<<" "<<tr[x].c<<' '<<tr[x].w<<endl*/,void();
	 // 让 len-c 时刻都 >= 0 ，所以维护最小值，如果存在最小值小于 0，那么不行.
	ll mid=(l+r)>>1; 
	getval(ls,tr[x].lc,tr[x].llen),getval(rs,tr[x].lc,tr[x].llen);
	tr[x].lc=0,tr[x].llen=0;
	if(ql<=mid) update(ls,l,mid,ql,qr,c,len);
	if(qr>mid) update(rs,mid+1,r,ql,qr,c,len);
	ll y= (tr[ls].w<tr[rs].w ? ls : rs);
	tr[x].w=tr[y].w,tr[x].c=tr[y].c,tr[x].len=tr[y].len;
	// cout<<l<<' '<<r<<' '<<tr[x].w<<' '<<tr[ls].w<<' '<<tr[rs].w<<endl;
}
signed main(){
	File(barn);
	n=read(),m=n<<1,minval=inf; ll flag=0,res;
	for(ll i=1;i<=n;i++){
		o[i]=read(),o[i+n]=o[i],flag|=(o[i]==0);
	}
	for(ll i=m;i>=n+1;i--) pc+=o[i],update(1,1,m,i,i,pc,m-i+1);
	for(ll i=1;i<=n;i++) update(1,1,m,i,i,-inf,inf);
	if(!flag) puts("0"),exit(0); minval=tr[1].w,minpos=m;
	for(ll i=n;i>=2;i--){
		update(1,1,m,i+n,i+n,-inf,inf);
		ll r=i+n-1,l=i-1;
		update(1,1,m,l,r,-o[r+1],-1),update(1,1,m,i,i,pc,n);
		if(tr[1].w>minval) minval=tr[1].w,minpos=i+n-1;
	}
	// cout<<minval<<' '<<minpos<<endl;
	for(ll i=minpos,j=minpos;i>=minpos-n+1;i--){
		if(!o[i]){
			while(!o[j]) j--;
			o[i]++,o[j]--,ans+=(i-j)*(i-j);
		}
		else j=min(j,i-1);
	}
	printf("%lld\n",ans),exit(0);
}

C. 游戏

很明显应该是 \(dp\)，很明显又应该是矩阵优化.

其实列个式子好像就很容易出来了，感觉并不是那种完全做不出来的题目。

C_code

#include<bits/stdc++.h>
using namespace std;
namespace BSS {
	#define ll long long 
	#define ull unsigned ll
	#define lf long 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 w=0; bool cit=1; char ch;
		while(!isdigit(ch=getchar())) if(ch=='-') cit=0; 
		while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
		return cit?w:-w;
	}
} using namespace BSS;

const ll mod=1e9+7;

ll n,p,q,m,Ts;
ll f[3],g[3][3],g1[3][3],g2[3][3];
auto ksm=[](ll a,ll b,ll c)->ll{
	ll res=1; a%=c;
	for(;b;b>>=1,a=a*a%c) if(b&1) res=res*a%c;
	return res%c;
};
inline void mul(){
	ll c[3]={0};
	for(ll j=1;j<=2;j++){
		for(ll k=1;k<=2;k++)
			c[j]=(c[j]+f[k]*g[k][j]%mod)%mod;
	}
	Copy(f,c);
}
inline void mulself(){
	ll c[3][3]={0};
	for(ll i=1;i<=2;i++){
		for(ll j=1;j<=2;j++)
			for(ll k=1;k<=2;k++)
				c[i][j]=(c[i][j]+g[i][k]*g[k][j]%mod)%mod;
	}
	Copy(g,c);
}
inline void mulmore(){
	ll c[3]={0};
	for(ll j=1;j<=2;j++){
		for(ll k=1;k<=2;k++)
			c[j]=(c[j]+f[k]*g2[k][j]%mod)%mod;
	}
	Copy(f,c);
}
signed main(){
	File(game);
	Ts=read();
	while(Ts--){
		Fill(f,0),Fill(g,0);
		ll x=ksm(1e8,mod-2,mod); f[2]=1;
		n=read(),p=read()%mod*x%mod,q=read()%mod*x%mod;
		x=ksm(1-p*q%mod+mod,mod-2,mod);
		g1[1][1]=p*(1-q+mod)%mod*x%mod,g1[2][1]=(1-p+mod)*x%mod;
		g1[1][2]=(1-q+mod)*x%mod,g1[2][2]=q*(1-p+mod)%mod*x%mod;	
		x=ksm(1-(1-p+mod)%mod*(1-q+mod)%mod+mod,mod-2,mod);
		g2[1][1]=(1-p+mod)*q%mod*x%mod,g2[2][1]=p*x%mod;
		g2[1][2]=q*x%mod,g2[2][2]=(1-q+mod)*p%mod*x%mod;
		for(ll i=1;i<=2;i++){
			for(ll j=1;j<=2;j++)
				for(ll k=1;k<=2;k++)
					g[i][j]=(g[i][j]+g2[i][k]*g1[k][j]%mod)%mod;
		}
		m=n>>1; for(;m;m>>=1,mulself()) if(m&1) mul();
		if(n&1) mulmore();
		printf("%lld\n",f[1]);
	}
	exit(0);
}

D. Sanrd

没改，先鸽.

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

Java教程

noip模拟74(待补)

A. 自然数

B. 钱仓

C. 游戏

D. Sanrd

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯