【JZOJ6214】【20190614】tetris

蔚落 2021-12-23 01:45 169阅读 0赞

## 题目 ##

这是一道和俄罗斯方块有关的有趣题目

底面宽度为\$N\$，高度无限，初始时方块高度为\$A\_i\$

你可以决定每次会下落一个\$1 \\times K\$或者\$K \\times 1\$的方块

你需要在10000次内把所有方块消完，输出方案

$N , K A\_i \\le 50 $

## 题解 ##

**![img][]**

#include<bits/stdc++.h>
    using namespace std;
    const int N=51,K=51;
    int n,m,k,a[N],b[N*K],c[K],mn,mx,ans;
    struct opt{int x,y;}Ans[10010];
    
    void put(int op,int x){Ans[++ans]=(opt){op,x};}
    
    bool judge(){
        for(int i=0;i<n;++i)(c[i%k]+=a[i])%=k;
        int tmp=c[0];for(int i=0;i<m;++i)if(c[i]!=tmp)return false;
        tmp=c[m];for(int i=m;i<k;++i)if(c[i]!=tmp)return false;
        return true;
    }
    
    int main(){
        freopen("tetris.in","r",stdin);
        freopen("tetris.out","w",stdout);
        scanf("%d%d",&n,&k);m=n%k;
        for(int i=0;i<n;++i)scanf("%d",&a[i]);
        
        if(!judge())return puts("-1"),0;
    
        for(int i=1;i<n;++i)while(a[i]<a[i-1])put(1,i),a[i]+=k;
        mn=mx=a[0];for(int i=1;i<n;++i)mn=min(mn,a[i]),mx=max(mx,a[i]);
        mx-=mn;for(int i=0;i<n;++i)a[i]-=mn,b[a[i]]++;
        
        for(int i=mx;i;--i)b[i]+=b[i+1];
        for(int i=1;i<=mx;++i)while(b[i]+k<=n)put(2,n-b[i]-k),b[i]+=k;
    
        for(int i=0;i<k;++i)c[i]=0;
        for(int i=1;i<=mx;++i)c[n-b[i]]++;
        for(int i=k-1;i;--i)c[i]+=c[i+1];
        
        mx-=c[0];
        int tmp=(mx-1)/k+1;mx=tmp*k;
        for(int i=0;i<k-1;++i){
            for(int j=0;j<tmp;++j)put(1,i);
            a[i]=mx-c[i+1];
        }
        for(int i=k-1;i<n;++i)a[i]=0;
            
        mx=0;for(int i=m;i<=k-1;++i)mx=max(mx,a[i]);
        for(int i=0;i<n;++i)while(a[i]<mx)put(1,i),a[i]+=k;
        for(int i=0;i<n;++i)a[i]-=mx;
        
        if(n%k){
            mx=0;for(int i=0;i<m;++i)mx=max(mx,a[i]);
            for(int i=0;i<m;++i)while(a[i]<mx)put(1,i),a[i]+=k;
            for(int i=m;i<n;i+=k)for(int j=0;j<mx;++j)put(2,i);
        }
        
        printf("%d\n",ans);
        for(int i=1;i<=ans;++i)printf("%d %d\n",Ans[i].x,Ans[i].y+1);
        return 0;
    }

转载于:https://www.cnblogs.com/Paul-Guderian/p/11074610.html

[img]: /images/20211220/fb082ccad56f47c982087d13f683cdc0.png