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

正文之前

果然,上一篇文章结尾的预言果然一语成谶,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分往上,不做多想,还有四天,抓紧吧 !!

原文发布于微信公众号 - 工科狗和生物喵(gh_3507b116a1f8)

原文发表时间:2018-04-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

POJ1656

比较水的题,数据量暴力可破,但是你以为这样就结束了吗? 如果数据量大一点呢?不得不说,平时做题还是应该深入一点。 我是在写二维线段树找手感的时候做到这题的,顺势...

3068
来自专栏数据结构与算法

洛谷P2770 航空路线问题(费用流)

为了满足流量的限制,肯定会想到拆点,把每个点拆为两个,连流量为$1$,费用为$1$的边

1203
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

O(1)效率的表面模糊算法优化。

     很久没有写文章了,主要是最近一段时间没有以前那么多空暇空间,内存和CPU占用率一致都很高,应前几日群里网友的要求,今天发个表面模糊的小程序来找回之前...

2466
来自专栏Vamei实验室

纸上谈兵: 拓扑排序

《文明》是一款风靡20多年的回合制策略游戏,由Sid Meier开发。《文明》结构宏大,内容丰富,玩法多样,游戏性强,称得上是历史上最伟大的游戏。在文明中,你可...

2139
来自专栏阿凯的Excel

剔除两侧极值求平均

祝新的一年,各位表亲财源广进! 不知道过年期间是否安好哇! 请各位表亲好好断句,不要说错话! 像小编这种英俊潇洒风流倜傥的,身边难免有很多选择。 我可以允...

3332
来自专栏人工智能LeadAI

你听过算法也是可以贪心的吗?

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法...

3977
来自专栏PPV课数据科学社区

【学习】【R语言读书会】《R实战》读书笔记(第七章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

3299
来自专栏小樱的经验随笔

ACM训练计划

看完人家的博客,发现任重道远。。。 一位高手对我的建议: 一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的,主要时间...

49110
来自专栏owent

09年8月14日 ECUST ACM 练习赛总结

今天在湖南的OJ上做题,发现不到两小时,他服务器就挂了,但是发现他和POJ上的一些题一样而且是连号的,就到POJ上继续了,我们队出了6题。

791
来自专栏程序生活

贪心算法总结贪心算法基本思路算法实现实例分析参考

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

2K4

扫码关注云+社区

领取腾讯云代金券