Codeforces Round #645 (Div. 2)

这一次的Div.2 大多数学思维。。

A. Park Lightingtime

https://codeforces.com/contest/1358/problem/A

题意：给一个n,m为边的矩形，问最少的灯使得整个矩形照亮

思路：n * m 为总区域数一个灯最多能照亮两块区域，贪心做：每次都取照亮两块

#include<bits/stdc++.h>
using namespace std;
int main() {
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t, n, m; cin >> t;
    while (t--) {
        cin >> n >> m;
        cout << (n * m) / 2 + (n *m) % 2 << endl;
    }
}

B. Maria Breaks the Self-isolation

https://codeforces.com/contest/1358/problem/B

题意：每个人有一个聚会值，要求来了的人数（算同时来的）>=聚会值，问最多能拉到多少人

思路:和之前的cfdiv2一道分配人，每个人有经验值很像，那道题是sort后从前往后尺取，这道题sort就从后往前贪心

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e5+10;
typedef long long LL;
LL a[maxn];
int main()
{
    LL t;cin>>t;
    while(t--)
    {
        LL n;cin>>n;
        for(LL i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        if(a[n]<=n) cout<<n+1<<endl;
        else 
        {
            LL ans=1;LL sum=0;
            for(LL i=n;i>=1;i--)
            {
                if(a[i]<=i)
                {
                    sum+=i;break;
                }
            }    
            cout<<sum+1<<endl;
        }    
    }
    return 0;
}

C. Celex Update

https://codeforces.com/contest/1358/problem/C

题意：求(a,b)–>(c,d)的所有路径总数中有多少路径和不同的。

思路：考虑到xy变化，移动方法一定是 (x2 - x1) * (y2 - y1) ，然后发现自己到自己也是一种 故最后+1

#include<bits/stdc++.h>
using namespace std;
int main() {
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long x1, x2, y1, y2, t;
    cin >> t; while (t--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (x2 - x1) * (y2 - y1) + 1 << endl;
    }
}

D. The Best Vacation

https://codeforces.com/contest/1358/problem/D

题意：每个月有d[i]天，有x天度假，要求连续，可以跨年，保证度假日子小于一整年。求d[i]求和最大的一段

思路：贪心+前缀和+二分

贪心：

有这么一段区间，贪A和贪B。

当bn(月的最后一天)>an-2,明显可以得出B是最优的。

那么当bnbn—->(等差递增)an>bn,而且a月比b月长且最大值更大，所以在a月的末尾作为最后一天最优。

所以贪心把末尾的一天放到月末。

然后我们利用前缀和统计每个月的天数和价值。然后枚举右端点，二分左端点，找到

sum[i]-sum[l]>x;且sum[i]-sum[l+1]<=x

那么价值为summoney[i]-summoney[l+1];再算多出的x部分–知道x多出有多少天，然后在多出的区间里用等差数列公式算出来。比如多出3天，就是那段区间的后三天的价值和。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 20;
typedef long long LL;
LL a[maxn];
LL sumday[maxn];
LL summoney[maxn];
int main(void)
{
    LL n, x; cin >> n >> x;
    for (LL i = 1; i <= n; i++)
    {
        cin >> a[i];
        sumday[i] = sumday[i - 1] + a[i];
        summoney[i] = summoney[i - 1] + (1 + a[i]) * a[i] / 2;
    }
    for (LL i = n + 1; i <= 2 * n; i++)
    {
        a[i] = a[i - n];
        sumday[i] = sumday[i - 1] + a[i];
        summoney[i] = summoney[i - 1] + (1 + a[i]) * a[i] / 2;
    }
    LL res = 0;
    for (LL i = 1; i <= 2 * n; i++)
    {
        LL l = 0; LL r = i + 1;
        //边界处理
        //找出第一个区间差大于等于x的位置 
        while (l < r)
        {
            LL mid = (l + r) >> 1;
            if (sumday[i] - sumday[mid] <= x) r = mid;
            else l = mid + 1;
        }
        if (l == 0 || r == i + 1) continue;
        LL resday = x - (sumday[i] - sumday[l]);
        LL sum = summoney[i] - summoney[l];
        if (a[l] >= resday) sum += (2 * a[l] - resday + 1) * resday / 2;
        res = max(res, sum);
    }
    cout << res << endl;
    return 0;
}

E、F待补。。。