Acwing.第 120 场周赛
A最大GCD
给定一个正整数 n（n≥2），请你确定两个正整数 a,b，使得 1≤a<b≤n，且 gcd(a,b)尽可能大。
输出 gcd(a,b)的最大可能值。
gcd(a,b)指 a,b的最大公约数。
提示：可以通过给定样例观察一下 n和答案之间的关系。
输入格式
第一行包含整数 T，表示共有 T组测试数据。
每组数据占一行，包含一个正整数 n。
输出格式
每组数据输出一行结果，一个整数，表示 gcd(a,b) 的最大可能值。
数据范围
前 3个测试点满足 1≤T≤10。
所有测试点满足 1≤T≤100，2≤n≤106。
A思路：
都给提示了，直接看样例就可以了。
A代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n;
cin>>n;
cout<<n/2<<endl;
}
int main(){
int t;
cin>>t;
// t=1;
while(t--){
solve();
}
return 0;
}
B数量
给定一个正整数 n。
保证 n的十进制表示不含 4和 7以外的数字。
请你统计，[1,n]范围内一共有多少个正整数满足其十进制表示不含 4和 7以外的数字。
注意，统计时不要漏掉 n。
输入格式
一个正整数 n。
输出格式
一个整数，表示满足条件的正整数数量。
数据范围
前 3个测试点满足 1≤n≤100。
所有测试点满足 1≤n≤109。
B思路：
如果是单独的从1到n肯定是会超时的，因为n是109，但是我们可以把最后一位单独拿出来，也就是说这个题我们可以O(108)的时间复杂度解决。
B代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int check(int x){
while(x){
if(x%10!=4&&x%10!=7){
return 0;
}
x/=10;
}
return 1;
}
void solve(){
int n;
cin>>n;
int ans=0;
for(int i=0;i<=n/10;i++){
if(check(i)){
if(i*10+7<=n){
ans+=2;
}
else{
ans+=1;
}
}
}
cout<<ans<<endl;
return ;
}
int main(){
int t=1;
while(t--){
solve();
}
return 0;
}
C字符串匹配
给定两个由大小写字母构成的字符串 s,t。
保证字符串 t的长度不小于字符串 s的长度。
请你对字符串 t进行调整，调整方法为依次执行以下两步：
去掉字符串 t中的若干字符，使得字符串 t的长度等于字符串 s的长度。注意，如果字符串 t的长度原本就等于字符串 s的长度，则忽略这一步。
重新调整字符串 t中各个字符的位置顺序（也可以不做任何调整）。
对于每个位置 i（0≤i<|s|）：
如果 ti与 si完全相同，则称两字符串在位置 i上完美匹配。
如果 ti与 si字母相同但是大小写不同（例如 a 和 A、b 和 B 等等），则称两字符串在位置 i上普通匹配。
如果以上均不满足，则称两字符串在位置 i上不匹配。
我们希望，经过调整后的字符串 t在与字符串 s进行匹配时：
完美匹配的位置尽可能多。
在满足上一条的前提下，普通匹配的位置尽可能多。
请你找到一种最佳调整方案，并输出在最佳方案中，两字符串的完美匹配的位置数量以及普通匹配的位置数量。
输入格式
第一行包含一个由大小写字母构成的字符串 s。
第二行包含一个由大小写字母构成的字符串 t。
输出格式
一行包含两个用空格隔开的数，分别表示完美匹配的位置数量和普通匹配的位置数量。
C思路：
一看到题就知道使用map来做，因为可以调整位置，所以直接贪心优先考虑完美匹配，然后是普通匹配，但是如果我们需要减去的长度不够的话，优先减去普通匹配里的个数，当普通匹配的个数不够在考虑完美匹配，根据这个思路模拟一下就可以了。
C代码：
我之前的代码找不到了，再写发现竟然没写对，看看大佬的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s,t;
map<char,int> mps,mpt;
int a,b;
char bianhuan(char c)
{
if(c<='Z' && c>='A')
{
c = c+32;
}
else c = c-32;
return c;
}
int main(){
cin>>s>>t;
for(int i =0;i<s.size();++i)mps[s[i]]++;
for(int i =0;i<t.size();++i)mpt[t[i]]++;
for(auto it:mps)
{
//完美匹配
char c = it.first;
int v = it.second;
if(mpt[c] >= v)
{
// 完全完美匹配
a += v;
mpt[c] -= v;
mps[c] = 0;
}
else
{
// 部分完美匹配
a += mpt[c];
mps[c] -= mpt[c];
mpt[c] = 0;
}
}
for(auto it:mps)
{
//部分匹配
char c = it.first;
int v = it.second;
b += min(v,mpt[bianhuan(c)]);
mps[c] = 0;
mpt[bianhuan(c)] = 0;
}
cout<<a<<" "<<b<<endl;
return 0;
}