Codeforces Round #850 (Div. 2, based on VK Cup 2022 - Final Round)(B,D)

这场真是太难了，\(C\)都做出了，\(B\)还做不出太烦了

B

最讨厌什么给出数组，要每一个数移动来符合条件的这种题，烦死了，一点都想不明白

先讲一下题意

给你两个数组\(a\)和\(b\)，可以根据这两个数组可以得到一些线段，对于\(a\)数组，第\(i\)个线段可以得到的线段是\(a_i-w,a_i+w\),对于\(b\)数组，第\(i\)个线段可以得到的线段是\(b_i-h,b_i+h\)

然后我们知道每一个数组得到的线段是不会重合的

我们题目的要求是我们可以让\(b\)数组整体移动\(d\),从而使\(b\)的每一个线段对应\(a\)的相应位置的线段是包含关系，变化后\(b_i-h+d,b_i+h+d\)包含于\(a_i-w,a_i+w\)

然后题目还告诉了我们，\(w>h\),所以我们知道每一段的长度是没问题的，那如果出现不满足条件的最优边界什么的导致的

有可能\(a_i\)和\(b_i\)离得太远了，我们可以试着让\(b_i\)变成\(a_i\),那么我们要让这两个数组尽量的靠近，那么最小的移动长度\(d\)为\(min(b_i-a_i)\),然后我们还需要微调

那么移动\(d\)后，一定会存在一个\(a_j\)和\(b_j\)是一样的，那么我们可以雀确的知道这一个是满足条件的，那么我们还需要判断其他的\(n-1\)个是否满足条件（在微调之后）

那么对于\(a_i\)和\(b_i-d\)(这个是\(b\)移动\(d\)之后的位置)

我们判断这两个线段，是否满足条件的话，可以看\(b_i-d-h-(a_i-w)\)<=\(w-h\)(两个线段的\(l\)端点的差值不可以大于\(w-h\))

可以简化成

\(b_i-a_i-d<=w-h\),对于这\(n-1\)个都要满足这个条件，那么对于\(max(b_i-a_i)\)也满足这个条件

#include <iostream>
using namespace std;
#define int long long 
const int maxn=1e5+10;
int t,n,w,h;
int a[maxn],b[maxn];
void solve()
{
    cin>>n>>w>>h;
    int mi=1e9+10,mx=-1e9-10;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin>>b[i];
        int now=b[i]-a[i];//让b[i]的到a[i]
        mi=min(mi,now);//最小移动的d
        mx=max(mx,now);
    }
    if (mx-mi>2*(w-h))
    {
        cout<<"NO\n";
    }
    else cout<<"YES\n";
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

D

这个题大意是有\(n\)个长度为\(3\)的字符串，每一个字符串只有\(w,i,n\)三种字符，并且\(w\)有\(n\)个，\(i\)有\(n\)个,\(n\)有\(n\)个,我们可以让两个字符串交换一个字符，最后实现\(n\)个字符串都是\(win\),问最少需要多少次交换

对于每一个字符，如果不是\(win\)，那么一定是某一个字符是多的，某一些字符是缺少的

那么对于我们要用最少的交换次数来到达目的

我们优先选择这样的两个字符串进行交换，\(a\)多出的字符刚好是\(b\)所缺少的，\(b\)多出的字符刚好是\(a\)所缺少的,这样可以满足两个字符的要求

还有一种情况，需要一个中间字符串来实现

假如\(a\)多出的是\(w\),少的是\(i\),那么\(b\)多出的需要是\(i\),少的是\(n\),这两个交换，可以让\(a\)变成\(win\),\(b\)变成多的由\(i\)变成了\(w\),但还是需要\(n\),那么我们还需要一个\(c\)，多出的是\(n\)，少的是\(w\)，就把那个从\(a\)转移到\(b\)的\(w\)再次转移到\(c\)，上，实现了\(a\)和\(c\)的某些条件的满足,顺便也实现了\(b\)的某些需求

但是我们要记得列举出所有的情况

#include <iostream>
#include <vector>
#include <array>
#include <string>
using namespace std;
const int maxn=1e5+10;
int t,n;
string s;
char get(int x)
{
    if (x==0) return 'w';
    if (x==1) return 'i';
    return 'n';
}
void solve()
{
    cin>>n;
    vector<int>cnt[3][3];
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        int tot[4]={0};
        for (int j=0;j<s.size();j++)
        {
            if (s[j]=='w') tot[0]++;
            else if (s[j]=='i') tot[1]++;
            else tot[2]++;
        }
        for (int j=0;j<3;j++)
        {
            for (int k=0;k<3;k++)
            {
                if (j==k) continue;
                if (tot[j]>1&&tot[k]<1)
                {
                    cnt[j][k].push_back(i);
                    tot[j]--;
                    tot[k]++;
                }
            }
        }
    }
    vector<array<int,4>>ans;
    for (int x=0;x<3;x++)
    {
        for (int y=x+1;y<3;y++)
        {
            while (cnt[x][y].size()&&cnt[y][x].size())
            {
                int i=cnt[x][y].back();
                cnt[x][y].pop_back();
                int j=cnt[y][x].back();
                cnt[y][x].pop_back();
                ans.push_back({i,x,j,y});
            }
        }
    }
    while (cnt[1][0].size()&&cnt[0][2].size()&&cnt[2][1].size())
    {
        int i=cnt[1][0].back();
        cnt[1][0].pop_back();
        int j=cnt[0][2].back();
        cnt[0][2].pop_back();
        int k=cnt[2][1].back();
        cnt[2][1].pop_back();
        ans.push_back({i,1,j,0});
        ans.push_back({j,1,k,2});
    }
    while (cnt[0][1].size()&&cnt[1][2].size()&&cnt[2][0].size())
    {
        int i=cnt[0][1].back();
        cnt[0][1].pop_back();
        int j=cnt[1][2].back();
        cnt[1][2].pop_back();
        int k=cnt[2][0].back();
        cnt[2][0].pop_back();
        ans.push_back({i,0,j,1});
        ans.push_back({j,0,k,2});
    }
    int sum=ans.size();
    cout<<sum<<'\n';
    for (auto [i,x,j,y]:ans)
    {
        cout<<i<<" "<<get(x)<<" "<<j<<" "<<get(y)<<'\n';
    }
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}