JZTXT

abc318

发布时间 2023-09-03 17:08:46作者: lightsong

A - Full Moon

https://atcoder.jp/contests/abc318/tasks/abc318_a

Problem Statement

Takahashi likes full moons.

Let today be day

1. The first day on or after today on which he can see a full moon is day M. After that, he can see a full moon every P days, that is, on day M+P, day

M+2P, and so on.

Find the number of days between day

1 and day N, inclusive, on which he can see a full moon.

 

解析

从M点开始计数，每隔P天记一次满月， 直到超过结束日N

 

Code

https://atcoder.jp/contests/abc318/submissions/45139743

int n, m, p;

int main()
{
    cin >> n >> m >> p;

    int count = 0;
    while(true){
        if (m>n){
            break;
        }
        
        count++;
        m += p;
    }

    cout << count << '\n';

    return 0;
}

 

B - Overlapping sheets

https://atcoder.jp/contests/abc318/tasks/abc318_b

求三块矩形覆盖格子数

 

 

解析

有重叠区域， 对于重叠区域计数，需要保证只计算一次。

以每个格子的左下的点作为格子的计数点，

使用二维map计数，第一维度以x作为key，第二维度以y作为key

 

Code

https://atcoder.jp/contests/abc318/submissions/45156595

map<int, map<int, bool>> flags;
int n;

int main()
{
    cin >> n;

    for(int i=0; i<n; i++){
        int a, b, c, d;
        
        cin >> a >> b >> c >> d;
        
        for(int x=a; x<b; x++){
            for(int y=c; y<d; y++){
                flags[x][y] = true;
            }
        }
    }

    int count = 0;
    for(auto x : flags){
        map<int, bool>& ypoints = x.second;
        count += ypoints.size();
    }

    cout << count << "\n";

    return 0;
}

 

C - Blue Spring

https://atcoder.jp/contests/abc318/tasks/abc318_c

Sample Input 1

Copy
5 2 10
7 1 6 3 6

Sample Output 1

Copy
20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be

(10×1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

 

解析

每天的费用为Fi元，

如果购买多天通行证，可以使用D天，总花费P元

该不该使用通行证， 需要进行判断？ 将每天的费用最大的三个加起来， 跟P元比较，

如果比P元小，应该使用通行证， 否则使用每天的费用。

 

Code

https://atcoder.jp/contests/abc318/submissions/45188710

LL n, d, p;
vector<LL> f;

int main()
{
    cin >> n >> d >> p;
    for(LL i=0; i<n; i++){
        LL temp;
        cin >> temp;
        f.push_back(temp);
    }

    sort(f.begin(), f.end());
    reverse(f.begin(), f.end());
    
//    for(LL i=0; i<n; i++){
//        cout << f[i] << " ";
//    }
//    cout << "\n";

    LL batch_sum = 0;
    vector<LL> batches;
    for(LL i=0; i<n; i++){
        batch_sum += f[i];
        
        if (i+1 == n || (i+1)%d == 0){
            batches.push_back(batch_sum);
            
            batch_sum = 0;
        }
    }

    reverse(batches.begin(), batches.end());

//    for(LL i=0; i<batches.size(); i++){
//        cout << batches[i] << " ";
//    }
//    cout << "\n";

    LL uppos = upper_bound(batches.begin(), batches.end(), p) - batches.begin();
    LL sum = 0;
    for(LL i=0; i<uppos; i++){
        sum += batches[i];
    }

    if (uppos < batches.size()){
        sum += p * (batches.size() - uppos);
    }

    cout << sum << "\n";

    return 0;
}