错题：

B

错因:

开关变量N和灯泡变量M混淆。

思路：

dfs枚举所有的开关灯情况，列举所有灯泡的状态，如果所有的灯泡都是开启状态就计数变量加一最后输出计数变量。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[15][15];
int k[15],p[15];
long long ans=0;
int kg[15];
bool check(int o){
    for(int i=0;i<m;i++){
        int sum=0;
        for(int j=0;j<k[i];j++){
            if(kg[s[i][j]]) sum++;
        }
        if(sum%2!=p[i]){
            return false;
        }
    }
    return true;
}
void g(int o){
    if(o==n+1){
        if(check(o)) ans++;
        return;
    }
    kg[o]=1;
    g(o+1);
    kg[o]=0;
    g(o+1);
}
int main(){
    freopen("switch.in","r",stdin);
    freopen("switch.out","w",stdout);
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>k[i];
        for(int j=0;j<k[i];j++) cin>>s[i][j];
    }
    for(int i=0;i<m;i++) cin>>p[i];
    g(1);
    cout<<ans<<endl;
    return 0;
}

C

错因:

用暴力做的，超时了。

思路：

算出n中所有能表示为a^b的数，并用n减。

参考代码

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

D

错因:

补题时一遍AC。

思路：

创建质数数组，循环枚举q，再枚举p,之后q^3+p的值如果小于n则计数变量加一，输出时输出计数变量。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main() {
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
	ll n;
	cin>>n;
	if(n<54){
		cout<<0<<endl;
		return 0;
	}
	ll ma = cbrt(n/2) + 1;
	vector<bool> prime(ma+1,true);
	for (ll i=2;i*i<=ma; i++) {
		if (prime[i]){
			for (ll j=i*i;j<=ma;j+=i) {
				prime[j]=false;
			}
		}
	}
	vector<ll> primes;
	for (ll i=2;i<=ma;i++) {
		if (prime[i]) primes.push_back(i);
	}
	ll sum = 0;
	for (ll j=0;j<primes.size();j++) {
		ll q=primes[j];
		ll q3=q*q*q;
		if (q3>n) break;
		ll mi=n/q3;
		mi=min(mi,q-1LL);
		ll l=0,r=j-1;
		ll ans=-10086;
		while (l<=r) {
			ll mid=(l+r) / 2;
			if (primes[mid]<=mi) {
				ans= mid;
				l=mid + 1;
			} else {
				r=mid - 1;
			}
		}
		sum+=ans+1;
	}
	cout<<sum<<endl;
	return 0;
}

E

错因:

此题精度要求高，我做题时用了精度不高的pow，应该用左除。

思路：

此题没学过DP的推公式，学过的用DP。

参考代码

#include<bits/stdc++.h>
using namespace std;
stack<char> a;
int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    string s;
    long long n,sum=1;
    cin>>n;
    long long cnt=n;
    for(long long i=1;i<=n;i++){
        cin>>s;
        a.push(s[0]);
    }
    while(!a.empty()){
        if(a.top()=='O') sum+=1LL<<cnt;
        a.pop();
        cnt--;
    }
    cout<<sum<<endl;
    return 0;
}

THE END