算法设计与分析课程综合复习

第三章 迭代法

杨辉三角形

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N][N];

int n;

int main(){
    cin >> n;
    for(int i = 0; i < n; ++ i) {
        a[i][0] = a[i][i] = 1;
        for(int j = 1; j < i; ++ j)
            a[i][j] = a[i-1][j-1] + a[i-1][j];
    }
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j <= i; ++ j)
            cout << a[i][j] << " ";
        puts("");
    }
    return 0;
}

加油站

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int dist;

int main(){
    cin >> dist;
    int dis = 500,oil = 500,cnt = 1;
    while(dis < dist) {
        cout << cnt << ": " << dis << " " << oil << endl;
        ++cnt;
        dis += 500/(2 * cnt - 1);
        oil += 500;
    }
    dis = dist - (dis - 500/(2 * cnt - 1));
    oil = oil - 500 + dis * (2 * cnt - 1);
    cout << cnt << ": " << dis << " " << oil << endl;
}

循坏置换

原始

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n,k;
int a[N];

int gcd(int a,int b){
    return !b?a:gcd(b,a % b);
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) cin >> a[i];
    int q = gcd(n,k);
    for(int i = 0; i < q; ++ i) {
        int tmp = a[i],p = i;
        for(int j = 0; j < n / q; ++ j) {
            p = (p + k) % n;
            swap(a[p],tmp);
        }
    }
    for(int i = 0; i < n; ++ i) cout << a[i];
}

改进

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n,k;
int a[N];
int p1,p2;

int gcd(int a,int b){
    return !b?a:gcd(b,a % b);
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; ++ i) cin >> a[i];
    int q = gcd(n,k);
    for(int i = 0; i < q; ++ i) {
        p1 = (i + (n/q - 1) * k) % n;
        int temp = a[p1];
        for(int j = n/q - 2; j >= 0; -- j) {
            p2 = (i + j * k) % n;
            a[p1] = a[p2];
            p1 = p2;
        }
        a[p2] = temp;
    }
    for(int i = 0; i < n; ++ i) cout << a[i];
}

阶乘

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N];

int n;
int d,i,j,len;
int b;

int main(){
    cin >> n;
    a[1] = 1;
    len = 1;
    for(int i = 2; i <= n; ++ i) {
        d = 0;
        for(j = 1; j <= len; ++ j) {
            b = a[j] * i;
            a[j] = b % 1000000;
            d = b / 1000000;
        }
        if(d) a[j] = d, ++ len;
    }
    for(int i = len; i >= 1; -- i) cout << a[i];
}

方程近似解

迭代法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-6;

int main(){
    double x1 = 0.4,x0 = 0;
    while(abs(x1 - x0) > eps) {
        x0 = x1;
        x1 = sqrt(sin(x0) + 1) / 3;
    }
    cout << x0;
}

二分法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-6;

int main(){
    double x1 = 0,x2 = 1,x = 0,x3 = 1;
    double f1 = 9 * x1 * x1 - sin(x1) - 1;
    double f2 = 9 * x2 * x2 - sin(x2) - 1;
    double f = 1;
    if(f1 * f2 < 0) {
        while(abs(x - x3) > eps) {
            x = (x1 + x2) / 2;
            f = 9 * x * x - sin(x) - 1;
            if(f == 0) break;
            if(f * f1 > 0) {
                x3 = x1;
                f1 = f;
                x1 = x;
            }
            else {
                x3 = x2;
                f2 = f;
                x2 = x;
            }
        }
    }
    cout << x << endl;
}

牛顿法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-6;

int main(){
   double x1,x2;
   cin >> x1;
   x2 = x1 - (9 * x1 * x1 - sin(x1) - 1) / (18 * x1 - cos(x1));
   while(abs(x1 - x2) > eps){
       x1 = x2;
       x2 = x1 - (9 * x1 * x1 - sin(x1) - 1) / (18 * x1 - cos(x1));
   }
   cout << x2;
}

第四章 蛮力法

链对

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N][N];

int n;

int main(){
    cin >> n;
    int x1,x2;
    cin >> x1;
    for(int i = 1; i < n; ++ i) {
        cin >> x2;
        a[x1][x2] ++ ;
        x1 = x2;
    }
    for(int i = 0; i < 10; ++ i)
        for(int j = 0; j <= i; ++ j) {
            if(a[i][j] && a[j][i]) 
                if(i != j) printf("(%d,%d) = %d,(%d,%d) = %d\n",i,j,a[i][j],j,i,a[j][i]);
                else 
                    if(a[i][j] > 1) printf("(%d,%d) = %d\n",i,j,a[i][j]);
        }
    return 0;
}

构造数字

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int main(){
    for(int a = 3; a < 10; ++ a)
        for(int d = 1; d < 10; ++ d) {
            int td = d * 100000 + d * 10000 + d * 1000 + d * 100 + d * 10 + d;
            if(td % a == 0) {
                int f = td / a;
                if((f/10000 == a) && (f/10%10==a) && (f%10==f/1000%10))
                    cout << f << " " << td << endl;
            }
        }
    return 0;
}

玫瑰矩阵

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int s[2];
int a[N][N];

int main(){
    cin >> n;
    int k = 1,i = n,t = 1;
    s[0] = -1,s[1] = 0;
    while(k <= n * n){
        for(int hc = 1; hc < 2 * i;++ hc) {
            int index = hc / (i + 1);
            s[index] += t;
            a[s[0]][s[1]] = k++;
        }
        -- i,t = 0 - t;
    }
    for(int i = 0; i < n; ++ i) {
        for(int j = 0; j < n; ++ j)
            cout << a[i][j] << "\t";
        puts("");
    }
    return 0;
}

旅行商

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int g[N][N];
int mn = 0x3f3f3f3f;
int path[N];
int a[N];

int cost(){
    int sum = 0;
    for(int i = 1; i < n; ++ i )
        sum += g[a[i-1]][a[i]];
    sum += g[a[n-1]][a[0]];
    return sum;
}

void copy(){
    for(int i = 0; i < n; ++ i)
        path[i] = a[i];
}

void solve(int u) {
    if(u >= n - 1) {
        if(mn > cost()) mn = cost(),copy();
        return;
    }
    for(int k = u; k < n; ++ k) {
        swap(a[k],a[u]);
        solve(u+1);
        swap(a[k],a[u]);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            cin >> g[i][j];
    for(int i = 0; i < n; ++ i) a[i] = i;
    solve(1);
    cout << mn << endl;
    for(int i = 0; i < n; ++ i) cout << path[i] << " ";
    return 0;
}

背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N],v[N];
bool vis[N],bags[N];

int n,c;
int res;
int cnt;

void dfs(int u,int cur_v,int cur_w){
    if(cur_w > c) return;
    if(u >= n) {
        if(res < cur_v) {
            res = cur_v;
            for(int i = 1; i <= n; ++ i) bags[i] = vis[i];
        }
        return;
    }
    dfs(u+1,cur_v+v[u+1],cur_w+w[u+1]);
    dfs(u+1,cur_v,cur_w);
}

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; ++ i) cin >> w[i] >> v[i];
    dfs(0,0,0);
    cout << res << endl;
    for(int i = 1; i <= n; ++ i)
        if(bags[i]) cout << i <<" ";
    return 0;
}

第五章 分治法

二分查找

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N];

int n,tar;

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    cin >> tar;
    int l = 1,r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(a[mid] >= tar) r = mid;
        else l = mid + 1;
    }
    if(a[r] == tar) cout << r << endl;
    else cout << -1;
    return 0;
}

大数相乘

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

#define SIGN(A) ((A > 0)?1:-1)

const int N = 110;

int x,y,n;

int mul(int x,int y,int n) {
    if(x == 0 || y == 0) return 0;
    if(n == 1) return x * y;
    int x1 = x/pow(10,n/2),y1 = y/pow(10,n/2);
    int x0 = x - x1 * pow(10,n/2),y0 = y - y1 * pow(10,n/2);
    int xy1 = mul(x1,y1,n/2),xy0 = mul(x0,y0,n/2),xy10 = mul(x1-x0,y0-y1,n/2);
    return xy1 * pow(10,n) + (xy10 + xy0 + xy1) * pow(10,n/2) + xy0;
}

int main(){
    cin >> x >> y >> n;
    int s = SIGN(x) * SIGN(y);
    int res = s * mul(abs(x),abs(y),n);
    cout << res;
    return 0;
}

第k小元素

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N];

int n,k;

int get(int l,int r,int k){
    if(l >= r) return a[l];
    int i = l,j = r,pivot = a[l];
    while(i < j) {
        while(a[i] <= pivot) ++ i;
        while(a[j] > pivot) -- j;
        if(i < j)  swap(a[i],a[j]);
    }
    a[l] = a[j],a[j] = pivot;
    if(j - l + 1 == k) return pivot;
    else if(j - l + 1 > k) return get(l,j-1,k);
    else return get(j+1,r,k-j-1+l);
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    cin >> k;
    cout << get(1,n,k);
    return 0;
}

最大子段和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N];
int n;

int f(int l,int r){
    if(l >= r) return a[l];
    int m = l + r >> 1;
    int res = max(f(l,m),f(m+1,r));
    int mxl,mxr;
    mxl = mxr = -0x3f3f3f3f;
    int sl = 0,sr = 0;
    for(int i = m; i >= l; -- i) {
        sl += a[i];
        mxl = max(mxl,sl);
    }
    for(int i = m + 1; i <= r; ++ i) {
        sr += a[i];
        mxr = max(mxr,sr);
    }
    res = max(res,mxl + mxr);
    return res;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    int res = f(1,n);
    cout << res;
}

第六章

回溯法

装载问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

bool vis[N],maxx[N];
int n,c,res,r;
int w[N],s[N];

void dfs(int u,int cur) {
    if(cur > c) return;
    if(u >= n) {
        if(res < cur) {
            res = cur;
            for(int i = 1; i <= n; ++ i) maxx[i] = vis[i];
        }
        return;
    }
    vis[u+1] = true;
    dfs(u+1,cur + w[u+1]);
    vis[u+1] = false;
    if(cur + s[n] - s[u+1] > res) dfs(u+1,cur);
}

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; ++ i) {
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }
    dfs(0,0);
    cout << res << endl;
    for(int i = 1; i <= n; ++ i) 
        if(maxx[i]) cout << i << " ";
    return 0;
}

N-皇后问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int cnt;
int n;
int x[N];

bool ok(int u) {
    for(int i = 1; i < u; ++ i)
        if(x[i] == x[u] || abs(x[i] - x[u]) == abs(i-u))
            return false;
    return true;
}

void dfs(int u){
    if(u > n) {
        cout << ++ cnt << endl;
        for(int i = 1; i <= n; ++ i) printf("(%d,%d)\n",i,x[i]);
        return;
    }
    for(int i = 1; i <= n; ++ i) {
        x[u] = i;
        if(ok(u)) dfs(u + 1);
    }
}

int main(){
    cin >> n;
    dfs(1);
}

0-1背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N],v[N],s[N];
int n,c;
int res;
bool vis[N], maxx[N];

void dfs(int u,int cur_w,int cur_v) {
    if(cur_w > c) return;
    if(u >= n) {
        if(res < cur_v) {
            res = cur_v;
            for(int i = 1; i <= n; ++ i) maxx[i] = vis[i];
        }
        return;
    }
    vis[u+1] = true;
    dfs(u+1,cur_w + w[u+1],cur_v + v[u+1]);
    vis[u+1] = false;
    if(cur_v + s[n] - s[u+1] > res) dfs(u+1,cur_w,cur_v);
}

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; ++ i) {
        cin >> w[i] >> v[i];
        s[i] = s[i-1] + v[i];
    }
    dfs(0,0,0);
    cout << res;
}

分支限界法

装载问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;

int w[N],s[N];

int n,c;
int res;

struct Node{
    int i,w;
};

queue<Node> q;
void bfs() {
    q.push({1,0});
    if(w[1] < c) q.push({1,w[1]});
    while(q.size()){
        int ssize = q.size();
        for(int i = 1; i <= ssize; ++ i) {
            auto t = q.front();q.pop();
            res = max(res,t.w);
            if(t.i < n) {
                if(t.w + w[t.i + 1] <= c) q.push({t.i+1,t.w + w[t.i + 1]});
                if(t.w + s[n] - s[t.i + 1] > res) q.push({t.i+1,t.w});
            }
        }
    }
}

int main(){
    cin >> n >> c;
    for(int i = 1; i <= n; ++ i) {
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }
    bfs();
    cout << res;
}

完全背包问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10;

int n;

int w[N],v[N];
int cnt[N];

int c;

int bestv;


typedef struct Node{
    int val,weight;
}Node;

int t1[N],t2[N];

void msort(int l,int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    msort(l,mid),msort(mid + 1,r);
    int i = l,j = mid + 1,k = 0;
    while(i <= mid && j <= r) {
        if(v[i] * 1.0 / w[i] >= v[j] * 1.0 / w[j]) t1[k] = v[i],t2[k++] = w[i ++];
        else t1[k] = v[j],t2[k++] = w[j ++];
    }
    while(i <= mid) t1[k] = v[i],t2[k++] = w[i ++];
    while(j <= r) t1[k] = v[j],t2[k++] = w[j ++];
    for(i = l,k = 0; i <= r; ++ i, ++ k) v[i] = t1[k],w[i] = t2[k];
}



void bfs(int u){
    queue<Node> q;
    for(int i = 0; i * w[u] <= c; ++ i) { 
        q.push({v[u] * i,w[u] * i});
        bestv = max(v[u] * i,bestv);
    }
    while(q.size()) {
        int s = q.size();
        ++ u;
        if(u == n + 1) break;
        for(int i = 1; i <= s; ++ i) {
            auto t = q.front();q.pop();
            int left = c - t.weight;
            if(t.val + left * v[u] * 1.0 / w[u] <= bestv) continue;
            for(int i = 0; t.weight + w[u] * i <= c; ++ i) {
                q.push({t.val + v[u] * i,t.weight + w[u] * i});
                bestv = max(bestv,t.val + v[u] * i);
            }
        }
    }
}

int main() {
    cin >> n >> c;
    for(int i = 1; i <= n; ++ i) 
        cin >> w[i] >> v[i];
    msort(1,n);
    bfs(1);
    cout << bestv << endl;
    return 0;
}

第七章 贪心算法

最优子结构

活动安排

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

struct Act{
    int s,e;
    bool sel;
    bool operator < (const Act &p) const{
        return e < p.e;
    }
}act[N];

int n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i)
        cin >> act[i].s >> act[i].e;
    sort(act + 1,act + n + 1);
    int st = act[1].s,ed = act[1].e;
    act[1].sel = true;
    int cnt = 1;
    for(int i = 2; i <= n; ++ i) {
        if(act[i].s >= ed)
            ++ cnt,st = act[i].s,ed = act[i].e,act[i].sel = true;
    }
    cout << cnt << endl;
    for(int i = 1; i <= n; ++ i) 
        if(act[i].sel)
            cout << i << " ";
    return 0;
}

极大值极小值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

const int N = 1010;

multiset<int> mx,mn;

int n;

int main(){
    cin >> n;
    int a;
    for(int i = 1; i <= n; ++ i) {
        cin >> a;
        mx.insert(-a),mn.insert(a);
    }
    for(int i = 1; i < n; ++ i){
        int a = *mx.begin();mx.erase(mx.find(a));
        int b = *mx.begin();mx.erase(mx.find(b));
        int c = *mn.begin();mn.erase(mn.find(c));
        int d = *mn.begin();mn.erase(mn.find(d));
        a = 0 - a,b = 0 - b;
        a = a * b + 1;
        c = c * d + 1;
        mx.insert(-a);mn.insert(c);
    }
    cout << 0 -*mx.begin() << " " << *mn.begin() << endl;
    return 0;
}

删除数字

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

char a[N];

int n,s;

int d[N];

void del(char *a,int t,int k) {
    for(int i = t; i < strlen(a) - k; ++ i)
        a[i] = a[i + k];
}


int main(){
    cin >> n >> s;
    scanf("%s",a);
    int i = 0,j = 0,last = -1;
    while(i < s && j < strlen(a)) {
        while(a[j] <= a[j + 1]) ++ j;
        if(j < strlen(a)) {
            del(a,j,1);
            if(j >= last) d[i] = j + i;
            else d[i] = d[i-1] - 1;
            last = j; ++ i,-- j;
            if(j < 0) j = 0;
        }
    }
    while(a[0] == '0' && strlen(a)) del(a,0,1);
    for(int i = 0; i < n - s; ++ i) cout << a[i];
    return 0;
}

第八章 动态规划

最优子结构、子问题重叠性

数字三角形

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510,inf = 0x3f3f3f3f;

int a[N][N],f[N][N];
int path[N][N];

int n;

int main() {
    scanf("%d", &n);
    
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= i; ++ j)
            scanf("%d",&a[i][j]);
            
    /*for(int i = 0; i <= n; ++ i) 
        for(int j = 0; j <= n + 1; ++ j)
            f[i][j] = -inf;*/
            
    for(int i = 1; i <= n; ++ i) f[n][i] = a[n][i];
    
    for(int i = n - 1; i >= 1; -- i)
        for(int j = 1; j <= i; ++ j)
            if(f[i + 1][j] > f[i + 1][j + 1])
                path[i][j] = 0,f[i][j] = f[i + 1][j] + a[i][j];
            else path[i][j] = 1,f[i][j] = f[i + 1][j + 1] + a[i][j];
    cout << f[1][1] << endl;
    int i,j = 1;
    for(i = 1; i < n; ++ i){
        printf("%d->",a[i][j]);
        j += path[i][j];
    }
    cout << a[n][j];
    return 0;
}

投资分配

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int f[N],g[N],t[N];
int a[N][N];
int gain[N];

int n,m;

int main(){
    cin >> m >> n;
    for(int i = 0; i <= n; ++ i) {
        cin >> f[i];
        g[i] = f[i];
        a[1][i] = i;
    }
    for(int i = 2; i <= m; ++ i) {
        for(int j = 0; j <= n; ++ j) {
            t[j] = g[j];
            cin >> f[j];
            a[i][j] = 0;
        }
        for(int j = 0; j <= n; ++ j)
            for(int k = 0; k <= j; ++ k)
                if(f[k] + g[j - k] > t[j])
                    t[j] = f[k] + g[j - k],a[i][j] = k;
        for(int i = 0; i <= n; ++ i)
            g[i] = t[i];
    }
    int res = n;
    for(int i = m; i >= 1; -- i)
        gain[i] = a[i][res],res -= gain[i];
    for(int i = 1; i <= m; ++ i) cout << gain[i] << " ";
    cout << endl << g[n] << endl;
    return 0;
}

01背包

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N],v[N];
int f[N][N];
bool bag[N];

int n,m;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
        cin >> w[i] >> v[i];
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j) {
            f[i][j] = f[i-1][j];
            if(j >= w[i]) f[i][j] = max(f[i][j],f[i-1][j-w[i]] + v[i]);
        }
    int j = m;
    for(int i = n; i >= 1; -- i)
        if(f[i][j] > f[i-1][j]) bag[i] = true,j -= w[i];
    for(int i = 1; i <= n; ++ i)
        if(bag[i]) cout << 1;
        else cout << 0;
    return 0;
}

矩阵连乘

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int p[N],m[N][N],s[N][N];

int n;

void output(int l,int r){
    if(l >= r) return;
    printf("(%d,%d): %d\n",l,r,s[l][r]);
    output(l,s[l][r]),output(s[l][r] + 1,r);
}

int main(){
    cin >> n;
    for(int i = 1; i <= n+1; ++ i) cin >> p[i];
    memset(m,0x3f,sizeof m);
    for(int i = 1; i <= n; ++ i) m[i][i] = 0;
    for(int len = 2; len <= n; ++ len)
        for(int i = 1; i <= n - len + 1; ++ i) {
            int j = i + len - 1;
            for(int k = i; k < j; ++ k) {
                int t = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1];
                if(t < m[i][j]) m[i][j] = t,s[i][j] = k;
            }
        }
    cout << m[1][n] << endl;
    output(1,n);
}

最长公共子序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

char a[N],b[N];
int f[N][N];
int n,m;

int main(){
    cin >> n >> m;
    scanf("%s%s",a + 1,b + 1);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j) {
            f[i][j] = max(f[i-1][j],f[i][j-1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j],f[i-1][j-1] + 1);
        }
    cout << f[n][m];
    return 0;
}

最大子段和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int n;
int a[N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    int res = 0,cur = 0;
    int st,ed;
    st = ed = -1;
    int i = 1;
    for(int j = 1; j <= n;++ j) {
        cur += a[j];
        if(cur > res) res = cur,st = i,ed = j;
        if(cur < 0) i = j + 1,cur = 0;
    }
    cout << res << " " << st << " " << ed << endl;
    return 0;
}

第九章 随机算法

线性同余生成伪随机

#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>
using namespace std;
const unsigned long b = 1194211693l;
const unsigned long c = 12345l;
static unsigned long rand_seed;

void mysrand(unsigned long seed){
    rand_seed = seed;
}
long myrand(){
    rand_seed = (rand_seed * b + c) % ((1 << 31) - 1);
    return rand_seed;
}
double myrandf(){
    return rand_seed * 1.0/((1 << 31) - 1);
}
int main(){
    mysrand(time(0));
    for(int i = 0; i < 50; ++ i) {
        myrand();
        cout << rand_seed << endl << myrandf() << endl;
    }
}

蒙特卡罗

#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>

using namespace std;

int main(){
    int n;
    cin >> n;
    double x,y;
    srand(time(0));
    int cnt = 0;
    for(int i = 0; i < n; ++ i) {
        x = rand() * 1.0 / RAND_MAX;
        y = rand() * 1.0 / RAND_MAX;
        if(x * x + y * y <= 1) ++ cnt;
    }
    cout << 4 * cnt * 1.0 / n;
}

素数判断

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

int qmi(int a, int k, int n)  // 求a^k mod p
{
   int y = 1,z = a;
   while(k){
       while(k % 2 == 0) {
           int x = z;
           z = z * z % n;
           k >>= 1;
           //if((z == 1) && (x != 1) && (x != n - 1)) return true;
       }
       -- k;
       y = y * z % n;
   }
   return y;
}


bool prime(int n) {
    srand(time(0));
    for(int i = 1; i < log10(n); ++ i) {
        int a = rand() % n + 1;
        if(qmi(a,n-1,n)) return false;
    }
    return true;
}

int n;
int main(){
    cin >> n;
    if(prime(n)) cout << "y" << endl;
    else cout << "n" << endl;
    return 0;
}

舍伍德算法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <ctime>

using namespace std;

const int N = 110;

int a[N];

int n,k;

int get(int l,int r,int k){
    if(l >= r) return a[l];
    int i = l,j = l + rand() % (r - l);
    swap(a[i],a[j]);
    int pivot = a[l];
    j = r;
    while(i < j) {
        while(a[i] <= pivot) ++ i;
        while(a[j] > pivot) -- j;
        if(i < j)  swap(a[i],a[j]);
    }
    a[l] = a[j],a[j] = pivot;
    if(j - l + 1 == k) return pivot;
    else if(j - l + 1 > k) return get(l,j-1,k);
    else return get(j+1,r,k-j-1+l);
}

int main(){
    srand(0);
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    cin >> k;
    cout << get(1,n,k);
    return 0;
}