2017.10.2 NOIP模拟赛

题解 套题

目录

• 2017.10.2 NOIP模拟赛
  • 最大矩形
    • 思路
    • 代码
  • 确定小组
    • 思路
    • 代码
  • 华容道游戏
    • 思路
    • 代码

最大矩形

思路

• 虽然需要按顺序在原图中选，但是考虑到每次选的矩形高只会受到最低的那个的影响，而宽只会受到选的矩形的数量的影响，所以与顺序无关；
• 那么我们考虑直接将高降序排序，不断选即可；

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::max;
using std::sort;
const int MAXN=100005;
int n;
int hi[MAXN];
bool cmp(int a,int b){return a>b;}
inline long long cal(){
    sort(hi+1,hi+n+1,cmp);
    int h=hi[1],w=1;
    long long ret=h;
    for(int i=2;i<=n;++i){
        h=hi[i];
        ++w;
        ret=max(ret,(long long)h*w);
    }
    return ret;
}
int main(){
    setIO("rectangle");
    int T;
    read(T);
    while(T--){
        read(n);
        for(int i=1;i<=n;++i)
            read(hi[i]);
        write(cal(),'\n');
    }
    return 0;
}

确定小组

思路

• 考虑到构造是很困难的，那么不妨求一下可行的方案数，看是不是唯一的；
• 那么考虑递推，设$f(i)$为只满足前$i$个人的回答时的方案数，$ans(i)$为第$i$个人的回答；
• 那么对于每个$i$，我们向左找到$j$；
• 若$j$~$i$没有人回答记者的问题，那么我们可以认为$j$~$i$是一组的，则$f(i)+=f(j-1)$；
• 若第$j$个人回答了问题，而且$j+1$~$i$没有人回答，那么可以认为$i$所在的组有$ans(j)$人，继续向左，若回答都等于$ans(j)$，则可认为他们都是一组的。当$i-j+1=ans(j')$时，可认为$j$~$i$是一组的，那么$f(i)+=f(j-1)$；
• 若之前有人回答，是$ans(j')$，且$ans(j)\neq ans(j')$，那么$j+1$~$i$可认为是一组的，所以此时停止向左扫；
• 直接说有些不清楚，看代码应该就明白了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cstring>
#include <climits>
#include <algorithm>
using std::min;
const int MAXN=1005;
int n;
int ans[MAXN];
inline int lim(int x){return min(2,x);}
inline bool jud(){
    //f[i]=前i个人的方案数
    static int f[MAXN];
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;++i){
        for(int j=i,belong_cnt=0;j;--j){
            if(ans[j]){
                if(belong_cnt && belong_cnt!=ans[j])
                    break;
                else belong_cnt=ans[j];
            }
            if(!belong_cnt || i-j+1==belong_cnt)
                f[i]=lim(f[i]+f[j-1]);
        }
    }
    return f[n]==1;
}
int main(){
    setIO("group");
    int T;
    read(T);
    while(T--){
        read(n);
        for(int i=1;i<=n;++i)
            read(ans[i]);
        if(jud()) puts("1");
        else puts("0");
    }
    return 0;
}

华容道游戏

思路

• 显然BFS裸题，但是实现起来确实困难；
• 我们考虑将原有的滑块分成$0,1 \times 1,2 \times 2,1 \times 2,2 \times 1$这$5$种本质不同的；
• 那么状态可以按$8$进制压缩到long long里；
• 而搜索时，我们只从每种块的左上角进行操作，用一个方向数组验证即可；
• 之后，把这个块抠出来，枚举和它相邻的空格，用同一个方向数组验证，看相邻的那个空格周围的空格是否和这个块匹配，再把空格放进去，这样实现会简单些；
• 这个看代码应该是很易懂的。

代码

#include <cstdio>
#include <queue>
#include <set>
using std::queue;
using std::set;
const int MAXN=7,MAXTP=9,n=5,m=4;
int type[MAXTP];
struct Graph{
    static const int mod=7;
    int c[MAXN][MAXN];
    int* operator[] (int i){return c[i];}
    long long hash(){
        long long ret=0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j)
                ret=ret<<3|type[c[i][j]];
        }
        return ret;
    }
    long long zip(){
        long long ret=0;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j)
                ret=ret<<3|c[i][j];
        }
        return ret;
    }
    void unzip(long long a){
        for(int i=n;i;--i){
            for(int j=m;j;--j){
                c[i][j]=a&mod;
                a>>=3;
            }
        }
    }
}G;
inline bool win(Graph &G){
    return G[5][2]==2 && G[5][3]==2;
}
inline int BFS(){
    static int dirx[]={0,1,0,-1},diry[]={1,0,-1,0};
    static int judx[5][4]={{},{0,0,0,0},{1,1,0,0},{1,1,0,0},{0,0,0,0}};
    static int judy[5][4]={{},{0,0,0,0},{1,0,1,0},{0,0,0,0},{1,0,1,0}};
    static queue<int> step;
    static queue<long long> que;
    static set<long long> se;
    if(win(G)) return 0;
    se.clear();
    while(que.size()) que.pop(),step.pop();
    se.insert(G.hash());
    que.push(G.zip()),step.push(0);
    bool can;
    int now;
    long long hs;
    while(que.size()){
        G.unzip(que.front());
        que.pop();
        now=step.front();
        step.pop();
        for(int i=1;i<=n;++i){
            for(int j=1,id,col;j<=m;++j){
                col=G[i][j],id=type[G[i][j]];
                if(id==0) continue;
                can=true;
                for(int k=0;k<4;++k)
                    can&=(G[i+judx[id][k]][j+judy[id][k]]==G[i][j]);
                if(!can) continue;
                for(int k=0;k<4;++k)
                    G[i+judx[id][k]][j+judy[id][k]]=0;
                for(int k=0,x,y;k<4;++k){
                    x=i+dirx[k],y=j+diry[k];
                    can=true;
                    for(int l=0;l<4;++l)
                        can&=(G[x+judx[id][l]][y+judy[id][l]]==0);
                    if(!can) continue;
                    for(int l=0;l<4;++l)
                        G[x+judx[id][l]][y+judy[id][l]]=col;
                    if(win(G)) return now+1;
                    hs=G.hash();
                    if(!se.count(hs)){
                        que.push(G.zip());
                        se.insert(hs);
                        step.push(now+1);
                    }
                    for(int l=0;l<4;++l)
                        G[x+judx[id][l]][y+judy[id][l]]=0;
                }
                for(int k=0;k<4;++k)
                    G[i+judx[id][k]][j+judy[id][k]]=col;
            }
        }
    }
    return -1;
}
inline void prepare(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(G[i][j]>=3){
                if(G[i-1][j]==G[i][j] || G[i+1][j]==G[i][j])
                    type[G[i][j]]=3;
                else if(G[i][j-1]==G[i][j] || G[i][j+1]==G[i][j])
                    type[G[i][j]]=4;
            }
            else type[G[i][j]]=G[i][j];
        }
    }
}
int main(){
    freopen("huarong.in","r",stdin);
    freopen("huarong.out","w",stdout);
    for(int i=0,lim=n+1,tmp=m+1;i<=lim;++i)
        G[i][0]=G[i][tmp]=-1;
    for(int i=0,lim=m+1,tmp=n+1;i<=lim;++i)
        G[0][i]=G[tmp][i]=-1;
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j)
                scanf("%d",&G[i][j]);
        }
        prepare();
        printf("%d\n",BFS());
    }
    return 0;
}