果然,上一篇文章结尾的预言果然一语成谶,2016-09-4我果然没做出来。没错,昨晚到现在都没有做出来,当然,也是我做了一晚上心灰意冷,然后去欺负本文的CCF 2016 - 04 去了 but 这一套题目的第二题就难?哭我,最后还是看了答案优化了下数据结构我在刚刚花了十几分钟改进才成功的!!
试题编号: | 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。注意,如果两天不相邻,销售量可能相同。
评测用例规模与约定 所有评测用例满足: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.
[进程已完成]
试题编号: | 201604-2 |
---|---|
试题名称: | 俄罗斯方块 |
时间限制: | 1.0s |
内存限制: | 256.0MB |
我的代码:
// 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分往上,不做多想,还有四天,抓紧吧 !!