Codeforces Round 524(Div. 2)
- 2020 年 2 月 18 日
- 筆記
题目大意:
需要邀请n个人来参加派对.需要制作邀请卡.一张邀请卡需要2红, 5绿, 8蓝. 每个笔记本有k个某种颜色.求最少需要多少个笔记本.
题解
答案显示是$ lceil 2n/k rceil + lceil 5n/k rceil + lceil 8n/k rceil $
#include <bits/stdc++.h> using namespace std; int n,k; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; int x = 2*n/k; if(x * k < 2*n) ++x; int y = 5*n/k; if(y * k < 5*n) ++y; int z = 8*n/k; if(z * k < 8*n) ++z; cout << x + y + z<< endl; return 0; }
B. Margarite and the best present
题目大意:
有一个序列. $a_i = i*(-1)^i$. 给定l, r. 求$sum_{i = l} ^ ra_i$.
题解
将这个序列看成两个等差序列.利用等差序列求和公式即可.
#include <bits/stdc++.h> using namespace std; int q; int l,r; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); while(cin >> q){ while(q--){ cin >> l >> r; int len = r - l + 1; int x = len/2, y = len - x; int ans = 0, ans1, ans2; ans1 = (x-y)*(l+r)/2; ans2 = (-y*(l+r-1) + x*(l+r+1))/2; if(l&1){ if(r&1){ ans = ans1; } else { ans = ans2; } } else { if(r&1){ ans = -ans2; } else { ans = -ans1; } } cout << ans << endl; } } return 0; }
C. Masha and two friends
题目大意:
AC
一开始有一个棋盘有黑白两种颜色。一开始将区域一(x1 y1) (x2 x2)这个区域(左下角和右下角的点构成一个矩形区域)全部涂成白色。然后将区域二(x3 y3) (x4 y4)这个区域全部涂成黑色.求最后棋盘上黑白的格子各有多少.
题解
计算区域一(x1 y1) (x2 y2)区域中一开始有白色格子w1 黑色格子b1 计算区域二(x3 y3) (x4 y4)区域中一开始有白色格子w3 黑色格子b3 计算上面两个区域相交的区域三(x5 y5) (x6 x6)区域中一开始有白色格子w2 黑色格子b2
一开始棋盘上有orw个白格子.orb个黑格子.
- 区域一涂成白色. orw += b1, orb -= b1
- 区域二和区域一二相交的地方区域三涂成黑色 2.1 获得区域二的白色 orb += w3, orw -= w3 2.2 获得相交部分的黑色 orb += b2, orw -= b2
在orb基础上增加的黑格子的数量是w3 + b2 – b1 对应的.在orw基础上减少的白格子的数量是-(w3 + b2 – b1)
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL n,m; LL bans, wans; LL x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4,x_5,y_5,x_6,y_6; LL b_1,b_2,b_3,w_1,w_2,w_3,orw,orb; int t; // 统计区间x1,y1,x2,y2之间黑白的个数 void tot(LL x_1, LL y_1, LL x_2, LL y_2, LL &w, LL &b){ LL x = x_2-x_1+1; LL y = y_2-y_1+1; LL l = (x*y)/2; w = l; b = l; if(x&1 && y&1) { if((x_1+y_1)&1) { // b色 ++b; } else ++w; } } int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); cin >> t; while(t--){ cin >> n >> m; cin >> x_1 >> y_1 >> x_2 >> y_2 >> x_3 >> y_3 >> x_4 >> y_4; x_5 = max(x_1, x_3); y_5 = max(y_1, y_3); x_6 = min(x_2, x_4); y_6 = min(y_2, y_4); tot(x_1, y_1, x_2, y_2, w_1, b_1); tot(x_3, y_3, x_4, y_4, w_3, b_3); w_2 = b_2 = 0; if(x_6 >= x_5 && y_6 >= y_5) tot(x_5, y_5, x_6, y_6, w_2, b_2); //cout << "w_1=" << w_1 << " " << b_1 << endl; // cout << "w_2=" << w_2 << " " << b_2 << endl; //cout << "w_3=" << w_3 << " " << b_3 << endl; orb = n*m/2; orw = n*m - orb; // cout << orw << " " << orb << endl; orb += (w_3 - b_1 + b_2); orw += (b_1 - w_3 - b_2); cout << orw << " " << orb << endl; } return 0; }
