比赛链接 / 官方题解链接
A. Non-zero
Solution
是 $0$ 的数必须加 $1$，否则乘积为 $0$；此后若和非零，则不用操作，否则操作数加一（任取一个非零数加一，由于和为零，能够保证存在至少一个正数，对其操作后乘积仍然非零）
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
int T, n, a;
int main(){
read(T);
while(T--){
read(n);
int ans = 0, sum = 0;
for(int i = 1; i <= n; i++){
read(a);
if(a == 0) a++, ans++;
sum += a;
}
printf("%d\n", ans + (sum == 0));
}
return 0;
}
|
B. Assigning to Classes
Solution
容易知道，尽量平均分最好，也就是说，若 $n$ 为奇数，就分成 $n:n$ 的两份；若 $n$ 为偶数，就分成 $n-1:n+1$ 的两份。先排序，则无论是哪种情形，两中位数都是 $a_n$ 和 $a_{n+1}$.
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 200005;
int T, n;
LL a[N];
int main(){
read(T);
while(T--){
read(n);
for(int i = 1; i <= 2 * n; i++) read(a[i]);
sort(a+1, a+2*n+1);
printf("%lld\n", a[n+1] - a[n]);
}
return 0;
}
|
C. Anu Has a Function
Solution
首先需要发现：$f(a,b)=(a|b)-b=a\&(\sim b)$，故 $f(f(\cdots f(f(a_1,a_2),a_3),\cdots a_{n-1})a_n)=a_1\&(\sim a_2)\&(\sim a_3)\&\cdots\&(\sim a_n)$. 其值与谁放在开头作为 $a_1$ 有关，剩余元素随意放即可。于是枚举放在开头的元素，计算它 $AND$ 上其他元素取反后的$AND$，后者可以通过预处理前后缀求得。
Code
>folded1
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
| #include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 100005;
int n, mark;
LL a[N], pre[N], sub[N], maxx = -1;
int main(){
read(n);
pre[0] = sub[n+1] = (1ll << 33) - 1;
for(int i = 1; i <= n; i++){
read(a[i]);
pre[i] = pre[i-1] & (~a[i]);
}
for(int i = n; i >= 1; i--){
sub[i] = sub[i+1] & (~a[i]);
LL res = a[i] & sub[i+1] & pre[i-1];
if(maxx < res){
mark = i;
maxx = res;
}
}
printf("%lld ", a[mark]);
for(int i = 1; i <= n; i++){
if(i == mark) continue;
printf("%lld ", a[i]);
}
putchar(10);
return 0;
}
|
D. Aerodynamic
Solution
手玩一些多边形后可以发现，$P$ 对边平行且相等（即中心对称）即可。
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 100005;
int n;
struct Point{
LL x, y;
}p[N];
typedef Point Vector;
Point operator - (Point A, Point B){ return (Point){A.x - B.x, A.y - B.y}; }
LL operator ^ (Vector A, Vector B){ return A.x * B.y - A.y * B.x; }
LL Length2(Vector A){ return (A.x * A.x + A.y * A.y); }
int main(){
read(n);
for(int i = 1; i <= n; i++) read(p[i].x, p[i].y);
if(n & 1){
puts("NO");
return 0;
}
else{
for(int i = 1; i <= n / 2; i++){
int j = i + n / 2;
int nxti = i + 1, nxtj = j + 1;
if(nxtj == n + 1) nxtj = 1;
Vector v1 = p[nxti] - p[i], v2 = p[nxtj] - p[j];
if((v1 ^ v2) != 0 || Length2(v1) != Length2(v2)){
puts("NO");
exit(0);
}
}
}
puts("YES");
return 0;
}
|
E. Water Balance
Solution
【参考官方题解】对于前缀和序列 $\{sum_i\}$，题设操作对应为：选择一段区间 $[l,r]$，并将其中的数 $sum_i(l\leq i\leq r)$ 更改为
这个式子实际上是 $(l-1,sum_{l-1}),(r,sum_r)$ 两点确定的直线上横坐标为 $i$ 的点的纵坐标。把所有点 $(i,sum_i)$ 画在坐标系中，发现求得下凸包即可。
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 1000005;
int n, ch[N];
LL a[N];
double s[N];
void getConvexHull(){
for(int i = 0; i <= n; i++){
while(ch[0] > 1 &&
(double)(a[ch[ch[0]]] - a[ch[ch[0]-1]]) / (ch[ch[0]] - ch[ch[0]-1]) >
(double)(a[i] - a[ch[ch[0]]]) / (i - ch[ch[0]]))
ch[0]--;
ch[++ch[0]] = i;
}
}
int main(){
read(n);
for(int i = 1; i <= n; i++) read(a[i]), a[i] += a[i-1];
getConvexHull();
int pt = 2;
for(int i = 1; i <= n; i++){
while(i > ch[pt]) pt++;
s[i] = (double)(a[ch[pt]] - a[ch[pt-1]]) / (ch[pt] - ch[pt-1]) * (i - ch[pt-1]) + a[ch[pt-1]];
}
for(int i = 1; i <= n; i++)
printf("%.9f\n", s[i] - s[i-1]);
return 0;
}
|