Codeforces Round #744 (Div. 3)部分题解(A ~ E2)

目录


前言

首先,是犯下了懒惰之罪的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(n2)就能过,直接两个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)

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)

思路

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)的 " * "为可以作为底的" * ",则进入第二个坑点:

以坐标为(i,j)的 " * " 为底的V字形的d究竟是多少?

我们在判断时是假设 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]句话,说完他们就会离开。(祖安玩家直呼内行)

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)

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

思路

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

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

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)

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:

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)
此时如果我们把3插在前面,它就会与 2(比3小的数) 产生一个逆序对:

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)
如果此时我们把3放在后面,它就会与 4、5(比3大的数) 产生两个逆序对:

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)
此时我们可以发现,当我们插入一个数的时候,我们就可以先统计一下在B中比A[i]大的数有多少个,比A[i]小的数有多少个,我们最终是无法避免产生逆序对的,那么我们就要选择数量较少的那一方来产生逆序对。每次都是取最小,答案也会是最小的。

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

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)
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的题解,博主比较菜,如果有哪里讲解的不对请在评论区赐教。

感谢。


吾日三省吾身:日更否?刷题否?快乐否?
更新了,但不是日更;已刷;happy!
吾心满意足。

Codeforces Round #744 (Div. 3)部分题解(A ~ E2)

上一篇:PHP获得真实客户端的真实IP REMOTE_ADDR,HTTP_CLIENT_IP,HTTP_X_FORWARDED_FOR


下一篇:Codeforces Round #744 (Div. 3)