第三周测试

7-1 数9

数论题
题目求有多少个9的倍数或者尾数为9的数。数据范围是1e9，所以肯定不能枚举判断。简单观察可以发现，9的倍数的个数是n/9。尾数为9的个数：当个位数字小于9时为n/10，个位数字等于9时为n/10+1。将这两者个数相加，然后再减去既是尾数为9也是9的倍数的个数即为答案。通过观察发现两种情况都符合的数是：个位数字是1的数再乘以9的值，即1 * 9， 11 * 9，21 * 9，31 * 9… 成等差数列，所以前n项符合这种数的个数为：(n-9)/90+1。代码如下：

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

int main(){
	int n, ans = 0;
	cin >> n; 
	ans = n/9 + n/10 - ((n-9)/90)-1;
	if(n%10 >= 9) ans++;
	cout << ans;
}

7-2 找零钱***

dfs
可以通过dfs来枚举所有可能性，最后找能满足条件的选择。
按顺序选择，每次可以选择使用这张钱，或者不使用这张钱，直到枚举完所有钱，或者找到一个符合条件的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n, m, arr[N], f = 0;

// 输出结果
void print(vector<int> ans){
	for(int i = 0; i < ans.size(); i++){
		if(i != 0) cout << " ";
		cout << ans[i];
	}
	cout << endl;	
}
// c:枚举到第c张钱， v：还差多少钱找齐  ans：存储答案数组
void dfs(int c, int v, vector<int> ans){
	if(c > n) return;  // 遍历完
	// 找到一种找零方式
	if(v == 0) {
		f = 1; print(ans); 
		return;
	}
	// 选择第c张面值的钱
	if(arr[c] <= v){
		ans.push_back(arr[c]);
		dfs(c+1, v-arr[c], ans);
		ans.pop_back();
	}
	// 不选择第c张面值的钱
	dfs(c+1, v, ans);
}

int main(){
	cin >> n;
	for(int i = 0; i<n; i++) cin >> arr[i];
	cin >> m;
	vector<int> ans;
	dfs(0, m, ans);
	if(f == 0) cout << "None";
}

7-3 取石子(一)

博弈
简单的博弈论可以通过分析先手的必胜态与必败态来寻找规律。
本题可以发现轮到某一人时必胜的数1, 2，必败的数是3。然后继续往后面推：
当有4个的时候先手可以取一个石子让后手必败， 即4是必胜的
当有5个的时候先手可以取两个石子让后手必败， 即5是必胜的
当有6个的时候先手无论是取一个还是两个，都会让对方变成必胜的。
…
这时我们就能找到规律了，石子是3的倍数的时候先手必败，其余情况，先手必胜。代码如下：

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

int main(){
	int n; cin >> n;
	if(n%3 == 0) cout << "Mary";
	else cout << "Tom";
}

7-4 666

dfs
这个题与去年蓝桥杯国赛的一道填空题有点像。把每个点都设为起点进行dfs，寻找连续的3个大于等于6的个数，将搜到的结果保存到对应的数组中。最后输出即可。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int d[4] = {1,-1,0,0}, f[4] = {0,0,1,-1};
int arr[N][N], dis[N][N], ans[N][N], m, n, cnt;

void dfs(int c, int x, int y){
	if(c == 3){
		cnt++; return;
	}
	dis[x][y] = 1;
	for(int i=0; i<4; i++){
		int fx = x+d[i], fy = y+f[i];
		if(fx>0 && fx<=n && fy>0 && fy<=m && arr[fx][fy]>=6 && dis[fx][fy]==0){
			dis[fx][fy] = 1;
			dfs(c+1,fx,fy);
			dis[fx][fy] = 0;
		}
	}
}

int main(){
	cin >> m >> n;
	for(int i = 1; i <= m; i++){
	 	for(int j = 1; j<=n; j++){
	 		cin >> arr[i][j];
		}
	}
	for(int i = 1; i <= m; i++){
	 	for(int j = 1; j<=n; j++){
	 		cnt = 0; memset(dis,0,sizeof(dis));
	 		if(arr[i][j] >= 6) dfs(1,i,j);
	 		ans[i][j] = cnt;
		}
	}
	int sum = 0;
	for(int i = 1; i <= m; i++){
	 	for(int j = 1; j<=n; j++){
	 		if(j!=1) cout << " ";
	 		cout << ans[i][j];
	 		sum += ans[i][j];
		}
		cout << endl;
	}
	cout << sum;
}

7-5 列车调度

最长上升子序列
简单观察可以看出，每个平行铁轨的里的列车顺序都必须是数字大的在前，数字小的在后，求需要最少的平行轨道，可以转化为求这个序列的最长上升子序列(跟拦截导弹那道题基本一样)，数据规模是1e5，所以不能用动态规划求（n^2复杂度），需要用二分法求（nlongn复杂度）。代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int arr[N], lis[N], len = 0, n;

int find(int x){
	int l = 0, r = len;
	while(l < r){
		int mid = (l+r)/2;
		if(lis[mid] > x) r = mid;
		else l = mid+1;
	}
	return (l+r)/2;
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> arr[i];
	for(int i = 0; i < n; i++){
		if(arr[i] > lis[len]){
			lis[++len] = arr[i];
		}
		else lis[find(arr[i])] = arr[i];
	}
	cout << len;
}

7-6 N阶楼梯上楼问题

记忆化递归，动态规划
一次只能上一级或者2级，所以上第2层的楼梯时，只能由第0层或第1层上去。
所以上第3层的楼梯时，只能由第1层或第2层上去。
所以得到递归公式dfs(n) = dfs(n-1)+dfs(n-2);
由于递归复杂度太高，直接写肯定会超时。可以用数组储存之前算出的结果，不需要重复计算。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[50];
ll dfs(int n){
	if(arr[n]) return arr[n];
	if(n == 1 || n == 0) return 1;
	else return arr[n] = dfs(n-1)+dfs(n-2);
}
int main(){
	int n;
	cin >> n;
	cout << dfs(n);
}

记忆化递归都可以转化为动态规划。状态转移方程是dp[i] = dp[i-1]+dp[i-2];代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[50];
int main(){
	int n;
	cin >> n;
	dp[0] = 1, dp[1] = 1;
	for(int i = 2; i <= n; i++){
		dp[i] = dp[i-1]+dp[i-2];
	}
	cout << dp[n];
}

7-7 词典

数据结构，散列表
使用c++中的map，或者unordered_map，可以非常容易的解决。一个单词对应一个外语单词。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map <string, string> mp;
int main(){
	int n, m;
	string a, b;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a >> b;
		mp[b] = a;
	}
	for(int i = 0; i < m; i++){
		cin >> a;
		if(mp.find(a)!=mp.end()) cout << mp[a] <<endl;
		else cout << "eh" << endl;
	}
}

7-8 最短路径

bfs
简单的bfs，根据输入格式，可以用邻接表储存边，能够节省空间，不过数据规模不大，直接使用邻接矩阵也可以。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 15;
vector<int>arr[15]; // 邻接表储存边的信息

int bfs(int a, int b){
	if(a == b) return 0;
	int dis[N] ={0};
	queue<pair<int, int>> q;
	q.push(make_pair(a,0));
	dis[a] = 1;
	while(!q.empty()){
		auto t = q.front(); q.pop();
		int t1 = t.first, t2 = t.second;
		for(int i = 0; i < arr[t1].size(); i++){
			if(arr[t1][i] == b) return t2+1;
			if(dis[arr[t1][i]] == 0){
				q.push(make_pair(arr[t1][i], t2+1));
				dis[arr[t1][i]] = 1;	
			}
		}
	}
	return -1;
}

int main(){
	int n, e, a, b;
	cin >> n >> e;
	for(int i = 0; i<e; i++){
		cin >> a >> b;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	cin >> a >> b;
	int ans = bfs(a,b);
	if(ans == -1) printf("There is no path between %d and %d.",a,b);
	else printf("The length of the shortest path between %d and %d is %d.",a,b,ans);
}

7-9 AC Me

字符串
getline读取一行字符串，然后统计就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[200];
int main(){
	string str;
	while(getline(cin,str)){
		memset(arr,0,sizeof(arr));
		for(int i = 0; i < str.size(); i++){
			arr[str[i]]++;
		}
		for(int i = 'a'; i<='z'; i++){
			printf("%c:%d\n",i,arr[i]);
		}
	}
}

7-10 点钞

数据范围是1e3，用一个数组记录数字之前是否出现过，没出现过就输出这个数，并标记，出现过就输出*。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[1005];
int main(){
	int n, a;
	cin >> n;
	for(int i = 0; i<n; i++){
		cin >> a;
		if(i!=0) cout << " ";		
		if(arr[a]) cout << "*";
		else cout << a;
		arr[a] = 1;
	}
}