Codeforces Round #848 (Div. 2)A-C

传送门

目录

A. Flip Flop Sum

 代码：

B. The Forbidden Permutation

代码：

C. Flexible String

 代码：

---

A. Flip Flop Sum

题意：给你一个长度为n的数组（数组元素只为1或者-1），你要且只能进行一次操作：对于所有i（1<=i<n），使，问你数组的最大和为多少.

思路：首先把所有元素和累加起来，然后直接遍历走一遍看存不存在两个相邻的负数，如果存在就把结果+4直接输出，否则去寻找是否存在一个负数，因为如果存在一个负数的时候结果并不会改变直接输出即可，否则就说明全部都是负数，那么就要输出res-4，

 代码：

void slove( )
{sc_int(n);int res=0;bool st=0;for(int i =1;i<=n;i++){sc_int(s[i]);res+=s[i];if(s[i]==-1)st=1;}for(int i =1;i<n;i++){if(s[i+1]==-1&&s[i]==-1){cout<<res+4<<endl;return ;}}if(!st)res-=4;cout<<res<<endl;
}

 

B. The Forbidden Permutation

题意：给你一个长度为n的排列，定义pos(x)为x在排列中的下标

然后对于给出的m个元素，如果存在一个序列i（1<=i<m ）

,使pos（)>pos()或者pos()>pos()+d，那么就说明它的好的，

现在给你一个操作，可以使排列中的两个相邻元素交换。问你在可以保证能够使这个序列是好的的情况下，问你需要交换的最小次数是多少（可以是0）

思路 ：对于每一个元素，如果要使它为好的，那么只有两种情况：的下标挪到的左边，或者的下标和的下标相差d+1，然后暴力取最小值就可。

代码：

void slove( )
{int p;cin>>n>>m>>p;map<int,int>q;for(int i =1;i<=n;i++){int x;sc_int(x);q[x]=i;}for(int i =1;i<=m;i++)sc_int(s[i]);int res=1e9;for(int i =1;i<m;i++){int a=q[s[i]],b=q[s[i+1]];res=min(res,b-a);if(b-a<=p){if(p<n-1)res=min(res,p-(b-a)+1);}else res=0;}res=max(res,0);cout<<res<<endl;return ;
}

 

C. Flexible String

题意：给你两个长度为n的英文字符串a,b和一个k（字符串中最多存在10种小写字母），你可以进行某次操作任意次：

使a串中的某一个字符存到一个容器Q中，同时这个字符替换成任意一个字符。但是容器中的字符中不能存在超过k种字符。

然后问你对于l,r(1<=l<=r<=n)，问你有多少对(l,r)，满足a[i]=b[i]，(l<=i<=r).

思路： 因为a字符串中最多有10中小写字母 ，那么可以直接把这10（也有可能小于10）种字符串存入数组中，然后用dfs遍历所有的k种字符存入Q的情况，然后计算直接取最大值即可，

时间复杂度最大也就O(n*(sqrt(2,10))，刚好1e8不会超时。

 代码：

#include<cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include<vector>
#include<queue>
#include<map>
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;const int N=1000000+100;
int n ,m,h,Time,k;
char a[N],b[N],c[12];
map<int,int>q;
ll ress;void init()
{for(int i =1;i<=n;i++) a[i]=b[i]=0;for(int i ='a';i<='z';i++)q[i]=0;for(int i =1;i<=11;i++)c[i]=0;
}void  cal()
{ll res=0,sum=0;int l=0,r=0;for(int i =1;i<=n;i++){if(a[i]==b[i]||q[a[i]]){if(!l){l=i;r=i;}else r++;}else if(l) {sum=r-l+1;res+=sum*(sum+1)/2;//这边可以计算一下，对于l，r  (l,r)=(r-l+1)*(r-l+1)/2r=l=0;//更新}}sum=r-l+1;if(l)res+=sum*(sum+1)/2;  ress=max(res,ress);
}   void dfs(int i, int x )//i是dfs到了当前位置，x是标记了x个元素
{if(x==min(Time,k)){//如果所有元素都被标记到了或者到了限制cal();return ;}i++;for( i ; i <= Time ; i++){q[c[i]]=1;dfs(i,x+1);q[c[i]]=0;        }return ;
}void slove( )
{ress=0;Time=0;sc_int(n),cin>>k;cin>>a+1>>b+1;for(int i =1;i<=n;i++)    {if(!q[a[i]]){//寻找第一次出现的字符c[++Time]=a[i];q[a[i]]=1;}}for(int i ='a';i<='z';i++)q[i]=0;//map用两次先初始化一下if(k==0){//k为0直接计算cal();cout<<ress<<endl;init();return ;}for(int i =1;i<=Time;i++)//开始dfs{q[c[i]]=1;dfs(i,1);q[c[i]]=0;}cout<<ress;cout<<endl;init();//结束后初始化
}int main()
{int t;sc_int(t);while(t--)slove();return 0;
}

总结：A题做的有点粗心，脑翻以为是至少一次（结果是只要一次），b题意度太久了，c思路是对的，但是小细节有些问题，以至于卡在一个地方卡了1个钟，最后还是凑巧用另一种方法ac后反着来找bug找到的，只能说还要继续训练了。