直研机试题模板

发表于 | 更新于 | 分类于 | 阅读次数：

准备一波模板，上机考之前抱抱佛脚。。。

头文件

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
// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#define fi first
#define se second
#define fe(i,a,b) for(int i=a; i<=b; ++i)
#define fne(i,a,b) for(int i=a; i<b; ++i)
#define mem(a, val) memset((a), (val), sizeof(a))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
//head

//fill memset <cstring>
//fill(arr, arr+N, value);
//pair std

Eratosthenes筛法

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
bool isPrime[1000];

void getPrimes(int n) {
    memset(isPrime, true, sizeof isPrime);
    for(int i=2; i<=sqrt(n+0.5); i++) if(isPrime[i])
            for(int j=i*i; j<=n; j+=i) isPrime[j] = false;
}

gcd & lcm

1
2
3
4
5
6
7
8
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    //为了防止溢出，可以先做除法，再乘上b
    return a / gcd(a, b) * b;
}

快速幂

1
2
3
4
5
6
7
8
9
10
ll powerMod(ll x, ll n, ll m) {
    ll res = 1;
    while (n > 0) {
        if  (n & 1) //  判断是否为奇数，若是则true
            res = (res * x) % m;
        x = (x * x) % m;
        n >>= 1;    //  相当于n /= 2;
    }
    return res;
}

大数加法

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
string add1(string s1, string s2) {
    if (s1 == "" && s2 == "")   return "0";
    if (s1 == "")   return s2;
    if (s2 == "")   return s1;
    string maxx = s1, minn = s2;
    if (s1.length() < s2.length()) {
        maxx = s2;
        minn = s1;
    }
    int a = maxx.length() - 1, b = minn.length() - 1;
    for (int i = b; i >= 0; --i) {
        maxx[a--] += minn[i] - '0'; //  a一直在减 ， 额外还要减个'0'
    }
    for (int i = maxx.length()-1; i > 0;--i) {
        if (maxx[i] > '9') {
            maxx[i] -= 10;//注意这个是减10
            maxx[i - 1]++;
        }
    }
    if (maxx[0] > '9') {
        maxx[0] -= 10;
        maxx = '1' + maxx;
    }
    return maxx;
}

大数阶乘

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
const int maxn = 100010;
int num[maxn], len;

/*
    在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度
    tip: 阶乘都是先求之前的(n-1)!来求n!
    初始化Init函数很重要，不要落下
*/

void init() {
    len = 1;
    num[0] = 1;
}

int mult(int num[], int len, int n) {
    ll tmp = 0;
    for(ll i = 0; i < len; ++i) {
         tmp = tmp + num[i] * n;    //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）
         num[i] = tmp % 10; //  保存在对应的数组位置，即去掉进位后的一位数
         tmp = tmp / 10;    //  取整用于再次循环,与n和下一个位置的乘积相加
    }
    while(tmp) {    //  之后的进位处理
         num[len++] = tmp % 10;
         tmp = tmp / 10;
    }
    return len;
}

int main() {
    init();
    int n;
    n = 1977; // 求的阶乘数
    for(int i = 2; i <= n; ++i) {
        len = mult(num, len, i);
    }
    for(int i = len - 1; i >= 0; --i)
        printf("%d",num[i]);    //  从最高位依次输出,数据比较多采用printf输出
    printf("\n");
    return 0;
}

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void pern(int list[], int k, int n) {   //  k表示前k个数不动仅移动后面n-k位数
    if (k == n - 1) {
        for (int i = 0; i < n; i++) {
            printf("%d", list[i]);
        }
        printf("\n");
    }else {
        for (int i = k; i < n; i++) {   //  输出的是满足移动条件所有全排列
            swap(list[k], list[i]);
            pern(list, k + 1, n);
            swap(list[k], list[i]);
        }
    }
}

二分

1
2
3
4
5
6
7
8
9
10
11
12
13
int binarySearch(int l, int r, int key) {
    while (l <= r) {
        int m = (l + r) >> 1;

        if (arr[m] < key)
            l = m + 1;
        else if (arr[m] > key)
            r = m - 1;
        else
            return m; // key found
    }
    return -(l + 1);  // key not found
}

dfs & bfs

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
void dfs(当前状态) {
//   if (边界状态) {
//       记录或输出
//       return;
//   }
//   for (所有子状态)
//       if (未访问过 && 满足约束条件) {
//           vis = true;
//           dfs(子状态);
//           vis = false;
//       }
}

int bfs() {
//    初始化
//    插入起始状态
//    while (队列非空) {
//        取出首节点
//        q.pop();
//        if (边界状态) {
//            返回结果
//        }
//        for (所有子状态)
//            if (未访问过 && 满足约束条件) {
//                vis = true;
//                加入队列
//            }
//    return INF;
}

LIS

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
/*
    状态转移dp[i] = max{ 1.dp[j] + 1 };  j<i; a[j]<a[i];
    d[i]是以i结尾的最长上升子序列
    与i之前的 每个a[j]<a[i]的 j的位置的最长上升子序列+1后的值比较
*/

void solve() {   // 参考挑战程序设计入门经典;
    for(int i = 0; i < n; ++i){  
        dp[i] = 1;  
        for(int j = 0; j < i; ++j){  
            if(a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);  
        }
    }
}  

/* 
    优化方法：
    dp[i]表示长度为i+1的上升子序列的最末尾元素  
    找到第一个比dp末尾大的来代替 
*/

void solve() {  
    for (int i = 0; i < n; ++i) {
        dp[i] = INF;
    }
    for (int i = 0; i < n; ++i) {  
        *lower_bound(dp, dp + n, a[i]) = a[i];  //  返回一个指针  
    }  
    printf("%d\n", *lower_bound(dp, dp + n, INF) - dp);  
}

/**
 * 函数lower_bound()返回一个 iterator。
 * 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，
 * 而这个位置标记了一个不小于value的值。
 */

LCS

1
2
3
4
5
6
7
8
9
10
11
void solve() {  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < m; ++j) {  
            if (s1[i] == s2[j]) {  
                dp[i + 1][j + 1] = dp[i][j] + 1;  
            } else {  
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);  
            }
        }
    }
}

Bellman-Ford

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
/**
 * 带负边，单源最短路, O(|V| * |E|)
 */
struct edge { int from, to, cost; };

edge es[MAX_E]; // 边

int d[MAX_V]; // 最短距离
int V, E; // 顶点数， 边数

void bellman_ford() {
    memset(d, INF, sizeof d);
    // fill(d, d+V, INF);
    d[s] = 0;
    while (true) {
        bool update = false;
        for (int i=0; i<E; i++) {
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if (!update) break;
    }
}

// bellman-ford找负圈
bool find_negative_loop() {
    memset(d, 0, sizeof d);
    for (int i=0; i<V; i++)
        for (int j=0; j<E; j++) {
            edge e = es[j];
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                if (i == V - 1) return true;
            }
        }
    return false;
}

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

/**
 * 非负边，单源最短路
 */
/**
 * 方法一：邻接矩阵, O(|V|^2)
 */
int cost[MAX_V][MAX_V]; // 边的权值，不存在为INF
int d[MAX_V];
bool vis[MAX_V];
int V;

void dijkstra(int s) {
    fill(d, d+V, INF);
    fill(vis, vis+V, false);
    d[s] = 0;
    while (true) {
        int v = -1;
        for (int u=0; u<V; u++)
            if (!vis[u] && (v == -1 || d[u] < d[v]))
                v = u;
        if (v == -1) break;
        vis[v] = true;
        for (int u=0; u<V; u++)
            d[u] = min(d[u], d[v] + cost[v][u]);
    }
}

/**
 * 方法二：优先队列,用于稀疏图，O(|E|)
 */
struct edge { int to, cost; };
int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    // greater -> 从小到大取出值
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(pii(0, s));
    while (!que.empty()) {
        pii p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(pii(d[e.to], e.to));
            }
        }
    }
}

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 任意两点最短路，O(|V|^3)
 */
int d[MAX_V][MAX_V]; // 不存在为INF，d[i][i] = 0
int V;
void warshall_floyd() {
    // 中介点必须在最外层循环
    for (int k=0; k<V; k++)
        for (int i=0; i<V; i++)
            for (int j=0; j<V; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

SPFA

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
/**
 * 负边，O(KE)
 */
vector<node> G[maxn];
bool inqueue[maxn];
int dist[maxn];

void Init()  
{  
    for(int i = 0 ; i < maxn ; ++i){  
        G[i].clear();  
        dist[i] = INF;  
    }  
}  
int SPFA(int s,int e)  
{  
    int v1,v2,weight;  
    queue<int> Q;  
    memset(inqueue,false,sizeof(inqueue)); // 标记是否在队列中  
    memset(cnt,0,sizeof(cnt)); // 加入队列的次数  
    dist[s] = 0;  
    Q.push(s); // 起点加入队列  
    inqueue[s] = true; // 标记  
    while(!Q.empty()){  
        v1 = Q.front();  
        Q.pop();  
        inqueue[v1] = false; // 取消标记  
        for(int i = 0 ; i < G[v1].size() ; ++i){ // 搜索v1的链表  
            v2 = G[v1][i].vex;  
            weight = G[v1][i].weight;  
            if(dist[v2] > dist[v1] + weight){ // 松弛操作  
                dist[v2] = dist[v1] + weight;  
                if(inqueue[v2] == false){  // 再次加入队列  
                    inqueue[v2] = true;  
                    //cnt[v2]++;  // 判负环  
                    //if(cnt[v2] > n) return -1;  
                    Q.push(v2);  
                } } }  
    }  
    return dist[e];  
}

/*
    不断的将s的邻接点加入队列，取出不断的进行松弛操作，直到队列为空  

    如果一个结点被加入队列超过n-1次，那么显然图中有负环  
*/

最小生成树

Prim

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
/**
 * 和Dijkstra一样，两种方式
 */
int cost[MAX_V][MAX_V];
int d[MAX_V];
bool vis[MAX_V];
int V;

int prim() {
    fill(d, d+V, INF);
    memset(vis, false, sizeof vis);
    d[0] = 0;
    int res = 0;
    while (true) {
        int v = -1;
        for (int u=0; u<V; u++)
            if (!vis[u] && (v == -1 || d[u] < d[v]))
                v = u;
        if (v == -1) break;
        vis[v] = true;
        res += d[v];
        for (int u=0; u<V; u++)
            d[u] = min(d[u], d[v] + cost[v][u]);
    }
    return res;
}

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
/**
 * 要用到并查集
 */
struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal() {
    sort(es, es+E, comp);
    init_union_find(V);
    int res = 0;
    for (int i=0; i<E; i++) {
        edge e = es[i];
        if (!sameSet(e.u, e.v)) {
            unite(e.u, e.v);
            res += ecost;
        }
    }
    return res;
}

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int fa[MAX_N];
// int rank[MAX_N];

void init(int n) {
    for (int i=0; i<n; i++) {
        fa[i] = i;
        // rank[i] = 0;
    }
}

int find(int x) {
    return x==fa[x] ? x : fa[x]=find(fa[x]);
}

bool sameSet(int x, int y) {
    return find(x) == find(y);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y)
        fa[x] = y;
}

线段树

点更新

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
struct node
{
    int left, right;
    int max, sum;
};

node tree[maxn << 2];
int a[maxn];
int n;
int k = 1;
int p, q;
string str;

void build(int m, int l, int r)//m 是 树的标号
{
    tree[m].left = l;
    tree[m].right = r;
    if (l == r){
        tree[m].max = a[l];
        tree[m].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(m << 1, l, mid);
    build(m << 1 | 1, mid + 1, r);
    tree[m].max = max(tree[m << 1].max, tree[m << 1 | 1].max);
    tree[m].sum = tree[m << 1].sum + tree[m << 1 | 1].sum;
}

void update(int m, int a, int val)//a 是 节点位置， val 是 更新的值（加减的值）
{
    if (tree[m].left == a && tree[m].right == a){
        tree[m].max += val;
        tree[m].sum += val;
        return;
    }
    int mid = (tree[m].left + tree[m].right) >> 1;
    if (a <= mid){
        update(m << 1, a, val);
    }
    else{
        update(m << 1 | 1, a, val);
    }
    tree[m].max = max(tree[m << 1].max, tree[m << 1 | 1].max);
    tree[m].sum = tree[m << 1].sum + tree[m << 1 | 1].sum;
}

int querySum(int m, int l, int r)
{
    if (l == tree[m].left && r == tree[m].right){
        return tree[m].sum;
    }
    int mid = (tree[m].left + tree[m].right) >> 1;
    if (r <= mid){
        return querySum(m << 1, l, r);
    }
    else if (l > mid){
        return querySum(m << 1 | 1, l, r);
    }
    return querySum(m << 1, l, mid) + querySum(m << 1 | 1, mid + 1, r);
}

int queryMax(int m, int l, int r)
{
    if (l == tree[m].left && r == tree[m].right){
        return tree[m].max;
    }
    int mid = (tree[m].left + tree[m].right) >> 1;
    if (r <= mid){
        return queryMax(m << 1, l, r);
    }
    else if (l > mid){
        return queryMax(m << 1 | 1, l, r);
    }
    return max(queryMax(m << 1, l, mid), queryMax(m << 1 | 1, mid + 1, r));
} 

// build(1,1,n);
// update(1,a,b);
// query(1,a,b);

区间更新

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
const int maxn = 100010;  

int t,n,q;  
ll anssum;  

struct node{  
    ll l,r;  
    ll addv,sum;  
}tree[maxn<<2];  

void maintain(int id) {  
    if(tree[id].l >= tree[id].r)  
        return ;  
    tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;  
}  

void pushdown(int id) {  
    if(tree[id].l >= tree[id].r)  
        return ;  
    if(tree[id].addv){  
        int tmp = tree[id].addv;  
        tree[id<<1].addv += tmp;  
        tree[id<<1|1].addv += tmp;  
        tree[id<<1].sum += (tree[id<<1].r - tree[id<<1].l + 1)*tmp;  
        tree[id<<1|1].sum += (tree[id<<1|1].r - tree[id<<1|1].l + 1)*tmp;  
        tree[id].addv = 0;  
    }  
}  

void build(int id,ll l,ll r) {  
    tree[id].l = l;  
    tree[id].r = r;  
    tree[id].addv = 0;  
    tree[id].sum = 0;  
    if(l==r)  {  
        tree[id].sum = 0;  
        return ;  
    }  
    ll mid = (l+r)>>1;  
    build(id<<1,l,mid);  
    build(id<<1|1,mid+1,r);  
    maintain(id);  
}  

void updateAdd(int id,ll l,ll r,ll val) {  
    if(tree[id].l >= l && tree[id].r <= r)  
    {  
        tree[id].addv += val;  
        tree[id].sum += (tree[id].r - tree[id].l+1)*val;  
        return ;  
    }  
    pushdown(id);  
    ll mid = (tree[id].l+tree[id].r)>>1;  
    if(l <= mid)  
        updateAdd(id<<1,l,r,val);  
    if(mid < r)  
        updateAdd(id<<1|1,l,r,val);  
    maintain(id);  
}  

void query(int id,ll l,ll r) {  
    if(tree[id].l >= l && tree[id].r <= r){  
        anssum += tree[id].sum;  
        return ;  
    }  
    pushdown(id);  
    ll mid = (tree[id].l + tree[id].r)>>1;  
    if(l <= mid)  
        query(id<<1,l,r);  
    if(mid < r)  
        query(id<<1|1,l,r);  
    maintain(id);  
}  

int main() {  
    scanf("%d",&t);  
    int kase = 0 ;  
    while(t--){  
        scanf("%d %d",&n,&q);  
        build(1,1,n);  
        int id;  
        ll x,y;  
        ll val;  
        printf("Case %d:\n",++kase);  
        while(q--){  
            scanf("%d",&id);  
            if(id==0){  
                scanf("%lld %lld %lld",&x,&y,&val);  
                updateAdd(1,x+1,y+1,val);  
            }  
            else{  
                scanf("%lld %lld",&x,&y);  
                anssum = 0;  
                query(1,x+1,y+1);  
                printf("%lld\n",anssum);  
            } } }  
    return 0;  
}