\(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;
}
}