深圳网站建设找哪家公司,素材图下载,免费建网站教程,建信网个人证书查询传送门
目录
A. Flip Flop Sum 代码#xff1a;
B. The Forbidden Permutation
代码#xff1a;
C. Flexible String 代码#xff1a; A. Flip Flop Sum 题意#xff1a;给你一个长度为n的数组#xff08;数组元素只为1或者-1#xff09;#xff0c;你要且只能进行…
传送门
目录
A. Flip Flop Sum 代码
B. The Forbidden Permutation
代码
C. Flexible String 代码 A. Flip Flop Sum 题意给你一个长度为n的数组数组元素只为1或者-1你要且只能进行一次操作对于所有i1in使问你数组的最大和为多少. 思路首先把所有元素和累加起来然后直接遍历走一遍看存不存在两个相邻的负数如果存在就把结果4直接输出否则去寻找是否存在一个负数因为如果存在一个负数的时候结果并不会改变直接输出即可否则就说明全部都是负数那么就要输出res-4 代码
void slove( )
{sc_int(n);int res0;bool st0;for(int i 1;in;i){sc_int(s[i]);ress[i];if(s[i]-1)st1;}for(int i 1;in;i){if(s[i1]-1s[i]-1){coutres4endl;return ;}}if(!st)res-4;coutresendl;
} B. The Forbidden Permutation 题意给你一个长度为n的排列定义pos(x)为x在排列中的下标 然后对于给出的m个元素如果存在一个序列i1im ,使pos)pos()或者pos()pos()d那么就说明它的好的 现在给你一个操作可以使排列中的两个相邻元素交换。问你在可以保证能够使这个序列是好的的情况下问你需要交换的最小次数是多少可以是0 思路 对于每一个元素如果要使它为好的那么只有两种情况的下标挪到的左边或者的下标和的下标相差d1然后暴力取最小值就可。 代码
void slove( )
{int p;cinnmp;mapint,intq;for(int i 1;in;i){int x;sc_int(x);q[x]i;}for(int i 1;im;i)sc_int(s[i]);int res1e9;for(int i 1;im;i){int aq[s[i]],bq[s[i1]];resmin(res,b-a);if(b-ap){if(pn-1)resmin(res,p-(b-a)1);}else res0;}resmax(res,0);coutresendl;return ;
} C. Flexible String 题意给你两个长度为n的英文字符串a,b和一个k字符串中最多存在10种小写字母你可以进行某次操作任意次 使a串中的某一个字符存到一个容器Q中同时这个字符替换成任意一个字符。但是容器中的字符中不能存在超过k种字符。 然后问你对于l,r(1lrn)问你有多少对(l,r)满足a[i]b[i](lir). 思路 因为a字符串中最多有10中小写字母 那么可以直接把这10也有可能小于10种字符串存入数组中然后用dfs遍历所有的k种字符存入Q的情况然后计算直接取最大值即可 时间复杂度最大也就O(n*(sqrt(2,10))刚好1e8不会超时。 代码 #includecstdio
#include iostream
#include algorithm
#include string.h
#include string
#include math.h
#includevector
#includequeue
#includemap
#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 N1000000100;
int n ,m,h,Time,k;
char a[N],b[N],c[12];
mapint,intq;
ll ress;void init()
{for(int i 1;in;i) a[i]b[i]0;for(int i a;iz;i)q[i]0;for(int i 1;i11;i)c[i]0;
}void cal()
{ll res0,sum0;int l0,r0;for(int i 1;in;i){if(a[i]b[i]||q[a[i]]){if(!l){li;ri;}else r;}else if(l) {sumr-l1;ressum*(sum1)/2;//这边可以计算一下对于lr (l,r)(r-l1)*(r-l1)/2rl0;//更新}}sumr-l1;if(l)ressum*(sum1)/2; ressmax(res,ress);
} void dfs(int i, int x )//i是dfs到了当前位置x是标记了x个元素
{if(xmin(Time,k)){//如果所有元素都被标记到了或者到了限制cal();return ;}i;for( i ; i Time ; i){q[c[i]]1;dfs(i,x1);q[c[i]]0; }return ;
}void slove( )
{ress0;Time0;sc_int(n),cink;cina1b1;for(int i 1;in;i) {if(!q[a[i]]){//寻找第一次出现的字符c[Time]a[i];q[a[i]]1;}}for(int i a;iz;i)q[i]0;//map用两次先初始化一下if(k0){//k为0直接计算cal();coutressendl;init();return ;}for(int i 1;iTime;i)//开始dfs{q[c[i]]1;dfs(i,1);q[c[i]]0;}coutress;coutendl;init();//结束后初始化
}int main()
{int t;sc_int(t);while(t--)slove();return 0;
} 总结A题做的有点粗心脑翻以为是至少一次结果是只要一次b题意度太久了c思路是对的但是小细节有些问题以至于卡在一个地方卡了1个钟最后还是凑巧用另一种方法ac后反着来找bug找到的只能说还要继续训练了。
