Educational Codeforces Round 171 (Div. 2)

A

猜结论，两条边的最小值最大时，两条边相等。所以取 \(min(x,y)\) 为边长的正方形，对角线就是所求。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

int x,y,k;
void solve()
{
    cin>>x>>y>>k;
    int t=min(x,y);
    cout<<0<<' '<<0<<' '<<t<<' '<<t<<'\n';
    cout<<0<<' '<<t<<' '<<t<<' '<<0<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

赛时罚时吃爽了 qwq。

首先若 \(n\) 为偶数，必须是两两匹配涂黑的，不能有列表外的被涂黑。涂 \((1,2)\)，\((3,4)\)，\((5,6)\) 等等。在这些的差值取最大就是 \(k\)。

若 \(n\) 为奇数，那么就是能且必须有一个数不是和列表中的数匹配涂黑，枚举这个数 \(i\)，将数组分为两部分 \((1,i-1)\) 和 \((i+1,n)\)，和 \(n\) 为偶数的情况一样考虑两部分。\(O(n^2)\) 复杂度完全可以。

一开始认为奇数情况下只能让开头和末尾的和其他的数涂黑 qwq。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long ll;
const int N=2005;
const ll inf=1e18;
int n;
ll a[N];

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll ans=inf;
    if(n&1)
    {
        ll ans=inf;
        for(int i=1;i<=n;i+=2)
        {
            ll mx=0;
            for(int j=1;j<i;j+=2) mx=max(mx,a[j+1]-a[j]);
            for(int j=i+1;j<=n;j+=2) mx=max(mx,a[j+1]-a[j]);
            ans=min(ans,mx);
        }
        cout<<max(1ll,ans)<<'\n';
    }   
    else 
    {
        ll mx=0;
        for(int i=2;i<=n;i+=2) mx=max(mx,a[i]-a[i-1]);
        cout<<mx<<'\n';
    } 
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C

首先肯定要贪心考虑，尽可能优惠后面的商品，尽可能多的优惠。

等于 \(0\) 的商品肯定不能优惠，因为可以有更优的选择。

将 \(0\) 和 \(1\) 分开，用双端队列存 \(1\) 的位置，每次取队尾，然后肯定是有 \(0\) 就用 \(0\) 的位置出现的商品和当前的拼起来优惠，否则取队首的 \(1\)。如果都没有的话就不能优惠。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int N=4e5+5;
int n;
string s;
deque<int> dq;
int st[N],tot;
ll ans;
void solve()
{
    cin>>n;
    cin>>s;
    tot=ans=0;
    for(int i=0;i<n;i++) 
    {
        if(s[i]-'0') dq.push_back(i+1);
        else st[++tot]=i+1;
        ans+=i+1;
    }
    while(dq.size())
    {
        int x=dq.back();dq.pop_back();
        while(tot&&st[tot]>x) tot--;
        if(tot) 
        {
            tot--;
            ans-=x;
        }
        else 
        {
            if(dq.size())
            {
                dq.pop_front();
                ans-=x;
            }
        }

    }
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

shi 一样的数学题，还没调出来。