目录
- 前言
- A - Casimir's String Solitaire(思维+水题)
- B - Shifting Sort (暴力)
- C - Ticks (暴力+思维)
- D - Productive Meeting(贪心+思维+优先队列)
- E1. Permutation Minimization by Deque(双端队列)
- E2. Array Optimization by Deque(贪心+离散化+线段树/树状数组)
前言
首先，是犯下了懒惰之罪的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)。
思路
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]:
- 序列B为空或者序列B的第一个元素不大于A[i]，把A[i]放在B的第一个位置；
- 不满足条件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]:
- 把A[i]放在B的第一个位置；
- 把A[i]放到B的末尾；
不加限制的话，我们可以写出很多个序列。
现在需要我们求出在这些序列B中，逆序对最少的那个序列B的逆序对个数是多少。
逆序对(i，j)满足：
- i < j
- 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的题解，博主比较菜，如果有哪里讲解的不对请在评论区赐教。
感谢。