A.
签到题:思路为:所求答案 = 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
思路一:用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; } }
未完待续。。。