发表更新数据结构与算法4 分钟读完 (大约589个字)

树状数组经典题

一个简单的整数问题

题目

第一类指令形如 “C-l-r-d”，表示把数列中第 $l-r$ 个数都加 $d$。

第二类指令形如 “Q-X”，表示询问数列中第 $x$ 个数的值。

阅读更多
发表更新数据结构与算法16 分钟读完 (大约2469个字)

并查集拓展

边带权

银河英雄传说

有 $T$ 条指令，每条指令格式为以下两种之一：

  1. $M-i-j$，表示让第 $i$ 号战舰所在列的全部战舰保持原有顺序，接在第 $j$ 号战舰所在列的尾部。

阅读更多
发表更新数据结构与算法2 分钟读完 (大约243个字)

二维差分

原理

紫色部分为所求区域，黄色区域为当前覆盖的区域。

$d[x1][y1] += w$ 表示将 $[x1, y1]$ 右下部分全部加上增量 $w$。

阅读更多
发表更新数据结构与算法3 分钟读完 (大约448个字)

RMQ算法原理及实现

RMQ（Range Minimum/Maximum Query），区间最值查询问题，是指：对于长度为 $n$ 的数列A，回答若干次询问 $RMQ(i,j)$，返回数列A中下标在区间 $[i,j]$ 中的最小/大值。

这里介绍Tarjan的Sparse-Table算法，预处理时间为 $O(nlogn)$，但查询只需要 $O(1)$，并且常数很小，算法也很容易写出。

1）预处理：

　设 $A[i]$ 是要求区间最值的数列，$d[i, j]$ 表示从第i个数起连续 $2^j$ 个数中的最小值。(DP的状态)

阅读更多
发表更新数据结构与算法3 分钟读完 (大约459个字)

存在负数的背包问题

题目1

体积和价值可能为负数的01背包。

Solution

逆向思维，对于体积为负的物品，我们可以一开始就装进去，背包对应的进行扩容，物品的体积和价值也对应取反。这样在进行背包dp 的时候就代表移除这个物品，答案取最大值即可。

阅读更多
发表更新数据结构与算法1 分钟读完 (大约197个字)

实现kth_element

快排的思想，选定一个基准数，将大于 $mid$ 的数放到右边，小于的放到左边，然后比较 $mid$ 和 $k$ 的位置，递归重复操作即可。 

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
#pragma GCC optimize("Ofast")
#include <cstdio>

inline int read() {
<!--more--> 
  int x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w ^= 1;
    c = getchar();
  }
  while (c <= '9' && c >= '0') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return w & 1 ? x : -x;
}

int kth_element(int* a, int l, int r, int k) {
  int mid = l - 1;
  for (int i = l; i < r; ++i) {
    if (a[i] < a[r] && a[i] ^ a[++mid]) a[i] ^= a[mid] ^= a[i] ^= a[mid];
  }
  if (a[++mid] ^ a[r]) a[mid] ^= a[r] ^= a[mid] ^= a[r];
  if (mid == k) return a[mid];
  return (mid >= k) ? kth_element(a, l, mid - 1, k)
                    : kth_element(a, mid + 1, r, k);
}

int a[2000006];

int main() {
  int n, k;
  n = read();
  k = read();
  for (int i = 0; i < n; ++i) a[i] = read();
  // random_shuffle(a, a + n);
  printf("%d\n", kth_element(a, 0, n - 1, n - k));
  return 0;
}
发表更新数据结构与算法3 分钟读完 (大约522个字)

杜教BM模板

用于求线性递推式第n项，扔进前k+x项即可

Code

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<ll> VI;
typedef pair<ll, ll> PII;
const ll mod = 10000;
ll powmod(ll a, ll b) {
  ll res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
ll _, n;
namespace linear_seq {
const ll N = 10010;
ll res[N], base[N], _c[N], _md[N];
vector<ll> Md;
void mul(ll *a, ll *b, int k) {
  rep(i, 0, k + k) _c[i] = 0;
  rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] =
      (_c[i + j] + a[i] * b[j]) % mod;
  for (ll i = k + k - 1; i >= k; i--)
    if (_c[i])
      rep(j, 0, SZ(Md)) _c[i - k + Md[j]] =
          (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
  rep(i, 0, k) a[i] = _c[i];
}
ll solve(ll n, VI a, VI b) {
  ll ans = 0, pnt = 0;
  ll k = SZ(a);
  assert(SZ(a) == SZ(b));
  rep(i, 0, k) _md[k - 1 - i] = -a[i];
  _md[k] = 1;
  Md.clear();
  rep(i, 0, k) if (_md[i] != 0) Md.push_back(i);
  rep(i, 0, k) res[i] = base[i] = 0;
  res[0] = 1;
  while ((1ll << pnt) <= n) pnt++;
  for (ll p = pnt; p >= 0; p--) {
    mul(res, res, k);
    if ((n >> p) & 1) {
      for (ll i = k - 1; i >= 0; i--) res[i + 1] = res[i];
      res[0] = 0;
      rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
    }
  }
  rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod;
  if (ans < 0) ans += mod;
  return ans;
}
VI BM(VI s) {
  VI C(1, 1), B(1, 1);
  ll L = 0, m = 1, b = 1;
  rep(n, 0, SZ(s)) {
    ll d = 0;
    rep(i, 0, L + 1) d = (d + (ll)C[i] * s[n - i]) % mod;
    if (d == 0)
      ++m;
    else if (2 * L <= n) {
      VI T = C;
      ll c = mod - d * powmod(b, mod - 2) % mod;
      while (SZ(C) < SZ(B) + m) C.pb(0);
      rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
      L = n + 1 - L;
      B = T;
      b = d;
      m = 1;
    } else {
      ll c = mod - d * powmod(b, mod - 2) % mod;
      while (SZ(C) < SZ(B) + m) C.pb(0);
      rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod;
      ++m;
    }
  }
  return C;
}
ll gao(VI a, ll n) {
  VI c = BM(a);
  c.erase(c.begin());
  rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
  return solve(n, c, VI(a.begin(), a.begin() + SZ(c)));
}
};  // namespace linear_seq
int main() {
  while (~scanf("%lld", &n) && n != -1) {
    vector<ll>v;
       v.push_back(0);
       v.push_back(1);
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(5);
        v.push_back(8);
        v.push_back(13);
        v.push_back(21);
        v.push_back(34);
      printf("%lld\n", linear_seq::gao(v, n));
  }
  return 0;
}

链接

分类

最新文章

归档

标签

C++内存管理1
C++基础3
C++面向对象3
DFS1
JVM3
Java反射1
Java基础2
Java多线程1
Makefile1
MySQL1
RMQ1
STL7
Vim1
二分2
动态规划14
区间dp3
博弈论1
回文1
图论2
多校训练3
字典树1
并查集4
思维15
操作系统2
数学7
最小生成树1
树2
树形dp2
树状数组5
状压dp3
线性dp1
网络编程1
背包dp2
计数dp5
计算机网络1
记忆化搜索2
设计模式2
贪心10
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×