2021-12-25
文章目录
A.Closing The Gap
题目
一排有 n 个方块塔，其中塔 i 的高度为 a i a_i ai。你是建筑团队的一员，你想让建筑看起来尽可能漂亮。在一天之内，您可以执行以下操作：
选择两个索引 i 和 j (1≤i,j≤n; i≠j)，将一个方块从塔 i 移动到塔 j。这实质上是将 a i a_i ai 减少了 1，而将 a j a_j aj 增加了 1。
你认为建筑物的丑陋是最高和最短建筑物之间的高度差。形式上，丑陋被定义为 max(a)−min(a)。
在任意天数之后，您可以达到的最小可能丑度是多少？
输入
第一行包含一个整数 t (1≤t≤1000)——测试用例的数量。然后是 t 个案例。
每个测试用例的第一行包含一个整数 n (2≤n≤100)——建筑物的数量。
每个测试用例的第二行包含 n 个空格分隔的整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 7 ) a_1,a_2,…,a_n (1≤a_i≤10^7) a1,a2,…,an(1≤ai≤107)——建筑物的高度。
输出
对于每个测试用例，输出一个整数——建筑物的最小可能丑陋程度。
题解：
如果 max(a)−min(a) 严格大于 1，您可以分别对 max 和 min 应用操作，这使它们彼此更接近。 换句话说，它要么减小 max(a)−min(a) 要么保持不变。 这意味着答案总是≤1。 现在剩下的就是确定答案是 0 还是 1。如果数组的总和可以被 n 整除，那么答案只能是 0，因为数组的总和在一次运算之后不能改变，并且如果它不能被 n 整除 n 你不能让每个元素都相等。 这意味着如果总和可被 n 整除，则答案为 0，否则为 1。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn=1e6+5;
void solve(){
int n;
cin >> n;
int a[1000] = {
0};
int sum = 0;
int maxx = 0;
for (int i = 0; i < n;i++){
cin >> a[i];
sum += a[i];
}
if(sum%n==0)
cout << "0\n";
else
cout << "1\n";
}
int main(){
ios::sync_with_stdio(0);
int t;
cin >> t ;
while(t--){
solve();
}
return 0;
}
B. And It’s Non-Zero
题目描述
给定一个数组，其中包含 [l,r] 中的所有整数。例如，如果 l=2 且 r=5，则数组将为 [2,3,4,5]。为了使数组的按位 AND 非零，您可以删除的最小元素数是多少？
按位 AND 是一种二元运算，它采用两个等长的二进制表示，并对每对相应的位执行 AND 运算。
输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)——测试用例的数量。然后是 t 个案例。
每个测试用例的第一行包含两个整数 l l l 和 r ( 1 ≤ l ≤ r ≤ 2 ⋅ 1 0 5 ) r (1≤l≤r≤2⋅10^5) r(1≤l≤r≤2⋅105)——数组的描述。
输出
对于每个测试用例，输出一个整数——问题的答案。
inputCopy
5
1 2
2 8
4 5
1 5
100000 200000
outputCopy
1
3
0
2
31072
在第一个测试用例中，数组是 [1,2]。目前，按位与为 0，因为 1 & 2=0。但是，删除1（或2）后，数组变为[2]（或[1]），按位AND变为2（或1）。可以证明这是最优的，所以答案是 1。
在第二个测试用例中，数组是 [2,3,4,5,6,7,8]。目前按位与为0，但删除4、5、8后，数组变为[2,3,6,7]，按位与为2，可以证明这是最优的，所以答案是 3。请注意，可能还有其他方法可以删除 3 个元素。
题解：
让我们解决补码问题：找到数组的最大子序列，使得它们的按位 AND 非零。令 x 是最佳子序列的按位和。由于 x≠0，因此 x 中必须至少设置一位。让我们迭代那个位，称之为 b，并在每次迭代中计算最大的子序列，其按位和设置了该位。对于要在最终答案中设置的第 b 位，所选子序列中的每个元素都必须设置该位。由于选择第 b 位打开的每个元素都是有效的子序列，这意味着第 b 位的答案是设置了第 b 位的元素的数量。因此，最终问题的答案是 n − m a x 1 ≤ b ≤ 30 c n t b n−max_{1≤b≤30}cnt_b n−max1≤b≤30cntb，其中 c n t b cnt_b cntb 是设置了第 b 位的元素的数量。
注意：最终答案是否包含多个设置位并不重要，它仍然包含在至少一种情况下，并且按位和仍然是非零的。
剩下的就是对所有 b 设置第 b 位的 [l…r] 范围内的元素数量进行计数。这可以通过预计算来完成，通过在回答任何测试用例之前创建 b 个前缀和数组，其中第 b 个数组的第 i 个元素是具有第 b 个位的整数 ≤i 的数量。在此之后，您可以使用前缀和技术来回答查询，如 c n t b = a b , r − a b , l cnt_b=a_{b,r}−a_{b,l} cntb=ab,r−ab,l，如果 a b a_b ab 是第 b 个数组。
挑战：解决 1 ≤ l ≤ r ≤ 1 0 9 1≤l≤r≤10^9 1≤l≤r≤109的问题。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn=1e6+5;
ll sum[maxn][20];
void solve(){
int l, r;
cin >> l >> r;
ll res = 0x3f3f3f;
for (int i = 0; i <= 18;i++){
ll temp = sum[r][i] - sum[l - 1][i];
res = min(res, temp);//最小就是要删掉的
}
cout << res << endl;
}
int main(){
ios::sync_with_stdio(0);
int t;
cin >> t ;
for (int i = 0; i <= 2e5;i++){
for (int j = 18; j >= 0;j--){
if(!((i>>j)&1))
sum[i][j] = sum[i - 1][j] + 1;
else
sum[i][j] = sum[i - 1][j];
}
}
while (t--)
{
solve();
}
return 0;
}
C. Menorah
题目详情
光明节烛台上有 n 根蜡烛，其中一些蜡烛最初是点燃的。我们可以用二进制字符串 s 来描述哪些蜡烛被点燃，其中第 i 根蜡烛被点燃当且仅当 s i = 1 s_i=1 si=1。
最初，蜡烛灯由字符串 a 描述。在操作中，您选择当前点亮的蜡烛。通过这样做，您选择的蜡烛将保持点亮状态，而其他所有蜡烛都会改变（如果它被点亮，它将熄灭，如果它未被点亮，它将被点亮）。
您想让蜡烛看起来与字符串 b 相同。您的任务是确定是否可行，如果可行，则找出所需的最少操作次数。
输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)——测试用例的数量。然后是 t 个案例。
每个测试用例的第一行包含一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n (1≤n≤10^5) n(1≤n≤105) — 蜡烛的数量。
第二行包含一个长度为 n 的字符串 a，由符号 0 和 1 组成——灯光的初始模式。
第三行包含一个长度为 n 的字符串 b，由符号 0 和 1 组成——所需的灯光模式。
保证n之和不超过 1 0 5 10^5 105。
输出
对于每个测试用例，输出将 a 转换为 b 所需的最少操作数，如果不可能，则输出 -1。
题解：
首先，让我们将蜡烛 i i i 的“类型”定义为字符串 a i b i a_ib_i aibi。例如，如果蜡烛当前未点亮并且必须在最后点亮，则其类型为 01 01 01。考虑每种类型的蜡烛数量很有用，因为蜡烛的位置与此问题无关。
现在，让我们考虑当我们连续执行两个操作时会发生什么。除了我们选择的蜡烛之外的所有蜡烛都会翻转两次，所以让我们关注我们选择的蜡烛会发生什么。如果我们两次选择同一根蜡烛，则没有任何变化。如果我们选择两个不同的蜡烛，它相当于交换字符串中的 1 1 1 和 0 0 0。
由于我们对两个连续操作的描述非常好，因此偶数个操作的任何序列都只是一个交换序列。因此，只要两个字符串中1的数量相同，就可以进行偶数次操作，并且最小操作次数将是字符串不同位置的数量。
现在，奇数个操作呢？嗯，这和执行一次操作然后将其减少到偶数次操作的情况相同。我们可以在第一次操作时选择两种类型的蜡烛：类型 10 10 10 和类型 11 11 11。只需尝试两种选项（如果存在），并在减少到偶数情况后找到最小操作次数。
最后，有些字符串可以执行偶数或奇数操作，因此在这些情况下，我们必须取两个选项中的最小值。总复杂度为 O ( n ) O(n) O(n)。
奖励：你能证明在奇数操作的情况下，永远没有必要选择类型为 10 10 10 的蜡烛吗？
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define INF 0x3f3f3f3f
const int maxn = 1e6 + 5;
void solve(){
int cnt = 0;
int n;
cin >> n;
string a, b;
cin >> a >> b;
int cnt1 = count(a.begin(), a.end(), '1');
int cnt2 = count(b.begin(), b.end(), '1');
for (int i = 0; i < n; i++)
if (a[i] != b[i])
cnt++;
int res = INF;
if (cnt1 == cnt2)
res = min(res, cnt);
if (cnt1 == n - cnt2 + 1)
res = min(res, (n - 1 - cnt) + 1);
if (res == INF)
cout << "-1\n";
else
cout << res << endl;
}
int main(){
ios::sync_with_stdio(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
京公网安备 11010502036488号