Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

A.

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

 

 签到题:思路为:所求答案 = 9 * (字符长度 - 1) + 最高位数 +(- 1)//通过判断语言确定是否需要再减个一 如果a****** > *******则需要加一反之不需要

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    int main () {
    	ll t;
    	cin >> t;
    	while(t--) {
    		ll ans;
    		ll temp = 0;
    		string num;
    		cin >> num;
    		ans = 9*(num.size() - 1) + num[0] - '0';
    		for (int i = 1; i < num.size(); ++i) {
    			if(num[i] < num[i - 1]) {
    				temp = 1;
    			}
    			if(num[i] > num[i - 1]) {
    				break;
    			}
    		}
    		ans -= temp;
    		cout << ans << endl;
    	}
    }

 B

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

思路一:用vector去重(错误)被T成狗

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    std::vector<char> v;
    int main () {
    	
    	ll t;
    	cin >> t;
    	while(t--) {
    		int num;
    		ll temp = 0;
    		std::vector<ll> a;
    		cin >> num;
    		for (int i = 0; i < num; i++) {
    			cin >> temp;
    			if(!(temp & 1))
    				a.push_back(temp);
    		}
    		ll ans = 0;
    		sort(a.begin(), a.end());
    		a.erase(unique(a.begin(), a.end()), a.end());
     
    		while(a.size()) {
    			a[a.size()-1] >>= 1;
    			//cout << "!" <<a[a.size()-1] << endl;
    			if(a[a.size()-1] & 1) {
    				a.erase(a.begin() + a.size() - 1);
    			}
    			ans++;
    			sort(a.begin(), a.end());
    			a.erase(unique(a.begin(), a.end()), a.end());
    			
    		}
    		cout << ans << endl;
    	}
    }

 正确思路:用队列进行处理,先筛出偶数进行处理,每次从大值除2进行是最快的,为奇数时剔除。每次操作进行去重。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
	priority_queue <ll> q;
	ll t;
	cin >> t;
	while(t--) {
		ll num;
		cin >> num;
		for(int i = 0; i < num; ++i) {
			ll temp;
			cin >> temp;
			if(!(temp & 1)) {
				q.push(temp);
			}		
		}
		ll ans = 0;
		ll temp; ll cur;
		if(!q.empty()) {
			ans++;
			temp = q.top();
			q.pop();
			if(!((temp / 2) & 1)){
				q.push(temp / 2);
			}
		}
		
		while(!q.empty()) {

			cur = q.top();
			q.pop();
			if(cur == temp){
				continue;
			}
			else {
				// cout << "ans:" << ans << endl;
				// cout << "cur:" << cur << endl;
				temp = cur;
				ans++;
				if(!((temp / 2) & 1)){
					q.push(temp / 2);
				}
			}
		}
		cout << ans << endl;
	}
}

 未完待续。。。

上一篇:[LeetCode] 606. Construct String from Binary Tree


下一篇:链栈(C++实现)