精华内容
下载资源
问答
  • 先上数据,我想做的就是对矩阵里面的数据进行判断,如果第i个数据的值小于0.1的话,就把它取为0,如果大于0.1 就保留该值: for j=1:705333 if abs(b(j)) b(j)=0 else b(j)=b(j); end end 但是因为数据...
  • 心得 思路:一个0~10000的数写成M*N的形式,且M&...如何判断测试点是几:吸收测试点的total之后,用if判断,二分法,如果大于某数,直接返回(看结果是段错误还是答案错误,再二分) 测试点7是9...

    心得

    思路:一个0~10000的数写成M*N的形式,且M>N,则M的范围是0~10000,N的范围是0~100
    这个对于m,n的判断很重要,因为二维数组不能开的太大,10000*10000会显示段错误
    几种段错误的原因:数组访问越界,或者数组开得过大
    如何判断测试点是几:吸收测试点的total之后,用if判断,二分法,如果大于某数,直接返回(看结果是段错误还是答案错误,再二分)

    测试点7是9973!!!

    比如下面这个过程:

    5000~9999之间没有测试点
    
    1000~5000之间没有测试点
    
    500~1000之间没有测试点
    
    测试点7段错误
    
    测试点7在500之上
    测试点7在1000之上
    测试点7在2500之上
    测试点7在7500之上
    测试点7在9500之上
    测试点7在9900之上
    测试点7在9945之上
    测试点7在9968之上
    测试点7在9971之上
    
    测试点7不是9971,9972
    
    测试点7是9973!!!
    
    测试点7在9974之下
    测试点7在9979之下
    测试点7在9990之下
    

    用习惯了VS2017之后,就回不去dev或者其他ide了,vs太好用了啊!尤其是调试功能以及随时报错、语法联想功能!
    但是考试的环境没有vs2017,只好提前用dev熟悉一下。这道题是第一道用dev做出的25分题,花了不少时间,但熟悉环境是主要的。也由此说明了不要过分依赖某一个特定的ide(尽管它真的很好用…),况且是在刷算法题,而不是开发一个项目。那些不用ide的控制台党不也一样高效的写代码吗?陌生的ide不应成为设计算法的瓶颈。

    题目

    在这里插入图片描述

    和OJ斗智斗勇

    在这里插入图片描述

    全部通过

    在这里插入图片描述

    代码

    #include<iostream>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    
    int mySort(int a1,int a2)
    {
    	return(a1>a2);
    }
    
    int main()
    {
    	int total;
    	cin>>total;
    	
    	//输入
    	int i,j;
    	int arr[10000];
    	for(i=0;i<total;i++)
    	{
    		cin>>arr[i];
    	} 
    	
    	//计算m,n   m行n列 
    	int m=0,n=0;
    	for(i=1;i<=sqrt(total);i++)
    	{
    		if(total%i==0)
    		{
    			n=i;
    			m=total/n;
    		}
    	}
    
    	//排序
    	sort(arr,arr+total,mySort);
    	
    
    	//摆放
    	int bi[10000][100];
    	int totalFlag=0;
    	
    	//按圈遍历
    	int up=0;
    	int down=m-1;
    	int left=0;
    	int right=n-1; 
    	
    //	cout<<"m="<<m<<endl;
    //	cout<<"n="<<n<<endl;
    //	cout<<"up="<<up<<endl;
    //	cout<<"down="<<down<<endl;
    //	cout<<"left="<<left<<endl;
    //	cout<<"right="<<right<<endl;
    	
    	while(1)
    	{
    		if(totalFlag==total)break;
    		
    		//上
    		for(i=left;i<=right;i++)
    		{
    			bi[up][i]=arr[totalFlag];
    			totalFlag++;
    		}
    		if(totalFlag==total)break;
    		
    		//右 
    		for(i=up+1;i<=down;i++)
    		{
    			bi[i][right]=arr[totalFlag];
    			totalFlag++;
    		}
    		if(totalFlag==total)break;
    			
    		//下
    		for(i=right-1;i>=left;i--)
    		{
    			bi[down][i]=arr[totalFlag];
    			totalFlag++;
    		}
    		if(totalFlag==total)break;
    		
    		//左 
    		for(i=down-1;i>=up+1;i--)
    		{
    			bi[i][left]=arr[totalFlag];
    			totalFlag++;
    		}
    		if(totalFlag==total)break;
    			
    		//改变边界 
    		up++;
    		down--;
    		left++;
    		right--;
    	} 
    	
    	//打印
    	for(i=0;i<m;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			cout<<bi[i][j];
    			if(j!=n-1)cout<<' ';
    		}
    		if(i!=m-1)cout<<endl;
    	} 
    	return 0;
    }
    
    展开全文
  • 由于m最大范围只有5,而且每一个位置只能够填写3和7,所以我们不妨考虑状压,用0和1分别表示3和7,这样就是一个5位的二进制数字。那么我们的限制条件也可以很好的通过位运算来判断。接着我们考虑这么多个位置如何...

     

     

    中文题。

    由于m最大范围只有5,而且每一个位置只能够填写3和7,所以我们不妨考虑状压,用0和1分别表示3和7,这样就是一个5位的二进制数字。那么我们的限制条件也可以很好的通过位运算来判断。接着我们考虑这么多个位置如何计算方案数。首先,我们简化问题,把问题变成一条链而不是一个圈,这样一个位置可以放什么数字就只是与前面四个位置有关系。如果之前的7的个数已经大于3的个数,那么当前位置放3和7都可以,否则就只能够放7。这样我们就可以写出状态转移方程:

    \small dp[i][status]=dp[i-1][status>>1]+dp[i-1][status>>1|(1<<(m-1)]

    其中dp[i][status]表示处理到第i个格子,当前状态位status的时候的方案数。显然当前状态根据往前第m个数字的状态,可以有最多两种选择。status>>1表示往前第m个数字取0的方案,status>>1|(1<<(m-1))表示往前第m个数字取1的方案。注意到这个转移方程,dp[i]只与dp[i-1]相关,又这个长度最多可以到1e12这么大,所以我们可以想到用矩阵快速幂去优化这个转移。转移矩阵也是很好构建,对于每一个状态,最多可以从之前的两个状态转移过来,类似于转移方程那样构造转移矩阵即可。

    现在,我们结合这题要求是换状来考虑这个问题。既然是换状,把变成链状来处理求出来之后,必然会有些方案是不合法的。引因为链状只是考虑了前四个,而环状之后最后m个位置还要往后考虑。于是我们不妨枚举一下最初m个位置的状态,然后再对应的枚举一下最后m个位置的状态,根据两个状态来判定这种组合是否合法。如果合法,那么把这一种组合方式的方案数加上。对于一个特定的起始状态x和最最终状态y,如果他们匹配合法,那么相当于是在初始的时候,只有x这个状态为1,最后的时候只有y这个状态为1,所以对应的方案数就是转移矩阵的(n-m)次方的第x行第y列的数值。把所有合法的起始状态和最终状态对应转移矩阵的(m-n)次方的对应位置的值求和就是最后的答案。具体见代码:

    #include<bits/stdc++.h>
    #define mod 998244353
    #define LL long long
    #define pb push_back
    #define lb lower_bound
    #define ub upper_bound
    #define INF 0x3f3f3f3f
    #define sf(x) scanf("%lld",&x)
    #define sc(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define clr(x,n) memset(x,0,sizeof(x[0])*(n+5))
    #define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
    using namespace std;
     
    const int N = 32;
     
    LL n,m,up;
     
    struct Matrix
    {
        LL a[N][N];
        Matrix(){memset(this,0,sizeof(Matrix));}
     
        Matrix operator *(const Matrix x) const
        {
            Matrix ans;
            for(int i=0;i<up;i++)
                for(int j=0;j<up;j++)
                {
                    for(int k=0;k<up;k++)
                        ans.a[i][j]+=a[i][k]*x.a[k][j]%mod;
                    ans.a[i][j]%=mod;
                }
            return ans;
        }
     
        friend Matrix operator ^(Matrix x,LL y)
        {
            Matrix ans;
            for(int i=0;i<up;i++)
                ans.a[i][i]=1;
            while(y)
            {
                if (y&1) ans=ans*x;
                x=x*x; y>>=1;
            }
            return ans;
        }
    } x;
     
    inline bool check(int x)
    {
        assert(x<up);
        return __builtin_popcount(x)>=(m+1)/2;
    }
     
    void init()
    {
        for(int i=0;i<up;i++)
        {
            if (!check(i)) continue;
            int j=i>>1;
            if (check(j)) x.a[i][j]=1;
            j|=up>>1;
            if (check(j)) x.a[i][j]=1;
        }
    }
     
    int main()
    {
        LL ans=0;
        sf(n); sf(m);
        up=(1<<m); init();
        x=x^(n-m);
        for(int i=0;i<up;i++)
        {
            if (!check(i)) continue;
            for(int j=0;j<up;j++)
            {
                if (!check(j)) continue;
                int tmp=(j<<m)|i,flag=0;
                for(int k=1,s=up-1;k<m;k++)
                    if (!check((tmp&(s<<k))>>k)) {flag=1;break;}
                if (!flag)
                    ans=(ans+x.a[j][i])%mod;
            }
        }
        printf("%lld\n",(ans+mod)%mod);
        return 0;
    }

     

    展开全文
  • 如何判断函数是凸函数? 设f是定义域为实数的函数,如果定义域内对于所有的实数x,f的二阶导大于等于0,称f是凸函数。 当x是向量时,如果其海森矩阵A是半正定的(H&gt;=0),f也是凸函数。 如果f的二阶导大于0...

    上月就弃坑了,谁知道又投份简历让我去面试,我是真的不想搞这些东西了,心累.

    如何判断函数是凸函数?

    设f是定义域为实数的函数,如果定义域内对于所有的实数x,f的二阶导大于等于0,称f是凸函数。

    当x是向量时,如果其海森矩阵A是半正定的(H>=0),f也是凸函数。

    如果f的二阶导大于0或者H>0,那么称f是严格凸函数。

    反之,如果二阶导小于0或者x是向量时,其海森矩阵小于0,f为凹函数

    LR 与 SVM 的相同和不同

    相同点

    1都是分类算法,都是监督学习算法(有标签),

    2都是判别模型(不用计算联合概率分布的模型KNN、SVM、LR,生成模型先计算联合概率p(Y,X)然后通过贝叶斯公式转化为条件概率,朴素贝叶斯,隐马尔可夫模型)

    3广为人之,且应用广泛

    不同点

    1支持向量机只考虑超平面附近的点--支持向量,而逻辑回归考虑所有的数据(远离的点对边界线的确定也起作用)

    2损失函数不同,LR用对数损失函数,SVM用合页损失函数

    3解决非线性问题,SVM引入核函数,而LR不解决非线性问题.因为LR所有点都参与决策,那么计算量太大,而SVM只有少数的支持向量参与计算

    4SVM要经过数据的归一化,依赖于数据的距离测度,LR没有这个问题

    随机森林和GBDT区别

    1)随机森林采用的bagging思想,而GBDT采用的boosting思想。
    2)组成随机森林的树可以是分类树,也可以是回归树;而GBDT只能由回归树组成。
    3)组成随机森林的树可以并行生成;而GBDT只能是串行生成。
    4)对于最终的输出结果而言,随机森林采用多数投票等;而GBDT则是将所有结果累加起来,或者加权累加起来。
    5)随机森林对异常值不敏感;GBDT对异常值非常敏感。
    6)随机森林对训练集一视同仁;GBDT是基于权值的弱分类器的集成。
    7)随机森林是通过减少模型方差提高性能;GBDT是通过减少模型偏差提高性能。

    方差与偏差:

    偏差指的是算法的期望预测与真实值之间的偏差程度,反映了模型本身的拟合能力;Bagging每个样本上训练出来的模型取平均值,减小了偏差,并行算法有这种作用

    方差度量了同等大小的训练集的变动导致学习性能的变化,刻画了数据扰动所导致的影响。Boosting是迭代算法,每一次迭代都根据上一次迭代的预测结果对样本进行加权,所以随着迭代进行,误差会越来越小,所以模型的 方差会不断减小

    如何进行特征选择?
    

    特征是否发散:如果一个特征不发散,例如方差接近于0,也就是说样本在这个特征上基本上没有差异,这个特征对于样本的区分并没有什么用。

    特征与目标的相关性:与目标相关性高的特征,应该优先选择。

    根据特征选择的形式分为以下几种:

    Filter(过滤法):按照发散性或者相关性对各个特征进行评分,设定阈值或者待选择阈值的个数,选择特征。

    Wrapper(包装法):根据目标函数(通常是预测效果),每次选择若干特征,或者排除若干特征。

    Embedded(嵌入法):先使用某些机器学习的算法和模型进行训练,得到各个特征的权值系数,根据系数从大到小选择特征。类似于Filter方法,但是是通过训练来确定特征的优劣。

    聚类算法中的距离度量有哪些
    

    欧氏距离:可以简单的描述为多维空间的点点之间的几何距离

    曼哈顿距离:如果欧式距离看成是多维空间对象点点的直线距离,那么曼哈顿距离就是计算从一个对象到另一个对象所经过的折线距离

    参考:  LR与SVM的异同  https://www.cnblogs.com/zhizhan/p/5038747.html

             RF和GBDT区别  https://blog.csdn.net/blank_tj/article/details/82453535

             方差与偏差 https://blog.csdn.net/zrh_CSDN/article/details/80934338

            特征选择   https://blog.csdn.net/datoutong_/article/details/78813233

    展开全文
  • 给定两个矩阵判断第二个矩阵在第一个矩阵哪些位置出现过 输出位置的左上角 有多个答案,按字典序输出 解法1 用一个数字来代替一个矩阵 枚举两个矩阵,n4,,504是1亿以内的 解法2 哈希字符串 ebacd ...

    习题课4-1(hash)

    矩形

    • 给定两个矩阵,判断第二个矩阵在第一个矩阵哪些位置出现过

    • 输出位置的左上角

    • 有多个答案,按字典序输出

    解法1

    • 一行行一列列依次比较
    • 枚举两个矩阵,n的4次方,,50的4次方是1亿以内的

    解法2

    • 将一个矩阵转化成一个数字

    哈希字符串

    • ebacd

    • hash(ebacd) = (5B^4+2B^3+B^2+3B^1+4B^0) mod mo
      
    • B是大于26的任意整数,最好取质数 mo为一个较大的质数

    • 将这个推广到正常的整数序列中去,假设所给的整数序列是a_i

    • hash({ai})=(i=1naiBni)  mod mo hash(\{a_i\}) = (\sum_{i=1}^na_iB^{n-i}) \space\space mod \space mo

    • 其中B是任意大于max{a_i}的整数,标程中B取233

    • 解决了一维,拓展到二维

    • 计算一个矩形A_{nXm}的hash值,我们先对每一行求一次hash值,得到n个hash值,然后再对n个hash值再做一遍一维hash

    • 一般来说下一次hash时,B取多少?应该大于等于mo

    • 尽量减少碰撞的可能(密码学里有个碰撞的概念)

    • 取两套B mo,如果算出来的hash1和hash2都相等,则认为这两个矩形相等

    代码解析

    • mo1 是1e9+7 mo2是1e9+9 B都是233(大于100(题目数据取值范围)的任意质数)

    • pair是一个二元组

    • for (int i = 1; i <= q; i++) {
                      p1 = p1 * pw % mo1;
                      p2 = p2 * pw % mo2;
                  }
      
    • 得到B^q次方的值,中间需要对mo取模

    • p1 = (mo1 - p1) % mo1;
      
    • (mo1-p1) = (-p1+mo1) 因为最后要求的是(-B^q)的值

    • for (int i = 1; i <= n; i++) {
                      long t1 = 0, t2 = 0;
                      for (int j = 1; j <= m; j++) {
                          if (j < q) {
      
      
                              t1 = (t1 * pw + a[i][j]) % mo1;
                              t2 = (t2 * pw + a[i][j]) % mo2;
                          } else {
                              t1 = h1[0][i][j] = (t1 * pw + a[i][j] + p1 * a[i][j - q]) % mo1;
                              t2 = h2[0][i][j] = (t2 * pw + a[i][j] + p2 * a[i][j - q]) % mo2;
                          }
                      }
                  }
      
    • j<q,是为了目标矩形的大小,计算出存储到h1()()()数组中的值是跟目标矩阵的大小相等的

    • 而当j>=q时,此时除了新加的a(i)(j),还要减掉前一次计算的头值

    • 按列计算hash值过程类似

    • 最后输出答案时,由于存储hash值的位置在右下角,而题目要求输出左上角,所以结果就是(i-p+1,j-q+1)

    标程

    • static class Task {
      
              // 类似于c++里的pair
              class pii {
                  public int first;
                  public int second;
      
                  public pii() {
                      first = second = 0;
                  }
      
                  public pii(int first, int second) {
                      this.first = first;
                      this.second = second;
                  }
              }
      
              final int N = 1005;
              final long mo1 = (long) 1e9 + 7; // 模数最好取质数
              final long mo2 = (long) 1e9 + 9;
              final long pw = 233; // base
      
              // 全局变量
          	// bb:对于b数组,bb[0][i][j]表示从(i,1)到(i,j)的横向hash值(对mo1)取模,bb[1][i][j]表示从(i,1)到(i,j)的横向hash值(对mo2)取模
              long[][][] h1 = new long[2][N][N];
              long[][][] h2 = new long[2][N][N];
              long[][][] bb = new long[2][N][N];
      
              // 为了减少复制开销,我们直接读入信息到全局变量中
              // a, b:题目所述数组,a的大小为(n+1)*(m+1),b的大小为(p+1)*(q+1),下标均从1开始有意义(下标0无意义,你可以直接无视)
              // n, m, p, q:题中所述
         		// n,m,p,q都是实际大小,上面+1是因为数组下标从0开始
              int[][] a = new int[N][N];
              int[][] b = new int[N][N];
              int n, m, p, q;
      
              // 求出a中有哪些位置出现了b
              // 返回值:一个pii的数组,包含所有出现的位置
              List<pii> getAnswer() {
                  // (a+b) % mo = ((a%mo)+(b%mo))%mo
                  // (a-b) % mo = ((a-b)%mo + mo) % mo // 要把范围限制在[0,mo-1]内
                  // (a*b) % mo = (a%mo) * (b%mo) %mo
                  // 注意,以下所有变量类似于p1,p2的,都表示同一意义,仅仅是取的模数不同(前者是对mo1取模,后者是对mo2),所以下方注释仅给mo1的注释
                  
                  // p1 = (-pw^q) % mo1
                  // pw^q在后面要用
                  long p1 = 1, p2 = 1;
                  for (int i = 1; i <= q; i++) {
                      p1 = p1 * pw % mo1;
                      p2 = p2 * pw % mo2;
                  }
                  // p1 = ((0-p1)%mo1 + mo1) %mo1
                  // 因为p1在上面幂乘的过程中一直对mo1取模,所以是mo1之内的
                  // p1 = (mo1-p1) % mo1;
                  p1 = (mo1 - p1) % mo1;
                  p2 = (mo2 - p2) % mo2;
      			
                  // 用a数组计算横向hash值,存储为h1[0]
                  // i表示矩阵的行号,是第几行
                  for (int i = 1; i <= n; i++) {
                      long t1 = 0, t2 = 0;
                      // j表示矩阵的列
                      for (int j = 1; j <= m; j++) {
                          // 一直循环到q-1
                          // 假设n,m=4,p,q=2
                          // 以第一行为例
                          // 此处算出[1][1]+[1][2]的hash值,存储到了[1][2]
                          if (j < q) {
      						// 之前,t1 = a[i][0] pw^(j-2) + a[i][1] pw^(j-3) + ... + a[i][j-2] pw + a[i][j-1]
                              // 之后,t1 = a[i][0] pw^(j-1) + a[i][1] pw^(j-2) + ... + a[i][j-1] pw + a[i][j]
                              // 所以 之前的t1乘上pw后,再加上a[i][j]就得到了之后的t1
                              t1 = (t1 * pw + a[i][j]) % mo1;
                              t2 = (t2 * pw + a[i][j]) % mo2;
                          } 
                          // 怎么由[1][1]+[1][2]推出[1][2]+[1][3]呢
                          else {
                              // 之前,t1 = a[i][j-q] pw^(j-1) + a[i][j-q+1] pw^(j-2) + ... + a[i][j-2] pw + a[i][j-1]
                              // 之后,t1 = a[i][j-q+1] pw^(j-1) + a[i][j-q+2] pw^(j-2) + ... + a[i][j-1] pw + a[i][j]
                              // 所以 之前的t1乘上pw后,再减去a[i][j-q] pw^j,再加上a[i][j]就得到了之后的t1
                              t1 = h1[0][i][j] = (t1 * pw + a[i][j] + p1 * a[i][j - q]) % mo1;
                              t2 = h2[0][i][j] = (t2 * pw + a[i][j] + p2 * a[i][j - q]) % mo2;
                          }
                      }
                  }
      
                  // p1 = (-pw^q)%mo1
                  p1 = 1;
                  p2 = 1;
                  for (int i = 1; i <= p; i++) {
                      p1 = p1 * pw % mo1;
                      p2 = p2 * pw % mo2;
                  }
      
                  p1 = (mo1 - p1) % mo1;
                  p2 = (mo2 - p2) % mo2;
      			
                  // 用h1[0]数组计算纵向hash值,存储为h1[1],与上方类似
                  // j表示矩阵的列
                  for (int j = 1; j <= m; j++) {
                      long t1 = 0, t2 = 0;
                      // i表示矩阵的行
                      for (int i = 1; i <= n; i++) {
                          if (i < p) {
                              t1 = (t1 * pw + h1[0][i][j]) % mo1;
                              t2 = (t2 * pw + h2[0][i][j]) % mo2;
                          } else {
                              t1 = h1[1][i][j] = (t1 * pw + h1[0][i][j] + p1 * h1[0][i - p][j]) % mo1;
                              t2 = h2[1][i][j] = (t2 * pw + h2[0][i][j] + p2 * h2[0][i - p][j]) % mo2;
                          }
                      }
                  }
      
      			// 计算b数组的横向hash值,存储为bb数组,与上方类似
                  // 计算小矩阵的hash值
                  // 先按行计算一遍
                  for (int i = 1; i <= p; i++) {
                      for (int j = 1; j <= q; j++) {
                          bb[0][i][j] = (bb[0][i][j - 1] * pw + b[i][j]) % mo1;
                          bb[1][i][j] = (bb[1][i][j - 1] * pw + b[i][j]) % mo2;
                      }
                  }
      
                  p1 = p2 = 0;
                  // 再按列计算一遍
                  // 用bb数组的最后一列来计算整个b数组的hash值,存储为p1
                  for (int i = 1; i <= p; i++) {
                      p1 = (p1*pw+bb[0][i][q])%mo1;
                      p2 = (p2*pw+bb[1][i][q])%mo2;
                  }
      			
                  // 若值相同,说明匹配到了相同的矩形(右下角),题中要求输出左上角,故得到的坐标是(i-p+1,j-q+1)
                  List<pii> ans = new ArrayList<>();
                  for (int i = p; i <= n; i++) {
                      for (int j = q; j <= m; j++) {
                          if (h1[1][i][j] == p1 && h2[1][i][j] == p2) {
                              ans.add(new pii(i - p + 1, j - q + 1));
                          }
                      }
                  }
      
                  return ans;
              }
      }
      

    回文串

    • 给定一个字符串,求出该字符串中有多少子串是回文串
    • 子串是字符串连续的一段
    • 回文串是原字符串倒序写出来和该字符串相同

    解法1

    • 把字符串倒过来写
    • 枚举子串是O(n2),判断回文串是O(n),整体是O(n3)

    解法2

    • 枚举子串
    • 每一个子串正序算一遍hash值,反序算一遍哈希值,结果相等则认为相等
    • 时间复杂度是O(n^2)

    解法3(manacher算法)

    • 线性时间求出
    • 格式化+对称性+单调性
    • 回文串长度有奇偶怎么办?
    • 格式化:在字符串中间插入一个相同字符
    • 对称性,回文串是对称的,每次记录最远的位置,根据对称性算出当前所在位置的回文串长度(至少长多少)
    • 单调性,每一次最远的位置是单调上升的
    0 1 2 3 4 5 6 7 8 9 10 11 12
    s % # a # a # b # a # a # $
    len 0 0 1 2 1 0 5 0 1 2 1 0 0
    cur 0 0 2 3 3 3 6 6 6 6 6 6 0

    代码解析

    • cursor是指针的意思

    • cur作为中心点

    • i是移动点

    • pos = cur*2-i 就是关于中心对称的右端点位置,

    • int pos = (cur<<1) - i;
                      int now = Math.max(Math.min(len[pos],cur+len[cur]-i),0);
      
    • cur+len(cur)-i求出i这个点通过对称性得出的至少的回文串长度

    • while(s[i-now-1] == s[i+now+1]) {
                          ++now;
                      }
      
    • 尝试往两边扩张

    • if (i+now > cur + len[cur]){
                          cur = i;
                      }
      
    • 更新cur,因为之前i+l(i)总是小于等于cur+l(cur)

    • 最后得到的答案就是最长回文串除以2向上取整,就是这个回文串及其子串的所有回文串数目

    标程

    • static class Task {
      
              /* 全局变量 */
              final int N = 500005;
      
              char[] s = new char[N*2];
              int[] len = new int[N*2];
      
              // 计算str中有多少个回文子串
              // 返回值:子串的数目
              long getAnswer(String str) {
                  
                  int n = str.length();
                  for (int i = n; i != 0 ; --i) {
                      s[i<<1] = str.charAt(i-1);
                      s[i<<1 | 1] = 0;
                  }
      
                  n = n << 1 | 1;
                  s[1] = 0;
                  s[0] = 1;
                  s[n+1] = 2;
      			
                  // manacher算法
                  int cur = 1;
                  long ans = 0;
                  for (int i = 2; i <= n; i++) {
                      // cursor是对称中心
                      // i和pos是关于cursor对称的对称点
                      int pos = (cur<<1) - i;
                      // now是pos到0的距离和i到2n的距离的最小者,如果越界了就是0
                      // now就是i能往两侧至少能拓展多长
                      int now = Math.max(Math.min(len[pos],cur+len[cur]-i),0);
                      while(s[i-now-1] == s[i+now+1]) {
                          ++now;
                      }
                      // cur+len[cur]要保证是最大的
                      // 找到一个比当前对称中心所处的回文串要大的对称中心点,更新对称中心
                      if (i+now > cur + len[cur]){
                          cur = i;
                      }
                      // 相当于now/2取上界
                      // 一个字母也算回文串
                      ans += Math.ceil(now/2.0);
                      // 更新目前的回文串长度
                      len[i] = now;
      
                  }
      
                  return ans;
              }
      
             
      }
      
    展开全文
  •  另外,可以用isgray判断矩阵是否是一个图像数据矩阵。 下边附件为本人和论坛好友huangpan讨论后的一个小MATLAB程序,实现的功能是求图像的峰值信噪比,挺简单的,但因为初学,收获了很多,也希望对大家有用吧。...
  • (2)我的思路:根据图形中的每个像素点的差异去判断,对原图的灰度图做二值化处理,不是线条的区域像素置0,有线条的区域置为255,然后逐列进行像素求和,如果列的和大于0则是检测到了线条,此时结束该列的扫描,
  • 面试题20:顺时针打印矩阵:首先需要判断每一步开始是的坐标点是否满足小于行数的一半且小于列数的一半,在最后一圈中,可能出现仅能向右走一行,仅能向右走一行向下走一列,向右走一行向下走一列向左走一行,能走...
  • 你必须知道的495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    1.30如何判断哪些标识符可以使用,哪些被保留了? 初始化 1.31 对于没有显式初始化的变量的初始值可以作怎样的假定?如果一个全局变量初始值为“零”,它可否作为空指针或浮点零? 1.32 下面的代码为什么不能...
  • 通过判断abr中每一点的相交(累积)数量,大于一定阈值的点就认为是圆。 以上是标准霍夫圆变换实现算法。 问题是它的累加到一个三维的空间,意味着比霍夫线变换需要更多的计算消耗。 Opencv霍夫圆变换对标准...
  • excel的使用

    2012-11-25 17:06:01
    再比如,公式: =if(SUM(A1:A5>0,SUM(A1:A5),0) 此式就利用了嵌套函数,意思是,当A1至A5的和大于0时,返回这个值,如果小于0,那么就返回0。 还有一点要提醒你注意:以上的符号均为半角,而且IF与括号之间...
  • 《你必须知道的495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    1.30 如何判断哪些标识符可以使用,哪些被保留了? 15 初始化 18 1.31 对于没有显式初始化的变量的初始值可以作怎样的假定?如果一个全局变量初始值为“零”,它可否作为空指针或浮点零? 18  1.32 下面的...
  • 2025NOIP普及组.rar

    2010-10-26 18:18:25
    这道题目非常简单,题目的意思已经把该题的算法描述得再清楚不过了,初始时Sn=0,n=0,然后每次循环nn+1,SnSn+1/n,,直到Sn大于K,最后输出K。另外实型(Real是最慢的,建议用Extended)的运算速度不是很快,而K为1~...
  • 1.30 如何判断哪些标识符可以使用,哪些被保留了? 15 初始化 18 1.31 对于没有显式初始化的变量的初始值可以作怎样的假定?如果一个全局变量初始值为“零”,它可否作为空指针或浮点零? 18  1.32 下面的...
  • 随着人们生活水平的提高,如何实现家庭防盗这一问题也变的尤其的突出,传统的机械锁由于其构造的简单,被撬的事件屡见不鲜,电子锁由于其保密性高,使用灵活性好,安全系数高,受到了广大用户的亲呢。 设计本课题时...
  • 3.3 判断取值范围是否跨越了2的幂边界 59 3.4 习题 61 第4章 算术边界 63 4.1 检测整数边界 63 4.2 通过加减法传播边界 65 4.3 通过逻辑操作传播边界 69 4.4 习题 73 第5章 位计数 74 5.1 统计值为“1”的位...
  •  rainDrop.x rainDrop.xLength : rainDrop.x - rainDrop.xLength这是因为,我们的雨滴是一直往下移动即y是增加的,我们上面知道斜率公式为:k=(y1-y2)/(x1-x2)即y1-y2肯定是大于0的,因此当斜率小于0的时候,...
  • 达内 coreJava 习题答案

    2010-02-10 19:49:01
    打印出第一个大于 3.1415小于 3.1416的值 class Pi { public static void main(String[] args){ double pi =0; //定义初始值 double fenZi = 4; //分子为4 double fenMu = 1; //第一个4,可看作分母为1 的...
  • o 3.11 为什么 sizeof 返回的值大于结构的期望值, 是不是尾部有填充? o 3.12 如何确定域在结构中的字节偏移? o 3.13 怎样在运行时用名字访问结构中的域? o 3.14 程序运行正确, 但退出时却 ``core dump''了,...

空空如也

空空如也

1 2 3
收藏数 41
精华内容 16
关键字:

如何判断矩阵大于0