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; }
