锐评

数量马上三位数了，感觉自己还是好菜

前三题都比较基础，第四题上了点难度就不会了，交第三题的时候排在50名左右，然后就没有然后了

交题点：牛客小白月赛98

A.骰子魔术

题目描述

jackle 正在给他的朋友表演一个关于骰子的魔术：

  • jackle 会拿出一枚骰子，骰子的表面分别写上了从 1∽500 的数字，朋友会随便说一个 1∽500 之间的点数，jackle 都能保证百分之百的掷出这个点数。

当然 jackle 有备而来，他准备了 n 枚特殊的骰子，第 i 枚特殊骰子，可以保证每次掷出的点数都为 ai​。
jackle 想问你，他能不能只拿出一枚事先准备好的特殊骰子，成功完成这次魔术。

输入描述:

第一行输入 2 个正整数 n (1 ≤ n ≤ 1000)，x ( 1 ≤ x ≤ 500)，分别表示 jackle 准备的特殊骰子数量，朋友说的那个点数。

第二行输入 n 个正整数 ai (1 ≤ ai ≤ 500)，分别表示每枚特殊骰子可以掷出的点数。

输出描述:

如果 jackle 可以成功完成这次魔术，请你输出 YES；否则请你输出 NO。

示例1输入

5 3
1 2 1 3 12

示例1输出

YES

说明

jackle 可以选择第 4 个骰子，因为 a4=x=3，所以他能百分之百掷出这个朋友说出的点数，所以可以完成这次魔术。

思路

非常明显的签到题了，只不过我第一分钟没看懂这个题让干嘛的，文字有点多有点绕

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, x, a[N];

void solve() {
	cin >> n >>x;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		if (a[i] == x) {
			cout << "YES\n";
			return;
		}
	}
	cout << "NO\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--) solve();
	return 0;
}

B.最少剩几个

题目描述

给定一个长度为 n 的序列 a，如果当前序列长度至少为 2，那么你每次可以做如下两种操作之一：

  1. 选择 i,j (i≠j)i,j\ (i\not =j)i,j (i​=j)，如果满足 ai+aja_i+a_jai​+aj​ 是奇数，那么你可以同时删除 ai,aja_i,a_jai​,aj​。

  2. 选择 i,j (i≠j)i,j\ (i\not =j)i,j (i​=j)，如果满足 ai×aja_i\times a_jai​×aj​ 是奇数，那么你可以同时删除 ai,aja_i,a_jai​,aj​。

你可以执行上面的操作无数次，只要你满足操作条件，jackle 想问你序列最少剩几个数？

你可以执行上面的操作无数次，只要你满足操作条件，jackle 想问你序列最少剩几个数？

输入描述:

第一行输入 1 个正整数 n (1 ≤ n ≤ 105)，表示序列的长度。
第二行输入 n 个正整数 ai (1 ≤ ai ≤ 109)。

输出描述:

输出序列最少剩几个数？

示例一输入

1
114514

示例一输出

1

示例一说明

只有一个数，啥也操作不了。

示例2输入

2
9 9

示例2输出

0

思路

偶数 + 奇数 = 奇数，奇数 * 奇数 = 奇数只需要看奇数和偶数的数量就可以，因此只要判断奇数和偶数的数量即可

如果偶数多，偶数先和奇数一比一消耗，剩下的都动不了

如果奇数多，先一比一消耗完偶数，看看剩下奇数两两一消，如果数量是偶数则全部消完，否则就剩一个

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, a[N];

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	int ji = 0, ou = 0;
	
	for (int i = 1; i <= n; ++ i) {
		if (a[i] & 1) ji ++;
		else ou ++ ;
	}
	// cout << ji << " " << ou << "\n";
	if (ou >= ji) {
		cout << ou - ji;
	}else {
		ji -= ou;
		if (ji & 1) cout << 1;
		else cout << 0;
	}
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--) solve();
	return 0;
}

C.两个函数

题目描述

jackle 给定两个函数：

f(x)=axg(x)={f(x)x=1∑i=1x−1f(f(i))x>1


他有 Q 次询问，每次给定 a, x，请你计算 g(x) mod  998244353 的结果。

输入描述:

第一行输入 1 个正整数 Q (1 ≤ Q ≤ 105)，表示询问次数。 接下来 Q 行，每行输入 2 个正整数 a, x (1 ≤ a , x ≤ 109)。

输出描述:

对于每组询问，输出 g(x) mod  998244353 的结果。

输入

3
1 1
2 2
9982 44353

输出

1
4
572321601

思路

当时很快就想出来了，立马提交，一遍过，排名直接从300+到50，但最后也止步于这道题了

只需要写一个函数讲 g( x ) 模拟出来就可以了，f ( f ( x ) )最后说到底只不过是多乘了个 a ，只不过最后算结果的时候每一步都要取模，并且除法要用逆元。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}


int g(int a, int x) {
	if (x == 1) return a % MOD;
	return x * (x - 1) % MOD * inv(2) % MOD * a % MOD * a % MOD;
}

int a, x;

void solve() {
	cin >> a >> x;
	cout << g(a, x) << "\n";
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	cin >> _;
	while (_--) solve();
	return 0;
}

D. 切割 01 串 2.0

题目描述

jackle 在校赛的时候出过一道 "切割 01 串" 的题目，如今他又出了一道切割 01 串的题目：
给定一个长度为 n 的 01 串，定义如下操作为一次 "切割"：

  • 将长度大于 1 的字符串分割为两个非空的连续字串，记分割出来的左侧字串 a 中 0 的出现次数为 C0​，右侧字串 b 中 1 出现的次数为 C1​，需要满足 L ≤ ∣C0−C1∣ ≤ R。

你每次切割完，都会得到两个新 01 串，你可以继续选择这些已经被你切出来的 01 串做切割，只要满足切割条件。

jackle 想问你最多可以切割多少次？

输入描述:

第一行输入 3 个整数，n (1 ≤ n ≤ 500)，L , R (0 ≤ L ≤ R ≤ 500)，分别表示字符串长度，和题目中的两个参数。 第二行输入 1 个长度为 n 的 01 串。

输出描述:

输出最多能切割多少次？

输入

6 2 3
011011

输出

3

说明

其中一种切割次数最多的切法如下：

第一次切割可以切：0 ∣ 11011，然后选择 11011 这个串继续做切割。

第二次切割可以切：1 ∣ 1011，然后选择 1011 这个串继续做切割。

第三次切割可以切：1 ∣ 011。

思路

当时看到这个题其实也想过dp，但是太难实现，看着样例我就默认从左边开始遍历，出现第一个满足条件的切法是就去切，然后用函数的递归实现，结果显而易见一直错误，结束后测试，只能过三分之一的样例。

看到题解说是区间dp，确实到我不会的地方了，不过他的办法还是很精妙，

令 dp[ l , r ] 的 01 串最多能切割几次，转移的时候枚举切割点 k 即可，同时判断一下切割是否合法，判断切割是否合法的时候可以用前缀和，这样总的时间复杂度就为 O(n3)。

d p l , r = { 0 l = r m a x ( d p l , r , d p l , k + d p k + 1 , r + 1 ) l != r ,满足切割条件

ps：自己再做的时候还是错，是遍历左端点再遍历右端点，再遍历切割点，后来想到，这样遍历的话dp[1][n]会早早的就得到答案，但是左端点不为1的其他区间的 dp 值都为 0 ，而dp[1][n]会用到那些dp值，因此会发生错误，所以要把dp[1][n]放到最后遍历，先遍历一个区间的长度，再遍历左端点，就可以求出右端点，然后依次进行即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 509;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, l, r;
int sum0[N], sum1[N];
int dp[N][N];


void solve() {
	cin >> n >> l >> r;
	string s; cin >> s;
	s = '?' + s;
	for (int i = 1; i <= n; ++ i) {
		sum0[i] = sum0[i - 1] + (s[i] == '0'); 
		sum1[i] = sum1[i - 1] + (s[i] == '1'); 
	}

	for (int len = 1; len <= n; ++ len) {
		for (int i = 1; i <= n - len + 1; ++ i) {
			if (len == 1) continue;
			int j = i + len - 1;
			for (int k = i; k < j; ++ k) {
				int t = abs((sum0[k] - sum0[i - 1]) - (sum1[j] - sum1[k]));
				if (t >= l && t <= r) {
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
				}
			}
		}
	}
	cout << dp[1][n];
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	//cin >> _;
	while (_--) solve();
	return 0;
}

E.and xor or

题目描述

给定一个长度为 n 的序列 a，jackle 想让你求出有多少个区间 [l,r] 满足如下条件：

  • 1 ≤ l ≤ r ≤ n

  • 2k1 ≤ ( al & al+1 & ... & ar) ⊕ (al ∣ al+1 ∣...∣ ar) < 2k2

其中 &， |，⊕，分别表示按位与，按位或，按位异或。

输入描述:

第一行输入 3 个整数 n (1 ≤ n ≤ 5×105)，k1,k2 (0 ≤ k1 < k2 ≤109)。 第二行输入 n 个整数 ai (0 ≤ ai ≤ 1018)。

输出描述:

输出满足条件的区间数量。

样例一输入

4 0 2
2 1 4 3

样例一输出

1

样例一说明

只有区间 [1,2] 满足条件：20 ≤ (2 & 1) ⊕ (2 ∣ 1) = 3 < 22

样例二输入

6 0 4
7 6 7 6 7 7

样例二输出

14

思路

这道题当初几乎是一点思路都没有，看了出题人的视频题解，然后又看了看大佬的题解，出题人的题解看了很久都没有理解，还是记一下这个大佬更简单的题解吧。

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

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

这个算是最简单的方法了，不过当时的 u != v 还是用了好久才理解。

如果 u == v 那么 a[i] 和 a[i - 1] 的第 j 位相等，如果和前面组在一起，那么公式中相 & 的结果为 1 ，相 | 的结果为 0 ，再 ^ 的结果就为 1 ，但是我们要的是在 k ~ 60 位不能有 1 ，因此 u == v 的时候这个区间就到此结束了，结果加上这个区间长度的所有子区间即可，长度再定位 1，重新往后找。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}

int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}

int n, k1, k2, a[N];

int solve(int x) {
	int ans = 0, cnt = 0;
	for (int i = 1; i <= n; ++ i) {
		bool ok = true;
		for (int j = x; j <= 60; ++ j) {//枚举x到60位
			int u = a[i] >> j & 1;
			int v = a[i - 1] >> j & 1;
			if (u != v) {
				ok = false;
			}
		}
		if (ok) cnt ++;
		else {
			ans += cnt * (cnt + 1) / 2;
			cnt = 1;
		}
	}
	ans += cnt * (cnt + 1) / 2;
	return ans;

}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _ = 1;
	//cin >> _;
	cin >> n >> k1 >> k2;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	cout << solve(k2) - solve(k1);
	return 0;
}