noip模拟24[matrix·block·graph]

\(noip模拟24\;solutions\)

这果然是wzz的题,见题如见人,感觉自己好像浪费了一套好题,只拿了30pts

只有第一题有分,害,后面的暴搜程序没有打,第一题状压少写了一层循环

惨死了,最后一题好难,是队奶奶给我讲会的

\(T1\;matrix\)

这个题真的很简单,考场一个小时的时候思路已经完全了,

为啥没切,就是手惨,

就是一个涉及到三层的状压,一看到数据范围10都不到,不是状压是啥???

维护\(f[i][j][k]\)表示第i层,覆盖状态为j,选择按钮的状态为k,注意覆盖状态和按钮不是一个东西

a[i]预处理原有的状态,g[i][j]预处理状态所需要的代价

然后一行一行的向下转移就行了,j中包含k的影响

AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int 
const int N=11;
int n,m;
int a[N],c[N][N];
int f[N][1<<10][1<<10],g[N][1<<10],las[N][1<<10];
int ans=0x3f3f3f3f;
signed main(){
	scanf("%d%d",&n,&m);
	int bas=1<<m;
	for(re i=1;i<=n;i++){
		char x[N];
		scanf("%s",x);
		for(re j=0;j<m;j++){
			int tmp=x[j]-‘0‘;
			a[i]|=(tmp<<j);
		}
	}
	for(re i=1;i<=n;i++){
		for(re j=0;j<m;j++)
			scanf("%d",&c[i][j]);
		//cout<<"i= "<<i<<" ";
		for(re j=0;j<bas;j++){
			int tmp=0;
			for(re k=0;k<10;k++)
				if(j&(1<<k))
					tmp+=c[i][k];
			g[i][j]=tmp;
			//cout<<j<<" "<<g[i][j]<<"   ";
		}
		//cout<<endl;
	}
	memset(f,0x3f,sizeof(f));
	for(re i=0;i<bas;i++)
		for(re j=0;j<bas;j++)
			f[0][i][j]=0;
	for(re i=0;i<n;i++){
		for(re j=0;j<bas;j++){
			for(re u=0;u<bas;u++){
				if((j|u)!=bas-1)continue;
				for(re k=0;k<bas;k++){
					if(f[i][j][k]==0x3f3f3f3f)continue;
					int tmp=u|((u<<1)&(bas-1))|(u>>1)|k|a[i+1];
					if(i==0)tmp=u|((u<<1)&(bas-1))|(u>>1)|a[i+1];
					f[i+1][tmp][u]=min(f[i+1][tmp][u],f[i][j][k]+g[i+1][u]);
				}
			}
		}
	}
	for(re i=0;i<bas;i++)ans=min(ans,f[n][bas-1][i]);
	printf("%d",ans);
}

\(T2\;block\)

这个题就是难了我一下午的题吗???

我对着这个题硬刚,刚了好久,第一问非常好理解,第二问的线段树就非常的神

第一问就是先排序,一个一个向里插,你会发现,当前序列中的数都比他大

所以这个数插入的位置-1就是有多少个比它大的数,所以这样就可以有了多种方案

所有的方案数相乘就是最后的方案数,

注意相等的情况,按照key从小到大排序,因为可以保证你当前的比上一个放的更加靠后

这样的话,和他一样的一定在他前面,当前能放的位置直接向后移就好了

第二问的线段树做法和第一问完全没有关系,不要再向第一个思路想了

考虑转变key的含义,让他表示当前数前面能够放几个比他大的数,

所以我们每插入一个数,就吧value比他小的数的key--,这样当有一个数的key为1的时候

只能继续插入小于等于他的数,注意这两个的取等啊啊啊

我们就可以直接按照value从小到大,然后建立一颗普普通通的线段树,

维护字典序最小的点,单点修改,区间修改,区间查询,就完事了,

实现还是挺麻烦的,我调了好久呢

AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int 
const int N=5e5+5;
const int mod=1e9+7;
int n;
struct node{
	int key,val;
	node(){}
	bool operator < (node x)const{
		if(val!=x.val)return val>x.val;
		return key<x.key;
	}
}sca[N];
bool cmp(node x,node y){
	if(x.val!=y.val)return x.val<y.val;
	return x.key<y.key;
}
int ans=1;
struct XDS{
	#define ls x<<1
	#define rs x<<1|1
	int val[N*4],key[N*4],now[N*4],who[N*4];
	int laz[N*4],mn[N*44];
	int mim(int x,int y){
		if(x==-1)return y;
		if(y==-1)return x;
		if(sca[x].key!=sca[y].key)return sca[x].key<sca[y].key?x:y;
		return sca[x].val<sca[y].val?x:y;
	}
	void pushup(int x){
		if(now[ls]<=now[rs])now[x]=now[ls],who[x]=who[ls];
		else now[x]=now[rs],who[x]=who[rs];
		mn[x]=mim(mn[ls],mn[rs]);
		return ;
	}
	void pushdown(int x){
		if(!laz[x])return ;
		laz[ls]+=laz[x];
		laz[rs]+=laz[x];
		now[ls]+=laz[x];
		now[rs]+=laz[x];
		laz[x]=0;
		return ;
	}
	void build(int x,int l,int r){
		if(l==r){
			//if(sca[l].key==17&&sca[l].val==4)cout<<x<<endl;
			val[x]=sca[l].val;
			key[x]=sca[l].key;
			now[x]=key[x];
			who[x]=l;
			mn[x]=l;
			return ;
		}
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(x);return ;
	}
	void change(int x,int l,int r,int pos){
		if(l==r){
			//if(sca[l].key==17&&sca[l].val==4)cout<<x<<endl;
			key[x]=0x3f3f3f3f;
			now[x]=0x3f3f3f3f;
			mn[x]=-1;
			return ;
		}
		pushdown(x);
		int mid=l+r>>1;
		if(pos<=mid)change(ls,l,mid,pos);
		else change(rs,mid+1,r,pos);
		pushup(x);return ;
	}
	void ins(int x,int l,int r,int ql,int qr){
		if(ql>qr)return ;
		if(ql<=l&&r<=qr){
			laz[x]-=1;
			now[x]-=1;
			return ;
		}
		pushdown(x);
		int mid=l+r>>1;
		if(ql<=mid)ins(ls,l,mid,ql,qr);
		if(qr>mid)ins(rs,mid+1,r,ql,qr);
		pushup(x);return ;
	}
	int query(int x,int l,int r,int ql,int qr){
		if(qr<ql)return -1;
		if(ql<=l&&r<=qr)return mn[x];
		pushdown(x);
		int mid=l+r>>1,ret=-1;
		if(ql<=mid)ret=mim(ret,query(ls,l,mid,ql,qr));
		if(qr>mid)ret=mim(ret,query(rs,mid+1,r,ql,qr));
		pushup(x);
		return ret;
	}
	#undef ls
	#undef rs
}xds;
int fro[N],beh[N];
signed main(){
	scanf("%d",&n);
	for(re i=1;i<=n;i++)scanf("%d%d",&sca[i].key,&sca[i].val);
	sort(sca+1,sca+n+1);
	int sum;
	for(re i=1;i<=n;i++){
		if(sca[i].val==sca[i-1].val){
			ans=1ll*ans*min(i,sca[i].key+sum)%mod;
			sum++;
		}
		else {
			ans=1ll*ans*min(i,sca[i].key)%mod;
			sum=1;
		}
	}
	//cout<<"sb"<<endl;
	sort(sca+1,sca+n+1,cmp);
	for(re i=1;i<=n;i++){
		if(sca[i].val==sca[i-1].val)fro[i]=fro[i-1];
		else fro[i]=i-1,beh[i-1]=i;
	}
	for(re i=n;i>=1;i--)if(!beh[i])beh[i]=beh[i+1];
	beh[n]=n;
	printf("%d\n",ans);
	//cout<<"sb"<<endl;
	//sort(sca+1,sca+n+1,cmp);
	//cout<<sca[1].key<<" "<<sca[1].val<<endl;
	xds.build(1,1,n);
	//cout<<"finish build"<<endl;
	for(re i=1;i<=n;i++){
		int tmp;
		//cout<<sca[xds.who[1]].key<<" "<<xds.who[1]<<endl;
		if(xds.now[1]==1)tmp=xds.query(1,1,n,1,beh[xds.who[1]]);
		else tmp=xds.mn[1];
		//cout<<"query"<<endl;
		printf("%d %d\n",sca[tmp].key,sca[tmp].val);
		xds.change(1,1,n,tmp);
		//cout<<"change"<<endl;
		xds.ins(1,1,n,1,fro[tmp]);
		//cout<<"ins"<<endl;
	}
}

noip模拟24[matrix·block·graph]

上一篇:nginx详细配置


下一篇:npx