【计算机本科补全计划】CCF计算机职业资格认证 2016-04-1/2(俄罗斯方块)详解

用户1687088

发布于 2018-05-07 17:19:42

7710

发布于 2018-05-07 17:19:42

正文之前

果然，上一篇文章结尾的预言果然一语成谶，2016-09-4我果然没做出来。没错，昨晚到现在都没有做出来，当然，也是我做了一晚上心灰意冷，然后去欺负本文的CCF 2016 - 04 去了 but 这一套题目的第二题就难?哭我，最后还是看了答案优化了下数据结构我在刚刚花了十几分钟改进才成功的！！

正文

1、折点记数

试题编号：	201604-1
试题名称：	折点计数
时间限制：	11.0s
内存限制：	256.0MB

问题描述
给定n个整数表示一个商店连续n天的销售量。如果某天之前销售量在增长，而后一天销售量减少，则称这一天为折点，反过来如果之前销售量减少而后一天销售量增长，也称这一天为折点。其他的天都不是折点。如下图中，第3天和第6天是折点。


给定n个整数a1, a2, …, an表示销售量，请计算出这些天总共有多少个折点。
为了减少歧义，我们给定的数据保证：在这n天中相邻两天的销售量总是不同的，即:
ai-1≠ai。注意，如果两天不相邻，销售量可能相同。

问题描述

给定n个整数表示一个商店连续n天的销售量。如果某天之前销售量在增长，而后一天销售量减少，则称这一天为折点，反过来如果之前销售量减少而后一天销售量增长，也称这一天为折点。其他的天都不是折点。如下图中，第3天和第6天是折点。给定n个整数a1, a2, …, an表示销售量，请计算出这些天总共有多少个折点。为了减少歧义，我们给定的数据保证：在这n天中相邻两天的销售量总是不同的，即: ai-1≠ai。注意，如果两天不相邻，销售量可能相同。

输入格式　　输入的第一行包含一个整数n。　　第二行包含n个整数，用空格分隔，分别表示 a1, a2, …, an。
输出格式　　输出一个整数，表示折点出现的数量。
样例输入 7 5 4 1 2 3 6 4
样例输出 2

评测用例规模与约定　　所有评测用例满足：1 ≤ n ≤ 1000，每天的销售量是不超过10000的非负整数。

#include<iostream>
using namespace std;

 //这一题没啥好讲的，很简单，昨天才知道CCF以前满分500分，100分就算合格，也就是说如果我去考试，这个题目就够我及格嘞。果然跟以前那些妖艳贱货hen不一样~~

int main()
{
    int a,b,c;  //最骚的还是这里，记得不要去存储输入的那些数
//因为只对相邻的三个数做比较，所以完全可以动态存储，视作一个滑动的窗口来看。那就很美了
    int n,count;
    cin>>n;
    cin>>a>>b;
    int N=n-2;
    while(N--)
    {
        cin>>c;
//标准答案用的是一个三目运算符，我本来也打算这么用的，但是想到貌似乘法也没多大的耗费，就干脆这么用了吧！~
        if((a-b)*(b-c)<0) 
            ++count;
        a=b;
        b=c;
    }
    cout<<count<<endl;
    return 0;
}

输出结果：

Last login: Wed Nov 29 15:12:25 on ttys000
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/CCF_2016_04_1 ; exit;
700
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 5 4 1 2 3 6 4 
398
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[进程已完成]

2、俄罗斯方块

试题编号：	201604-2
试题名称：	俄罗斯方块
时间限制：	1.0s
内存限制：	256.0MB

问题描述　　俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。　　游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。　　在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。　　具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。
输入格式　　输入的前15行包含初始的方格图，每行包含10个数字，相邻的数字用空格分隔。如果一个数字是0，表示对应的方格中没有方块，如果数字是1，则表示初始的时候有方块。输入保证前4行中的数字都是0。　　输入的第16至第19行包含新加入的板块的形状，每行包含4个数字，组成了板块图案，同样0表示没方块，1表示有方块。输入保证板块的图案中正好包含4个方块，且4个方块是连在一起的（准确的说，4个方块是四连通的，即给定的板块是俄罗斯方块的标准板块）。　　第20行包含一个1到7之间的整数，表示板块图案最左边开始的时候是在方格图的哪一列中。注意，这里的板块图案指的是16至19行所输入的板块图案，如果板块图案的最左边一列全是0，则它的左边和实际所表示的板块的左边是不一致的（见样例）
输出格式　　输出15行，每行10个数字，相邻的数字之间用一个空格分隔，表示板块下落后的方格图。注意，你不需要处理最终的消行。样例输入 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 3
样例输出 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0

我的代码：

// Failed Program  By looking at the general answer, I finally Finish it! Good Boy!

#include<iostream>
using namespace std;

int main()
{
    int a[16][10];  //在最后一横排进行置 1，防止因为最下层为0导致的穿透棋盘。
    int b[4][4]; 
    int zuo[4][2];  //用于存储四个1所在的坐标。
    int s=0;  用于在输入的时候提取坐标输入 4*2 数组
    int column,x;  
    for(int i=0;i<15;++i)
        for(int j=0;j<10;++j)
        {
            cin>>x;
            a[i][j]=x;
        }
    for(int i;i<10;++i)
        a[15][i]=1;
    for(int i=0;i<4;++i)
        for(int j=0;j<4;++j)
        {
            cin>>x;
            b[i][j]=x;
            if(x==1)  // 就是此处，用于记录四个坐标，我一开始思路因为少了一这一步，所以很尴尬！
            {
                zuo[s][0]=i;
                zuo[s][1]=j;
                ++s;
            }
        }
    cin>>column;
    bool flag=false;  //设计停止标志位。用于打断循环所用。
    int stopraw=1;
    for(int i=0;i<15;i++)
    {
        if(flag)
            break;
        else
        {
            for(int j=0 ;j<4;++j)
            {
                if(a[stopraw+zuo[j][0]][column+zuo[j][1]-1]==1)  //如果相对的位置上有1了。?，那么就退一步，并且置位flag进行循环退出。
                {
                    flag=true;
                    --stopraw;
                }
            }
            ++stopraw;
        }
    }
    --stopraw;
    for(int i=0;i<4;++i)  //置位原有的棋盘位置，刷新棋盘布局。
        a[stopraw+zuo[i][0]][column+zuo[i][1]-1]=1;

    for(int i=0;i<15;++i)
    {
        for(int j=0;j<10;++j)
        {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

运行结果：

Last login: Wed Nov 29 15:18:53 on ttys000
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/CCF_2016_04_2 ; exit;
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 0 0 1 0 0 0 0 
0 0 0 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 
0 0 0 0 0 0 1 0 0 0 
1 1 1 0 0 0 1 1 1 1 
0 0 0 0 1 0 0 0 0 0 
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.

[进程已完成]

咱们再来看看CSDN的一个博客里面给出来的标准答案~

/* CCF201604-2 俄罗斯方块 */

#include <iostream>

const int ROW = 15;
const int COL = 10;
const int N = 4;

int board[ROW+1][COL];
int block[N][N];
struct {
    int row, col;
} coords[N];

using namespace std;

int main()
{
    int row, col;

    // 输入数据
    for(int i=0; i<ROW; i++)
        for(int j=0; j<COL; j++)
            cin >> board[i][j];
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> block[i][j];
    cin >> col;

    // 底边全放1
    for(int j=0; j<COL; j++)
        board[ROW][j] = 1;

    // 提取小方块坐标
    int k = 0;
    for(int i=N-1; i>=0; i--)
        for(int j=0; j<N; j++)
            if(block[i][j] == 1) {
                coords[k].row = i;
                coords[k].col = j;
                k++;
            }

    // 模拟小方块落下过程
    row = 1;
    col--;
    bool checkflag;
    for(;;) {
        checkflag = false;
        for(int i=0; i<N; i++)
            if(board[row + coords[i].row][col + coords[i].col] == 1) {
                checkflag = true;
                break;
            }
        if(checkflag)
            break;
        row++;
    }
    row--;

    // 合并小方块到方格
    for(int i=0; i<N; i++)
        board[row + coords[i].row][col + coords[i].col] = 1;

    // 输出结果
    for(int i=0; i<ROW; i++) {
        for(int j=0; j<COL; j++) {
            if(j != 0)
                cout << " ";
            cout << board[i][j];
        }
        cout << endl;
    }

    return 0;
}

不得不说我的短了一大截啊，主要收获的观念就是，在一开始输入4 * 4的矩阵的时候，因为系统限定了只要四个格子是1，所以完全可以可以提取出来四个1所在的位置，组成一个4 * 2的二维数组，然后在模拟下落过程中，不需要对当前4 * 4所在的棋盘（就是15 * 10的格子中的一个4 * 4 子集）进行全盘检索。只需要对4 * 2数组中所存储的坐标进行四点排查，如果四个点所在的棋盘坐标都没有1，那么就继续下落，如果有一个地方是1，就代表着已经碰到了。接触到了原先棋盘中的1，所以此时就需要退一步，--stopraw就是这一步，然后既然知道了stopraw，那么就可以把原来的存储在4 * 2数组中的相对坐标位置进行置1，完成本次下落。

正文之后

心灰意冷，原来当初老实说要我考280分。不是在低估我。。是真的我估计大部分人也就这个水平，现在只期望200分往上，不做多想，还有四天，抓紧吧！！

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-04-21，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

人工智能

ios

存储

本文分享自工科狗和生物喵微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度