算法日常练习4

2021年10月4日练习。

BJTU-ALGO 1355

火柴棒拼等式，经典的枚举问题。首先确定\(1111+1=1112\)共需要27根火柴，而题设说明\(n\leq24\)，故枚举范围可知。

#include <iostream>
using namespace std;
const int costs[10] = { 6,2,5,5,4,5,6,3,7,6 };
int cost(int n) {
	int c = 0;
	while (1) {
		c += costs[n % 10];
		n /= 10;
		if (n == 0) {
			break;
		}
	}
	return c;
}
int main() {
	int n, ans = 0;
	cin >> n;
	if (n >= 13) {
		int avail_matches = n - 4;//可用来做数字的只有这些火柴
		//至多20根 1111+1=1112 16+5=21
		for (int i = 0; i <= 1111; i++) {
			for (int j = 0; j <= 1111; j++) {
				if (cost(i) + cost(j) + cost(i + j) == avail_matches) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

平台上写的是要求读写文件，实际上是用 cout 进行流输出。

#include <iostream>
#include <fstream>
using namespace std;
const int costs[10] = { 6,2,5,5,4,5,6,3,7,6 };
int cost(int n){
	int c = 0;
	while (1) {
		c += costs[n % 10];
		n /= 10;
		if (n == 0) {
			break;
		}
	}
	return c;
}
int main() {
	int n, ans = 0;
	//read file
	fstream File;
	File.open("matches.in");
	if (!File) {
		cout << "打开失败" << endl;
		exit(-1);
	}
	File >> n;
	File.close();

	if (n >= 13) {
		int avail_matches = n - 4;//可用来做数字的只有这些火柴
		//至多20根 1111+1=1112 16+5=21
		for (int i = 0; i <= 1111; i++) {
			for (int j = 0; j <= 1111; j++) {
				if (cost(i) + cost(j) + cost(i + j) == avail_matches) {
					ans++;
				}
			}
		}
	}
	//write ans
	File.open("matches.out", ios::out);
	if (!File) {
		cout << "打开失败" << endl;
		exit(-1);
	}
	File << ans;
	File.close();
	return 0;
}

LintCode 1316

主要是检索超时，经提示应该是需要使用单调栈解决问题，明日再解...

class Solution {//超时
public:
    /**
     * @param arr: the arr
     * @return: the sum of the luck number
     */
    int luckNumber(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int l_min = 40001, r_max = 0;
            bool l_find = false, r_find = false;
            for (int j = 0; j <= i - 1; j++) {
                if (arr[j] > arr[i]) {
                    l_min = min(l_min, arr[j]);
                    l_find = true;
                }
            }
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[i]) {
                    r_max = max(r_max, arr[j]);
                    r_find = true;
                }
            }
            if (l_find && r_find && l_min % r_max == 0) {
                ans++;
            }
        }
        return ans;
    }
};

和为\(k\)

排序后利用双指针就能解决问题，时间复杂度为\(O(n\log n)\)。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n, k, ans = 0;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end(), less<int>());
	int i = 0, j = n - 1;
	while(i < j){
		if (v[i] + v[j] == k) {
			ans++;
			i++;//这个地方不好 20211007
			j--;
		}
		else if(v[i] + v[j] < k) {
			i++;
		}
		else {
			j--;
		}
	}
	cout << ans << endl;
	return 0;
}

BJTU-ALGO 1225

给定一个自然数\(M\)，求满足和恰为\(M\)的连续自然数的组数，要求从开始数排序从小到大依次输出起始数与最终数。实际上就是等差数列性质及分解因数。

#include <iostream>
#include <stack>//vector可以使用emplace_back()方法代替push_back()方法
using namespace std;
int main() {
	int M;
	cin >> M;
	stack<pair<int, int>> s;
	for (int i = 2; i * i <= 2 * M; i++) {
		if (2 * M % i == 0 && ((M * 2 / i + i) % 2 == 1)) {//
			s.push(pair<int, int>((2 * M / i - i + 1) / 2, (2 * M / i + i - 1) / 2));
		}
	}
	while (!s.empty()) {
		cout << s.top().first << ' ' << s.top().second << endl;
		s.pop();
	}
	return 0;
}

幸运数

定义幸运数为因数只有\(3,5,7\)的因数的正整数，输入一个正整数，求出小于这个数的幸运数个数。对数运算估计范围后暴力枚举+快速幂应该就可以解决。

#include <iostream>//有问题 20211007
#include <queue>
using namespace std;
unsigned long long fast_pow(unsigned long long x, unsigned long long y) {//快速幂，学学位运算
	unsigned long long ans = 1;
	while (y) {
		if (y & 1) {
			ans *= x;
		}
		x *= x;
		y >>= 1;
	}
	return ans;
}
int main() {
	int ans = 0;
	//const unsigned long long lim = 1000000000000;
	unsigned long long lim;
	cin >> lim;
	for (int i = 0; i <= 26; i++) {
		for (int j = 0; j <= 18; j++) {
			for (int k = 0; k <= 15; k++) {
				if(fast_pow(3,i) * fast_pow(5, j) * fast_pow(7, k) < lim){
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}