A. 单次交换

思路：遍历s，打标记，与零取最大值

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=300;
long long ans,v[N];
string s;

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout); 
	cin>>s;
	s=" "+s;
	bool flag=false; 
	for(int i=1;i<s.size();i
++){
		v[s[i]]++;
		ans+=i
-v[s[i]];
//		cout<<ans<<' '<<i-v[s[i]]<<endl;
		if(v[s[i]]>1) flag=true;
	}
	cout<<max(ans+flag,1ll*1);
	return 0;
}

B. 开关

思路：深搜，判断当按下开关灯是否会亮

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=15;
int n,m,s[N],f[N][N],p[N],flag[N],ans;

void dfs(int l){
	if(l>n){
		for(int i=1;i<=m;i++){
			int cnt=0;
			for(int j=1;j<=n;j++){
				int x=f[i][j];
				if(x&&flag[j]){
					cnt++;
				}
			}
			if(cnt%2!=p[i]){
				return;
			}
		}
		ans++;
		return;
	}
	flag[l]=1;
	dfs(l+1);
	flag[l]=0;
	dfs(l+1);
}

int main(){
	freopen("switch.in","r",stdin);
	freopen("switch.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int k;
		cin>>k;
		for(int j=1;j<=k;j++){
			int x;
			cin>>x;
			f[i][x]=1;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>p[i];
	}
	dfs(1);
	cout<<ans;
	return 0;
}

C. 不可表示的数

思路：遍历

题解：

#include <bits/stdc++.h>
using namespace std;

long long n,ans;
unordered_map<long long,long long> mp;

long long s(long long a){
	long long cnt=0,b=a*a;
	while(b<=n){
		cnt++;
		mp[b]++;
		b*=a;
	}
	return cnt;
}

int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	cin>>n;
	for(long long i=2;i<=n/i;i++){
		if(mp[i]) continue;
		ans+=s(i);
	}
	cout<<n-ans;
	return 0;
}

D. 幸运数

思路：先筛出1e6之内的所有质数，内部第一层枚举 p（记得用 prime 数组），判断条件为i(p)^4<n，因为 q>p，如果 i^4=n ,由于q>p，则没有解。第二层循环枚举 q，判断条件为 i*j^3<=n。

题解：

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
long long p[N],st[N],cnt,n,ans;

void get_primes(int n) {
	for (long long i=2; i<=n; i++) {
		if (!st[i]) p[++cnt] = i;
			for (long long j=1; p[j]<=n/i; j++) {
				st[p[j]*i] = 1;
				if (i%p[j] == 0) break;
			}
	}
	return; 
}

int main(){
	freopen("lucky.in","r",stdin);
	freopen("lucky.out","w",stdout);
	cin>>n;
	get_primes(1000000);
	for(long long i=1;i<=cnt;i++){
		if(p[i]*p[i]*p[i]*p[i]>n) break;
		for(long long j=i+1;j<=cnt;j++){
			if(p[i]*p[j]*p[j]*p[j]>n) break;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

E. 逻辑表达式

思路：首先对于每一个 OR 运算，前面要么 x[i]=1，要么 y[i-1]=1，要么两者皆满足，很显然，对于前者，x[1]~x[i-1] 可以随便选择，而后者要么来自 x[0] 或者前面的 OR 运算，所以只需要累加 2^i ，最后在增加 1 即可。

题解：

#include <bits/stdc++.h>
using namespace std;

long long n,ans=1;
string s[70];

int main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	freopen("expr.in","r",stdin);
	freopen("expr.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	for(int i=n;i>=1;i--){
		if(s[i]=="OR"){
			ans+=(1ll<<i);
		}
	}
	cout<<ans;
	return 0;
}