CodeforcesRound#512

CodeforcesRound#512

A.In Search of an Easy Problem

题目大意 : 有\(1\)输出\(HARD\), 否则输出\(EASY\)

题解 : 同题面

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

int n, judge = 1;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read();

for(register int i = 1; i <= n; i++) {
int x = read();
if(x) judge = false;
}

if(judge) puts("EASY");
else puts("HARD");
return 0;
}

B.Vasya and Cornfield

题目大意 : 给定你一个矩形的四个角, 每次询问一个点是否在这个矩形内

题解 : 他这个矩形的四条边都很特殊, 斜率都是\(1\)\(-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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

int n, d, m;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read(), d = read(), m = read();
for (register int i = 1; i <= m; i++) {
int x = read(), y = read();
if (x + y < d || x + y > 2 * n - d) printf("NO\n");
else if (y - x < -d || y - x > d) printf("NO\n");
else printf("YES\n");
}
return 0;
}

C.Vasya and Golden Ticket

题目大意 : 给你一个序列, 序列中的元素都小于等于\(9\), 大于等于\(0\), 问你时候存在一种划分方案使得每个划分的区间内的元素的和都相等, 要求划分出的区间连续

题解 : 直接考虑枚举将这个序列划分成\(con\)个区间, 然后顺着累加每一个元素, 如果当前累积的和乘以\(con\)大于整个序列的和直接\(break\), 如果乘起来等于这个序列的和就将累积的和清零, 如果最后可以直接输出\(YES\)就好了

然后就\(A\)

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

int a[maxn], s[maxn], n;

char str[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read();
scanf("%s", str + 1);

for(register int i = 1; i <= n; i++) a[i] = str[i] - '0';

for(register int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

int con = 2;

while(con <= n) {
int o = 0, judge = 1;
//if((s[n] % con) != 0) {con++; continue;}
for(register int i = 1; i <= n; i++) {
o += a[i];
if(o * con == s[n]) o = 0;
else if(o * con > s[n]) {
judge = 0; break;
}
}
if(judge) {puts("YES"); return 0;}
con++;
} puts("NO");
return 0;
}

D.Vasya and Triangle

题目大意 : 给你一个\(n\), 一个\(m\), 一个\(k\), 要求在\((0, 0), (n, 0), (0,m), (n, m)\)这四个点构成的矩形内找到三个整点使得这三个点构成的三角形的面积等于\(\frac {n \cdot m}{k}\)

题解 : 如果这三个点的坐标为\((x_0, y_0), (x_1, y_1), (x_2, y_2)\), 它们构成三角形的面积为 \[ \large{|}\frac{(x_1-x_0) \cdot(y_1-y_0) - (x_2-x_0) \cdot (y_2-y_0)}{2}\large{|} \] 那么如果\(2 \cdot n \cdot m \ne 0 (mod \ \ k)\), 就无解, 否则有解

我们考虑构造一组\((a, b)\)使得\(a \cdot b = \frac{2 \cdot n \cdot m}{k}\), 并且\((a \le n \&\& b \le m) || (a \le m \&\& b \le n)\)

\(P = \frac{2 \cdot n \cdot m}{k}\), \(a = gcd(n, P), b = \frac{P}{a}\), 如果此时满足上述条件那么直接输出就好了

否则我们考虑将\(m\)的每一个素因子都往\(a\)上乘, 每乘一次就判断一下是否满足条件

关于正确性的证明 : 不会

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
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

LL n, m, k, Q, P;

inline LL read() {
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void judge(LL Q, LL P) {
if((Q <= n && P / Q <= m) || (Q <= m && P / Q <= n)) {
puts("YES");
cout << "0 0" << endl;
if(Q <= n && P / Q <= m) {
cout << Q << " 0" << endl;
cout << "0 " << P / Q << endl;
}
else {
cout << P / Q << " 0" << endl;
cout << "0 " << Q << endl;
} exit(0);
}
}

inline void solve(LL n) {
LL z = n;
for(register LL i = 2; i * i <= z; i++) {
if(z % i == 0) {
int cnt = 0;
while(z % i == 0) z /= i, cnt++;
for(register int j = 1; j <= cnt; j++)
if(Q % i == 0) {
judge(Q, P);
Q /= i;
judge(Q, P);
}
}
}

judge(Q, P);

if(Q % z == 0) {
judge(Q, P);
Q /= z;
judge(Q, P);
}
}

int main() {
n = read(); m = read(); k = read();

if(n * m * 2 % k != 0) {puts("NO"); return 0;}

Q = n * m * 2 / k, P = Q;

solve(n); solve(m); Q = P;

solve(m); solve(n);

puts("NO");
return 0;
}

E.Vasya and Good Sequences

题目大意 : 给你一个长度为\(N\)的序列, 序列中的每个元素的二进制下的一的位置可以互换, 从而变成另一个数

问你有多少个区间\([l,r]\)满足 : \[ a_l \oplus a_{l+1} \oplus a_{l+2} \oplus...\oplus a_r = 0 \] 题解 : 设\(b_i\)\(a_i\)在二进制下一的个数

我们可以转化一下问题, 题目就是要我们求出有多少个区间满足 \[ (\sum_{i = l} ^{i \le r} b_i) = 0 (mod \ \ 2) \& \& \ \ 2 \cdot max\{b_i\} \le \sum_{i = l} ^{i \le r} b_i \] 我们考虑到\(1 \le a_i \le 10^{18}\)所以\(1 \le b_i \le 64\), 所以对于每一个左端点, 我们向左暴力扫\(65\)个数, (不放心就\(128\)个数, 反正给了2s), 就可一保证在此之后的右端点一定是满足第二个条件的, 然后直接拿前缀和统计一下\(b_i\)的前缀和中有多少个是偶数, 有多少个是奇数

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 5e5 + 5;

LL n, b[maxn], s[maxn], S[2][maxn];

LL a[maxn], ans;

inline LL read() {
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int main() {
n = read();

for(register int i = 1; i <= n; i++) {
a[i] = read();
for(register int j = 0; (1ll << j) <= a[i]; j++)
if(a[i] & (1ll << j)) b[i]++;
s[i] = s[i - 1] + b[i];
S[0][i] = S[0][i - 1] + ((s[i] & 1) == 0);
S[1][i] = S[1][i - 1] + ((s[i] & 1) == 1);
}

//cerr << S[0][n] + S[1][n] << endl;

for(register int i = 1; i <= n; i++) {
LL maxv = b[i];
for(register int j = i + 1; j <= min(i + 128, (int)n); j++) {
maxv = max(maxv, b[j]);
if((s[j] - s[i - 1]) % 2 == 0 && maxv * 2 <= s[j] - s[i - 1])
ans++;
}

if(i + 128 < n) ans += (S[s[i - 1] & 1][n] - S[s[i - 1] & 1][i + 128]);
} cout << ans;
return 0;
}

F.Putting Boxes Together

题目大意 : 给定\(N\)个二元组\((a_i, w_i)\), 每次询问一个区间\([l, r]\), 要求输出 \[ \sum_{i = l}^{i \le r} w_i \cdot |x + i - a_i| \] 这个式子的最小值对\(10^9 + 7\)取膜后的答案

\(PS\) : 保证\(a_i < a_{i + 1}\)

题解 : 设\(g_i = a_i - i\), 上述式子变为 : \[ \sum_{i = l}^{i \le r} w_i \cdot |x - g_i| \] 很显然我们可以将后面那个东西看成数轴上两个点的距离, \(w_i\)这个系数可以抽象成\(w_i\)个点摞在一起

最后问题被抽象为了数轴上有\(\sum w_i\)个点, 要求出一个点使得这个点到\(\sum w_i\)的距离和最小

这个点很显然就是\(\sum w_i\)个点排序后的最中间的那个点

所以每一次询问我们直接求出一个最小的\(pos\)使得 \[ 2 \cdot (\sum _{i = l} ^ {i \le pos} w_i) \ge \sum _ {i = l} ^ {i \le r} w_i \] 求出这个位置后, 在这个位置左边的和右边的分开处理(可以去掉绝对值), 就好了

然后这道题很良心的是它保证了\(g_i\)有序, 所以我们可以直接二分套\(BIT\)或者在线段树上二分, 但是如果\(g_i\)无序, 我们可以考虑带修主席树, 也是可以维护上面那个式子的

代码 :

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
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 5;
const int P = 1e9 + 7;

int n, m, a[maxn], w[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int dec(int x, int y) {x -= y; return x < 0 ? x + P : x;}
inline int mul(int x, int y) {LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}

struct BIT {
LL C[maxn];
inline void modify(int p, int x) {while(p <= n) {C[p] += x; p += (-p & p);}}
inline LL query(int p) {LL rnt = 0; while(p) {rnt += C[p]; p -= (-p & p);} return rnt;}
}T;

struct _BIT {
int C[maxn];
inline void modify(int p, int x) {while(p <= n) {C[p] = pls(C[p], x); p += (-p & p);}}
inline int query(int p) {int rnt = 0; while(p) {rnt = pls(rnt, C[p]); p -= (-p & p);} return rnt;}
}T0;

inline int getpos(int l, int r) {
LL S = T.query(r) - T.query(l - 1), tmp = 0;
int mid = (l + r) / 2, ans = 0, L = l;
while(l <= r) {
mid = (l + r) / 2;
tmp = T.query(mid) - T.query(L - 1);
if(tmp * 2 >= S) r = mid - 1, ans = mid;
else l = mid + 1;
} return ans;
}

int main() {
n = read(); m = read();

for(register int i = 1; i <= n; i++) a[i] = read() - i;
for(register int i = 1; i <= n; i++) {
w[i] = read(); T.modify(i, w[i]);
T0.modify(i, mul(a[i], w[i]));
}

for(register int i = 1; i <= m; i++) {
int l = read(), r = read();
if(l < 0) {
T.modify(-l, r - w[-l]);
T0.modify(-l, dec(mul(a[-l], r), mul(a[-l], w[-l])));
w[-l] = r;
}
else {
int pos = getpos(l, r);
int S0 = (T.query(pos) - T.query(l - 1) + P) % P;
int S1 = (T.query(r) - T.query(pos) + P) % P;
int P1 = dec(mul(S0, a[pos]), dec(T0.query(pos), T0.query(l - 1)));
int P2 = dec(dec(T0.query(r), T0.query(pos)), mul(S1, a[pos]));
printf("%d\n", pls(P1, P2));
}
}
return 0;
}