Hexo
0%

Posted on In ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

块状数组

对整体数组进行分块执行

零散块暴力处理，适用于操作数较小时

对区间[l,r]的数加上k

询问[l,r]中有多少数大于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
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
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
const int SQ = 1e3 + 10;
/*
st[i]: 第i块的起始下标
ed[i]: 第i块的终止下标
size[i]: 第i块的长度
bel[i]: 下标为i的数据对应第几块
mark[i]: 第i块整块的修改值
*/
int n, m, a[maxn], st[SQ], ed[SQ], size[SQ], bel[maxn], mark[SQ];
vector<int> v[SQ]; // 第i块的集合

void init_block()
{
    int sq = sqrt(n);
    for (int i = 1; i <= sq; ++i)
    {
        st[i] = n / sq * (i - 1) + 1;
        ed[i] = n / sq * i;
    }
    ed[sq] = n;
    for (int i = 1; i <= sq; ++i)
    {
        for (int j = st[i]; j <= ed[i]; ++j)
            bel[j] = i;
    }
    for (int i = 1; i <= sq; ++i)
        size[i] = ed[i] - st[i] + 1;
}

void update(int t) // 更新排序后的数组
{
    for (int i = 0; i <= size[t]; ++i)
        v[t][i] = a[st[t] + i];
    sort(v[t].begin(), v[t].end());
}

void solve()
{
    cin >> n >> m;
    int sq = sqrt(n);
    init_block();
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= sq; ++i)
    {
        for (int j = st[i]; j <= ed[i]; ++j)
            v[i].push_back(a[j]);
    }

    for (int i = 1; i <= sq; ++i)
        sort(v[i].begin(), v[i].end());

    while (m--)
    {
        int l, r, k, ope;
        cin >> ope >> l >> r >> k;
        if (ope == 1) // 将[l,r]的每个数加上k
        {
            if (bel[l] == bel[r]) // 同一块直接暴力
            {
                for (int i = l; i <= r; ++i)
                    a[i] += k;
                update(bel[l]);
                continue;
            }
            // 零散块处理
            for (int i = l; i <= ed[bel[l]]; ++i)
                a[i] += k;
            for (int i = st[bel[r]]; i <= r; ++i)
                a[i] += k;
            update(bel[l]);
            update(bel[r]);
            for (int i = bel[l] + 1; i < bel[r]; ++i) // 中间一大段的块直接打标记
                mark[i] += k;
        }
        else//查找[l,r]中大于等于k的个数
        {
            int sum = 0;
            if(bel[l]==bel[r])
            {
                for (int i = l; i <= r;++i)
                {
                    if(a[i]+mark[bel[i]]>=k)
                        sum++;
                }
                cout << sum << endl;
                continue;
            }
            for (int i = l; i <= ed[bel[l]];++i)
            {
                if(a[i]+mark[bel[i]]>=k)
                    sum++;
            }
            for (int i = st[bel[r]]; i <= r;++i)
            {
                if(a[i]+mark[bel[i]]>=k)
                    sum++;
            }
            //二分查找k-mark[i]的位置
            for (int i = bel[l] + 1; i < bel[r] - 1;++i)
            {
                sum += v[i].end() - lower_bound(v[i].begin(), v[i].end(), k - mark[i]);
            }
            cout << sum << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}
Read more »

Posted on In ,
Symbols count in article: 230 Reading time ≈ 1 mins.

快速幂

1
2
3
4
5
6
7
8
9
10
11
//计算a的b次方mod m
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

根据费马小定理，如果 m 是一个质数，我们可以计算 $a^{b\ mod\ (m-1)}$ 来加速算法过程

Read more »

Posted on In ,
Symbols count in article: 3.1k Reading time ≈ 3 mins.

高精度计算

存储

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
#include <cstdio>
#include <cstring>

static const int LEN = 1004;

int a[LEN], b[LEN];

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

int main() {
  read(a);
  print(a);

  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
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
#include <cstdio>
#include <cstring>

static const int LEN = 1004;

int a[LEN], b[LEN], c[LEN], d[LEN];

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

//加法计算器
void add(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] + b[i];
    if (c[i] >= 10) {
      c[i + 1] += 1;
      c[i] -= 10;
    }
  }
}

//减法计算器
void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

//乘法计算器(高精度-低精度)
void mul_short(int a[], int b, int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    // 直接把 a 的第 i 位数码乘以乘数，加入结果
    c[i] += a[i] * b;

    if (c[i] >= 10) {
      // 处理进位
      // c[i] / 10 即除法的商数成为进位的增量值
      c[i + 1] += c[i] / 10;
      // 而 c[i] % 10 即除法的余数成为在当前位留下的值
      c[i] %= 10;
    }
  }
}

//乘法计算器(高精度-高精度)
void mul(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];

    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}


bool greater_eq(int a[], int b[], int last_dg, int len) {
  if (a[last_dg + len] != 0) return true;
  for (int i = len - 1; i >= 0; --i) {
    if (a[last_dg + i] > b[i]) return true;
    if (a[last_dg + i] < b[i]) return false;
  }
  return true;
}

//除法计算器
void div(int a[], int b[], int c[], int d[]) {
  clear(c);
  clear(d);

  int la, lb;
  for (la = LEN - 1; la > 0; --la)
    if (a[la - 1] != 0) break;
  for (lb = LEN - 1; lb > 0; --lb)
    if (b[lb - 1] != 0) break;
  if (lb == 0) {
    puts("> <");
    return;
  }

  for (int i = 0; i < la; ++i) d[i] = a[i];
  for (int i = la - lb; i >= 0; --i) {
    while (greater_eq(d, b, i, lb)) {
      for (int j = 0; j < lb; ++j) {
        d[i + j] -= b[j];
        if (d[i + j] < 0) {
          d[i + j + 1] -= 1;
          d[i + j] += 10;
        }
      }
      c[i] += 1;
    }
  }
}

int main() {
  read(a);

  char op[4];
  scanf("%s", op);

  read(b);

  switch (op[0]) {
    case '+':
      add(a, b, c);
      print(c);
      break;
    case '-':
      sub(a, b, c);
      print(c);
      break;
    case '*':
      mul(a, b, c);
      print(c);
      break;
    case '/':
      div(a, b, c, d);
      print(c);
      print(d);
      break;
    default:
      puts("> <");
  }

  return 0;
}
Read more »

Posted on In ,
Symbols count in article: 188 Reading time ≈ 1 mins.

卡特兰数

令h(0)=1,h(1)=1，catalan数满足递推式。h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)h(0) (n>=2)。也就是说，如果能把公式化成上面这种形式的数，就是卡特兰数。

h(n)=c(2n,n)-c(2n,n+1)

h(n)=C(2n,n)/(n+1)

Read more »

Posted on In ,
Symbols count in article: 164 Reading time ≈ 1 mins.

斐波那契数列

$F_{n-1}F_{n+1}-F_n^{2} = (-1)^n$

$F_{n+k}=F_kF_{n+1}+F_{k-1}F_n$

取上一条性质中k=n，我们得到$F_{2n}=F_n(F_{n+1}+F_{n-1})$

GCD性质：$(F_m,F_n)=F_{(m,n)}$

Read more »