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是10^{9，但是我们可以把最后一位单独拿出来，也就是说这个题我们可以O(10}8)的时间复杂度解决。

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;
}