牛客小白月赛98 （个人题解）（补全）

前言：

昨天晚上自己一个人打的小白月赛（因为准备数学期末已经写烦了），题目难度感觉越来越简单了（不在像以前一样根本写不了一点，现在看题解已经能看懂一点了），能感受到自己在不断进步，希望在暑假能更努力一点吧，，少打点游戏，多学学算法，还有web的学习也要抓起来了，这几天不是在看高数就是在打游戏，感觉好堕落。

正文：

链接：(1条未读私信) 牛客小白月赛98_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A 骰子魔术：

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main(){
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		int d;
		cin>>d;
		a[d]++;
	}
	if(a[x])cout<<"YES";
	else cout<<"NO";
	return 0;
}

桶排秒了。

B 最少剩几个？：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,res=0,ans=0;
	cin>>n;int o=n;
	while(o--){
		int x;
		cin>>x;
		if(x%2==1)res++;
	}
	int z=n-res;
	if(z>=res){
		ans=n-2*res;
	}
	else{
		ans=n-2*z-((res-z)/2)*2;
	}
	cout<<ans<<endl;
	return 0;
}

因为奇数加偶数一定是奇数，奇数乘奇数一定为奇数，分两种情况讨论，当偶数数量大于奇数的时候直接用总数减奇数数量的两倍；当奇数大于偶数的时候先减去偶数的两倍在考虑剩下的奇数即可。

C 两个函数：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll quickmod(ll a, ll b, ll c)
{
  ll ans = 1;
  a = a % c;
  while(b)
  {
    if(b&1) ans = (ans * a) % c;
    b = b >> 1;
    a = (a * a) % c;
  }
  return ans;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		ll a,x,ans;
		cin>>a>>x;
		if(x==1)ans=a*x%mod;
		else{
			ans=(((a*a)%mod)*((x)*(x-1)/2%mod))%mod;
		}
		cout<<ans<<endl;
	}
	return 0;
}

我们可以将公式转化为

$g(x)=ax......x=1$

$g(x)=a^{2}(\sum (n-1))=a^{2}(\frac{x(x-1)}{2})..........x>1$

最后直接一边算一遍取模即可。

D 切割 01 串 2.0：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dp[1000][1000];
int pre[N],suf[N];
int main(){
    int t = 1;
    while(t --）{
    int n,l,r; cin >> n >> l >> r;
    string s; cin >> s;
    s = "#" + s;
    // 区间dp
    // dp[a][b] = dp[a][k] + dp[k+1][b] + 1;
    for(int i = 1; i <= n ; i ++){
        if(s[i] == '0') pre[i] = pre[i - 1] + 1;
        else pre[i] = pre[i - 1];
    }
    for(int i = 1 ; i <= n ; i ++){
        if(s[i] == '1') suf[i] = suf[i - 1] + 1;
        else suf[i] = suf[i - 1];
    }
    for(int len = 2 ; len <= n ; len ++){
        for(int i = 1 ; i <= n - len + 1; i ++){
            int j = i + len - 1;
            for(int k = i ; k < j ; k ++){
                int q0 = pre[k] - pre[i - 1];
                int q1 = suf[j] - suf[k];
                int res = abs(q0 - q1);
                if(res >= l && res <= r)
                    dp[i][j] = max(dp[i][j],dp[i][k] + dp[k + 1][j] + 1);
            }
        }
    }
    cout << dp[1][n];
    }
}

比赛时这题一直想用递归，根本没去想是dp，甚至是我练过的区间dp，导致我用递归一直暴内存，怎么优化都过不了。其实细想想这题确实就是区间dp，因为从小区间推导到大区间就免去了对一次切割产生两个子段进行·递归的过程,详情可以见代码。

E and xor or：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
ll a[N];
ll n,k1,k2;
ll work(int x){
	ll ans=0,cnt=0;
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=x;j<=60;j++){
			int u=a[i]>>j&1;
			int v=a[i-1]>>j&1;
			if(u!=v){
				flag=false;
			}
		}
		if(flag)cnt++;
		else{
			ans+=cnt*(cnt+1)/2;
			cnt=1;
		}
	}
	ans+=cnt*(cnt+1)/2;
	return ans;
}
int main(){
	
	cin>>n>>k1>>k2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<work(k2)-work(k1)<<endl;
	return 0;
}

看了题解发现这题还挺简单，

利用前缀和的思想，用所有结果小于 2^k2的子数组个数 - 所有结果小于2^k1的子数组个数，即为答案。

发现这个 2^k 刚好只有一位(二进制下)，要结果小于它，则必须满足在二进制中 k ~ 60 位中不能有 1。根据题目条件，满足不能有 1 即这个子数组元素在k ~ 60位的每一位不能同时存在 1 和 0。