首页 > 其他 > 详细

Face The Right Way思维。。。

时间:2020-04-06 11:08:37      阅读:43      评论:0      收藏:0      [点我收藏+]

题目再次链接

题意:

  已知01序列a,求通过对长度为k的序列取反能使序列全部变为1的k的最大值,及此时的最少取反次数。

分析:

  首先,先想一想怎么暴力吧。这样想:要保证最小,那么必然不会对同一个区间反转两次,而在k一定时,则不会以同一个数为起点反转两次,于是我们有如果第一个数是0,则反转,是1,则不反转,第一个是否反转就可以确定了,然后按照反转操作进行反转,反转完之后再判断第二个,一直到最后一个(如果区间后端超了n,那么将不会反转成功),然后我们枚举k找到最大的满足条件的k,以及其反转次数。

  暴力还是比较简单的,就是枚举+模拟,但是这样的复杂的接受不了。怎么办呢,我们想想可以对哪个环节进行优化,枚举,枚举可以改为二分吗?不行的,因为你无法保证2不可以3就一定不可以,该枚举还是要枚举。并且n2logn的效率也不是很好。

  那模拟环节呢,你会发现,其实我们判断他需不需要改变是1的,只不过是模拟改变的过程还要走一遍k,这是复杂度无法接受的原因,那么我们能不能在保证判断是1的情况下改掉模拟修改的复杂度,当然不一定是模拟,总之要找一种方法记录下来修改保证判断操作是1.

  其实还是比较好想到的:因为我们在判断i的过程中只需考虑它前面k-1个区间的修改次数,这个就相对好记录了,边判断边记录就可以了,这样维护它被修改的次数的操作也变为1了。问题就迎刃而解了。

代码:

  

#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn=5000+10;
bool a[maxn];
int f[maxn];
int sum[maxn];
int Co(int k,int n){
    memset(f,0,sizeof(f));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++){
        bool js=a[i];
        if((sum[i-1]-sum[max(i-k,0)])%2)
            js=!js;
        if(js){
            if(i+k-1>n)//直接判断这个k不行
                return -1;//这里为了防止和0次冲突
            f[i]=1;
        }
        sum[i]=f[i]+sum[i-1];
    }
    return sum[n];
}
int main(){
    int n;
    scanf("%d",&n);
    char js;
    for(int i=1;i<=n;i++){
        scanf(" %c",&js);
        if(js==B)
            a[i]=1;
    }
    int k;
    for(k=n;k>=1;k--)//倒序,找到一个就可应break了
        if(Co(k,n)+1)
            break;
    printf("%d %d",k,Co(k,n));
    return 0;
}

  然后就是我们再想一下对枚举的优化,我们可不可以先把所有的质数判断出来,然后找比最大的可以完成的质数还大的和数,如果合数有不能完成的质因子,那它也不能完成(想想为什么),不过这种方法的优化可能不大。

Face The Right Way思维。。。

原文:https://www.cnblogs.com/wish-all-ac/p/12640446.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!