第三周測驗-有解無憂

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;
	}
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275078.html

標籤：其他

上一篇：A*演算法

下一篇：2021年春季ACM訓練賽第5場