A.换零钞

题目描述

$x$ 星球的钞票的面额只有： $100$ 元， $5$ 元， $2$ 元， $1$ 元，共 $4$ 种。

小明去 $x$ 星旅游，他手里只有 $2$ 张 $100$ 元的 $x$ 星币，太不方便，恰好路过 $x$ 星银行就去换零钱。

小明有点强迫症，他坚持要求 $200$ 元换出的零钞中 $2$ 元的张数刚好是 $1$ 元的张数的 $10$ 倍，剩下的当然都是 $5$ 元面额的。

银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？

（ $5$ 元， $2$ 元， $1$ 元面额的必须都有，不能是 $0$ ）

思路

这道题目是数学题目，设一元的张数是 $x$ ，两元的张数为 $10x$ ，五元的张数为 $\frac{\left(200-x-10x\:\cdot \:\:2\right)}{5}$

可以的到所有张数的函数表达式 $f\left(x\right)\:=\:\frac{\left(200-x-10x\:\cdot \:\:\:2\right)}{5}+11x$

进一步化简可以得： $f\left(x\right)\:=\:40+\frac{34x}{5}$

由于题目需要最小张数，且需要为整数，所以 $x=5$ 时， $f\left(x\right)$ 可以取的最小值 $74$

代码

#include<bits/stdc++.h>
using namespace std;

int main() {
    cout << 74 << endl;
    return 0;
}
复制代码

B.激光样式

题目描述

$x$ 星球的盛大节日为增加气氛，用 $30$ 台机光器一字排开，向太空中打出光柱。

安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！

国王很想知道，在目前这种 $bug$ 存在的情况下，一共能打出多少种激光效果？

显然，如果只有 $3$ 台机器，一共可以成 $5$ 种样式，即：

全都关上（ $sorry$ , 此时无声胜有声，这也算一种）

开一台，共 $3$ 种

开两台，只 $1$ 种

$30$ 台就不好算了，国王只好请你帮忙了。

思路

动态规划DP

用0表示激光灯灭
用1表示激光灯亮

一盏灯的时候可以是 $0$ ， $1$ 即灭或者亮；
两盏灯的时候可以是 $00$ ， $01$ ， $10$ （并排）
三盏灯的时候可以是 $000$ ， $010$ ， $100$ ， $001$ ， $101$ （并排）

因此可以看出三盏灯的样式种数是由两部分组成的，

第一部分就是，前面两盏灯不管亮不亮，第三盏灯都不亮
第二部分就是，第二盏灯灭的前提下，第三盏灯亮，而第二盏灯灭的样式种数等于只有一盏灯时候的样式种数。

$dp[i]$ 表示一共有 $i$ 盏灯时候的样式种类

可以得到DP初始条件: $dp\left[1\right]\:=\:2,\:dp\left[2\right]\:=\:3$

状态转移方程： $dp\left[i\right]\:=\:dp\left[i\:-\:1\right]\:+\:dp\left[i\:-\:2\right]\:\left(i\:\ge \:3\right)$

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int dp[31];
    dp[1] = 2;
    dp[2] = 3;
    for (int i = 3; i <= 30; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }   
    cout << dp[30] << endl;
    return 0;
}
复制代码

C.格雷码

题目描述

格雷码是以n位的二进制来表示数。

与普通的二进制表示不同的是，它要求相邻两个数字只能有1个数位不同。

首尾两个数字也要求只有1位之差。

有很多算法来生成格雷码。以下是较常见的一种：

从编码全0开始生成。

当产生第奇数个数时，只把当前数字最末位改变（0变1，1变0）

当产生第偶数个数时，先找到最右边的一个1，把它左边的数字改变。

用这个规则产生的4位格雷码序列如下：

思路

答案：a = a ^ ((a & (-a)) << 1); //填空

从前面的很明显可以看出，(a << 1) ^ a就可以了，但是后面从0111开始就不行了。

从下一个开始逆向推理 $0101\:XOR\:0111\:=\:0010$ 因此需要想办法把0111 变成 0010
0111 取其负数 1001 再 $XOR$ 即可得到 0010 带入其他奇数验证，成立。

代码

#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 = a ^ ((a & (-a)) << 1) ; //填空
		}
	}
}

int main()
{
	f(4);
	return 0;
}
复制代码

D.调手表

题目描述

小明买了块高端大气上档次的电子手表，他正准备调时间呢。

在 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$ ，意义如题。
$0 < k < n <= 100000$

输出

一行一个整数
表示：按照最优策略按键，从一个时间调到另一个时间最多要按多少次。

思路

动态规划DP

题目要求是最优策略，所以一定要求+i的时候，是最少次数的，每次只能+1或者+k，从一个时刻调整到另一个时刻，需要加上 $\left[0,\:n\:-\:1\right]$

$dp[i]$ 表示 $+i$ 需要的次数，默认只有一个 $+1$ 按钮，所以直接初始化 $dp[i] = i$ ;

其次需要初始化 $+k$ 的次数 $dp\left[i\right]\:=\:dp\left[i\:-\:k\right]\:+\:1$

状态转移方程式

$dp\left[i\right]\:=\:min\left(dp\left[\left(i\:+\:n\:-\:k\right)\:\%\:n\right]\:+\:1,\:dp\left[i\:-\:1\right]\:+\:1\right);$

代码

#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int main() {
    int n, k;
    cin >> n >> k;
    // 初始化dp初始状态
    for (int i = 0; i < n; i++) {
        dp[i] = i; // 初始化为多少分钟需要调整多少次，默认为一分钟调整一次；
    }
    for (int i = k; i < n; i += k) {
        dp[i] = dp[i - k] + 1; // 从0开始，每过k步 就+1
    }
    int sum = -1;
    while (1) { // 如果结果是收敛的，则停止循环。
        int now_sum = 0;
        for (int i = 1; i < n; i ++) {
            now_sum += dp[i];
            // 状态转移方程式
            dp[i] = min(dp[(i + n - k) % n] + 1, dp[i - 1] + 1);
        }
        if (now_sum == sum) break;
        sum = now_sum;
    }
    int ans = dp[0];
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}
复制代码