题意:一张折纸需要用 2 张红纸、5 张绿纸和 8 张蓝纸,现在需要 n 张折纸,已知无数本三种颜色的书,每本颜色书由 k 张相应颜色的纸组成,现在让你确定至少需要多少本书才能得到这 n 张折纸
思路:分别计算不同颜色的纸需要多少书然后加和,书只能多买不能少买用个向上取整的函数即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| #include <bits/stdc++.h> using namespace std; typedef long long ll;
signed main() { ios::sync_with_stdio(false), cin.tie(0); ll n, k; cin >> n >> k; ll a = n * 2, b = n * 5, c = n * 8; ll ans = ceil(a * 1.0 / k) + ceil(b * 1.0 / k) + ceil(c * 1.0 / k); cout << ans << endl; return 0; }
|
题意:有个长度为 1e9 的数列,它的权值 a[i]=i*(-1)i,计算 [l,r]
区间内的权值和
思路:a1=-1 a2=2 a3=-3 a4=4 a5=-5 ...
,如果 n 为偶数那么权值和正好是从 1 开始两两项加和得 n/2,如果 n 为奇数那么就是 n/2-n,区间权值和再用个前缀和相减
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; typedef long long ll;
ll cal(ll x) { if (x % 2 == 0) return x / 2; else return (x - 1) / 2 - x; }
signed main() { ios::sync_with_stdio(false), cin.tie(0); int t; cin >> t; while (t--) { int l, r; cin >> l >> r; ll ans = cal(r) - cal(l - 1); cout << ans << endl; } return 0; }
|
题意:有一个 n*m 的棋盘,它的上色方式如下图,现在要涂两层油漆,第一层油漆是白色,第二层油漆是黑色(如果和第一层油漆重合就覆盖掉第一层油漆),两层油漆给出左上角和右下角的两个坐标 (x1,y1) (x2,y2) (x3,y3) (x4,y4)
,注意 x 代表的是所处的列数,y 代表的是所处的行数,请你确定这个棋盘涂完两层油漆后的白块和黑块的数量
思路:首先根据容斥原理我们只要知道白块的数量了用整个棋盘的面积减去就是白块的数量就是黑块的数量了
- 起初棋盘如果面积是偶数那么白块数量就是一半 n*m/2,否则比黑块多一块 n*m/2+1
- 先不考虑重叠的问题统计两层油漆分别对白块的影响
- 第一层白漆会让其内部的黑块全部变为白块,如果覆盖的面积是偶数那么白块就增加一半,如果覆盖面积是奇数的话就需要判断这个油漆覆盖的面积是黑块多一块还是白块多一块,找规律我们不难发现黑块的位置都是
x%2!=y%2
,白块的位置都是 x%2==y%2
,如果油漆左上角是黑块那么就是黑块多一块,否则就是白块多一块
- 第二层黑漆会让其内部的白块全部变为黑块,规律和上述一样
- 再考虑是否会重叠的问题,如果两层油漆真的重叠了那么第一层油漆被染白的黑块实际上又变回了黑块,所以我们需要减去在重叠部分多统计的白块
找重叠区域的方法:取两层油漆左上角的 x 最大值和 y 的最大值作为重叠区域的左上角坐标,取两层油漆右下角的 x 的最小值和 y 的最小值作为重叠区域的右下角坐标,我们可以先用最普通的情况总结规律再用其他情况验证
这类题本身并不难,只要划分好计算步骤并处理好相应的细节以九年义务教育的水平应该是可以做出来的
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
| #include <bits/stdc++.h> using namespace std; typedef long long ll;
signed main() { ios::sync_with_stdio(false), cin.tie(0); ll t; cin >> t; while (t--) { ll n, m; cin >> n >> m; ll cnt; if (n * m % 2 == 0) cnt = n * m / 2; else cnt = n * m / 2 + 1; ll x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; ll x3, x4, y3, y4; cin >> x3 >> y3 >> x4 >> y4; ll w = x2 - x1 + 1, h = y2 - y1 + 1; if (w % 2 == 1 && h % 2 == 1 && x1 % 2 == y1 % 2) cnt += w * h / 2; else cnt += (w * h + 1) / 2; w = x4 - x3 + 1, h = y4 - y3 + 1; if (w % 2 == 1 && h % 2 == 1 && x3 % 2 == y3 % 2) cnt -= (w * h + 1) / 2; else cnt -= (w * h) / 2; int xx1 = max(x1, x3), yy1 = max(y1, y3), xx2 = min(x2, x4), yy2 = min(y2, y4); if (xx1 <= xx2 && yy1 <= yy2) { w = xx2 - xx1 + 1, h = yy2 - yy1 + 1; if (w % 2 && h % 2 && xx1 % 2 == yy1 % 2) cnt -= (w * h) / 2; else cnt -= (w * h + 1) / 2; } cout << cnt << ' ' << n * m - cnt << endl; } return 0; }
|