1.奖券数目
有些人很迷信数字，比如带“4”的数字，认为和“死”谐音，就觉得不吉利。
虽然这些说法纯属无稽之谈，但有时还要迎合大众的需求。某抽奖活动的奖券号码是5位数（10000-99999），要求其中不要出现带“4”的号码，主办单位请你计算一下，如果任何两张奖券不重号，最多可发出奖券多少张。
请提交该数字（一个整数），不要写任何多余的内容或说明性文字。
思路:枚举+判断
#include<bits/stdc++.h> using namespace std; int cnt; //52488 bool solve(int num){ while(num){ if(num % 10 == 4){ return false; } num /= 10; } return true; } int main() { for(int i = 10000; i <=99999; i++){ if(solve(i)){ cnt++; } } cout<<cnt<<endl; return 0; }
答案:52488
2.星系炸弹
在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。
每个炸弹都可以设定多少天之后爆炸。
比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。
有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。
请填写该日期，格式为 yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19
请严格按照格式书写。不能出现其它文字或符号。
思路:计算器,手算,程序都行
答案:2017-08-05
7.牌型种数
小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？
请填写该整数，不要填写任何多余的内容或说明文字。
法一 暴力求解
#include<bits/stdc++.h> using namespace std; int arr[13],total; int main() { for( arr[0] = 0; arr[0] <= 4; arr[0]++) for(arr[1] = 0; arr[1] <= 4; arr[1]++) for(arr[2] = 0; arr[2] <= 4; arr[2]++) for(arr[3] = 0; arr[3] <= 4; arr[3]++) for(arr[4] = 0; arr[4] <= 4; arr[4]++) for(arr[5] = 0; arr[5] <= 4; arr[5]++) for( arr[6] = 0; arr[6] <= 4; arr[6]++) for(arr[7] = 0; arr[7] <= 4; arr[7]++) for(arr[8] = 0; arr[8] <= 4; arr[8]++) for(arr[9] = 0; arr[9] <= 4; arr[9]++) for(arr[10] = 0; arr[10] <= 4; arr[10]++) for( arr[11] = 0; arr[11] <= 4; arr[11]++) for(arr[12] = 0; arr[12] <= 4; arr[12]++) { if(arr[0]+arr[1]+arr[2]+arr[3]+arr[4]+arr[5]+arr[6] +arr[7]+arr[8]+arr[9]+arr[10]+arr[11]+arr[12]==13) { total++; break; } } cout<<total<<endl; return 0; }
法二 DFS
相当于有13个桶，每个桶里面最大取4
从第一个桶开始取，取值0~4，达到数目13，跳出，达不到，判断是否越界。未越界，那么就接着搜索，从下一桶开始艘。
一共是52张牌，不算花色的话就是13种类型，我用0-12来编号。然后0~12个桶里面每个桶都有4张花色不同的牌。程序从第0号桶开始搜索，当前没有选取牌，所以此时选出牌的数量就是0。dfs()函数中的参数pos代表当前搜索到哪个桶，cnt表示已经选取出来的牌数。先不考虑递归出口。跳过dfs中两个if判断。num取得是4和13-cnt中的小值。因为当前桶还没有选取最多有4张牌。但是需要注意的是，假如搜到当前位置时选出来的牌数已经达到了11张，而我们每人只能够拿走13张牌，所以当前位置我们最多只能再选取两张。一个是2，一个是4，很明显，当前桶可取的数量一定会选取较小的数值当作实际容量。再下一个for循环中我们需要做的就是确定当前桶中要拿走的数量，一张一张拿，再去搜下一个位置。当我们搜下一个位置时发现我们手中的牌已经达到了13张，那么祝贺你，已经搜寻到了一种可行方案，总方案数sum++，然后return。如果当前牌数没有到达13张，但是搜寻的位置到了13号桶，对不起我家没有那么多桶（注意程序中是从0开始编号的），此刻直接返回上一个位置和牌数，搜寻下一个可行方案。
代码如下
#include<bits/stdc++.h> using namespace std; int total; //3598180 void dfs(int pos,int cnt) { if(cnt == 13){//判断是否已经找到了13张 total++; return; } if(pos == 13){//判断是否到了13这个桶的位置 ,这个桶没有,结束. return; } int num = min(13-cnt,4);//取最小值 这里边必须设成局部变量, 因为每个dfs都有一个 num,最后还得递归回去. for(int i = 0; i <=num; i++){ dfs(pos+1,cnt+i); } return;//为了符合dfs格式最好写上 } int main() { dfs(0,0); cout<<total<<endl; return 0; }
8.移动距离
X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3…
当排满一行时，从下一行相邻的楼往反方向排号。
比如：当小区排号宽度为6时，开始情形如下：
1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …
我们的问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动）
输入为3个整数w m n，空格分开，都在1到10000范围内
w为排号宽度，m,n为待计算的楼号。
要求输出一个整数，表示m n 两楼间最短移动距离。
例如：
用户输入：
6 8 2
则，程序应该输出：
4
再例如：
用户输入：
4 7 20
则，程序应该输出：
5
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms
思路
假设m楼的位置是(x1,y1),n楼的位置是(x2,y2),那么 min_dis = abs(x2-x1) + abs(y2 - y1);这样就把问题转换成了找n,m楼坐标.
方法一:模拟填充到max(n,m)
#include<iostream> #include<math.h> using namespace std; int w,m,n,cnt,x,y,x1,x2,y_1,y2,flag;//y1是个函数名,所以一定不要用这个命名啊. int main() { x = 1; y = 1; flag = 1; cin>>w>>m>>n; int maxRow = max(m,n); while(cnt++<=maxRow){ if(y==w+1){//当从左执行到最右边,转变方向 x++; y = w; flag = !flag; } if(y==0){//当从右执行到最左边,转变方向 x++; y = 1; flag = !flag; } if(cnt==m){ x1 = x; y_1 = y; } if(cnt==n){ x2 = x; y2 = y; } if(flag){//向右 y++; }else{//向左 y--; } } int result = abs(x1-x2)+abs(y_1-y2); cout<<result<<endl; return 0; }
下面是自己最初的代码,写的比较复杂但很困惑,运行竟然没过.有大佬能看懂的可以看看,帮忙指导下哪里写错了.
#include<bits/stdc++.h> using namespace std; const int maxsize = 10000; int map1[maxsize+10][maxsize+10],w,m,n,cnt,flag; int arr[2][2],index1 = 0; int main() { cin>>w>>m>>n; flag = 1; cnt = 1; for(int i = 1; i <= maxsize; i++) { if(index1 >= 2){ break; } if(flag){//从前往后 for(int j = 1; j <= w; j++){ if(cnt==m||cnt==n){ arr[index1][0] = i; arr[index1][1] = j; index1++; } map1[i][j]=cnt++; } flag=!flag; }else{ for(int j = w; j >= 1; j--){ if(cnt==m||cnt==n){ arr[index1][0] = i; arr[index1][1] = j; index1++; } map1[i][j] = cnt++; } flag=!flag; } } int result = abs(arr[0][0]-arr[1][0])+abs(arr[0][1]-arr[1][1]); cout<<result<<endl; return 0; }
