Acwing 算法基础课 c++模板整理（附python语法基础题）（二）-阿里云开发者社区

SPFA判负环

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m;
const int N = 100005;
int cnt[N];
int dist[N];
typedef  pair<int, int> PII;//first表示指向点，second表示距离
vector<PII> graph[N];
bool spfa() {
    queue<int> q;
    for(int i=1;i<=n;i++)
        q.push(i);
    while (!q.empty()) {
        int curnode = q.front();
        q.pop();
        for (auto node : graph[curnode]) {
            if (dist[node.first] > dist[curnode] + node.second) {
                dist[node.first] = dist[curnode] + node.second;
                cnt[node.first]=cnt[curnode]+1;
                if (cnt[node.first] >= n)
                    return true;
                q.push(node.first);
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({ y,z });
    }
    if (spfa())
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Bellman-Ford

#include<iostream>
#include<cstring>
using namespace std;
int n, m, k;
struct Edge {
    int x, y, z;
};
Edge edges[10005];
int dist[505];
int backup[505];
int main() {
    cin >> n >> m >> k;
    memset(dist, 0x3f3f3f3f, sizeof dist);
    memset(backup, 0x3f3f3f3f, sizeof backup);
    for(int i=0;i<m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        edges[i] = { x,y,z };
    }
    dist[1] = 0;
    while (k--) {
        for (int i = 1; i <= n; i++)
            backup[i] = dist[i];
        for (int i = 0; i < m; i++) 
            dist[edges[i].y] = min( dist[edges[i].y],backup[edges[i].x] + edges[i].z );
    }
    if (dist[n] >= 0x3f3f3f3f / 2)
        cout << "impossible";
    else
        cout << dist[n];
    return 0;
}

Prim

#include<cstring>
#include<iostream>
using namespace std;
const int N = 505;
int graph[N][N];
int dist[N];
int s[N];
int n, m;
int res = 0;
void prim() {
    s[1] = true;
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
        dist[i] = graph[1][i];
    for (int i = 1; i <= n; i++) {
        int curnode = 0;
        for (int j = 1; j <= n; j++) {
            if (!s[j] && (curnode==0||dist[j] < dist[curnode]))
                curnode = j;
        }
        if (curnode&&dist[curnode] == 0x3f3f3f3f) {
            res = 0x3f3f3f3f;
            return;
        }
        if (curnode) {
            s[curnode] = true;
            res += dist[curnode];
            for (int j = 1; j <= n; j++)
                if (!s[j] && dist[j] >  graph[curnode][j])
                    dist[j] =  graph[curnode][j];
        }
    }
}
int main() {
    cin >> n >> m;
    memset(graph, 0x3f3f3f3f, sizeof graph);
    memset(dist, 0x3f3f3f3f, sizeof dist);
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z < graph[x][y])
            graph[x][y] =graph[y][x]= z;
    }
    for (int i = 0; i <= n; i++)
        graph[i][i] = 0;
    prim();
    if (res < 0x3f3f3f3f)
        cout << res;
    else
        cout << "impossible";
    return 0;
}

Kruskal

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000005;
struct edge {
    int u, v, w;
    bool operator <(const edge& b) const {
        return w < b.w;
    }
};
int p[N];
edge edges[N];
int find(int a) {
    if (a!= p[a]) 
        p[a] = find(p[a]);
    else return p[a];
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (u!=v)
            edges[i] = { u,v,w };
    }
    for (int i = 0; i <=n; i++)
        p[i] = i;
    sort(edges, edges + m);
    long long res = 0;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        u = find(u);
        v = find(v);
        if (u != v) {
            res += w;
            cnt++;
            p[find(u)] =v;
        }
    }
    if (cnt < n - 1)
        cout << "impossible";
    else
        cout << res;
    return 0;
}

染色法判定二分图

#include<iostream>
#include<vector>
using namespace std;
const int N = 100005;
int color[N];
int res = true;
vector<int> G[N];
void dfs(int i, int clr) {
    color[i] = clr;
    for (auto node : G[i]) {
        if(!color[node])
            dfs(node, 3 - clr);
        else if (color[node] == color[i]) {
            res = false;
            return;
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    while (m--){
        int u, v;
        cin >> u >> v;
        if (u != v) {
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
    for (int i = 1; i <= n; i++) {
        if(!color[i])
            dfs(i, 1);
    }
    if (res)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

匈牙利算法

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 1005;
vector<int> graph[N];
int match[N];
int st[N];
bool find(int x) {
    for (auto node : graph[x]) {
        if (!st[node]) {
            st[node] = true;
            if (!match[node] || find(match[node])) {
                match[node]=x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }
    int res = 0;
    for (int i = 1; i <= n1; i++) {
        memset(st, false, sizeof st);
        if (find(i))
            res++;
    }
    cout << res << endl;
    return 0;
}

数论

线性筛

#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

分解质因数

#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x){
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}

试除法求约数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> get_divisors(int x){
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0){
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        auto res = get_divisors(x);
        for (auto x : res) cout << x << ' ';
        cout << endl;
    }
    return 0;
}

约数个数

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- ){
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0){
                x /= i;
                primes[i] ++ ;
            }
        if (x > 1) primes[x] ++ ;
    }
    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;
    cout << res << endl;
    return 0;
}

约数之和

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while (n -- ){
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0){
                x /= i;
                primes[i] ++ ;
            }
        if (x > 1) primes[x] ++ ;
    }
    LL res = 1;
    for (auto p : primes){
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }
    cout << res << endl;
    return 0;
}

gcd

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

欧拉函数

#include <iostream>
using namespace std;
int phi(int x){
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0){
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        int x;
        cin >> x;
        cout << phi(x) << endl;
    }
    return 0;
}

筛法欧拉函数

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int euler[N];
bool st[N];
void get_eulers(int n){
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0){
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}
int main(){
    int n;
    cin >> n;
    get_eulers(n);
    LL res = 0;
    for (int i = 1; i <= n; i ++ ) res += euler[i];
    cout << res << endl;
    return 0;
}

快速幂

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){
    LL res = 1 % p;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }
    return 0;
}

快速幂求逆元

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){
    LL res = 1;
    while (b){
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}

扩展欧几里得算法

给定n nn对正整数a i , b i a_i,b_iai,bi，对于每对数，求出一组x i , y i x_i,y_ixi,yi，使其满足 a i × x i + b i × y i = g c d ( a i , b i ) a_i×x_i+b_i×y_i=gcd(a_i,b_i)ai×xi+bi×yi=gcd(ai,bi)。

#include <iostream>
#include <algorithm>
using namespace std;
int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}

线性同余方程

给定n nn组数据a i , b i , m i a_i,b_i,m_iai,bi,mi，对于每组数求出一个x i x_ixi，使其满足a i × x i ≡ b i ( m o d m i ) a_i×x_i≡b_i(\mod m_i)ai×xi≡bi(modmi)，如果无解则输出 impossible。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main(){
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b, m;
        scanf("%d%d%d", &a, &b, &m);
        int x, y;
        int d = exgcd(a, m, x, y);
        if (b % d) puts("impossible");
        else printf("%d\n", (LL)b / d * x % m);
    }
    return 0;
}

扩展中国剩余定理

表达整数的奇怪方式。给定2 n 2n2n个整数a 1 , a 2 , … , a n a_1,a_2,…,a_na1,a2,…,an和m 1 , m 2 , … , m n m_1,m_2,…,m_nm1,m2,…,mn，求一个最小的非负整数x xx，满足∀ i ∈ [ 1 , n ] , x ≡ m i ( m o d a i ) ∀i∈[1,n],x≡m_i(\mod a_i)∀i∈[1,n],x≡mi(modai)。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){
    if(b == 0){
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
LL inline mod(LL a, LL b){
    return ((a % b) + b) % b;
}
int main(){
    scanf("%d", &n);
    LL a1, m1;
    scanf("%lld%lld", &a1, &m1);
    for(int i = 1; i < n; i++){
        LL a2, m2, k1, k2;
        scanf("%lld%lld", &a2, &m2);
        LL d = exgcd(a1, -a2, k1, k2);
        if((m2 - m1) % d){ puts("-1"); return 0; }
        k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));
        m1 = k1 * a1 + m1;
        a1 = abs(a1 / d * a2);
    }
    printf("%lld\n", m1);
    return 0;
}

同余方程

关于x xx的方程a x ≡ 1 ( m o d b ) ax≡1(modb)ax≡1(modb)的最小正整数解

#include<iostream>
typedef long long LL;
using namespace std;
LL exgcd(LL a,LL b,LL&x,LL&y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main(){
    LL a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b;
    return 0;
}

斐波那契(矩阵快速幂)

#include<iostream>
typedef long long LL;
using namespace std;
LL n,m;
LL M[2][2]={
    {0,1},
    {1,1}
};
LL res[2]={1,0};
void mulrm(){
    LL ans[2]={0};
    for(LL i=0;i<2;i++)
        for(LL j=0;j<2;j++)
            ans[i]+=res[j]*M[i][j]%m;
    for(LL i=0;i<2;i++)
        res[i]=ans[i]%m;
}
void mulmm(){
    LL ans[2][2]={0};
    for(LL i=0;i<2;i++){
        for(LL j=0;j<2;j++){
            for(LL k=0;k<2;k++)
                ans[i][j]+=M[i][k]*M[k][j]%m;
        }
    }
    for(LL i=0;i<2;i++)
        for(LL j=0;j<2;j++)
            M[i][j]=ans[i][j]%m;
}
void qpow(LL n){
    while(n){
        if (n&1)
            mulrm();
        mulmm();
        n>>=1;
    }
}
int main(){
    cin>>n>>m;
    qpow(n+2);
    cout<<res[1]-1;
    return 0;
}

高斯消元

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];
int gauss(){  // 高斯消元，答案存于a[i][n]中，0 <= i < n
    int c, r;
    for (c = 0, r = 0; c < n; c ++ ){
        int t = r;
        for (int i = r; i < n; i ++ )  // 找绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps) continue;
        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);  // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];  // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];
        r ++ ;
    }
    if (r < n){
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }
    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];
    return 0; // 有唯一解
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            scanf("%lf", &a[i][j]);
    int t = gauss();
    if (t == 2) puts("No solution");
    else if (t == 1) puts("Infinite group solutions");
    else{
        for (int i = 0; i < n; i ++ ){
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }
    return 0;
}

组合数

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init(){
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
int main(){
    int n;
    init();
    scanf("%d", &n);
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", c[a][b]);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main(){
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ ){
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    scanf("%d", &n);
    while (n -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p){
    if (b > a) return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- ){
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(LL a, LL b, int p){
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main(){
    int n;
    cin >> n;
    while (n -- ){
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}

卡特兰数

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int qmi(int a, int k, int p){
    int res = 1;
    while (k){
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main(){
    int n;
    cin >> n;
    int a = n * 2, b = n;
    int res = 1;
    for (int i = a; i > a - b; i -- ) res = (LL)res * i % mod;
    for (int i = 1; i <= b; i ++ ) res = (LL)res * qmi(i, mod - 2, mod) % mod;
    res = (LL)res * qmi(n + 1, mod - 2, mod) % mod;
    cout << res << endl;
    return 0;
}

能被整除的数

给定一个整数n nn和m mm个不同的质数p 1 , p 2 , … , p m p_1,p_2,…,p_mp1,p2,…,pm。

请你求出1 ∼ n 1∼n1∼n中能被p 1 , p 2 , … , p m p_1,p_2,…,p_mp1,p2,…,pm中的至少一个数整除的整数有多少个。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> p[i];
    int res = 0;
    for (int i = 1; i < 1 << m; i ++ ){
        int t = 1, s = 0;
        for (int j = 0; j < m; j ++ )
            if (i >> j & 1){
                if ((LL)t * p[j] > n){
                    t = -1;
                    break;
                }
                t *= p[j];
                s ++ ;
            }
        if (t != -1){
            if (s % 2) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}

龟速乘法

#include<iostream>
using namespace std;
typedef long long LL;
LL a,b,p;
LL qadd(LL a,LL b,LL p){
    LL res=0;
    while(b){
        if (b&1)
            res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}
int main(){
    cin>>a>>b>>p;
    cout<<qadd(a,b,p);
    return 0;
}

DP

01背包

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

完全背包

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

多重背包

#include<iostream>
#include<algorithm>
using namespace std;
int dp[10005];
int v[1005];
int w[1005];
int s[1005];
int vf[10005], wf[10005];
int N, V;
int main() {
    cin >> N >> V;
    for (int i = 1; i <= N; i++)
        cin >> v[i] >> w[i]>>s[i];
    int idx = 0;
    for (int i = 1; i <= N; i++) {
        int cur = 1;
        int res = s[i];
        while (res>=cur) {
            res = res - cur;
            idx++;
            vf[idx] = cur * v[i];
            wf[idx] = cur * w[i];
            cur = cur * 2;
        }
        if (res>0) {
            idx++;
            vf[idx] = res * v[i];
            wf[idx] = res * w[i];
        }
    }
    for(int i=1;i<=idx;i++)
        for (int j = V; j >= vf[i]; j--) {
            dp[j] = max(dp[j], dp[j - vf[i]] + wf[i]);
        }
    cout << dp[V];
    return 0;
}

分组背包问题

有N NN组物品和一个容量是V VV的背包。

每组物品有若干个，同一组内的物品最多只能选一个。

每件物品的体积是v i j v_{ij}vij，价值是w i j w_{ij}wij，其中i ii是组号,j jj是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    cout << f[m] << endl;
    return 0;
}

数字三角形

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][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 <= i + 1; j ++ )
            f[i][j] = -INF;
    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}

石子合并

设有N NN堆石子排成一排，其编号为1 ， 2 ， 3 ， … ， N 1，2，3，…，N1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这N NN堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];
    for (int len = 2; len <= n; len ++ )
        for (int i = 1; i + len - 1 <= n; i ++ ){
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k ++ )
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}

lis

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int len = 0;
    for (int i = 0; i < n; i ++ ){
        int l = 0, r = len;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}

整数划分

一个正整数n nn可以表示成若干个正整数之和，形如n = n 1 + n 2 + … + n k n=n_1+n_2+…+n_kn=n1+n2+…+nk，其中n 1 ≥ n 2 ≥ … ≥ n k , k ≥ 1 n_1≥n_2≥…≥n_k,k≥1n1≥n2≥…≥nk,k≥1。

我们将这样的一种表示称为正整数n nn的一种划分。

现在给定一个正整数n nn，请你求出n nn共有多少种不同的划分方法。

完全背包解法

状态表示：

f[i][j]表示只从1~i中选，且总和等于j的方案数

状态转移方程:

f[i][j] = f[i - 1][j] + f[i][j - i];

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
int main(){
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n] << endl;
    return 0;
}

其他算法

状态表示：

f[i][j]表示总和为i，总个数为j的方案数

状态转移方程：

f[i][j] = f[i - 1][j - 1] + f[i - j][j];

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main(){
    cin >> n;
    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}

1050. 鸣人的影分身

在火影忍者的世界里，令敌人捉摸不透是非常关键的。

我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。

影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。

针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。

那么问题来了，假设鸣人的查克拉能量为M MM，他影分身的个数最多为N NN，那么制造影分身时有多少种不同的分配方法？

注意：

影分身可以分配0 00点能量。

分配方案不考虑顺序，例如：M = 7 , N = 3 M=7,N=3M=7,N=3，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。

#include<cstring>
#include<iostream>
using namespace std;
int f[15][15];
int main(){
    int t;
    cin>>t;
    while(t--){
        int m,n;
        cin>>m>>n;
        memset(f,0,sizeof f);
        f[0][0]=1;
        //把m划分成n个数
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                f[i][j]+=f[i][j-1];
                if (i>=j)
                    f[i][j]+=f[i-j][j];
            }
        }
        cout<<f[m][n]<<endl;
    }
    return 0;
}

NOIP2001数字划分

将整数n nn分成k kk份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。

#include<iostream>
using namespace std;
int dp[205][10];
int main(){
    int n,k;
    cin>>n>>k;
    dp[0][0]=0;
    for(int i=0;i<=n;i++)
        dp[i][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++){
                dp[i][j]=dp[i-1][j-1];
            if(i>j)
                dp[i][j]+=dp[i-j][j];
        }
    }
    cout<<dp[n][k];
}

滑雪

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n, m;
int g[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y){
    int &v = f[x][y];
    if (v != -1) return v;
    v = 1;
    for (int i = 0; i < 4; i ++ ){
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
            v = max(v, dp(a, b) + 1);
    }
    return v;
}
int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &g[i][j]);
    memset(f, -1, sizeof f);
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));
    printf("%d\n", res);
    return 0;
}

没有上司的舞会

Ural 大学有N NN名职员，编号为1 ∼ N 1∼N1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数H i H_iHi给出，其中1 ≤ i ≤ N 1≤i≤N1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

#include<iostream>
#include<vector>
using namespace std;
const int N=6005;
int f[N][2];
vector<int> G[N];
bool st[N];
int H[N];
void dfs(int root){
    f[root][1]=H[root];//选自己
    for(auto node:G[root]){
        dfs(node);
        f[root][0]+=max(f[node][0],f[node][1]);//不选自己
        f[root][1]+=f[node][0];//选自己
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        G[v].push_back(u);
        st[u]=1;
    }
    int root=0;
    for(int i=1;i<=n;i++){
        if (st[i]==0){
            root=i;
            break;
        }
    }
    dfs(root);
    cout<<max(f[root][0],f[root][1]);
    return 0;
}

最短Hamilton路径

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    if (i >> k & 1)
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
    cout << f[(1 << n) - 1][n - 1];
    return 0;
}

蒙德里安的梦想

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];
int main(){
    while (cin >> n >> m, n || m){
        for (int i = 0; i < 1 << n; i ++ ){
            int cnt = 0;
            bool is_valid = true;
            for (int j = 0; j < n; j ++ )
                if (i >> j & 1){
                    if (cnt & 1){
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt ++ ;
            if (cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
        for (int i = 0; i < 1 << n; i ++ ){
            state[i].clear();
            for (int j = 0; j < 1 << n; j ++ )
                if ((i & j) == 0 && st[i | j])
                    state[i].push_back(j);
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1; i <= m; i ++ )
            for (int j = 0; j < 1 << n; j ++ )
                for (auto k : state[j])
                    f[i][j] += f[i - 1][k];
        cout << f[m][0] << endl;
    }
    return 0;
}

计数问题

给定两个整数a aa和b bb，求a aa和b bb之间的所有数字中0 ∼ 9 0∼90∼9的出现次数。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999
*/
int get(vector<int> num, int l, int r){
    int res = 0;
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}
int power10(int x){
    int res = 1;
    while (x -- ) res *= 10;
    return res;
}
int count(int n, int x){
    if (!n) return 0;
    vector<int> num;
    while (n){
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i -- ){
        if (i < n - 1){
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }
        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }
    return res;
}
int main(){
    int a, b;
    while (cin >> a >> b , a){
        if (a > b) swap(a, b);
        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    return 0;
}

Nim游戏

给定n nn堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

#include <iostream>
#include <cstdio>
using namespace std;
/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/
int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
}

Acwing 算法基础课 c++模板整理（附python语法基础题）（二）