Codeforces Round #524 (Div. 2)（前三题题解）

这场比赛手速场+数学场，像我这样读题都读不大懂的蒟蒻表示呵呵呵。

第四题搞了半天，大概想出来了，但来不及（中途家里网炸了）查错，于是我交了两次丢了100分。幸亏这次没有掉rating。

比赛传送门：https://codeforces.com/contest/1080。

A.Petya and Origami

题意：Petya要发出n张邀请函，每张请函需要2张红纸，5张绿纸，8张蓝纸。现在商店里有一些不同颜色的笔记本，每本中有k张颜色相同的纸，求最少要买几本笔记本。

这题就是一道模拟题，算出每种纸的数量，答案加上数量除以k，对于每张颜色如果还有余数，答案加一。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(int x = l; x <= r; x++)
 7 #define repd(x, r, l) for(int x = r; x >= l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 10000007;
22 int lowbit(int x){ return x & -x; }
23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p; } return x; }
24 //head by DYH
25 
26 int main(){
27     int n, k;
28     scanf("%d%d", &n, &k);
29     int a = n * 2, b = n * 5, c = n * 8;
30     int ans = a / k + b / k + c / k;
31     if(a % k) ans++;
32     if(b % k) ans++;
33     if(c % k) ans++;
34     printf("%d
", ans);
35     return 0;
36 }

View Code Problem-A

B. Margarite and the best present

题意：有一个序列，a_i = (-1)ⁱ * i，现在有t个询问，问你a_x~y的和。

看到这题想到了小学奥数题，对于每个询问只要求a_1~y - a_1~x-1就好了，至于a_1～i就很好求了，当i是偶数就是i / 2, 否则是i - i / 2。搞不懂为什么有人在luogu群上问这题是不是莫队（蒟蒻表示压根不会莫队）。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(int x = l; x <= r; x++)
 7 #define repd(x, r, l) for(int x = r; x >= l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN
13 #define fi first
14 #define se second
15 #define SZ(x) ((int)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<int> vi;
19 typedef pair<int, int> pii;
20 const int INF = 1 << 30;
21 const int p = 10000007;
22 int lowbit(int x){ return x & -x; }
23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p; } return x; }
24 //head by DYH
25 
26 int solve(int x){
27     int res = x / 2;
28     if(x % 2 == 1) res -= x;
29     return res;
30 }
31 
32 int main(){
33     int t;
34     scanf("%d", &t);
35     rep(times, 1, t){
36         int x, y;
37         scanf("%d%d", &x, &y);
38         int ans = solve(y) - solve(x - 1);
39         printf("%d
", ans);
40     }
41     return 0;
42 }

View Code Problem-B

C.Masha and two friends

题意：有一个n * m的黑白相间的棋盘，(1, 1)为白色。现在把(x₁, y₁)到(x₂, y₂)这个矩阵涂白(x₁ <= x₂, y₁ <= y₂)，再把(x₃, y₃)到(x₄, y₄)这个矩阵涂黑(x₃ <= x₄, y₃ <= y₄)。现在问你有多少个黑格子和白格子。注：有多组数据。

A 、B两题都挺水，C、D开始就是数学题了，感觉自己好菜。

要求求黑格子和白格子，只要求其中一个就好了，另一个就是拿总个数减一下，我就是求白格子的个数。

这题看上去很烦（其实打起来也很烦），但其实就是原有的个数 + 第一次涂白的黑格子个数 - 第二次涂黑的白格子个数。

第一次涂白的黑格子数就是(x₁, y₁)到(x₂,y₂)这个矩阵中原有的黑格数（然而我统计了白格子个数再拿总数减）。

统计白格子的个数方法就是总的格子个数 / 2，如果总个数是奇数，就看左下角是否是白格子((x + y) % 2 == 0)。求黑格子数也是一样。

求第二次涂黑的白格子个数是(x₃, y₃)到(x₄, y₄)这个矩阵原有的白格数 + 两次涂色相交的矩阵中原来黑格子的个数（因这些格子已经被涂成白色，已经被算入答案，要减掉）。

求区间内原有的黑白格数我就不再说了，主要就是求相交的矩阵。

先判断有无相交：

x2 < x3 || x1 > x4 || y2 < y3 || y1 > y4

可以画个图方便理解。

然后就是相交的矩阵的坐标。（用X₁, Y₁, X₂, Y₂表示）

X1 = max(x1, x3), X2 = min(x2, x4), Y1 = max(y1, y3), Y2 = min(y2, y4)

这题就这样草率的讲完了，有不理解可以看代码画几个图模拟下。

代码如下

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #define rep(x, l, r) for(LL x = l; x <= r; x++)
 7 #define repd(x, r, l) for(LL x = r; x >= l; x--)
 8 #define clr(x,y) memset(x, y, sizeof(x))
 9 #define all(x) x.begin(), x.end()
10 #define pb push_back
11 #define mp make_pair
12 #define MAXN
13 #define fi first
14 #define se second
15 #define SZ(x) ((LL)x.size())
16 using namespace std;
17 typedef long long LL;
18 typedef vector<LL> vi;
19 typedef pair<LL, LL> pii;
20 const LL INF = 1 << 30;
21 const LL p = 10000007;
22 LL lowbit(LL x){ return x & -x; }
23 LL fast_power(LL a, LL b){ LL x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p; } return x; }
24 //head by DYH
25 
26 LL judge(LL x1, LL y1, LL x2, LL y2){
27     LL x = x2 - x1 + 1, y = y2 - y1 + 1;
28     LL res = x * y / 2;
29     if(x * y % 2 == 1 && (x1 + y1) % 2 == 0) res++;
30     return res;
31 }
32 
33 LL check(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3, LL x4, LL y4){
34     if(x2 < x3 || x1 > x4 || y2 < y3 || y1 > y4) return 0;
35     LL X1 = max(x1, x3), X2 = min(x2, x4), Y1 = max(y1, y3), Y2 = min(y2, y4);
36     return (X2 - X1 + 1) * (Y2 - Y1 + 1) - judge(X1, Y1, X2, Y2);
37 }
38 
39 int main(){
40     LL t;
41     scanf("%I64d", &t);
42     rep(times, 1, t){
43         LL n, m;
44         scanf("%I64d%I64d", &n, &m);
45         LL x1, y1, x2, y2, x3, y3, x4, y4;
46         scanf("%lI64d%I64d%Id%I64d%I64d%I64d%I64d%I64d", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
47         LL ans = judge(1, 1, n, m);
48         ans += (x2 - x1 + 1) * (y2 - y1 + 1) - judge(x1, y1, x2, y2);
49         ans -= check(x1, y1, x2, y2, x3, y3, x4, y4) + judge(x3, y3, x4, y4);
50         printf("%I64d %I64d
", ans, n * m - ans);
51     }
52     return 0;
53 }

View Code Problem-C

完成日期：2018-11-25 04:05:27