Codeforces Round 524(Div. 2)

xiaohejun

发布于 2020-02-18 09:23:57

2770

发布于 2020-02-18 09:23:57

文章被收录于专栏：xiaohejun的算法知识分享xiaohejun的算法知识分享

题目大意:

需要邀请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;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-11-242，如有侵权请联系 cloudcommunity@tencent.com 删除

sum

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

sum

登录后参与评论

0 条评论

热度