x星球的钞票的面额只有：100元，5元，2元，1元，共4种。 小明去x星旅游，他手里只有2张100元的x星币，太不方便，恰好路过x星银行就去换零钱。 小明有点强迫症，他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍， 剩下的当然都是5元面额的。
银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？ （5元，2元，1元面额的必须都有，不能是0）
水题，直接暴力，最好手动验算一下，稳
#include<iostream> using namespace std; int main(){ for(int i=1;i<=200;i++){ int j=10*i; int k=(200-i-2*j)/5; if(k>0&&(200-i-2*j)%5==0){ cout<<"i:"<<i<<" j:"<<j<<" k:"<<k<<endl; cout<<"i+j+k:"<<i+j+k<<endl; } } return 0; }答案:74
x星球的盛大节日为增加气氛，用30台机光器一字排开，向太空中打出光柱。 安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！ 国王很想知道，在4目前这种bug存在的情况下，一共能打出多少种激光效果？
显然，如果只有3台机器，一共可以成5种样式，即： 全都关上（sorry, 此时无声胜有声，这也算一种） 开一台，共3种 开两台，只1种
30台就不好算了，国王只好请你帮忙了。
要求提交一个整数，表示30台激光器能形成的样式种数。
很多大神都用BFS做的此题，但一向数学风格的我第一眼看到这种题目，都想找规律，也即是归纳法 不难归纳出前4个灯的情况数 1:2 2:3 3:5 4:8 好敏感的数字，不正是斐波那契数列(此时便可大胆求出答案了，下面的分析只为求稳)，那么可以用dp的思想(或者就是个简单的数学题吧)来想这题 a[i]=a[i-1]+a[i-2]
现在有i台机器，那么其样式数可不可以由i-1和i-2台推出来呢？ 第i台激光器只有两种状态，开或者不开 1.不开，既然不开那么有没有这台机器都没什么影响了，也就想当于没有这台机器了此时的情况数自然就是a[i-1]了 2.开，那么第i-1台肯定不能开，同理第i-1台相当于没有，而第i台一定开着(i-1一定不开)，这两台机器不会再影响 到其他机器了，相当于第i和i-1台机器都不存在，那么此时的样式数就是a[i-2]了 综合以上两点，i台机器的情况数a[i]=a[i-1]+a[i-2] 其中a[1]=2 a[2]=3 求a[30]=?
#include<iostream> using namespace std; int main(){ int a[40]; a[1]=2,a[2]=3; for(int i=3;i<=31;i++){ a[i]=a[i-1]+a[i-2]; } cout<<a[30]<<endl; return 0; }答案:2178309
格雷码是以n位的二进制来表示数。 与普通的二进制表示不同的是，它要求相邻两个数字只能有1个数位不同。 首尾两个数字也要求只有1位之差。
有很多算法来生成格雷码。以下是较常见的一种： 从编码全0开始生成。 当产生第奇数个数时，只把当前数字最末位改变（0变1，1变0） 当产生第偶数个数时，先找到最右边的一个1，把它左边的数字改变。 用这个规则产生的4位格雷码序列如下： 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
以下是实现代码，仔细分析其中逻辑，并填写划线部分缺少的代码。
#include <stdio.h> void show(int a,int n) { int i; int msk = 1; for(i=0; i<n-1; i++) msk = msk << 1; for(i=0; i<n; i++){ printf((a & msk)? "1" : "0"); msk = msk >> 1; } printf("\n"); }
void f(int n) { int i; int num = 1; for(i=0; i<n; i++) num = num<<1; int a = 0; for(i=0; i<num; i++){ show(a,n); if(i%2==0){ a = a ^ 1; } else{ a = _________________________ ; //填空 } } }
int main() { f(4); return 0; }
本题要用到树状数组的lowbit函数，并且要知道底层如何实现，很简单 -a&a 详见:https://blog.csdn.net/hza419763578/article/details/86304818
要求填的是偶数个时如何将a的最右边一个1的左边一位取反然后重新赋值给a a&-a得到a最右边一个1及其后面的0组成的二进制数的十进制值，左移一位再与a本身异或就达到效果 如:a=4即a=0100 那么-a&a=100 (100<<1)=(1000) 1000^0100=1100 达到目的了
#include <stdio.h> //二进制方式输出a n位二进制形式 void show(int a,int n){ int i; int msk = 1; for(i=0; i<n-1; i++) msk = msk << 1;// msk=2^(n-1) n为4不变时每次都是1000 for(i=0; i<n; i++){ printf((a & msk)? "1" : "0");//每次n仅一位为1(由高到低) a只有对应位也为1时才返回非0 否则0 就是输出a的n位二进制形式 msk = msk >> 1; } printf("\n"); } void f(int n){ int i; int num = 1; for(i=0; i<n; i++) num = num<<1;//2^n int a = 0; for(i=0; i<num; i++){//n位则共2^n个格雷码序列 show(a,n);//打印第i个 就是a就是第i个格雷码的10进制数值 if(i%2==0){//下次输出的就是i+1 i偶数 i+1奇数 a = a ^ 1;//异或运算 ^0不变 ^1取反(1->0 0->1) 本行就是第奇数(i+1)个格雷码直接把当前数字最末位改变即可 }else{ a =a^((a&-a)<<1); //第偶数(i+1)个 先找到a的最右边的一个1，把它左边的数字改变 //学过树状数组知道lowbit函数的实现就好办了 -a&a就是最后一个1及其后面的0 //左移一位就是最右边一个1往左移一位(比如100->1000)，就是最右一个1的左边一位取反 } } } int main(){ f(4); //for(int i=0;i<16;i++) show(i,4);//验证show函数的作用是输出a的n位二进制形式 return 0; }答案:a^((a&-a)<<1)
小明买了块高端大气上档次的电子手表，他正准备调时间呢。 在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n 分钟。 大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 0 ，那么按一下按钮就会 变成 1，再按一次变成 2 。如果当前的数是 n - 1，按一次后会变成 0 。 作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多1，则要按 n - 1 次加一按钮才能调 回正确时间。 小明想，如果手表可以再添加一个按钮，表示把当前的数加 k 该多好啊…… 他想知道，如果有了这个 +k 按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。 注意，按 +k 按钮时，如果加k后数字超过n-1,则会对n取模。 比如，n=10, k=6 的时候，假设当前时间是0，连按2次 +k 按钮，则调为2。
「输入格式」 一行两个整数 n, k ，意义如题。
「输出格式」 一行一个整数 表示：按照最优策略按键，从一个时间调到另一个时间最多要按多少次。
「样例输入」 5 3
「样例输出」 2
「样例解释」 如果时间正确则按0次。否则要按的次数和操作系列之间的关系如下： 1：+1 2：+1, +1 3：+3 4：+3, +1
「数据范围」 对于 30% 的数据 0 < k < n <= 5 对于 60% 的数据 0 < k < n <= 100 对于 100% 的数据 0 < k < n <= 100000
资源约定： 峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms
本题个人感觉，要么是n%k+n/k-1 要么是n/k-1+(k-1) 要么是k-1 n%k>0 差为n-1: (n%k-1)+n/k 或者差为n/k*k-1： 此时为:n/k-1+(k-1) n%k==0 差为n-1: (n/k-1)+(k-1)
每次都有可能:k较大 差为k-1: k-1 比如:6 5
#include<iostream> #include<algorithm> using namespace std; int main(){ int n,k; cin>>n>>k; cout<<max(max(n/k-1+k-1,n%k+n/k-1),k-1)<<endl; return 0; }很慌，就这几行代码，然而果然不行。。。比如10 9 会输出8 然而0~8其实按两次+9即可 18=8。问题就来了，最后剩<k这么多要调时到底是k次+1还是多次+k呢？
改进一下：（还是有bug 用例：50 12）
#include<iostream> #include<algorithm> using namespace std; int n,k; int Time(int i){ int d=n-k; return min(i,n/k-1+(n-i)%d+(n-i)/d); } int main(){ cin>>n>>k; int m=-1; for(int i=1;i<k;i++){ int x=Time(i); if(m<x) m=x; } cout<<max(max(n/k-1+Time(k-1),Time(n%k)+n/k-1),m)<<endl; return 0; }分析得好乱。。云里雾里，不知道还有没有坑，就这么找坑填坑。。浪费时间还不一定对。。。算了，老老实实BFS吧，本题若是想到如何BFS即n层到第n+1层怎么走。。其实也很简单了。。。。
BFS代码 :
初始化a[]={0} a[0]=0第一个入队 然后只要a[Top+1<n]和a[(Top+k)%n]==0（等于0表示未入队） 其值为a[Top]+1 然后入队
也即每次至多入队两个，每走到下一层最多入队两个(按下1和按下k)
#include<iostream> #include<queue> using namespace std; int n,k,a[100010]={0}; int BFS(){ queue<int> q; q.push(0); int Max=0; while(!q.empty()){ int Top=q.front(); q.pop(); if(Max<a[Top]) Max=a[Top]; if(Top+1<=n-1&&a[Top+1]==0){ a[Top+1]=a[Top]+1; q.push(Top+1); } if(a[(Top+k)%n]==0){ //巧妙保证了 0~n-1 a[(Top+k)%n]=a[Top]+1; //%n别忘了 q.push(Top+k); } } return Max; } int main(){ cin>>n>>k; cout<<BFS()<<endl; return 0; }果然上面的公式法，50 12时就错了。还是BFS保险，不能投机取巧
本题陷阱在于多次+k可能比多次+1快 难点在于想到用BFS
第5题拿数据分吧。。第六题感觉唯一一份题解也不大靠谱，和暴搜40分钟的答案不一样。由于100000可以特判，运气好的话第6题可以拿40%的分，105*0.4=42分快比得上第四题全对了。。。第六题数据分也不少了。。
时间不够。。2017水题题解
对于16进制，我们使用字母A-F来表示10及以上的数字。 如法炮制，一直用到字母Z，就可以表示36进制。 36进制中，A表示10，Z表示35，AA表示370 你能算出 MANY 表示的数字用10进制表示是多少吗? 请提交一个整数，不要填写任何多余的内容（比如，说明文字）
#include<iostream> using namespace std; int toInt(char c){ return c-'A'+10; } int main(){ for(int i=0;i<=25;i++){ cout<<10+i<<":"<<char('A'+i)<<" "; if(i==0) cout<<endl; } cout<<endl; cout<<toInt('M')*36*36*36+toInt('A')*36*36+toInt('N')*36+toInt('Y')<<endl; return 0; }水题求稳，最好验算
答案:1040254
小明家的一面装饰墙原来是 3*10 的小方格。 现在手头有一批刚好能盖住2个小方格的长方形瓷砖。 瓷砖只有两种颜色：黄色和橙色。
小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。 小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。 （瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝） 显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】
但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
本题参考网上大佬的做法，发现答案五花八门，随便找找就找到了6个版本，答案分别是114434、101466、120302、28163、2310、105760然而114434这个答案的居多，于是参考了下这份代码，加了点注释，且改进了下(加了个判断是否没块都铺到了的判断，不过只要总块数是偶数个，就似乎并不影响答案)
#include<iostream> using namespace std; int n,m,ans=0; int a[6][20]={0};//数组定义大一点 n,m范围就是[1~4,1~18] 冗余就不用考虑越界了 //数组a的值含义 0越界值 -1未铺 1铺黄 2铺红 //判断(x,y)可能涉及的2*2连块是否颜色相同 bool judge(int x,int y){ //不要空想 纸上画画 求稳 int v=a[x][y]; if(v==a[x+1][y]&&v==a[x][y+1]&&v==a[x+1][y+1]) return false;//(x,y)做为左上 if(v==a[x][y+1]&&v==a[x-1][y]&&v==a[x-1][y+1]) return false;//(x,y)做为左下 if(v==a[x][y-1]&&v==a[x+1][y]&&v==a[x+1][y-1]) return false;//(x,y)做为右上 if(v==a[x][y-1]&&v==a[x-1][y]&&v==a[x-1][y-1]) return false;//(x,y)做为右下 return true; } //判断是否全部铺到 bool isPuAll(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]!=1&&a[i][j]!=2) return false;//未铺满 } } return true; } //从左到右 从上到下 遍历每一块 void dfs(int x,int y){ //遍历到最后一块了 肯定结束了 而且最后一块无论横着竖着都扑不了 一定被铺过了 if(x==n&&y==m){ if(isPuAll()) ans++;//全部都铺到才算是一种铺法 因为题目要求不能只铺一部分 return; } if(y>m){ dfs(x+1,1); return;//不能少 } //本块未铺 赶紧铺 if(a[x][y]==-1){ //横着铺 if(a[x][y+1]==-1){ //横铺黄 a[x][y]=1,a[x][y+1]=1; //judge千万别忘了 if(judge(x,y)) dfs(x,y+1);//铺好了 继续从左到右 从上到下 铺下一块 //回退 可以省略而直接被下面的赋值给覆盖 但是为了方便理解还是加上吧 a[x][y]=-1,a[x][y+1]=-1; //横铺红 a[x][y]=2,a[x][y+1]=2;//铺好了 铺好后要judge是否合法 if(judge(x,y)) dfs(x,y+1);//继续从左到右 从上到下 铺下一块 //回退 不可略 否则影响下面纵着铺 横纵交错完全可以啊 a[x][y]=-1,a[x][y+1]=-1; } //纵着铺 if(a[x+1][y]==-1){ //纵铺黄 a[x][y]=1,a[x+1][y]=1; if(judge(x,y)) dfs(x,y+1);//铺好了 继续从左到右 从上到下 铺下一块 //回退 可以省略而直接被下面的赋值给覆盖 但是为了方便理解还是加上吧 a[x][y]=-1,a[x+1][y]=-1; //纵铺红 a[x][y]=2,a[x+1][y]=2; if(judge(x,y)) dfs(x,y+1);//铺好了 继续从左到右 从上到下 铺下一块 //回退 不可略 否则影响后序铺法 (dfs(x+1,y+1之类的未改值 其实默认回退了) dfs的全局变量值一定要回退 a全局数组) a[x][y]=-1,a[x+1][y]=-1; } }else{//铺过了 直接尝试下一块 dfs(x,y+1); } } int main(){ n=3,m=10; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=-1; dfs(1,1); cout<<ans; return 0; }答案:114434
