Hexo
0%

算法模板

发表于 更新于 分类于
kruskal算法模板（来自洛谷）和

kruskal

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
#include<iostream>
#include<algorithm>
using namespace std;
#define re register
#define il inline
il int read()
{
    re int x = 0, f = 1; char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * f;
}
struct Edge
{
    int u, v, w;
}edge[200005];
int fa[5005], n, m, ans, eu, ev, cnt;
il bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
//快排的依据（按边权排序）
il int find(int x)
{
    while (x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}
//并查集循环实现模板，及路径压缩，不懂并查集的同学可以戳一戳代码上方的“并查集详解”
il void kruskal()
{
    sort(edge, edge + m, cmp);
    //将边的权值排序
    for (re int i = 0; i < m; i++)
    {
        eu = find(edge[i].u), ev = find(edge[i].v);
        if (eu == ev)
        {
            continue;
        }
        //若出现两个点已经联通了，则说明这一条边不需要了
        ans += edge[i].w;
        //将此边权计入答案
        fa[ev] = eu;
        //将eu、ev合并
        if (++cnt == n - 1)
        {
            break;
        }
        //循环结束条件，及边数为点数减一时
    }
}
int main()
{
    n = read(), m = read();
    for (re int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    //初始化并查集
    for (re int i = 0; i < m; i++)
    {
        edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
    }
    kruskal();
    //printf("%d", ans);
    cout << ans << endl;
    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
#include<iostream>
#include<algorithm>
using namespace std;
int number_node, number_edge, ans, cnt;
int father[5005];
struct Edge
{
 int u, v, w;
};
Edge edge[200005];
bool cmp(const Edge& a, const Edge& b)
{
 return a.w < b.w;
}
int findfather(int x)
{
 while (x != father[x])//请注意这里是x和father[x]，x必须是index，否则错误
  x = father[x] = father[father[x]];//这里x必须是father数组的index，否则错误
 return x;
}
void kruskal()
{
 sort(&edge[1], &edge[number_edge + 1], cmp);
 for (int i = 1; i <= number_edge; i++)
 {
  int father_u = findfather(edge[i].u);
  int father_v = findfather(edge[i].v);
  if (father_u == father_v)//这个一定要判断是否在同一个等价类中，否则错误
   continue;
  ans = ans + edge[i].w;
  father[father_v] = father_u;
  if (++cnt == number_node - 1)//计数变量和循环变量不是一个，如果是一个就会使得循环终止条件判断错误
   break;
 }
}
int main()
{
 cin >> number_node >> number_edge;
 for (int i = 1; i <= number_edge; i++)
 {
  cin >> edge[i].u >> edge[i].v >> edge[i].w;
 }
 for (int i = 1; i <= number_node; i++)
 {
  father[i] = i;
 }
 kruskal();
 cout << ans << endl;
 return 0;
}

dijkstra

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
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct node
{
 int cost;
 int number;
 bool operator<(const node& a)const
 {
  return a.cost < cost;
 }
};
priority_queue<node>q;
struct Edge//前向星存边
{
 int next, v, w;
 //next存的是与该边最近的的起始点一样的边的编号
};
bool vis[100005];
Edge edge[500005];
int n, m, s, cnt,dis[100005],father[100005];
//cnt是边的编号
//father表示以某点位父结点引出的最后一条边
void add_edge(int next, int v, int w)
//存边，目的是用cnt编号把边链起来，next是点
{
 cnt++;
 edge[cnt].w = w;
 edge[cnt].v = v;
 edge[cnt].next = father[next];
 //与cnt边同起点的下一条边的位置
 father[next] = cnt;
 //不断更新以next为起点的所有边中的最大编号
}
void dijkstra()
{
 dis[s] = 0;
 node temp = { 0,s };
 q.push(temp);
 while (!q.empty())
 {
  temp = q.top();
  q.pop();
  int x = temp.number;
  int c = temp.cost;
  if (vis[x])
  {
   continue;
  }
  vis[x] = 1;
  for (int i = father[x]; i ; i = edge[i].next)
  {
   int v = edge[i].v;
   if (dis[v] > dis[x] + edge[i].w)
   {
    dis[v] = dis[x] + edge[i].w;
    if (!vis[v])
    {
     q.push({ dis[v],v });
    }
   }
  }
 }
}
int main()
{
 cin >> n >> m >> s;
 for (int i = 1; i <= n; i++)
 {
  dis[i] = 0x7fffffff;
 }
 for (int i = 1; i <= m; i++)
 {
  int u, v, w;
  cin >> u >> v >> w;
  add_edge(u, v, w);
 }
 dijkstra();
 for (int i = 1; i <= n; i++)
 {
  cout << dis[i] << " ";
 }
 return 0;
}

这个是用vector存图，相对于链式前向星更好理解一点。//vector这个模板RE了，正确模板请移步算法复习——单源最短路径

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
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<climits>
#include<functional>
using namespace std;
const int MAX_V = 10005;
bool vis[MAX_V];//一定要有vis数组，否则会出现死循环，MLE。
struct edge
{
 int cost, to;
};
using P = pair<int, int>;
vector<edge>G[MAX_V];//相当于用一个二维动态数组把所有以某个固定点为起点的边存在一起，便于遍历。
int dis[MAX_V];
void dijkstra(const int& start)
{
 priority_queue<P, vector<P>, greater<P> >que;
 fill(dis, dis + MAX_V, INT_MAX);
 dis[start] = 0;//不能忘记初始化start位置的dis，否则会导致图不连通，也不能在这里就修改start的vis,这将导致在进入while循环后直接被continue掉
 que.emplace(0, start);
 while (!que.empty())
 {
  P p = que.top();
  que.pop();
  int v = p.second;
  if (vis[v] == 1)
   continue;
  vis[v] = 1;
  if (dis[v] < p.first)//别忘记加上这一句话，节省运行时间
   continue;
  for (edge e : G[v])
  {
   if (dis[e.to] > dis[v] + e.cost)//是e的cost不是v的cost
    dis[e.to] = dis[v] + e.cost;
   que.emplace(dis[e.to], e.to);//入队列的是dis[e.to]而不是e.to的cost
  }
 }
}
void add_edge(int u, int v, int w)
{
 edge temp = { w,v };
 G[u].push_back(temp);
}
int main()
{
 int V_number, U_number, start;
 int u, v, w;
 cin >> V_number >> U_number >> start;
 for (int i = 1; i <= U_number; i++)
 {
  cin >> u >> v >> w;
  if (u == v)
   continue;
  add_edge(u, v, w);
 }
 dijkstra(start);
 for (int i = 1; i <= V_number; i++)
 {
  if (dis[i] == INT_MAX)
   dis[i] = 2e31 - 1;
  cout << dis[i] << " ";
 }
 return 0;
}

floyd并记录最短路径

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
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
std::vector<vector<int> > weight;
std::vector<vector<int> > path;
stack<int> shortpath;
int vertexnum;
int edgenum;
const int intmax = 10000;
void initialvector() {
 weight.resize(vertexnum);//路径权重数组
 path.resize(vertexnum);//保存最短路径数组,记录前继
 for (int i = 0; i < vertexnum; i++) {//建立数组
  weight[i].resize(vertexnum, intmax);
  path[i].resize(vertexnum, -1);
 }
}
void getData() {//获取数据
 cin >> vertexnum;
 initialvector();
 int from, to;
 double w;
 for (int i = 0; i < vertexnum; i++)
 {
  for (int j = 0; j < vertexnum; j++)
  {
   cin >> w;
   if (w != 10000)
   {
    weight[i][j] = w;
    path[i][j] = i;
    weight[i][i] = 0;
    path[i][i] = i;
    weight[j][j] = 0;
    path[j][j] = j;
   }
  }
 }
}
void floyd() {
 for (int k = 0; k < vertexnum; k++)
  for (int i = 0; i < vertexnum; i++)
   for (int j = 0; j < vertexnum; j++) {
    if ((weight[i][k] > 0 && weight[k][j] && weight[i][k] < intmax && weight[k][j] < intmax) && (weight[i][k] + weight[k][j] < weight[i][j])) {//前面一部分是防止加法溢出
     weight[i][j] = weight[i][k] + weight[k][j];
     path[i][j] = path[k][j];
    }
   }
}
void displaypath(int source, int dest) {
 int temp = dest;
 while (temp != source) {
  shortpath.push(temp);
  temp = path[source][temp];
  if (temp == -1)
  {
   cout << "NO\n";
   while (!shortpath.empty())
   {
    shortpath.pop();
   }
   return;
  }
 }
 shortpath.push(source);
 cout << weight[source][dest] << "\n";
 while (!shortpath.empty()) {
  cout << shortpath.top() << " ";
  shortpath.pop();
 }
 cout << "\n";
}
int main(int argc, char const* argv[])
{
 getData();
 //for (int i = 0; i < vertexnum; i++) {
 // for (int j = 0; j < vertexnum; j++) {
 //  cout << weight[i][j] << "\t";
 // }
 // cout << endl;
 //}
 floyd();
 int from, to;
 cin >> from >> to;
 while (from != -1 && to != -1)
 {
  displaypath(from, to);
  cin >> from >> to;
 }
 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
#include<iostream>
#include<algorithm>
using namespace std;

struct Edge
{
    int u, v;
};

int father[50];
Edge edge[105];
int result[105];//把father数组塞到map里看一下每个根节点出现了几次，以此确定节点的个数
int N_number, V_number;

int find_father(int x)
{
    while (x != father[x])
    {
        x = father[x];
    }
    return x;
}

int main()
{
    cin >> N_number >> V_number;
    for (int i = 1; i <= V_number; i++)
    {
        cin >> edge[i].u >> edge[i].v;
    }

    for (int i = 1; i <= N_number; i++)
    {
        father[i] = i;
    }

    for (int i = 1; i <= V_number; i++)
    {
        int fa_u = find_father(edge[i].u);
        int fa_v = find_father(edge[i].v);
        if (fa_u != fa_v)
            father[fa_v] = fa_u;
    }

    for (int i = 1; i <= N_number; i++)
    {
        result[find_father(i)]++;//不能把father直接塞进去，因为father中有一些节点是没有更新过的，比如两条边第一次加入1-2，则father[1] = 2,第二次加入2-3，则father[2] = 3,那么1的father和2，3是不一样的，不能根据father中的元素直接判断子图个数，而要再次更新一遍father数组。
    }

    int cnt = 0;
    int data[50];
    for (int i = 1; i <= N_number; i++)
    {
        if (result[i] > 0)
        {
            data[++cnt] = result[i];//万恶的oj为了自己judge方便，还要要求顺序，先把次数存起来，然后排个序再输出
        }
    }
    cout << cnt << endl;
    sort(data + 1, data + cnt + 1);
    for (int i = 1; i <= cnt; i++)
    {
        cout << data[i] << " ";
    }
    cout << endl;
    return 0;
}

如果不要求输出子图中的节点个数，可以直接使用unique对father数组进行去重，注意，去重之前一定要先排序。

1
2
3
sort(&father[1], &father[city_number + 1]);
int* end = unique(&father[1], &father[city_number + 1]);
int count = end - &father[1];

LCA

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
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
enum{MAXN = 500005};
int node_number, question, root,cnt;
int last[MAXN], fa[MAXN][22], Dep[MAXN];
struct Edge
{
 int to, next;
};
Edge edge[2 * MAXN];
void dfs(int x, int father)
{
 int i, k, y;
 fa[x][0] = father;
 Dep[x] = Dep[father] + 1;
 k = ceil(log(Dep[x]) / log(2));
 for (i = 1; i <= k; i++)
 {
  fa[x][i] = fa[fa[x][i - 1]][i - 1];
 }
 y = last[x];
 for (i = last[x]; i; i = edge[i].next)
 {
  if (edge[i].to != father)
  {
   dfs(edge[i].to, x);
  }
 }
}
void add_edge(int x, int y)
{
 cnt++;
 edge[cnt].to = y;
 edge[cnt].next = last[x];
 last[x] = cnt;
}
int LCA(int x, int y)
{
 int i, k, s;
 s = ceil(log(node_number) / log(2));
 if (Dep[x] < Dep[y])
 {
  swap(x, y);
 }
 k = Dep[x] - Dep[y];
 for (i = 0; i <= s; i++)
 {
  if (k & (1 << i))
  {
   x = fa[x][i];
  }
 }
 if (x == y)
 {
  return x;
 }
 s = ceil(log(Dep[x]) / log(2));
 for (i = s; i >= 0; i--)
 {
  if (fa[x][i] != fa[y][i])
  {
   x = fa[x][i];
   y = fa[y][i];
  }
 }
 return fa[x][0];
}
int main()
{
 int i, x, y;
 //cin >> node_number >> question >> root;
 scanf("%d%d%d", &node_number, &question, &root);
 for (i = 1; i <= node_number-1; i++)
 {
  //cin >> x >> y;
  scanf("%d%d", &x, &y);
  add_edge(x, y);
  add_edge(y, x);
 }
 dfs(root, 0);
 for (int i = 1; i <= question; i++)
 {
  //cin >> x >> y;
  scanf("%d%d", &x, &y);
  //cout << LCA(x, y) << endl;
  printf("%d\n", LCA(x, y));
 }
 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
#include<iostream>
using namespace std;
enum{MAXN = 50005};
int father[3 * MAXN], cnt;
//1 self 2 food 3 enemy
int find_parent(int x)
{
 if (father[x] != x)
 {
  father[x] = find_parent(father[x]);
 }
 return father[x];
}
void union_(int x, int y)
{
 int x1 = find_parent(x);
 int y1 = find_parent(y);
 if (x1 != y1)
 {
  father[x1] = y1;
 }
}
int main()
{
 int N, K, mode, x, y;
 cin >> N >> K;
 for (int i = 1; i <= 3 * N; i++)
 {
  father[i] = i;
 }
 while (K--)
 {
  cin >> mode >> x >> y;
  if (x > N || y > N)
  {
   cnt++;
   continue;
  }
  if (mode == 1)
  {
   if (find_parent(x) == find_parent(y + N) || find_parent(x) == find_parent(y + 2 * N))
   {
    cnt++;
    continue;
   }
   union_(x, y);
   union_(x + N, y + N);
   union_(x + 2 * N, y + 2 * N);
  }
  else if (mode == 2)
  {
   if (x == y)
   {
    cnt++;
    continue;
   }
   if (find_parent(x) == find_parent(y + N) || find_parent(x) == find_parent(y))
   {
    cnt++;
    continue;
   }
   union_(x + 2 * N, y + N);
   union_(x + N, y);
   union_(x, y + 2 * N);
  }
 }
 cout << cnt << endl;
 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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<map>
using namespace std;
double a, b, c, d;
map<double,int>m;
double f(double x)
{
 return a * x * x * x + b * x * x + c * x + d;
}
double binary_search(double left, double right)
{
 double mid;
 if (f(left) == 0)
 {
  return left;//左端点特判
 }
 while(right-left>=0.001)
  //到这个精度已经不需要深究是返回右端点还是左端点了，但是一定只能挑一个返回
 {
  mid = (left + right) / 2;
  if (f(mid)*f(left) <= 0)
  {
   right = mid;
  }
  else
  {
   left = mid;
  }
 }
 return right;//避免重复只返回右端点
}
int main()
{
 cin >> a >> b >> c >> d;
 for (int i = -100; i <= 100; i++)//题目已知条件一个长度为1的小区间只能有一个解
 {
  if (f(i) * f(i + 1) <= 0)
   //判断这个小区间内是不是有解，只有有解搜索才有正确结果，请注意由于二分的思路，一旦开始搜索必然会返回一个结果无论正确与否。
  {
   double x1 = binary_search(i, i + 1.0);
   if (m[x1] == 0)//用个map把重复的解筛掉
   {
    printf("%.2f ", x1);
    m[x1] = 1;
   }
   if (m.size() == 3)
   {
    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
#include<iostream>
#include<fstream>
using namespace std;
enum{MAXN = 50005};
int D, total_rock, get_rock, Left, Right;
int dis1[MAXN], dis2[MAXN];
bool judge(int value)
{
 int cnt = 0;
 int now = 0;
 for (int i = 1; i <= total_rock+1; i++)
 {
  dis2[i] = dis1[i];
 }
 for (int i = 1; i <= total_rock; i++)
 {
  if (dis2[i] - dis2[now] < value)
  {
   cnt++;
  }
  else
  {
   now = i;
  }
 }
 if (cnt <= get_rock)
  return true;
 else
  return false;
}
int binary_search()
{
 int mid;
 while (Left+1 < Right)
 {
  mid = (Left + Right) / 2;
  if (judge(mid))
  {
   Left = mid;
  }
  else
  {
   Right = mid;
  }
 }
 return mid;
}
int main()
{
 cin >> D >> total_rock >> get_rock;
 if (total_rock == 0)
 {
  cout << D << endl;
  return 0;
 }
 for (int i = 1; i <=total_rock; i++)
 {
  cin >> dis1[i];
 }
 dis1[total_rock+1] = D;
 Left = 1;
 Right = D;
 binary_search();
 if (judge(Right))
 {
  cout << Right << endl;
 }
 else
 {
  cout << Left << endl;
 }
 return 0;
}

字符串next

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
#include<iostream>
#include<string>
#include<vector>
using namespace std;
enum{MAXAN = 50005};
string alphabet, mingwen, anwen;
string Alphabet, temp_aim;
vector<int>shift;
int nextval[MAXAN], Q;
void getnext(string s)
{
 int len = s.length();
 int j = -1;
 nextval[0] = -1;
 for (int i = 1; i < len; i++)
 {
  if (j != -1 && s[i] != s[j + 1])
  {
   j = nextval[j];
  }
  if (s[i] == s[j + 1])
   j++;
  nextval[i] = j;
 }
}
int cal(string t, string p)
{
 getnext(p);
 int n = t.length();
 int m = p.length();
 int j = -1;
 int ans = 0;
 for (int i = 0; i < n; i++)
 {
  while (j != -1 && t[i] != p[j + 1])
   j = nextval[j];
  if (t[i] == p[j + 1])
   j++;
  if (j == m - 1)
  {
   ans++;
   j = nextval[j];
  }
 }
 return ans;
}
int main()
{
 cin >> Q;
 while (Q--)
 {
  cin >> alphabet >> anwen >> mingwen;
  Alphabet = alphabet + alphabet;
  int mod = alphabet.size() - 1;
  for (int i = 0; i <= mod; i++)
  {
   if (i == 0)
   {
    temp_aim = anwen;
   }
   else
   {
    for (int j = 0; j < anwen.size(); j++)
    {

     temp_aim[j] = Alphabet[Alphabet.find(anwen[j]) + i];
    }
   }
   if (cal(mingwen, temp_aim) == 1)
   {
    shift.push_back(i);
   }
  }
  if (shift.size() == 0)
  {
   cout << "no solution" << endl;
  }
  else if (shift.size() == 1)
  {
   cout << "unique: " << shift[0] << endl;
  }
  else
  {
   cout << "ambiguous:";
   for (int i = 0; i < shift.size(); i++)
   {
    cout << " " << shift[i];
   }
   cout << endl;
  }
  shift.clear();
 }
 return 0;
}

SparseTable

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
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
enum{MAXN = 100005};
int number_M, number_Q;
int f[MAXN][20];
void initial()
{
 for (int i = 1; i <= floor(log(number_M)/log(2)); i++)
 {
  for (int j = 1; j <= (number_M-(1<<i)+1); j++)
  {
   f[j][i] = min(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
  }
 }
}
int search(int x, int y)
{
 int value;
 int k = floor(log(y - x + 1) / log(2));
 value = min(f[x][k], f[y - (1 << k) + 1][k]);
 return value;
}
int main()
{
 int x, y;
 cin >> number_M >> number_Q;
 for (int i = 1; i <= number_M; i++)
 {
  cin >> f[i][0];
 }
 initial();
 for (int i = 1; i <= number_Q; i++)
 {
  cin >> x >> y;
  cout << search(x, y) << " ";
 }
 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
#include<iostream>
#include<cstdio>
using namespace std;
enum{MAXM = 500005};
int c[MAXM], numberofdata,demo,a[MAXM];
int lowbit(int x)
{
 return x & (-x);
}
int getSum(int x)
{
 int Sum = 0;
 for (int i = x; i > 0; i = i - lowbit(i))
 {
  Sum = Sum + c[i];
 }
 return Sum;
}
void insert(int x, int d)
{
 for (int i = x; i <= numberofdata; i = i + lowbit(i))
 {
  c[i] = c[i] + d;
 }
}
int main()
{
 int mode, x, y;
 //cin >> numberofdata >> demo;
 scanf("%d %d", &numberofdata, &demo);
 for (int i = 1; i <= numberofdata; i++)
 {
  //cin >> a[i];
  scanf("%d", &a[i]);
  insert(i, a[i]);
 }
 for (int i = 1; i <= demo; i++)
 {
  //cin >> mode >> x >> y;
  scanf("%d %d %d", &mode, &x, &y);
  if (mode == 1)
  {
   insert(x, y);
  }
  else if (mode == 2)
  {
   int ans = getSum(y) - getSum(x-1);//啊，千万别忘了减一
   //cout << ans << endl;
   printf("%d", ans);
  }
 }
 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
#include<iostream>
using namespace std;
using ll = long long int;
ll Base, Index, Mod, ans = 1;
int main()
{
 cin >> Base >> Index >> Mod;
 ll b = Index, base = Base;
 if (Index == 0)
 {
  ans = 1 % Mod;
  cout << base << "^" << b << " mod " << Mod << "=" << ans << endl;
  return 0;
 }
 while (Index > 0)
 {
  if (Index & 1)
  {
   ans = Base * ans % Mod;
  }
  Base = Base * Base%Mod;
  Index = Index >> 1;
 }
 cout << base << "^" << b << " mod " << Mod << "=" << ans << endl;
 return 0;
}