发表于

每天都在努力，证明我是在认真的活着

发表于

RMQ算法用途

RMQ算法：对于任意给定的一个数列a,求RMQ(a,i,j)就是求a数列中[i,j]中的最大值和最小值。

时间复杂度

RMQ算法是快速求区间最值得离线算法，预处理的复杂度为O(n*logn),查询O(1)[用线段树也可以做，RMQ算法主要用到了DP的思想]

算法实现

DP+位运算

发表于

1881: 身份证校验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*直接模拟题目的意思就可以了，开始做的时候没注意“如果末位是X，则对应位为10”。
*/
#include<iostream>
#include<cstring>

using namespace std;
int main(){
    string a;
    cin>>a;
    int sa=a.length();
    int ans=0;
    ans=7*(a[0]-'0')+9*(a[1]-'0')+10*(a[2]-'0')+5*(a[3]-'0')
    +8*(a[4]-'0')+ 4*(a[5]-'0')+ 2*(a[6]-'0')+ 1*(a[7]-'0')
    +6*(a[8]-'0') +3*(a[9]-'0')+ 7*(a[10]-'0')+ 9*(a[11]-'0')
    +10*(a[12]-'0') +5*(a[13]-'0')+8*(a[14]-'0')+4*(a[15]-'0')
    +2*(a[16]-'0');
      if(a[sa-1]=='X'||a[sa-1]=='x')ans=ans+10;
      else ans=ans+a[17]-'0';
      if(ans%11==1)cout<<"Success"<<endl;
      else cout<<"Failure"<<endl;
    return 0;
}
阅读全文 »

发表于

求a^n的值

//最容易想到的求a^n的代码  
typedef long long LL;
LL powr(LL a,LL n){
    if(n==0)return 1;
    else{
        LL ans=1;
        for(int i=1;i<=n;i++)ans=ans*a;
        return ans;
    }
}

快速幂

用上面的代码求a^n的时间复杂度为O(n)，其实这个时间复杂度一般情况下还可以，但是如果遇到很大的n，那么最后求出的数据的值很大，计算量会暴涨。
快速幂运用了结合律的思想而且使用了位运算极大的节省了时间，一般情况下，位运算是比其他的运算快很多的，因为其他运算在计算机中都是转换为位运算来计算的。直接使用位运算也可以为我们节省很多的时间。

阅读全文 »

发表于

欧拉函数定义

1：文字描述:对于正整数n，欧拉函数是小于n的正整数中与n互质的整数的个数。
例如：PHI(2)=1,PHI(3)=2。
所以容易得到素数t的欧拉函数值为t-1
2：公式:PHI(n)=n(1-1/p1)…(1-1/pi)
p1,p2…pi为唯一分解定理中的因数。
(即n=p1^k1 p2^k2 …pi^ki)

阅读全文 »