Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing7 minutes read (About 1102 words)

［心痛］线段树或树状数组求逆序数

原文地址

线段树或树状数组求逆序数

求逆序数的方法有分治，归并，本文只介绍线段树或树状数组求逆序数的办法，众所周知，线段树和树状树可以用来解决区间操作问题，就是因为这两个算法区间操作的时间复杂度很低O(logN)，才让这种方法具有可行性。

首先先来看一个序列   6 1 2 7 3 4 8 5，此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数，但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组，然后找出这个数后面有多少个数是小于这个数的，小于它逆序数+1。仔细想一下，如果我们不用枚举这个数后面的所有数，而是直接得到小于这个数的个数，那么效率将会大大提高。

总共有N个数，如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢？不妨假设有一个区间 [1,N]，只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0，然后把第i个数之前出现过的数都在相应的区间把它的值定为1，那么问题就转换成了[i+1,N]值的总和。再仔细想一下，区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1)，所以区间[i+1,N]值的总和等于N-[1,i]的值！因为总共有N个数，不是比它小就是比它(大或等于)。

现在问题已经转化成了区间问题，枚举每个数，然后查询这个数前面的区间值的总和， i-[1,i] 既为逆序数。

线段树预处理时间复杂度O(NlogN)，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(3*NlogN)

树状数组不用预处理，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(2*NlogN)

线段树:
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// 线段树
#include <stdio .h>
#include <string .h>
#include <stdlib .h>
#define MAX 51000
#define MID(a,b) (a+b)>>1
#define R(a) (a< <1|1)
#define L(a) a<<1
typedef struct {
    int num,left,right;
}Node;
int ans[MAX];
Node Tree[MAX<<2];
int n;

void Build(int t,int l,int r)         //以1为根节点建立线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].num=0;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
}

void Insert(int t,int l,int r,int x)     //向以1为根节点的区间[l,r]插入数字1
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].num+=x;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Insert(R(t),l,r,x);
    }
    else if(r< =mid)
    {
        Insert(L(t),l,r,x);
    }
    else
    {
        Insert(L(t),l,mid,x);
        Insert(R(t),mid+1,r,x);
    }
    Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}

int Query(int t,int l,int r)           //查询以1为根节点，区间[l,r]的和
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
        return Tree[t].num;
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        return Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        return Query(L(t),l,r);
    }
    else
    {
        return Query(L(t),l,mid)+Query(R(t),mid+1,r);
    }
}


int main()
{
    int a,n,i,t;
    scanf("%d",&t);
    long long int k;
    while(t--)
    {
        scanf("%d",&n);
        memset(Tree,0,sizeof(Tree));  //初始化线段树
        Build(1,1,n);
        for(i=1;i<=n;i++)             //输入n个数
        {
            scanf("%d",&ans[i]);
        }
        for(i=1,k=0;i<=n;i++)
        {
            a=ans[i];
            Insert(1,a,a,1);          //把线段树[ans[i],ans[i]]区间的值插入为1
            k=k+(i-Query(1,1,a));     //查询区间[1,ans[i]]值的总和,逆序数等于i-[1,ans[i]]
        }
        printf("%lld\n",k);
    }
    return 0;
}

树状数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 树状数组
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 100010
int c[MAX],a[MAX],ans[MAX],n;

int Lowbit(int x)      //返回二进制最后一个1所表示的数
{
  return x&(-x);
}

void Updata(int x)     //向前更新
{
  while(x<=n)
  {
    c[x]++;
    x+=Lowbit(x);
  }
}

int Sum(int x)         //向后更新求和
{
  int sum=0;
  while(x>0)
  {
    sum+=c[x];
    x-=Lowbit(x);
  }
  return sum;
}

int main()
{
  int i,t,k;
    scanf("%d",&t);
  while(t--)
  {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
    {
      scanf("%d",&ans[i]);
    }
    memset(c,0,sizeof(c));        //初始化树状数组
    for(i=1,k=0;i<=n;i++)
    {
      Updata(ans[i]);         //向后更新节点ans[i].k
      k=k+(i-Sum(ans[i]));    //向前查询节点ans[i].k
    }
    printf("%d\n",k);
  }
  return 0;
}

 

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programinga few seconds read (About 25 words)

FFZU-ACM月赛不行了

线段树/树状数组的另一种用法不会，它的逆向问题更不会

Posted Updated  Semprathlon / Simfae Dean OSa few seconds read (About 27 words)

Mac OS 下怎样写作业

我本以为 存在WPS office for Mac而不存在Microsoft office for Mac，真实情况正好相反...

Posted Updated  Semprathlon / Simfae Dean Abouta few seconds read (About 8 words)

OOP outline 

  • 抽象
  • 继承
  • 封装
  • 多态
Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing5 minutes read (About 692 words)

【GDUT-ACM】大灌水

难以容忍的两个WA
Problem C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            priority_queue<LL,vector<LL>,greater<LL> > que;
            CLEAR(a);
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++) scanf("%lld",&a[i]);
            sort(a,a+n);
            for(int i=1;i<=m;i++)
            {
                que.push(a[n-i]);
            }
            LL ans=a[n-1];
            for(int i=n-m-1;i>=0;i--)
            {
                LL k=que.top();
                que.pop();
                que.push(k+a[i]);
                ans=max(ans,k+a[i]);
            }
            printf("%lld\n",ans);
        }
    return 0;
}

Problem D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e5;
const LL maxl=1e5+10;
const int inf=99999999;
const float eps=1e-3;
 
LL a[maxn];
bool vis[maxl];
int n,m;
vector<LL> vec;
 
void init();
void solve();
void outp();
 
void get_prime()
{
    vec.clear();
    CLEAR(vis);
    int k=0;
    for (int i = 2; i < maxl;i++)
        if(!vis[i])
        {
            k++;
            vec.push_back(i);
            for (int j = 1; i * j <= maxl; j++)
            {
            vis[i * j] = 1;
            }
        }
}
 
int getfac(LL n)
{
    if (n<2) return 0;
    int h=0,res=0;
    while(h<vec.size())
    {
        if (n%vec[h]==0) res++;
        while (n%vec[h]==0) n/=vec[h];
        h++;
    }
    return res;
}
 
LL pow2(LL n)
{
    if (n<=0) return 1;
    else if (n==1) return 2;
    else if (n&1)
    {
        int k=pow2((n-1)>>1);
        return (k*k)<<1;
    }
    else
    {
        int k=pow2(n>>1);
        return k*k;
    }
}
 
int main()
{
    get_prime();
    int T;
    LL n,m;
    scanf("%d",&T);
    while(T--)
        {
            scanf("%lld%lld",&n,&m);
            if (m%n) {printf("0\n");continue;}
            else if (n==1) {printf("1\n");continue;}
            LL t=m/n;
            //printf("%d\n",getfac(t));
            LL ans=pow2(getfac(t)-1);
            printf("%lld\n",ans);
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1113
    User: semprathlon
    Language: C++
    Result: Wrong Answer
****************************************************************/

=====================================
Problem F
罕见的PE，输出末尾不能有多余空格，防不胜防

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=200;
const int inf=99999999;
const float eps=1e-3;
 
int a[maxn];
 
void init();
void solve();
void outp();
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(a);
            scanf("%d%d",&n,&m);
            int mina=inf,h=0;
            for(int i=0;i<m;i++)
            {
                int k;
                scanf("%d",&k);
                if (k<mina)
                {
                    mina=k;
                    a[h++]=k;
                }
            }
            sort(a,a+h);
            int k=0;
            for(int i=1;i<=n;i++)
            {
                if (k<h-1&&a[k+1]<=i) k++;
                if (i<n) printf("%d ",a[k]);
                else printf("%d",a[k]);
            }
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
 
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1121
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1488 kb
****************************************************************/

Problem G

1
2
3
4
5
6
7
8
9
int main()
{
    while(~scanf("%d",&n))
        {
            int k=n/3;
            printf("%d\n",(n%3)?2*k+n%3-1:2*k);
        }
    return 0;
}

Problem E
裸的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int maxn=2e5;
const int inf=99999999;
const float eps=1e-3;
 
int f[maxn];
int n,m;
 
int getf(int n)
{
    if (f[n]==n) return n;
    else return f[n]=getf(f[n]);
}
 
bool unite(int u,int v)
{
    int x=getf(u);
    int y=getf(v);
    if (x!=y)
    {
        f[ y ]=x;return 1;
    }
    else return 0;
}
 
 
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(f);
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++) f[i]=i;
            for(int i=1;i<=m;i++)
            {
                int u,v;
                scanf("%d%d",&u,&v);
                unite(u,v);
            }
            int ans=-1;
            for(int i=1;i<=n;i++)
                if (f[i]==i) ans++;
            printf("%d\n",ans);
        }
    return 0;
}
 
/**************************************************************
    Problem: 1118
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:264 ms
    Memory:2264 kb
****************************************************************/

=====================
还有个来不及提交的！［个人原因，15：26才加入比赛
Problem H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int maxn=2e4;
const int inf=99999999;
const float eps=1e-3;
const pair<int,int> p0=make_pair(0,0);

int a[maxn],f1[maxn],f2[maxn];
pair<int,int> g1[maxn],g2[maxn];

void init();
void solve();
void outp();


int main()
{
    int T,n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        CLEAR(a);
        CLEAR(f1);
        CLEAR(f2);
        CLEAR(g1);
        CLEAR(g2);
        scanf("%d",&a[1]);
        f1[1]=f2[1]=0;
        g1[1]=g2[1]=p0;
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if (f1[i-1]<f2[i-1])
            {
                g1[i]=make_pair(a[i],g1[i-1].second);
                g2[i]=make_pair(g1[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g1[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g1[i-1].second);
            }
            else
            {
                g1[i]=make_pair(a[i],g2[i-1].second);
                g2[i]=make_pair(g2[i-1].first,a[i]);
                f1[i]=f1[i-1]+abs(a[i]-g2[i-1].first);
                f2[i]=f2[i-1]+abs(a[i]-g2[i-1].second);
            }

        }
        printf("%d\n",min(f1[n],f2[n]));
    }
}

Posted Updated  Semprathlon / Simfae Dean ACM-ICPC / Programing3 minutes read (About 486 words)

【GDUT-ACM】水题差点写跪了，囧

Problem B: 神奇的编码

Description

假如没有阿拉伯数字，我们要怎么表示数字呢
小明想了一个方法如下：
1 -> A
2 -> B
3 -> C
….
25 -> Y
26 -> Z
27 -> AA

28 -> AB
….

现在请你写一个程序完成这个转换

Input

输入的第一个数为一个正整数T,表明接下来有T组数据。
每组数据为一个正整数n ( n <= 1000)

Output

对于每个正整数n,输出他对应的字符串

Sample Input

3 1 10 27

Sample Output

A J AA

没什么神奇的，本质还是进制转换

心急如焚之时，代码风格无比混乱；那个26的倍数的特殊处理，是个大痛点，AC一次耗时25min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))
 
using namespace std;
 
typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;
 
 
int n;
 
void init();
void solve();
void outp();
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            string str;
            scanf("%d",&n);
            //n+=(n-1)/26;
            //n++;
            //if (n%26==0) n--;
            while(n)
            {
                char ch=(n%26)?n%26+'A'-1:(n--,'Z');
                str=ch+str;
                n/=26;
            }
            printf("%s",str.c_str());
            puts("");
        }
    return 0;
}
 
void solve()
{
}
 
void init()
{
    for(int i=1;i<=n;i++)
    {
 
    }
}
 
void outp()
{
    printf("\n");
}
 
/**************************************************************
    Problem: 1112
    User: semprathlon
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1484 kb
****************************************************************/

=======================分隔符==============================

题E
自我感觉正确，可是未能在结束前提交。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n;

char* solve(double v,double d);

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            double v,d;
            scanf("%lf%lf",&v,&d);
            puts(solve(v,d));
        }
    return 0;
}

char* solve(double v,double d)
{
    return (char*)(((v*v*sqrt(2.0))/10.0-d>eps)?"Fire":"Retreat");
}

题A
耗时16min，循环队列，简直没有TLE/MLE的理由

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int n;
int que[maxsize],h,r;
 
int EnQ(int id)
{
    if ((r+1)%maxsize!=h)
    {
        r=(r+1)%maxsize;
        que[r]=id;
        return 0;
    }
    else return -1;
}
 
int DeQ()
{
    if (h!=r)
    {
        int t=h;
        h=(h+1)%maxsize;
        return que[t];
    }
    else return -1;
}
 
int Query(int k)
{
    if (h==r) return -1;
    int t=(h<=r)?r-h:maxsize-r+h;
    return (t>=k)?que[(h+k)%maxsize]:-1;
}
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        {
            CLEAR(que);h=r=0;
            int cas,k;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                scanf("%d",&cas);
            switch(cas)
            {
                case 1:scanf("%d",&k);EnQ(k);break;
                case 2:DeQ();break;
                case 3:scanf("%d",&k);
                if (Query(k)>=0) printf("%d\n",Query(k));
                else puts("na li you zhe me duo ren");
                break;
            }
            }
        }
    return 0;
}
Posted Updated  Semprathlon / Simfae Dean Programinga few seconds read (About 102 words)

在学校机房电脑发现了Microsoft Windows SDK v6 0A

大概是为win32编程准备的。。。
开始菜单项含有：

  • GUID生成器

  • IL反汇编程序

  • manifest generator

  • OLE-COM Object Viewer

  • WinDiff

  • Windows 资源本地化编辑器

  • 安装Microsoft FXCop

  • 服务跟踪查看器

  • 服务配置编辑器

  • 合成日志查看器

  • 清单生成和编辑工具

    • 有几样正是我经常听说却没有认真学习的旧名词

    Posted Updated  Semprathlon / Simfae Dean Programing8 minutes read (About 1174 words)

    BigInteger从Java移植到cpp，自己写了两天，写崩了。。。

    自己的：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    const int LEN=100;
    typedef struct HighPrecision
    {
    	short data[LEN],h;
    	HighPrecision()
    	{
    		CLEAR(data);
    		h=0;
    	}
    	HighPrecision(int n)
    	{
    		CLEAR(data);
    		h=0;
    		while(n>0) data[h++]=n%10,n/=10;
    		if(!data[h]) h--;
    	}
    	/*HighPrecision(const HighPrecision &a)
    	{
    		memcpy(data,a.data,sizeof(data));
    		h=a.h;
    	}*/
    	const HighPrecision &operator= (int n)
    	{
    		CLEAR(data);
    		h=0;
    		while(n>0) data[h++]=n%10,n/=10;
    		if(!data[h]) h--;
    		return *this;
    	}
    	const HighPrecision &operator= (const HighPrecision &a)
    	{
    		memcpy(data,a.data,sizeof(data));
    		h=a.h;
    		return *this;
    	}
    	bool odd()
    	{
    		return data[0]&1;
    	}
    	void output()
    	{
    		for(int i=h;i>=0;i--) printf("%d",data[i]);
    	}
    } BigInteger;

    bool operator< (const BigInteger &a,const BigInteger &b)
    {
    	if (a.h<b.h) return 1;
    	else if (a.h>b.h) return 0;
    	else
    	{
    		int h=b.h,k=0;
    		for(int i=h;i>=0;i--)
    			if (a.data[i]!=b.data[i]) {k=i;break;}
    		return a.data[k]<b.data[k];
    	}
    }

    bool operator< (const BigInteger &a,int n)
    {
    	return a<BigInteger(n);
    }

    bool operator> (const BigInteger &a,const BigInteger &b)
    {
    	if (a.h<b.h) return 0;
    	else if (a.h>b.h) return 1;
    	else
    	{
    		int h=b.h,k=0;
    		for(int i=h;i>=0;i--)
    			if (a.data[i]!=b.data[i]) {k=i;break;}
    		return a.data[k]>b.data[k];
    	}
    }

    bool operator> (const BigInteger &a,int n)
    {
    	return a>BigInteger(n);
    }

    bool operator== (const BigInteger &a,const BigInteger &b)
    {
    	if (a.h!=b.h) return 0;
    	else
    	{
    		int h=b.h,k=0;
    		for(int i=h;i>=0;i--)
    			if (a.data[i]!=b.data[i]) {k=i;break;}
    		return a.data[k]==b.data[k];
    	}
    }

    bool operator== (const BigInteger &a,int n)
    {
    	return a==BigInteger(n);
    }

    bool operator>= (const BigInteger &a,const BigInteger &b)
    {
    	return (a>b)||(a==b);
    }

    BigInteger operator+(const BigInteger &a,const BigInteger &b)
    {
    	BigInteger c;
    	int h=max(a.h,b.h);
    	for(int i=0;i<=h;i++)
    	{
    		c.data[i]+=a.data[i]+b.data[i];
    		c.data[i+1]=c.data[i]/10;
    		c.data[i]%=10;
    	}
    	while(c.data[c.h+1]>0) c.h++;
    	return c;
    }

    BigInteger operator+(const BigInteger &a,int n)
    {
    	return a+BigInteger(n);
    }

    BigInteger operator+= (const BigInteger &a,const BigInteger &b)
    {
    	return a+b;
    }

    BigInteger operator-(const BigInteger &a,const BigInteger &b)
    {
    	BigInteger c(a);
    	int h=c.h;
    	for(int i=0;i<=c.h;i++)
    	{
    		c.data[i]-=b.data[i];
    		if (c.data[i]<0)
    		{
    			c.data[i]+=10;
    			c.data[i+1]--;
    		}
    	}
    	while(c.data[c.h]<1) c.h--;
    	return c;
    }

    BigInteger operator-(const BigInteger &a,int n)
    {
    	return a-BigInteger(n);
    }

    BigInteger operator-= (const BigInteger &a,const BigInteger &b)
    {
    	return a-b;
    }

    BigInteger operator* (const BigInteger &a,const BigInteger &b)
    {
    	BigInteger c;
    	for(int i=0;i<=a.h;i++)
    		for(int j=0;j<=b.h;j++)
    			c.data[i+j-1]+=a.data[i]*b.data[j];
    	int k=0;
    	while(c.data[k++]>0)
    	{
    		c.data[k+1]+=c.data[k]/10;
    		c.data[k]%=10;
    	}
    	c.h=(k-1>=0)?k-1:0;
    	return c;
    }

    BigInteger operator*= (const BigInteger &a,const BigInteger &b)
    {
    	return a*b;
    }

    BigInteger operator/ (const BigInteger &a,const BigInteger &b)
    {
    	BigInteger c,tmp;
    	int h=max(a.h,b.h);
    	for( int i = h; i >= 0; i-- ){
    		tmp*= 10;
    		tmp+= a.data[i];
    		while( tmp >= b ) { tmp -= b; c.data[i]++; }
    	}
    	c.h=a.h;
    	while(c.data[c.h]<1) c.h--;
    	return c;
    }

    BigInteger operator/ (const BigInteger &a,int n)
    {
    	return a/BigInteger(n);
    }

    BigInteger operator/= (const BigInteger &a,const BigInteger &b)
    {
    	return a/b;
    }

    BigInteger operator% (const BigInteger &a,const BigInteger &b)
    {
    	BigInteger c,tmp;
    	int h=max(a.h,b.h);
    	for( int i = h; i >= 0; i-- ){
    		tmp*= 10;
    		tmp+= a.data[i];
    		while( tmp >= b ) { tmp -= b; c.data[i]++; }
    	}
    	tmp.h=a.h;
    	while(tmp.data[tmp.h]<1) tmp.h--;
    	return tmp;
    }

    BigInteger operator>>(const BigInteger &a,int n)
    {
    	BigInteger c(a);
    	for (int i=1;i<=n;i++) c=c/2;
    	return c;
    }

    别人的：

    http://blog.csdn.net/wall_f/article/details/8373395

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    const int MAXN = 410;

    struct bign
    {
    	int len, s[MAXN];
    	bign ()
    	{
    		memset(s, 0, sizeof(s));
    		len = 1;
    	}
    	bign (int num) { *this = num; }
    	bign (const char *num) { *this = num; }
    	bign operator = (const int num)
    	{
    		char s[MAXN];
    		sprintf(s, "%d", num);
    		*this = s;
    		return *this;
    	}
    	bign operator = (const char *num)
    	{
    		for(int i = 0; num[i] == '0'; num++) ;  //去前导0
    		len = strlen(num);
    		for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
    		return *this;
    	}
    	bign operator + (const bign &b) const //+
    	{
    		bign c;
    		c.len = 0;
    		for(int i = 0, g = 0; g || i < max(len, b.len); i++)
    		{
    			int x = g;
    			if(i < len) x += s[i];
    			if(i < b.len) x += b.s[i];
    			c.s[c.len++] = x % 10;
    			g = x / 10;
    		}
    		return c;
    	}
    	bign operator += (const bign &b)
    	{
    		*this = *this + b;
    		return *this;
    	}
    	void clean()
    	{
    		while(len > 1 && !s[len-1]) len--;
    	}
    	bign operator * (const bign &b) //*
    	{
    		bign c;
    		c.len = len + b.len;
    		for(int i = 0; i < len; i++)
    		{
    			for(int j = 0; j < b.len; j++)
    			{
    				c.s[i+j] += s[i] * b.s[j];
    			}
    		}
    		for(int i = 0; i < c.len; i++)
    		{
    			c.s[i+1] += c.s[i]/10;
    			c.s[i] %= 10;
    		}
    		c.clean();
    		return c;
    	}
    	bign operator *= (const bign &b)
    	{
    		*this = *this * b;
    		return *this;
    	}
    	bign operator - (const bign &b)
    	{
    		bign c;
    		c.len = 0;
    		for(int i = 0, g = 0; i < len; i++)
    		{
    			int x = s[i] - g;
    			if(i < b.len) x -= b.s[i];
    			if(x >= 0) g = 0;
    			else
    			{
    				g = 1;
    				x += 10;
    			}
    			c.s[c.len++] = x;
    		}
    		c.clean();
    		return c;
    	}
    	bign operator -= (const bign &b)
    	{
    		*this = *this - b;
    		return *this;
    	}
    	bign operator / (const bign &b)
    	{
    		bign c, f = 0;
    		for(int i = len-1; i >= 0; i--)
    		{
    			f = f*10;
    			f.s[0] = s[i];
    			while(f >= b)
    			{
    				f -= b;
    				c.s[i]++;
    			}
    		}
    		c.len = len;
    		c.clean();
    		return c;
    	}
    	bign operator /= (const bign &b)
    	{
    		*this  = *this / b;
    		return *this;
    	}
    	bign operator % (const bign &b)
    	{
    		bign r = *this / b;
    		r = *this - r*b;
    		return r;
    	}
    	bign operator %= (const bign &b)
    	{
    		*this = *this % b;
    		return *this;
    	}
    	bool operator < (const bign &b)
    	{
    		if(len != b.len) return len < b.len;
    		for(int i = len-1; i >= 0; i--)
    		{
    			if(s[i] != b.s[i]) return s[i] < b.s[i];
    		}
    		return false;
    	}
    	bool operator > (const bign &b)
    	{
    		if(len != b.len) return len > b.len;
    		for(int i = len-1; i >= 0; i--)
    		{
    			if(s[i] != b.s[i]) return s[i] > b.s[i];
    		}
    		return false;
    	}
    	bool operator == (const bign &b)
    	{
    		return !(*this > b) && !(*this < b);
    	}
    	bool operator != (const bign &b)
    	{
    		return !(*this == b);
    	}
    	bool operator <= (const bign &b)
    	{
    		return *this < b || *this == b;
    	}
    	bool operator >= (const bign &b)
    	{
    		return *this > b || *this == b;
    	}
    	string str() const
    	{
    		string res = "";
    		for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
    		return res;
    	}
    };

    istream& operator >> (istream &in, bign &x)
    {
    	string s;
    	in >> s;
    	x = s.c_str();
    	return in;
    }

    ostream& operator << (ostream &out, const bign &x)
    {
    	out << x.str();
    	return out;
    }

    int main()
    {
    	bign a, b, c, d, e, f, g;
    	while(cin>>a>>b)
    	{
    		a.clean(), b.clean();
    		c = a+b;
    		d = a-b;
    		e = a*b;
    		f = a/b;
    		g = a%b;
    		cout<<"a+b"<<"="<<c<<endl; // a += b
    		cout<<"a-b"<<"="<<d<<endl; // a -= b;
    		cout<<"a*b"<<"="<<e<<endl; // a *= b;
    		cout<<"a/b"<<"="<<f<<endl; // a /= b;
    		cout<<"a%b"<<"="<<g<<endl; // a %= b;
    		if(a != b) printf("YES\n");
    		else printf("NO\n");
    	}
    	return 0;
    }

    Posted Updated  Semprathlon / Simfae Dean Programinga minute read (About 153 words)

    所以，Interface就是我学OOP的时候，被一而再再而三无视掉的东西

    请问高手,c++/vc怎么写接口(interface)!!!!!!!!!!!!-CSDN论坛-CSDN.NET-中国最大的IT技术社区.

    从C++语言的角度来看，interface就是一个纯虚类，所以它定义的是一组方法的规范，作为接口实现者，必须从这个纯虚类继承一个class并实现所有要求的接口方法。 例： 以下是接口定义（C++语法） class Iface { public: virtual HRESULT __stdcall method1(long) = 0; virtual HRESULT __stdcall method2() = 0; };

    以下是接口实现
    class CIface : public Iface
    {
    public:
    virtual HRESULT __stdcall method1(long a)
    {
    // do something
    return S_OK;
    }
    virtual HRESULT __stdcall method2()
    {
    // do something
    return S_OK;
    }
    };

    Follow

    Categories

    Tags

    ACM-ICPC14
    AC自动机1
    AWS2
    Adobe1
    Angular1
    Apache1
    Arch Linux2
    BFS2
    BIT3
    Bestcoder23
    Bitset3
    Bootstrap1
    C++2
    CCPC1
    Catalan1
    CentOS3
    Clover2
    Compiler1
    Contest6
    Cpp1
    DFS3
    DNS1
    DP13
    DSDT3
    Data Analytics2
    Dinic1
    Docker2
    Eclipse1
    Expect1
    Fibonacci1
    Frontend1
    GLUT1
    GPT1
    GUI1
    Gentoo1
    Geometry1
    Git1
    Github2
    Graduate1
    HTML1
    Hash2
    Heap1
    Interview4
    JNUOJ1
    Java12
    K8s1
    KMP1
    Linux3
    Live Archive2
    MBR1
    MS=DOS1
    Mac14
    Manhattan1
    Multi-Uni5
    MySQL8
    Möbius反演1
    NAS2
    NetworkFlow1
    NoSQL1
    OS2
    OpenCV1
    OpenGL2
    Python11
    RMQ1
    React2
    Regional3
    Repost1
    Ryzen1
    SQLserver1
    SSH1
    SSL1
    System Design1
    TOEFL1
    Template3
    Tree1
    Trie2
    TypeScript2
    UEFI4
    UX1
    Ubuntu15
    Unix1
    Windows2
    Wordpress3
    ZFS1
    ZOJ1
    ajax1
    asm1
    css1
    cuda1
    cudnn1
    curl1
    docker1
    es61
    font1
    ftp1
    git1
    gitlab1
    hardware1
    hdu2
    hexo1
    html1
    https1
    iOS1
    interview1
    java1
    javascript1
    jdk1
    jquery1
    js7
    json1
    kext1
    macOS2
    network2
    nginx4
    node1
    nodejs1
    npm1
    php8
    python1
    react2
    react native1
    regex1
    string4
    二分图1
    二分查找3
    博弈1
    容斥原理3
    并查集1
    并行计算1
    微积分1
    扫描线3
    数列1
    数独1
    数论1
    概率2
    模拟4
    欧拉回路1
    百度之星1
    知乎1
    离散化1
    约瑟夫1
    线段树3
    组合数学1
    网络赛2
    背包1
    背包问题1
    转载博文1
    递归1

    Subscribe for updates

    Links

    ×