这场比赛手速场 + 数学场, 像我这样读题都读不大懂的蒟蒻表示呵呵呵.
第四题搞了半天, 大概想出来了, 但来不及 (中途家里网炸了) 查错, 于是我交了两次丢了 100 分. 幸亏这次没有掉 rating.
比赛传送门: https://codeforces.com/contest/1080.
A.Petya and Origami
题意: Petya 要发出 n 张邀请函, 每张请函需要 2 张红纸, 5 张绿纸, 8 张蓝纸. 现在商店里有一些不同颜色的笔记本, 每本中有 k 张颜色相同的纸, 求最少要买几本笔记本.
这题就是一道模拟题, 算出每种纸的数量, 答案加上数量除以 k, 对于每张颜色如果还有余数, 答案加一.
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x,y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long LL;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 10000007;
- int lowbit(int x){ return x & -x; }
- 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; }
- //head by DYH
- int main(){
- int n, k;
- scanf("%d%d", &n, &k);
- int a = n * 2, b = n * 5, c = n * 8;
- int ans = a / k + b / k + c / k;
- if(a % k) ans++;
- if(b % k) ans++;
- if(c % k) ans++;
- printf("%d\n", ans);
- return 0;
- }
- View Code Problem-A
- B. Margarite and the best present
题意: 有一个序列, ai = (-1)i * i, 现在有 t 个询问, 问你 ax~y 的和.
看到这题想到了小学奥数题, 对于每个询问只要求 a1~y - a1~x-1 就好了, 至于 a1~i 就很好求了, 当 i 是偶数就是 i / 2, 否则是 i - i / 2. 搞不懂为什么有人在 luogu 群上问这题是不是莫队(蒟蒻表示压根不会莫队).
代码如下:
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(int x = l; x <= r; x++)
- #define repd(x, r, l) for(int x = r; x>= l; x--)
- #define clr(x,y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN
- #define fi first
- #define se second
- #define SZ(x) ((int)x.size())
- using namespace std;
- typedef long long LL;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- const int INF = 1 <<30;
- const int p = 10000007;
- int lowbit(int x){ return x & -x; }
- 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; }
- //head by DYH
- int solve(int x){
- int res = x / 2;
- if(x % 2 == 1) res -= x;
- return res;
- }
- int main(){
- int t;
- scanf("%d", &t);
- rep(times, 1, t){
- int x, y;
- scanf("%d%d", &x, &y);
- int ans = solve(y) - solve(x - 1);
- printf("%d\n", ans);
- }
- return 0;
- }
- View Code Problem-B
- C.Masha and two friends
题意: 有一个 n * m 的黑白相间的棋盘,(1, 1)为白色. 现在把 (x1, y1) 到(x2, y2)这个矩阵涂白 (x1 <= x2, y1 <= y2), 再把(x3, y3) 到(x4, y4)这个矩阵涂黑(x3 <= x4, y3 <= y4). 现在问你有多少个黑格子和白格子. 注: 有多组数据.
A ,B 两题都挺水, C,D 开始就是数学题了, 感觉自己好菜.
要求求黑格子和白格子, 只要求其中一个就好了, 另一个就是拿总个数减一下, 我就是求白格子的个数.
这题看上去很烦(其实打起来也很烦), 但其实就是原有的个数 + 第一次涂白的黑格子个数 - 第二次涂黑的白格子个数.
第一次涂白的黑格子数就是 (x1, y1) 到(x2,y2)这个矩阵中原有的黑格数(然而我统计了白格子个数再拿总数减).
统计白格子的个数方法就是总的格子个数 / 2, 如果总个数是奇数, 就看左下角是否是白格子((x + y) % 2 == 0). 求黑格子数也是一样.
求第二次涂黑的白格子个数是 (x3, y3) 到(x4, y4)这个矩阵原有的白格数 + 两次涂色相交的矩阵中原来黑格子的个数(因这些格子已经被涂成白色, 已经被算入答案, 要减掉).
求区间内原有的黑白格数我就不再说了, 主要就是求相交的矩阵.
先判断有无相交:
x2 <x3 || x1> x4 || y2 <y3 || y1> y4
可以画个图方便理解.
然后就是相交的矩阵的坐标.(用 X1, Y1, X2, Y2 表示)
X1 = max(x1, x3), X2 = min(x2, x4), Y1 = max(y1, y3), Y2 = min(y2, y4)
这题就这样草率的讲完了, 有不理解可以看代码画几个图模拟下.
代码如下
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #define rep(x, l, r) for(LL x = l; x <= r; x++)
- #define repd(x, r, l) for(LL x = r; x>= l; x--)
- #define clr(x,y) memset(x, y, sizeof(x))
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define mp make_pair
- #define MAXN
- #define fi first
- #define se second
- #define SZ(x) ((LL)x.size())
- using namespace std;
- typedef long long LL;
- typedef vector<LL> vi;
- typedef pair<LL, LL> pii;
- const LL INF = 1 <<30;
- const LL p = 10000007;
- LL lowbit(LL x){ return x & -x; }
- 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; }
- //head by DYH
- LL judge(LL x1, LL y1, LL x2, LL y2){
- LL x = x2 - x1 + 1, y = y2 - y1 + 1;
- LL res = x * y / 2;
- if(x * y % 2 == 1 && (x1 + y1) % 2 == 0) res++;
- return res;
- }
- LL check(LL x1, LL y1, LL x2, LL y2, LL x3, LL y3, LL x4, LL y4){
- if(x2 <x3 || x1> x4 || y2 <y3 || y1> y4) return 0;
- LL X1 = max(x1, x3), X2 = min(x2, x4), Y1 = max(y1, y3), Y2 = min(y2, y4);
- return (X2 - X1 + 1) * (Y2 - Y1 + 1) - judge(X1, Y1, X2, Y2);
- }
- int main(){
- LL t;
- scanf("%I64d", &t);
- rep(times, 1, t){
- LL n, m;
- scanf("%I64d%I64d", &n, &m);
- LL x1, y1, x2, y2, x3, y3, x4, y4;
- scanf("%lI64d%I64d%Id%I64d%I64d%I64d%I64d%I64d", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
- LL ans = judge(1, 1, n, m);
- ans += (x2 - x1 + 1) * (y2 - y1 + 1) - judge(x1, y1, x2, y2);
- ans -= check(x1, y1, x2, y2, x3, y3, x4, y4) + judge(x3, y3, x4, y4);
- printf("%I64d %I64d\n", ans, n * m - ans);
- }
- return 0;
- }
- View Code Problem-C
完成日期: 2018-11-25 04:05:27
来源: http://www.bubuko.com/infodetail-2860041.html