codeforces global round 18


好久没有水博客了,现在在摸鱼,正好水一篇
昨天邮箱里收到一封codeforces的比赛邀请,然后就在想正好是平安夜,可以打一打这个作为休息昨天写高数和电路写麻了
然后记录一下我写的三道签到题

首先是最简单的第一题
A. Closing The Gap
time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output
There are n block towers in a row, where tower i has a height of ai. You’re part of a building crew, and you want to make the buildings look as nice as possible. In a single day, you can perform the following operation:

Choose two indices i and j (1≤i,j≤n; i≠j), and move a block from tower i to tower j. This essentially decreases ai by 1 and increases aj by 1.
You think the ugliness of the buildings is the height difference between the tallest and shortest buildings. Formally, the ugliness is defined as max(a)−min(a).

What’s the minimum possible ugliness you can achieve, after any number of days?

Input
The first line contains one integer t (1≤t≤1000) — the number of test cases. Then t cases follow.

The first line of each test case contains one integer n (2≤n≤100) — the number of buildings.

The second line of each test case contains n space separated integers a1,a2,…,an (1≤ai≤10^7) — the heights of the buildings.

Output
For each test case, output a single integer — the minimum possible ugliness of the buildings.

Example
input

1
2
3
4
5
6
7
3
3
10 10 10
4
3 2 1 2
5
1 2 3 1 5

output

1
2
3
0
0
1

题目大意就是给一串数字,然后可以:给其中一个增加1以及另一个减小1。然后要求这串数字最大高度差的最小值。
稍微想想就能发现只要总长度能被数字个数整除就是0,否则就是1。
代码就很简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int all[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n,sum=0;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> all[i];
sum+=all[i];//计算总和
}
if (sum%n==0)//判断
{
cout << "0" << endl;
}
else
{
cout << "1" << endl;
}

}
return 0;//华丽结束
}

然后就是第二题,其实也很简单((
B. And It’s Non-Zero
time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output
You are given an array consisting of all integers from [l,r] inclusive. For example, if l=2 and r=5, the array would be [2,3,4,5]. What’s the minimum number of elements you can delete to make the bitwise AND of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.

Input
The first line contains one integer t (1≤t≤10^4) — the number of test cases. Then t cases follow.

The first line of each test case contains two integers l and r (1≤l≤r≤2⋅10^5) — the description of the array.

Output
For each test case, output a single integer — the answer to the problem.

Example
input

1
2
3
4
5
6
5
1 2
2 8
4 5
1 5
100000 200000

output

1
2
3
4
5
1
3
0
2
31072

大意是输入一个区间,求一个最小数a,删掉区间里的a个数后能使得区间内每个数按位与得到的值不为0。
身为蒟蒻的我第一次提交超时惹
这个数据量应该先打好表,然后用前缀和。也就是算出从1到n中二进制下31位(实际上没有31位)上各个位置1出现的次数。
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int all[N][40];
int main()
{
int t;
cin >> t;
for (int i = 1; i < N; i++)
{
int temp=i,now=0;
while (temp)//当后面都为0时就不用判断了
{
all[i][now]+=(temp&1);
all[i][now]+=all[i-1][now];//计算前缀和
temp>>=1;
now++;//下一位
}
}
while (t--)
{
int l,r,maxn=0;
scanf("%d%d",&l,&r);
for (int i = 0; i < 25; i++)
{
maxn=max(maxn,all[r][i]-all[l-1][i]);//遍历每一位求出最大值
}
printf("%d\n",(r-l+1)-maxn);
}
return 0;//华丽结束
}

最后是我写出来的最后一道签到题
C. Menorah
time limit per test:2 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output
There are n candles on a Hanukkah menorah, and some of its candles are initially lit. We can describe which candles are lit with a binary string s, where the i-th candle is lit if and only if si=1.

Initially, the candle lights are described by a string a. In an operation, you select a candle that is currently lit. By doing so, the candle you selected will remain lit, and every other candle will change (if it was lit, it will become unlit and if it was unlit, it will become lit).

You would like to make the candles look the same as string b. Your task is to determine if it is possible, and if it is, find the minimum number of operations required.

Input
The first line contains an integer t (1≤t≤10^4) — the number of test cases. Then t cases follow.

The first line of each test case contains a single integer n (1≤n≤10^5) — the number of candles.

The second line contains a string a of length n consisting of symbols 0 and 1 — the initial pattern of lights.

The third line contains a string b of length n consisting of symbols 0 and 1 — the desired pattern of lights.

It is guaranteed that the sum of n does not exceed 10^5.

Output
For each test case, output the minimum number of operations required to transform a to b, or −1 if it’s impossible.

Example
input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
5
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
9
001011011
011010101

output

1
2
3
4
5
0
1
-1
3
4

题目大意:给一串蜡烛,有的亮有的灭,要求你使得这串蜡烛所处的状态和要求的状态相同。0和1分别表示蜡烛的亮和灭。现在可以进行一种操作:保持一盏亮着的蜡烛状态不变,并使其他所有蜡烛变为它现在相反的状态。要求最少次数操作使得达成上述目的。
乍一看感觉很复杂,但是仔细思考我们发现:我们可以通过两步操作交换一盏亮着的蜡烛和一盏暗着的蜡烛的状态;以及我们可以通过一步操作使得现在亮着的蜡烛的个数变为先前暗着的蜡烛的个数+1。那么我们可以得出结论:当要求状态的亮着的蜡烛个数b不等于原状态亮着的蜡烛的个数a、且b不等于原状态暗着的蜡烛个数p+1时,则不可能达到要求状态。此时要求解问题就很简单了,详见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int all[N],target[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int lit=0,un=0,litt=0,unn=0,res=0,dif=0,difa=0,difb=0,diffa=0,diffb=0,diff=0;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
scanf("%1d",&all[i]);//格式化输入方便判断
lit+=all[i];//记录原来亮着的
un+=(all[i]^1);//记录原来暗着的
}
for (int i = 0; i < n; i++)
{
scanf("%1d",&target[i]);
litt+=target[i];//记录要求亮着的
unn+=(target[i]^1);//记录要求暗着的
if (all[i]!=target[i])
{
dif++;//记录不改变总亮灯数时的不同个数
}
else
{
diff++;//记录改变总亮灯数时的不同个数
}
}
if (((litt!=lit)&&(litt!=un+1)))//不满足条件即不可能
{
cout << "-1" << endl;
}
else
{
if (un+1==lit)//如果两种情况的亮灯数都满足条件,则输出最小值
{
res=min(dif,diff);
}
else
{
if (litt==lit)//原亮灯数等于要求状态亮灯数的情况
{
res=dif;
}
else//改变后满足条件的情况
{
res=diff;
}
}
cout << res << endl;
}
}
return 0;//华丽结束
}

然后就水完了一篇博客
以后可能会经常参加这种比赛,加油到以后某一天说不定就能AK了呢想peach