10.8 考试-白红宇

10.8 考试

阅读量：4918 次

发布时间：2019-06-11

本文共 10251 字，大约阅读时间需要 34 分钟。

贪心的选

首先从0开始，让[1,可以达到dmax]都有青蛙

设las=1，now=dmax，当前[las,now]的石头上蹲满了青蛙

然后考虑从las开始走，当前las指的青蛙一定是跳到它能到的范围内最近的那个石头

reason：最左边的石头是最早不能用的，所以要最先用掉

(我这样其实对于是保证了最多的青蛙过去，不保证最优的步数)

1.青蛙都一样，无权值

2.每一个石头蹲过一次后，就沉下去了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ char q=getchar();int ans=0; while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=2000006;int T;int n,m,D,L;int a[N];bool flag[N];int er(int l,int r,int pos){ int mid,ans=pos; while(l<=r) { mid=(l+r)>>1; if(a[mid]-a[pos]<=D&&ans
            
             =r) break; if(a[mid]-a[pos]<=D) l=mid+1; else r=mid-1; } return ans;}int work(){ if(D>=L) return m; int las=1,now=0,temp,ans=0,tlas; while(now<=n&&a[now]<=D)++now;--now; if(now<=0) return 0; while(1) { temp=now;tlas=now+1; while(temp>=las&&L-a[temp]<=D) --temp,++ans; if(temp
             
              =m) printf("Excited\n"); else printf("%d\n",temp); }}

用线段树维护三个值：

1.这个区间最终加的层数add

2.这个区间最多删前面的层数del

3.这个区间最终加的层数的总价值addv

然后合并区间的时候

1.add[ls]<=del[rs]

那左边的删没了del[x]=del[rs]-add[ls]+del[ls] add[x]=add[rs] addv[x]=addv[rs]

2.add[ls]>del[rs]

del[x]=del[ls] add[x]=add[ls]-del[rs]+add[rs]

但是计算addv的时候，你需要用到一个合并函数，就像 bzoj楼房建设/前一次考试T3Treap一样

而且合并的是后要利用已经处理出来的信息，不然会T

最后ans=addv[1]

$O(nlogn+nlog^2n)$

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ char q=getchar();int ans=0; while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=200006;int m,Q;int op[N],val[N];struct TREE{ int de[N*6],ad[N*6],adv[N*6]; int cal(int le,int l,int r,int x) { if(le==0) return 0; if(l==r) return adv[x]; int mid=(l+r)>>1; if(ad[x<<1]<=de[x<<1|1]) return cal(le,mid+1,r,x<<1|1); int temp=ad[x<<1]-de[x<<1|1]; if(temp
             
              >1; if(ad[x<<1]<=de[x<<1|1]) { ad[x]=ad[x<<1|1];adv[x]=adv[x<<1|1]; de[x]=de[x<<1]+de[x<<1|1]-ad[x<<1]; } else { ad[x]=ad[x<<1]-de[x<<1|1]+ad[x<<1|1]; de[x]=de[x<<1]; adv[x]=adv[x<<1|1]+cal(ad[x<<1]-de[x<<1|1],l,mid,x<<1); } } void build(int l,int r,int x) { if(l==r) { if(op[l]==0) de[x]=0,ad[x]=1,adv[x]=val[l]; else de[x]=val[l],ad[x]=0,adv[x]=0; return ; } int mid=(l+r)>>1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); pushup(l,r,x); } void add(int pos,int op,int val,int l,int r,int x) { if(l==r) { if(op==0) de[x]=0,ad[x]=1,adv[x]=val; else de[x]=val,ad[x]=0,adv[x]=0; return ; } int mid=(l+r)>>1; if(pos<=mid) add(pos,op,val,l,mid,x<<1); else add(pos,op,val,mid+1,r,x<<1|1); pushup(l,r,x); }}T;int main(){ //freopen("weed.in","r",stdin); //freopen("T2.out","w",stdout); //m=read();Q=read(); scanf("%d%d",&m,&Q); for(int i=1;i<=m;++i) //op[i]=read(),val[i]=read(); scanf("%d%d",&op[i],&val[i]); T.build(1,m,1); //printf("aaa %d\n",T.adv[1]); int c,opop,vv; for(int i=1;i<=Q;++i) { //c=read();opop=read();vv=read(); scanf("%d%d%d",&c,&opop,&vv); T.add(c,opop,vv,1,m,1); printf("%d\n",T.adv[1]); }}

啊啊啊，这个题是最恶心的...

首先题意上的旋转是90度，还有数据范围其实是2000...

实际上，你可以用char、开O3 卡一波常就过了...

还是说正解吧...

维护每一个点的上下左右分别是谁

然后修改的时候，就像割布一样把边缘割下来，然后再缝上去

这样只需要修改边缘，$O(nq大常数)$

然后割的布内部之间的关系不会变，但是之前的上不再是上，而是右

所以要规定一个正方向之类的东西

而第0列的方向是不会变的，而且我们可以从一个点推到它相邻的一个点(这个可以枚举相邻点的4个方向得出)

然后就是呃呃呃呃呃呃呃呃呃呃新的代码了...

#pragma GCC optimize("O3")#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ int ans=0;char q=getchar(); while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=3006;int n,m,Q;char a[N][N];char t[N][N];inline void rot(int lx,int ly,int rx,int ry){ for(int i=lx;i<=rx;++i) { for(int j=ly;j<=ry;++j) t[lx+j-ly][ry-(i-lx)]=a[i][j]; } for(int i=lx;i<=rx;++i) for(int j=ly;j<=ry;++j) a[i][j]=t[i][j];}int main(){ //freopen("drink.in","r",stdin); //freopen("T3.out","w",stdout); n=read();m=read();Q=read(); int tin; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { tin=read(); a[i][j]=tin+'0'; } int lx,ly,c; for(int i=1;i<=Q;++i) { lx=read();ly=read();c=read(); rot(lx,ly,lx+c-1,ly+c-1); } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%c ",a[i][j]); printf("\n"); }}

char、O3卡常过

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ int ans=0;char q=getchar(); while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=2006;struct son{ int x,y; son (){x=0;y=0;} son(int xx,int yy) { x=xx;y=yy; } bool friend operator == (son &a,son &b) { if(a.x==b.x&&a.y==b.y) return 1; return 0; }};int n,m,Q;int ax,ay,c;int a[N][N];son d[N][N][4];int bx[10]={-1,0,1,0};int by[10]={0,1,0,-1};int fan[10]={2,3,0,1};inline int getd(son now,son t){ for(int i=0;i<4;++i) if(d[t.x][t.y][i]==now) return i;}inline void walk(son &now,int &di){ int temp=getd(now,d[now.x][now.y][di]); now=d[now.x][now.y][di]; di=fan[temp];}inline void change(son t1,int d1,son t3,int d3){ //printf("t1x=%d t1y=%d d1=%d t3x=%d t3y=%d d3=%d\n",t1.x,t1.y,d1,t3.x,t3.y,d3); d[t1.x][t1.y][d1]=t3; d[t3.x][t3.y][d3]=t1;}void out1(son now){ printf("out1: %d %d ",now.x,now.y); for(int i=0;i<4;++i) printf("%dV%d ",d[now.x][now.y][i].x,d[now.x][now.y][i].y); printf("\n");}void out11(){ /*printf("aaaa \n"); for(int k=0;k<4;++k) { printf("\n"); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%dV%d ",d[i][j][k].x,d[i][j][k].y); printf("\n"); } printf("\n"); } printf("\n");*/ son now; int di; for(int i=1;i<=n;++i) { now=son(i,0);di=1; for(int j=1;j<=m;++j) { walk(now,di); printf("%dV%d ",now.x,now.y); } printf("\n"); } printf("\n"); son tt[10][10]; for(int j=1;j<=m;++j) { now=son(0,j);di=2; for(int i=1;i<=n;++i) { walk(now,di); tt[i][j]=now; } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%dV%d ",tt[i][j].x,tt[i][j].y); printf("\n"); }}inline void rot(){ //printf("ax=%d ay=%d c=%d\n",ax,ay,c); son now=son(ax,0); son ls,lx,rs,rx; int lsd,lxd,rsd,rxd; int di=1; for(int j=1;j<=ay;++j) walk(now,di); //out1(now); ls=now;lsd=di; for(int i=1;i

被卡内存的正解

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ int ans=0;char q=getchar(); while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=2006;int n,m,Q;int ax,ay,c;int a[N][N],dui[N][N];int v[N*N];int d[N*N][4];int bx[10]={-1,0,1,0};int by[10]={0,1,0,-1};int fan[10]={2,3,0,1};inline int getd(int now,int t){ for(int i=0;i<4;++i) if(d[t][i]==now) return i;}inline void walk(int &now,int &di){ int temp=getd(now,d[now][di]); now=d[now][di]; di=fan[temp];}inline void change(int t1,int d1,int t3,int d3){ //printf("t1x=%d t1y=%d d1=%d t3x=%d t3y=%d d3=%d\n",t1.x,t1.y,d1,t3.x,t3.y,d3); d[t1][d1]=t3; d[t3][d3]=t1;}/*void out1(son now){ printf("out1: %d %d ",now.x,now.y); for(int i=0;i<4;++i) printf("%dV%d ",d[now.x][now.y][i].x,d[now.x][now.y][i].y); printf("\n");}*//*void out11(){ printf("aaaa \n"); for(int k=0;k<4;++k) { printf("\n"); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%dV%d ",d[i][j][k].x,d[i][j][k].y); printf("\n"); } printf("\n"); } printf("\n"); son now; int di; for(int i=1;i<=n;++i) { now=son(i,0);di=1; for(int j=1;j<=m;++j) { walk(now,di); printf("%dV%d ",now.x,now.y); } printf("\n"); } printf("\n"); son tt[10][10]; for(int j=1;j<=m;++j) { now=son(0,j);di=2; for(int i=1;i<=n;++i) { walk(now,di); tt[i][j]=now; } } for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) printf("%dV%d ",tt[i][j].x,tt[i][j].y); printf("\n"); }}*/inline void rot(){ //printf("ax=%d ay=%d c=%d\n",ax,ay,c); int now=dui[ax][0]; int ls,lx,rs,rx; int lsd,lxd,rsd,rxd; int di=1; for(int j=1;j<=ay;++j) walk(now,di); //out1(now); ls=now;lsd=di; for(int i=1;i
             
              =0&&j+by[k]>=0) d[dui[i][j]][k]=dui[i+bx[k]][j+by[k]];}int main(){ //freopen("drink.in","r",stdin); //freopen("T3.in","r",stdin); //freopen("T3.out","w",stdout); n=read();m=read();Q=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=read(); chu(); //getans(); for(int i=1;i<=Q;++i) { ax=read();ay=read();c=read(); rot(); //getans();cout<

卡它一波内存A掉的正解

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define ll long long#define mem(a,b) memset(a,b,sizeof(a))using namespace std;inline int read(){ int ans=0;char q=getchar(); while(q<'0'||q>'9')q=getchar(); while(q>='0'&&q<='9'){ans=ans*10+q-'0';q=getchar();} return ans;}const int N=2006;int n,m,Q;int ax,ay,c;int a[N][N],dui[N][N];int v[N*N];int d[N*N][4];int bx[10]={-1,0,1,0};int by[10]={0,1,0,-1};int fan[10]={2,3,0,1};inline int getd(int now,int t){ for(int i=0;i<4;++i) if(d[t][i]==now) return i;}inline void walk(int &now,int &di){ int temp=getd(now,d[now][di]); now=d[now][di]; di=fan[temp];}inline void change(int t1,int d1,int t3,int d3){ d[t1][d1]=t3; d[t3][d3]=t1;}inline void rot(){ int now=dui[ax][0]; int ls,lx,rs,rx; int lsd,lxd,rsd,rxd; int di=1; for(int j=1;j<=ay;++j) walk(now,di); ls=now;lsd=di; for(int i=1;i
             
              =0&&j+by[k]>=0) d[dui[i][j]][k]=dui[i+bx[k]][j+by[k]];}int main(){ //freopen("drink.in","r",stdin); //freopen("T3.in","r",stdin); //freopen("T3.out","w",stdout); n=read();m=read();Q=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) a[i][j]=read(); chu(); for(int i=1;i<=Q;++i) { ax=read();ay=read();c=read(); rot(); } getans();}