AcWing 第 120 场周赛
AcWing 5146. 最大GCD
提示:可以通过给定样例观察一下 n和答案之间的关系。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t, x;
int main() {
cin >> t;
for(int i = 0; i < t; i++) {
cin >> x;
cout << x / 2 << endl;
}
return 0;
}
如果此题变为求最大$gcd$的$a,b$该如何思考呢? ($1≤a<b≤n $)
任意一个数$n$的所有因数一定不可能大于这个数的$\lfloor n/2 \rfloor$,那$n$的因子最大能取多大呢?我们可以分奇偶来考虑,偶数的情况一定为$n/2$,奇数的情况我们可以确定的是一定不会是$\lfloor n/2 \rfloor$,且要小于$\lfloor n/2 \rfloor$,故$b$一定要取最大的偶数,另一个数$a$也就很显然了就是b的最大因子,就能求出最大$gcd$
AcWing 5147. 数量
最开始以为是数位dp,做着做着发现可以用二进制解决,将1设为7,0设为4,分别枚举一下长度1到n是10的几次方的所有二进制排列即可快速枚举出答案,时间复杂度为O(2^10)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int st[10];
int check(int n) {
int cnt = 0;
while(n) {
n /= 10;
cnt++;
}
return cnt;
}
int get() {
int res = 0;
for(int l = 1; l <= check(n); l++) {
for(int i = 0; i < (1 << l); i++) {
memset(st, 0, sizeof st);
int cnt = 0;
int j = i;
while(j) {
if(j & 1) st[cnt] = 1;
j >>= 1;
cnt++;
}
int s = 0;
for(int k = 0; k < l; k++) {
if(st[k] == 1) s = s * 10 + 7;
else s = s * 10 + 4;
}
if(s <= n) res++;
}
}
return res;
}
int main() {
cin >> n;
cout << get() << endl;
return 0;
}
AcWing 5148. 字符串匹配
第三题要先保证所有能完美匹配的字符都完美匹配,最后再来进行普通匹配
在用map的erase来优化时间(删除匹配完成后字符个数为0的情况的键值对)但一直报错,最后发现不用erase就能ac(注释代码加上会报错)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int good, ok;
map<char, int> mp1, mp2;
string s, t;
int main() {
cin >> s >> t;
for(auto x : s) mp1[x]++;
for(auto x : t) mp2[x]++;
for(auto [k, v] : mp1) {
if(mp2.find(k) != mp2.end()) {
int t = min(v, mp2[k]);
good += t;
mp2[k] -= t;
mp1[k] -= t;
// if(mp1[k] == 0) mp1.erase(k);
// if(mp2[k] == 0) mp2.erase(k);
}
}
for(auto [k, v] : mp1) {
if(islower(k)) {
char c = toupper(k);
if(mp2.find(c) != mp2.end()) {
int t = min(v, mp2[c]);
ok += t;
}
}
else {
char c = tolower(k);
if(mp2.find(c) != mp2.end()) {
int t = min(v, mp2[c]);
ok += t;
}
}
}
cout << good << " " << ok << endl;
return 0;
}