T1单次交换

解决方案

算出所有可能的情况后，循环遍历不同的数量。

错误原因

数组开小了。

正确代码

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

T2开关

解决方案

首先用N位二进制数表示所有开关的状态（0表示关，1表示开），之后枚举所有2^N种可能的开关组合，对每种组合，检查是否满足所有灯泡的点亮条件。最后统计满足条件的组合数量即可。

T3不可表示的数

解决方案

先算出所有“可表示的数”，之后生成连续数列去删除可表示的数，剩下的就是“不可表示的数”啦。

错误原因

时间超限，只从正面想了，没有反过来思考。启示:有时思考问题，反过来想会比正的容易。

正确代码

#include<bits/stdc++.h>;
using namespace std;
long long f(long long n){
	unordered_set<long long> p;
	for (long long b=2;b<=log2(n)+1;++b) {
		long long a=2;
		while(true){
			long long s=pow(a,b);
			if (s>n)break;
			p.insert(s);
			a++;
		}
	}
	return n-p.size();
}
int main(){
    //freopen("num.in","r",stdin);
    //freopen("num.out","w",stdout);
	long long n;
	cin>>n;
	cout<<f(n);
	return 0;
}

T4幸运数

解决方案

需要找到所有满足k=p×q³（p和q为质数且p<q）且k≤N的整数。

正确代码

#include <bits/stdc++.h>
using namespace std;
vector<int> si(int max) {
	vector<bool> prime(max+1,true);
	prime[0]=prime[1]=false;
	for (int i = 2; i*i<=max; ++i) {
		if (prime[i]){
			for (int j = i * i; j <= max; j += i) {
				prime[j]=false;
			}
		}
	}
	vector<int> primes;
	for (int i=2;i<=max;++i) {
		if (prime[i]) primes.push_back(i);
	}
	return primes;
}
long long cnt(long long N) {
	if(N<2*3*3*3) return 0;
	int mq = cbrt(N / 2) + 1;
	vector<int> primes = si(mq);
	long long c = 0;
	for (size_t j = 0; j < primes.size(); ++j) {
		long long q=primes[j];
		long long qc=q*q*q;
		if (qc > N) break;
		long long mp = N / qc;
		mp=min(mp,q -1LL);
		int l=0,r=j-1;
		int v=-1;
		while (l<=r) {
			int mid=(l+r) / 2;
			if (primes[mid]<=mp) {
				v= mid;
				l=mid + 1;
			} else {
				r=mid - 1;
			}
		}
		c+=(v+1);
	}
	return c;
}
int main() {
    //freopen("lucky.in","r",stdin);
    //freopen("lucky.out","w",stdout);
	long long n;
	cin>>n;
	cout<<cnt(n);
	return 0;
}

注：所有freopen已注释