目录

• 前言
• A - Casimir's String Solitaire(思维+水题)
• • 题目大意
  • 思路
  • AC代码
• B - Shifting Sort (暴力)
• • 题目大意
  • 思路
  • AC代码
• C - Ticks (暴力+思维)
• • 题目大意
  • 思路
  • AC代码
• D - Productive Meeting(贪心+思维+优先队列)
• • 题目大意
  • 思路
  • AC代码
• E1. Permutation Minimization by Deque(双端队列)
• • 题目大意
  • 思路
  • AC代码
• E2. Array Optimization by Deque(贪心+离散化+线段树/树状数组)
• • 题目大意
  • 思路
  • AC代码

前言

首先，是犯下了懒惰之罪的Mr.RainsdRop。

自以为连续日更很了不起，向外宣称自己是一个日更博主。大家不知道，当《废柴日记1：Python与C++中关于随机数的那些事》写到最后的时候，电脑仅仅剩下20%的电量，而文章还有至少一段没写。当时的Mr.RainsdRop闭上眼睛，看到的便是已然成神的 God Jun 。
God Jun 说：“你的电脑将会供你发完博客。你只可到这里，不可越过。”
然而，Mr.RainsdRop却逐渐忘记了 God Jun 对他的恩赐，开始周更，开始拖更。

于是 God Jun 降下了祂的惩罚，让Mr.RainsdRop在比赛时比到一半的时候电脑没电自动关机。

故事大概就是这样，总之很可惜，没有打完整场。
赛后感觉是至少4题可以出，时间够的话前6个题都可以做。

闲话不多说了，上主菜。

A - Casimir’s String Solitaire(思维+水题)

比赛链接：https://codeforces.com/problemset/problem/1579/A

题目大意

给出一个仅有字母A、B、C组成的字符串。
对于这个字符串我们有两种处理方式：

1.选择一个字母A和一个字母B，然后让它们消失；
2.选择一个字母C和一个字母B，然后让它们消失；

问我们能不能让这个给定的字符串消失。

思路

先统计一下三种字母的数量，然后根据题意推理一下。
根据题意，消除一个字符串的充要条件为：字母B的数量等于字母A、C的数量总和。

所以只有这一个条件成立时才会输出YES，否则就是NO。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;

int main()
{
    ios::sync_with_stdio(false);
    int n,t;
    cin>>t;
    while(t--){
        string ss;
        int a,b,c;
        a=b=c=0;
        cin>>ss;
        for(int i=0;i<ss.size();i++){
            if(ss[i]=='A') a++;
            else if(ss[i]=='B') b++;
            else c++;
        }
       
        if(a+c==b) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

B - Shifting Sort (暴力)

比赛链接：https://codeforces.com/problemset/problem/1579/B

题目大意

给定一个长度为n的数字序列(可能无序但也可能有序)。
你的目标就是通过指定的手法把序列变得有序，输出操作次数与每次的操作方式。

操作方法：
选定L，R(1 ≤ L < R ≤ n)，然后让区间内的数字左移D次。

举例：

现在有序列[3,1,5,4]。
我们选定区间2~4，也就是[1,5,4]。
然后整体左移1格，[1,5,4]就变成了[5,4,1]。
再次左移，[5,4,1]就变成了[4,1,5]。
再次左移，[4,1,5]就变成了[1,5,4]。

最后的答案可以不是次数最少的方案，只要满足把序列变成有序即可。

思路

首先根据题目所描述的操作方式，我们知道：
当我们选定一个长度为K的序列，我们对其操作K-1次，最后一位数会来到序列的起始位置，其他的数的位置会向后退一位。

博主当时在做的时候，暴力的思想是没问题的：
每次寻找当前序列中最小的没有归位的数字，然后选择它应该呆在的位置为L，它当前的位置为R，然后移动(R - L)次。

结果当时实现的想复杂了，又是map又是离散化的，最后搞着搞着电脑关机了，心态都崩了。
后来发现O(n²)就能过，直接两个for循环暴力跑就可以，围绕着上面粗体字的思想。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int n,x,t;
    cin>>t;
    while(t--)
    {
        int x;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        vector<pair<pair<int,int>,int> > arry;
        for(int i=1;i<=n;i++){
            int pos=i;
            for(int j=i;j<=n;j++){
                if(a[j]<a[pos]) pos=j;
            }
            if(pos==i) continue;
            else{
                x=a[pos];
                arry.push_back(make_pair(make_pair(i,pos),pos-i));
                for(int j=pos;j>i;j--){   //区间内其他数字后退一位
                    a[j]=a[j-1];
                }
                a[i]=x;
            }
        }
        int len=arry.size();
        cout<<len<<endl;
        if(len==0) cout<<endl;
        else{
            for(int i=0;i<len;i++)
                cout<<arry[i].first.first<<" "<<arry[i].first.second<<" "<<arry[i].second<<endl;
        }


    }
    return 0;
}

C - Ticks (暴力+思维)

比赛链接：https://codeforces.com/problemset/problem/1579/C

题目大意

现在有一张n*m的图，图上有 " * " 和 " . " 两种符号。
你可以通过指定方式把所有的 " * " 变成 " . " 。

操作方式：
如果当前的点(i，j)满足条件：

• 点(i，j)为 " * " ；
• 存在一个半径d(d>0)，满足 (i−h，j±h) (0 <= h <= d)为 " * " ；

此时我们可以将这部分 " * " 变成 " . " 。

现在，我们限制，所有的d都要至少要大于等于k。
问我们能否把一张图变成一张全是 " . " 的图。

注意：一个" * "是可以重复的被使用多次的。
例如下图，以第三行第三列的(3，3)形成的V字形与第四行第六列的(4，6)形成的V字形都用到了第二行第四列的(2，4)。

思路

C题并不是很难，只是东西有点多，有点类似于大模拟，需要花费一点时间。

首先要确定一点：一个 " * " 是可以多次被使用的。
有了这个点就说明我们没法在原本的图上动手脚，否则一旦一个点先前被用过，后面的 " * " 就没法再使用它了，这就可能导致答案的错误。
所以我们把整个地图拷贝两份，一份用来查询信息，另一份地图用来改造。

接下来我们需要去处理一个 " * " 能不能形成一个以它为底的符合要求的V字形。
整张图之中的所有" * "分为两种：可以作为底的" * " 和 不可以作为底的" * "。

我们先按照d==k来判断坐标为(i，j)的 " * " 属于哪种：

int d=k;
int x=i-1,y1=j-1,y2=j+1,flag=1;   
//flag==1:这个" * "是可以作为底的 / flag==0:这个" * "是不可以作为底的     
while(d--)
{
    if(x==0||y1==0||y2==m+1)      //判越界
    {
        flag=0;                
        break;
    }
    if(ss[x][y1]!='*'||ss[x][y2]!='*')  //不满足条件
    {
        flag=0;
        break;
    }
    x--,y1--,y2++;
}

如果坐标为(i，j)的 " * "为可以作为底的" * "，则进入第二个坑点：

我们在判断时是假设 d==k，然而真实情况并不是这样。

其实这里有巧招，代码给你，自己悟一下吧：
(提示：经过判断之后的坐标为(i，j)的 " * " 的性质)

vis[i][j]=1;

for(x=i-1,y1=j-1,y2=j+1; x>0&&y1>0&&y2<=m&&ss[x][y1]=='*'&&ss[x][y2]=='*' ; x--,y1--,y2++)
    vis[x][y1]=vis[x][y2]=1;

剩下的就是理解上面的核心然后完善代码了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;

char ss[50][50];
int vis[50][50];

int main()
{
    int n,m,k,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1; i<=n; i++)
            scanf("%s",ss[i]+1);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                vis[i][j]=(ss[i][j]=='*')?0:1;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(ss[i][j]=='*')
                {
                    int d=k;
                    int x=i-1,y1=j-1,y2=j+1,flag=1;
                    while(d--)
                    {
                        if(x==0||y1==0||y2==m+1)
                        {
                            flag=0;
                            break;
                        }
                        if(ss[x][y1]!='*'||ss[x][y2]!='*')
                        {
                            flag=0;
                            break;
                        }
                        x--,y1--,y2++;
                    }
                    if(!flag)
                        continue;
                    vis[i][j]=1;
                    for(x=i-1,y1=j-1,y2=j+1; x>0&&y1>0&&y2<=m&&ss[x][y1]=='*'&&ss[x][y2]=='*' ; x--,y1--,y2++)
                        vis[x][y1]=vis[x][y2]=1;
                }
        string ff="YES";
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(!vis[i][j])
                {
                    ff="NO";
                    break;
                }
        cout<<ff<<endl;
    }
    return 0;
}

D - Productive Meeting(贪心+思维+优先队列)

比赛链接：https://codeforces.com/problemset/problem/1579/D

题目大意

会议室中有n个人，他们每个人可以说a[i]句话，说完他们就会离开。(祖安玩家直呼内行)

问最多可以产生几次对话，输出每次对话的双方的编号。
(对话：两个不同的人对着对方说一句话)

思路

这其实是很简单的贪心题。
每次我们只需要让说话次数最多的两个人骂一次，然后双方说话次数-1，扔回优先队列里。

这tm是D题？比完赛再看就直接脑溢血。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;

struct node
{
    int x,pos;
    node(){}
    node(int xx,int pp):x(xx),pos(pp){}

    bool operator<(const node &a)const{
        return a.x>x;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    int n,x,t;
    cin>>t;
    while(t--)
    {
        priority_queue<node> q;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>x;
            if(x) q.push(node(x,i));
        }
        vector<pair<int,int> > arr;
        while(q.size()>=2){
            node a=q.top();
            q.pop();
            node b=q.top();
            q.pop();
            arr.push_back(make_pair(a.pos,b.pos));
            a.x--;
            b.x--;
            if(a.x) q.push(a);
            if(b.x) q.push(b);
        }
        cout<<arr.size()<<endl;
        for(int i=0;i<arr.size();i++)
            cout<<arr[i].first<<" "<<arr[i].second<<endl;
    }
    return 0;
}

E1. Permutation Minimization by Deque(双端队列)

比赛链接：https://codeforces.com/problemset/problem/1579/E1

题目大意

给你一个长度为n的序列A，现在有一个空的序列B，让你把A中的所有元素按照规则放入序列B之中。

假设当前需要放入A[i]:

1. 序列B为空或者序列B的第一个元素不大于A[i]，把A[i]放在B的第一个位置；
2. 不满足条件1，把A[i]放到B的末尾；

输出序列B。

思路

妥妥的双端队列，没啥可说的。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int n,x,t;
    cin>>t;
    while(t--){
        cin>>n;
        deque<int> q;
        for(int i=0;i<n;i++){
            cin>>x;
            if(q.empty()) q.push_back(x);
            else{
                if(x<=q.front()) q.push_front(x);
                else q.push_back(x);
            }
        }
        while(!q.empty()){
            cout<<q.front();
            q.pop_front();
            if(!q.empty())
                cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

E2. Array Optimization by Deque(贪心+离散化+线段树/树状数组)

比赛链接：https://codeforces.com/problemset/problem/1579/E2

题目大意

给你一个长度为n的序列A，现在有一个空的序列B，让你把A中的所有元素按照规则放入序列B之中。

假设当前需要放入A[i]:

1. 把A[i]放在B的第一个位置；
2. 把A[i]放到B的末尾；

不加限制的话，我们可以写出很多个序列。

现在需要我们求出在这些序列B中，逆序对最少的那个序列B的逆序对个数是多少。

逆序对(i，j)满足：

1. i < j
2. B[i] > B[j]

思路

这个题的难度瞬间就上来了，和它一比，前面的就跟饭前小零食一样。

先别自乱阵脚，我们一点一点的分析。

• 当序列B中元素数量为0的时候，我们插入任何一个数都不会产生逆序对
• 当序列B中有元素的时候，对于新来的A[i]，它要么放在最前面，要么放在最后面。那么此时就会产生逆序对。

举个例子，如下图所示，我们要在原有的B序列上插入一个3：

此时如果我们把3插在前面，它就会与 2(比3小的数) 产生一个逆序对:

如果此时我们把3放在后面，它就会与 4、5(比3大的数) 产生两个逆序对：

此时我们可以发现，当我们插入一个数的时候，我们就可以先统计一下在B中比A[i]大的数有多少个，比A[i]小的数有多少个，我们最终是无法避免产生逆序对的，那么我们就要选择数量较少的那一方来产生逆序对。每次都是取最小，答案也会是最小的。

理解了这里之后，我们就要去处理数据了。

2e5个数却有1e9的范围，太浪费了。
我们假想一下，就算输入2e5个数，每个数字都不相同，那也只有2e5个数字。

所以我们这里先对数据进行离散化：

for(int i=1; i<=n; i++)
{
    cin>>a[i];
    arr.push_back(a[i]);
}

sort(arr.begin(),arr.end());

arr.erase(unique(arr.begin(),arr.end()),arr.end()); //这一步很重要

for(int i=1; i<=n; i++)
{
    a[i]=lower_bound(arr.begin(),arr.end(),a[i])-arr.begin()+1;
}

接下来我们使用线段树，树上的每个结点具有三个属性l，r，num。
每个结点的num的含义：大小在[l，r]之间的数字的个数。

struct node
{
    int l,r;
    ll num;
}tree[4*maxn];

接下来就是基础线段树的操作：单点修改+区间询问。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
struct node
{
    int l,r;
    ll num;
}tree[4*maxn];

ll a[maxn];

//建树 O(logn)
inline void build(int l,int r,int i)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].num=0;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
}

//单点更新O(logn)   区间更新O(nlogn)
inline void update(int x,int l,int r,int i)
{
    if(tree[i].l==tree[i].r)
    {
        tree[i].num++;
        return ;
    }
    int mid=(l+r)>>1;

    if(x<=mid)
        update(x,l,mid,i*2);
    if(x>mid)
        update(x,mid+1,r,i*2+1);
    tree[i].num=tree[i*2].num+tree[i*2+1].num;
}


//查询 O(logn)
inline ll query(int l,int r,int i)
{
    //cout<<"("<<tree[i].l<<" , "<<tree[i].r<<")"<<endl;
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        return tree[i].num;
    }
    if(tree[i].l>r||tree[i].r<l)
        return 0;
    ll s=0;
    int mid=(tree[i].l+tree[i].r)>>1;
    if(mid>=l)
        s+=query(l,r,i*2);
    if(mid<=r)
        s+=query(l,r,i*2+1);
    return s;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        vector<ll> arr;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            arr.push_back(a[i]);
        }
        sort(arr.begin(),arr.end());
        arr.erase(unique(arr.begin(),arr.end()),arr.end());
        build(1,n,1);
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(arr.begin(),arr.end(),a[i])-arr.begin()+1;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll les=query(1,a[i]-1,1);
            ll more=i-1-query(1,a[i],1);
            update(a[i],1,n,1);
            ans+=min(les,more);
        }
        cout<<ans<<endl;

    }
}

赛后来看，这套题真的很简单，能力强的大佬可以轻轻松松6道题，博主这种垃圾只能赛后悔恨了。

题解就到这里结束了，接下来也会给大家继续带来一些CF的题解，博主比较菜，如果有哪里讲解的不对请在评论区赐教。

感谢。