当前位置：首页 > article >正文

Educational Codeforces Round 171 (Rated for Div. 2)（A~D题题解）

article 2024/10/30 7:54:01

真不愧是教育场，老老实实给我收拾了一顿，直接给我干报废了

~~当时b题一直没有看清楚题，一直以为一个点可以用多次，导致直接错了12发~~

话不多说，直接来进入今日份快乐

A. Perpendicular Segments

思路：我们发现边最大是1e3，但是k最大可以达到1414，那么就知道有可能会是对角线形式的，因此我们不妨可以大胆猜想一下，就是最大的正方形的对角线，最大正方形，肯定就是有最小的边决定

#include <iostream>
using namespace std;
#define int long long

int t;
int x, y, k;

void solve() {
    cin >> x >> y >> k;
    int flag = min(x, y);
    cout << 0 <<" "<< 0 <<" ";
    cout << flag <<" "<< flag <<" ";
    cout << 0 <<" "<< flag <<" ";
    cout << flag <<" "<< 0 <<" ";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. Black Cells

思路：我们题目要求的是a数组中的每一个单元格都要标记为黑的，而且最多只能由一个地方（不处于a数组中的值）可以为黑的——这个地方就是为了处理奇数情况

我们对于偶数来说，每个点只能用一次，必然是相邻两个点两两链接才能获得最小的k，1和2连接，3和4连接，依次对应，对于奇数，我们就枚举每一个数被移出去的情况下，剩下的点所需要的最小的k，然后找到最小的即可

二分板题吧算是

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
int a[200005];
bool check(int x)
{
    for (int i = 2; i <= n; i+=2)
    {
        if (a[i] - a[i - 1] > x)
        {
            return false;
        }
    }
    return true;
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    if (n % 2 == 0)
    {
        int l = 1, r = 1e18 + 3;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (check(mid))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        cout << l << "\n";
    }
    else
    {
        int minn = LLONG_MAX;
        for (int i = 1; i <= n; i++)
        {
            int q[200005], index = 0;
            for (int j = 1; j <= n; j++)
            {
                if (j != i)
                {
                    q[++index] = a[j];
                }
            }

            int l = 1, r = 1e18;
            while (l < r)
            {
                int mid = (l + r) / 2;
                bool valid = true;
                for (int j = 2; j <= index; j+=2)
                {
                    if (q[j] - q[j - 1] > mid)
                    {
                        valid = false;
                        break;
                    }
                }
                if (valid)
                {
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            minn = min(minn, l);
        }
        cout << minn << "\n";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Action Figures

思路：从后往前遍历每一天，记录可以购买的物品。对于每一天，如果可以访问商店并且有可购买的商品，我们将其加入队列。若当天无法购买商品，我们可以把这个商品和队列中的商品进行匹配，将最贵的商品零元购。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n;
string s;
void solve()
{
    cin>>n;
    cin>>s;
    vector<int> a(n,0);
    int flag=n-1;
    for(int i=n-2;i>=0;i--)
    {
        if(s[i]=='1') 
		continue;
        while(s[flag]=='0'&&flag>i) 
		{
			flag--;
		}
        if(flag>i) 
		{
			a[flag]=1;
		    flag--;
		}
    }
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]||s[i]=='0') 
		continue;
        sum++;
    }
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='1'&&sum>=2&&a[i] ==0)
        {
            a[i]=1;
            sum-=2;
        }
    }
    int ans=0;
    for(int i=0;i<n;i+=1)
    {
    	if(a[i]==0)
        ans+=i+1;
    }
    cout<<ans<<endl;

}

signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    solve();
    return 0;
}

D. Sums of Segments

思路：类似与套娃前缀和吧，然后用二分优化时间复杂度

a数组：就是我们的原数组

pre数组：a数组的前缀和数组

prepre数组：pre数组的前缀和数组

这里说一下b数组的一些操作，我们可以将b数组分为n个区间，每个区间的值都是从s(i,i)到s(i,n)

sum数组，用来统计b数组的每个区间的总和

preb数组，b数组区间的前缀和数组

pos数组，用来统计b数组每个区间的结尾位置是多少

我们首先来分析一下题意要干什么，就是说给你一个两个下标，让你计算这个区间内的b数组的值的累加和

n的数据大小为3e5，也就是说如果存一个一维数组要存到4.5*1e10的大小，很明显，不论是时间还是空间都会爆掉，所以不能用1维数组存

因此我们采用上述方法将b数组分成n个区间，这样就能计算了，我们用前缀和可知，如果我们能够得到 preb[ r ] 的值和 preb[ l - 1 ]的值，相减就是最终结果

那我们现在想要做的就是如何去就出这两个数，我们可以求出这两个数在第几行第几列，然后直接计算即可

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n, q;
int a[300005];
int l, r, mid;

int f(int x) {
    return (n + n - x + 1) * x / 2;
}

void solve() {
    cin >> n;
    vector<int> pre(n + 1, 0); // a数组前缀和数组
    vector<int> prepre(n + 1, 0); // pre数组前缀和数组
    vector<int> sum(n + 1, 0); // 将b数组分为n个区间，每个区间的和
    vector<int> preb(n + 1, 0); // b数组的区间前缀和
    vector<int> pos(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
        prepre[i] = prepre[i - 1] + pre[i];
    }

    for (int i = 1; i <= n; i++) {
        sum[i] = (prepre[n] - prepre[i - 1]) - (n - i + 1) * pre[i - 1];
        preb[i] = preb[i - 1] + sum[i];
        pos[i] = pos[i - 1] + (n - i + 1);
    }

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int posl, posr;
        cin >> posl >> posr;

        // 先计算posl在第几行第几列
        l = 0; r = n;
        while (l < r) {
            mid = (l + r + 1) / 2;
            if (pos[mid] < posl) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int il = l + 1, jl = posl - pos[l];

        // 再计算posr在第几行第几列
        l = 0; r = n;
        while (l < r) {
            mid = (l + r + 1) / 2;
            if (pos[mid] < posr) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int ir = l + 1, jr = posr - pos[l];

        // 准备计算preb[posr]-preb[posl-1]
        int prebr = preb[ir - 1];
        prebr+=prepre[ir+jr-1]-prepre[ir-1]-jr*pre[ir-1];
        
        
        int prebl = preb[il - 1];
        prebl+=prepre[il+jl-2]-prepre[il-1]-(jl-1)*pre[il-1];
        cout<<prebr-prebl<<"\n";
    }
}

signed main() {
    solve();
    return 0;
}

查看全文

http://www.kler.cn/a/371276.html