Educational Codeforces Round 122 (Rated for Div. 2)

A
暴力

#include <bits/stdc++.h>
using namespace std;
int T, a, b;
int main() {
    cin >> T;
    while (T -- ) {
    	int n;
    	cin >> n;
    	vector<int> v;
    	while (n) {
    		v.push_back(n % 10);
    		n /= 10;
    	}
    	reverse(v.begin(), v.end());
    	int minn = 0x3f3f3f3f;
    	int res;
    	for (int i = 1; i <= 999; i ++ ) {
    		if (i % 7 == 0) {
    			int j = i;
    			vector<int> ans;
    			while (j) {
    				ans.push_back(j % 10);
    				j /= 10;
    			}
    			reverse(ans.begin(), ans.end());
    			if (ans.size() != v.size())	continue;
    			else {
    				int sum = 0;
    				for (int i = 0; i < v.size() ; i ++ )
    					if (v[i] != ans[i])
    						sum ++;
    				if (minn > sum)	{
    					res = i;
    					minn = sum;
    				}
    			}
    		}
    	}
    	cout << res << endl;
    }
    return 0;
}

B
简单思维

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T;
char s[N];
int main() {
    cin >> T;
    while (T -- ) {
    	cin >> s + 1;
    	int n = strlen(s + 1);
    	int sum0 = 0, sum1 = 0;
    	for (int i = 1; i <= n; i ++ ) {
    		if (s[i] == '0')	sum0 ++;
    		else sum1 ++;
    	}
    	if (sum0 == sum1) cout << sum0 - 1 << endl;
    	else cout << min(sum0, sum1) << endl;
    }
    return 0;
}

C
暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, hc, dc, hm, dm;
int k, w, a;
bool check(int b, int a)
{
	int t = hm / a + (hm % a == 0 ? 0 : 1);
	t --;
	if (b > dm * t)	return true;
	else return false;
}
signed main() {
    cin >> T;
    while (T -- ) {
    	cin >> hc >> dc;
    	cin >> hm >> dm;
    	cin >> k >> w >> a;
    	bool flag = 0;
    	for (int i = 0; i <= k; i ++ ) {
    		int _hc = i * a + hc;
    		int _dc = (k - i) * w + dc;
    		if (check(_hc, _dc)) {
    			flag = 1;
    			break;
    		}
    	}
    	if (flag)	cout << "YES" << endl;
    	else cout << "NO" << endl;
    }
    return 0;
}

D
发现最多的步骤不超过12次，所以可以直接01背包

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, n, k;
int a[N], b[N], c[N], f[1000010];
int main() {
    cin >> T;
    while (T -- ) {
    	cin >> n >> k;
    	for (int i = 1; i <= n; i ++ )	cin >> b[i];
    	for (int i = 1; i <= n; i ++ )	cin >> c[i];
    	function<void()> bfs = [&]() {
    		queue<int> q;
    		q.push(1);
    		unordered_map<int, int> st, d;
    		st[1] = 1;
    		d[1] = 0;
    		while (q.size()) {
    			auto t = q.front();
    			q.pop();
    			for (int i = 1; i <= t; i ++ ) {
    				if (!st.count(t + t / i) && t + t / i <= 1000) {
    					st[t + t / i] = 1;
    					d[t + t / i] = d[t] + 1;
    					q.push(t + t / i);
    				}
    			}
    		}
    		for (int i = 1; i <= n; i ++ ) 
    			a[i] = d[b[i]];
    	};
    	bfs();
    	int maxx = min(12 * n, k);
    	for (int i = 0; i <= maxx; i ++ )	f[i] = 0;
    	for (int i = 1; i <= n; i ++ ) 
    		for (int j = maxx; j >= a[i]; j -- ) 
    			f[j] = max(f[j], f[j - a[i]] + c[i]);
    	cout << f[maxx] << endl;
    }
    return 0;
}