2020-2-6 蓝桥杯阶段模拟总结
排名：10
总人数：18
填空题：error 2
编程题：error 2
一句话：不理想！
比赛经验：最陌生的可以说是填空题，自己写一个程序，运行结果，然后填上，主要陌生的原因是你运行出来没有样例数据，你无法检查基本的对错，这是分阶段的，主要是搜索题目为主，这一次给我经验就是可能出现一些很离谱的数做填空的时候，比如振兴中华这个题目，一共4*5的矩阵，找路径数目，我给人填了个一万多，事后想想，确实不应该啊，确实是大了点啊，这个我觉得原因就是做题还是少了，写代码不稳啊，不能1A，再有就是比赛的时候太急了，急着去坐后面的，没有放平心态啊，再有就是有点大男子主义，觉得19级参赛有心理压力，觉得自己年纪比人家高，打不过人家话不好看，其实这是很不对的，大家都是在学习，学习就应该放下一切，不管什么年级性别群体地位，抛下这一切，放平心态，这一点我深刻检讨，以后绝对不会了。
对于搜索，这里再明确一下
搜索比较常用的就是DFS和BFS，这两个算法，BFS常用于最短路径问题，DFS常用于方法数问题，注意的是，我用的是常用，不是绝对的，比如下面给出的剪格子这个题，要求的是最小的块数，最小我们第一时间想到的是BFS，但是对于这个题来讲，BFS是找不全的，比如挖洞的这个情形，我们是选择外面这一圈，BFS是绝对不可能成环的，比如我们这个圈是逆时针走的，但在逆时针走的过程中，BFS同时也会顺时针走，这就不适合我们这个题，我们就选择DFS来做
下面是错题总结：
3.
标题: 振兴中华
小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）
从我做起振 12345
我做起振兴 23456
做起振兴中 34567
起振兴中华 45678
比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
要求跳过的路线刚好构成“从我做起振兴中华”这句话。
请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
答案是一个整数，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
思路：这个题刚开始的思路我想的是用dfs，然后走到第几步就是第几个字，但是明显是我疏忽大意草率了，我们注意的是，人家给的这个图很好，“从我做起振兴中华”在图中每个字的右边和下边都是这句话中这个字的下一个字，所以我们用dfs模拟，让dfs只往右或者下走
AC：
#include<cstdio>
#include<iostream>
using namespace std;
#define MAXN 7
int Next[2][2] = {{0,1},{1,0}};
int n = 4;
int m = 5;
int sum = 0;
void dfs(int x,int nowx,int nowy)
{
if(x == 8)
{
sum++;
}
else
{
for(int i = 0; i < 2; i++)
{
int nextx = nowx + Next[i][0];
int nexty = nowy + Next[i][1];
if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m)
{
dfs(x+1,nextx,nexty);
}
}
}
}
int main()
{
dfs(1,1,1);
cout<<sum<<endl;
return 0;
}
6.标题：三部排序
一般的排序有许多经典算法，如快速排序、希尔排序等。
但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。
比如，对一个整型数组中的数字进行分类排序：
使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!!
以下的程序实现了该目标。
其中x指向待排序的整型数组，len是数组的长度。
void sort3p(int* x, int len)
{
int p = 0;
int left = 0;
int right = len-1;
while(p<=right){
if(x[p]<0){
int t = x[left];
x[left] = x[p];
x[p] = t;
left++;
p++;
}
else if(x[p]>0){
int t = x[right];
x[right] = x[p];
x[p] = t;
right--;
}
else{
__________________________; //填空位置
}
}
}
如果给定数组：
25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0
则排序后为：
-3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25
请分析代码逻辑，并推测划线处的代码，通过网页提交
注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
思路：这个题在比赛的时候思路不清晰，写错了，现在在整理整理思路，他用的思想基本上是快排的思想，只是思想，实际上跟快排差距很大....
这个题的切入点主要就是这三个if-else，第一个if说的是如果p指针指的数是个负数就交换left和p所指的数，我们在这里可能有疑惑啊，跳过去不就行了吗，交换啥啊，毕竟是人家的代码嘛，慢慢看，第二个else是说，如果p指的是正数，我们就跟right指针的值交换，并且right指针左移，第三个if-else就是我们要填的了，根据前面的意思，必然是处理0的情况，对于p指的是正数的时候，无脑的与right进行交换，也就是说与0配合的是第一个if-else，我们在写第一个if——else的时候就提出过疑问，为什么判断是负数却要交换left和p呢，我觉得显示是在0的时候，p++，left不动，这样left指的是0，p指的是后面的数，如果有负数再交换，保持0在数列的中间
9.标题：带分数
100 可以表示为带分数的形式：100 = 3 + 69258 / 714
还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
例如：
用户输入：
100
程序输出：
11
再例如：
用户输入：
105
程序输出：
6
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
思路：全排列，然后枚举前面整数的位数，对剩余的位数进行假分数整合就行了，因为一共就9个数，顶多1e6，时间比较充裕，直接做就行了
AC
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
vector<int> number;
int main()
{
cin>>n;
int total = 0;
int sum = 0;
int temp = n;
while(temp>0)
{
temp/=10;
total++;
}
number.resize(9);
for(int i = 0; i < 9; i++)
{
number[i] = i+1;
}
do
{
for(int i = 1; i <= total; i++)
{
int sum1 = 0;
for(int j = 1; j <= i; j++)
{
sum1 = sum1*10 + number[j-1];
}
int part = 9-i;
for(int j = 1; j <= part/2; j++)
{
int h = part - j;
int sum2 = 0;
int sum3 = 0;
for(int a = i; a < i+h; a++)
{
sum2 = sum2*10 + number[a];
}
for(int b = i+h; b < 9; b++)
{
sum3 = sum3*10 + number[b];
}
if(sum2%sum3 == 0)
{
if(sum1 + sum2/sum3 == n) sum++;
}
}
}
}while(next_permutation(number.begin(),number.end()));
cout<<sum<<endl;
return 0;
}
10.标题：剪格子
如图p1.jpg所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0
程序输入输出格式要求：
程序先读入两个整数 m n 用空格分割 (m,n<10)
表示表格的宽度和高度
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000
程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。
例如：
用户输入：
3 3
10 1 52
20 30 1
1 2 3
则程序输出：
3
再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
则程序输出：
10
(参见p2.jpg)
资源约定：
峰值内存消耗 < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
思路：这个题求得是最少的模块数，第一反应是BFS，但是BFS不能成圈，正如上面经验总结的那样，得用DFS，也就是说看到题目之后不要激动，想想能不能办再上手，这样既快又准！加油
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define MAXN 15
bool book[MAXN][MAXN];
int group[MAXN][MAXN];
int Next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<int> result;
int n,m;
int sum = 0;
void dfs(int block,int now_value,int x,int y)
{
if(now_value>sum/2) return;
else if(now_value == sum/2)
{
result.push_back(block);
return;
}
else
{
book[x][y] = true;
for(int i = 0; i < 4; i++)
{
int nowx = x + Next[i][0];
int nowy = y + Next[i][1];
if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m&&!book[nowx][nowy])
{
//cout<<nowx<<" "<<nowy<<" "<<now_value<<endl;
dfs(block+1,now_value+group[nowx][nowy],nowx,nowy);
book[nowx][nowy] = false;
}
}
}
}
int main()
{
cin>>m>>n;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin>>group[i][j];
sum += group[i][j];
}
}
memset(book,0,sizeof(book));
dfs(1,group[1][1],1,1);
//cout<<"no"<<endl;///////////////////////////////////////////////
int minn = 0x3f3f3f;
for(int i = 0; i < result.size(); i++)
{
if(minn > result[i]) minn = result[i];
}
cout<<minn<<endl;
return 0;
}