T1 单次交换

题意：求恰好执行一次以下操作后可能得到的不同字符串的数量。

思路： 1.字符计数：使用数组cnt统计每个字符在字符串中出现的次数。

2.总对数计算：计算所有可能的字符对数量，公式为n*(n-1)/2，其中n是字符串长度。

3.相同字符对的处理：对于每个字符，减去其相同字符对的数量，公式为cnt[i]*(cnt[i]-1)/2。

4.结果调整：如果字符串中存在重复字符，结果加 1。

这个算法的核心在于理解f标记的作用，它能让存在重复字符时，结果额外加 1，否则保持不变。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int cnt[130];
int main()
{
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	string s;
	cin>> s;
	int f = 0;
	ll n = s.size();
	for(int i = 0;i < n;++i)
	{
		cnt[s[i]]++;
	}
	ll ans = n*(n-1)/2;
	for(int i = 'a';i <= 'z';++i)
	{
		ans -= (ll)cnt[i]*(cnt[i] - 1)/2;
		if(cnt[i] > 1) f = 1;
	}
	cout<< ans + f;
	return 0;
}

T3 不可表示的数

题意：题目要求我们统计在1到N之间的整数中，有多少个数不能表示为$a^b$的形式，其中a和b都是不小于2的整数。

思路：统计所有能表示为$a^b$的数，并存储在一个集合里自动去重。用总数N减去集合的大小，即可得到答案。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
    ll n;
    cin>> n;
    set<ll>r;
    for(ll j = 2;j <= sqrt(n);j++)
	{
        for(ll g = 2;pow(j,g) <= n;g++)
		{
            r.insert(pow(j,g));
        }
    }
    ll sum = n - r.size();
    cout<< sum << endl;
    
    return 0;
}