AcWing算法基础课

算法基础课
- 第一章基础算法
  - 785.快速排序
  - 786.第k个数
  - 787.归并排序
  - 788.逆序对的数量*
  - 789.数的范围
  - 790.数的三次方根
  - 791.高精度加法
  - 792.高精度减法
  - 793.高精度乘法
  - 794.高精度除法*
  - 759.前缀和
  - 796.子矩阵的和
  - 797.差分
  - 798.差分矩阵*
  - 799.最长连续不重复子序列
  - 800.数组元素的目标和
  - 2816.判断子序列
  - 801.二进制中1的个数
  - 802.区间和**
  - 803.区间和并
- 第二章数据结构
  - 826.单链表
  - 872.双链表*
  - 828.模拟栈
  - 3302.表达式求值**
  - 829.模拟队列
  - 830.单调栈
  - 154.滑动窗口**
  - 831.KMP字符串**
  - 835.Trie字符串统计*
  - 143.最大异或对*
  - 836.合并集合
  - 837.连通块中点的数量
  - 240.食物链**
  - 838.堆排序
  - 839.模拟堆**
  - 840.模拟散列表
  - 841.字符串哈希**
- 第三章搜索与图论
  - 842.排列数字
  - 844.走迷宫
  - 845.八数码*
  - 846.树的重心*
  - 847.图中点的层次
  - 848.有向图的拓扑序列
  - 849.Dijkstra求最短路I
  - 850.Dijkstra求最短路II
  - 853.有边数限制的最短路*
  - 851.spfa求最短路
  - 852.spfa判断负环*
  - 854.Floyd求最短路
  - 858.Prim求最小生成树
  - 859.Kruskal算法求最小生成树
  - 860.染色法判定二分图
  - 861.二分图的最大匹配*
- 第四章数学知识
  - 866.试除法判断质数
  - 867.分解质因数
  - 870.筛质数*
  - 869.试除法求约数
  - 870.约数个数
  - 871.约数之和
  - 872.最大公约数
  - 873.欧拉函数
  - 874.筛法求欧拉函数**
  - 875.快速幂
  - 876.快速幂求逆元*
  - 877.扩展欧几里得算法*
  - 878.线性同余方程**
  - 204.表达整数的奇怪方式***
  - 883.高斯消元解线性方程组**
  - 884.高斯消元解异或线性方程组*
  - 885.求组合数I
  - 886.求组合数II
  - 887.求组合数III
  - 888.求组合数IV*
  - 889.满足条件的01序列
  - 890.能被整除的数
  - 891.Nim游戏
  - 892.台阶-Nim游戏
  - 893.集合-Nim游戏*
  - 894.拆分-Nim游戏**
- 第五章动态规划
  - 2.01背包
  - 3.完全背包问题
  - 4.多重背包问题I
  - 5.多重背包问题II*
  - 9.分组背包问题
  - 898.数字三角形
  - 895.最长上升子序列
  - 896.最长上升子序列II
  - 897.最长公共子序列*
  - 902.最短编辑距离*
  - 899.编辑距离*
  - 282.石子合并
  - 900.整数划分
  - 338.计数问题***
  - 291.蒙德里安的梦想**
  - 91.最短Hamilton路径*
  - 285.没有上司的舞会
  - 901.滑雪
- 第六章贪心
  - 905.区间选点
  - 908.最大不相交区间数量
  - 906.区间分组*
  - 907.区间覆盖*
  - 148.合并果子
  - 913.排队打水
  - 104.货仓选址
  - 125.耍杂技的牛*

算法基础课

第一章基础算法

785.快速排序

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int num[N];

void quickSort(int l, int r)
{
    if(l >= r)
    {
        return;
    }
    int x = num[l+r>>1];
    int i = l-1, j = r+1;
    while(i < j)
    {
        do i++; while(num[i] < x); //不加等号,防止全都一样穿了整个数组
        do j--; while(num[j] > x);
        if(i < j) //两个指针错位的
        {
            swap(num[i], num[j]);
        }
    }
    quickSort(l, j); //两个指针错位的
    quickSort(j+1, r);
    
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    quickSort(1, n);
    for(int i = 1; i <= n; ++ i)
    {
        cout << num[i] << " ";
    }
    return 0;
}

786.第k个数

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, k;
int num[N];

//函数作用，排序l-r并且找到l-r这个区间从小到大的第t个数
int quickSort(int l, int r, int k)
{
    if(l == r)
    {
        return num[l]; 
    }
    int x = num[l+r>>1];
    int i = l-1, j = r+1;
    while(i < j)
    {
        do i ++; while(num[i] < x); //不取等号防穿
        do j --; while(num[j] > x);
        if(i < j) //i,j会错位
        {
            swap(num[i], num[j]);
        }
    }
    int lcnt = j-l+1;
    if(k <= lcnt)
    {
        return quickSort(l, j, k); //i和j错位了
    }
    else
    {
        return quickSort(j+1, r, k-lcnt);
    }
}

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

787.归并排序

#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;
int num[N];
int tp[N];


//作用：排序l-r区间
void mergeSort(int l, int r)
{
    if(l >= r)
    {
        return ;
    }
    int mid = l+r>>1;
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    int i = l, j = mid+1, t = l;
    while(i <= mid && j <= r)
    {
        tp[t++] = num[i]<=num[j]?num[i++]:num[j++];
    }
    while(i <= mid)
    {
        tp[t++] = num[i++];
    }
    while(j <= r)
    {
        tp[t++] = num[j++];
    }
    for(int i = l; i <= r; ++ i)
    {
        num[i] = tp[i];
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    mergeSort(1, n);
    for(int i = 1; i <= n; ++ i)
    {
        cout << num[i] << " ";
    }
    return 0;
}

788.逆序对的数量*

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5+5;

int n;
int num[N];
int tp[N];

//对l-r区间进行排序，并且返回这个区间的逆序对数量
LL mergeSort(int l ,int r)
{
    if(l >= r)
    {
        return 0;
    }
    int mid = l+r>>1;
    LL lcnt = mergeSort(l, mid);
    LL rcnt = mergeSort(mid+1, r);
    LL res = lcnt+rcnt;
    int i = l, j = mid+1, t = l;
    //以右半边为基准不动点，则res += S[mid+1]+S[mid+2]+...+S[r]
    while(i <= mid && j <= r)
    {
        if(num[i] <= num[j]) //不产生逆序对
        {
            tp[t++] = num[i++];
        }
        else //产生逆序对
        {
            tp[t++] = num[j++];
            res += (mid-i+1);
        }
    }
    //逆序对统计以右半边区间为基准
    while(i <= mid)
    {
        tp[t++] = num[i++];
    }
    //不产生逆序对
    while(j <= r)
    {
        tp[t++] = num[j++];
    }
    for(int i = l; i <= r; ++ i)
    {
        num[i] = tp[i];
    }
    return res;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    cout << mergeSort(1, n) << endl;
    return 0;
}

789.数的范围

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, q;

int num[N];

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    while(q --)
    {
        int k;
        cin >> k;
        int resL = -1, resR = -1;
        //求起始位置，即大于等于k的最小值
        int l = 1, r = n;
        while(l < r)
        {
            int mid = l+r>>1;
            if(num[mid] >= k)
            {
                r = mid;
            }
            else l = mid+1;
        }
        if(num[l] == k)
        {
            resL = l-1; //位置从0开始计数
        }
        //求终止位置，即小于等于k的最大值
        l = 1, r = n;
        while(l < r)
        {
            int mid = l+r+1>>1;
            if(num[mid] <= k)
            {
                l = mid;
            }
            else r = mid-1;
        }
        if(num[l] == k)
        {
            resR = l-1; //位置从0开始计数
        }
        cout << resL << " " << resR << endl; 
    }
    return 0;
}

790.数的三次方根

#include 
#include 
#include 

using namespace std;

const double eps = 1e-8;

double n;

int main()
{
    cin >> n;
    double l = -100, r = 100;
    while(r-l > eps)
    {
        double mid = (r+l)/2;
        if(mid*mid*mid >= n)
        {
            r = mid;
        }
        else
        {
            l = mid;
        }
    }
    printf("%.6lf\n", l);
    return 0;
}

791.高精度加法

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

string sa, sb;

int a[N], b[N];

int main()
{
    cin >> sa >> sb;
    int la = sa.size(), lb = sb.size();
    for(int i = la-1, j = 0; i >= 0; -- i, ++ j)
    {
        a[j] = sa[i]-'0';
    }
    for(int i = lb-1, j = 0; i >= 0; -- i, ++ j)
    {
        b[j] = sb[i]-'0';
    }
    int r = 0;
    int len = max(la, lb);
    int bit = 0;
    //结果存到b数组
    while(bit < len)
    {
        b[bit] += a[bit] + r;
        r = b[bit]/10;
        b[bit] %= 10;
        bit ++;
    }
    if(r > 0)
    {
        b[bit] = r;
        len ++;
    }
    for(int i = len-1; i >= 0; -- i)
    {
        cout << b[i];
    }
    return 0;
}

792.高精度减法

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

string sa, sb;

int a[N], b[N];

int main()
{
    cin >> sa >> sb;
    int la = sa.size(), lb = sb.size();
    if(la < lb || (la == lb && sa < sb))
    {
        cout << "-";
        swap(sa, sb);
        swap(la, lb);
    }
    for(int i = la-1, j = 0; i >= 0; -- i, ++ j)
    {
        a[j] = sa[i]-'0';
    }
    for(int i = lb-1, j = 0; i >= 0; -- i, ++ j)
    {
        b[j] = sb[i]-'0';
    }
    //计算结果存到a数组
    int r = 0; //借位
    for(int i = 0; i < la; ++ i)
    {
        a[i] = (a[i]-r) - b[i];
        if(a[i] < 0)
        {
            a[i] += 10;
            r  = 1;
        }
        else
        {
            r = 0;
        }
    }
    int idxStart = la-1;
    while(a[idxStart] == 0 && idxStart >= 0)
    {
        idxStart --;
    }
    if(idxStart < 0)
    {
        cout << 0;
    }
    else
    {
        for(int i = idxStart; i >= 0; -- i)
        {
            cout << a[i];
        }
    }
    return 0;
}

793.高精度乘法

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+10; //注意比平时还要多加五位

string sa;
int b;

int a[N];

int main()
{
    cin >> sa >> b;
    if(b == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    int la = sa.size();
    for(int i = la-1, j = 0; i >= 0; -- i, ++ j)
    {
        a[j] = sa[i]-'0';
    }
    //结果存到a数组中
    int len = la;
    int r = 0; //进位
    for(int i = 0; i < la; ++ i)
    {
        a[i] = a[i]*b+r;
        r = a[i]/10;
        a[i] %= 10;
    }
    while(r > 0)
    {
        a[len] = r%10;
        r = r/10;
        len ++;
    }
    for(int i = len-1; i >= 0; -- i)
    {
        cout << a[i];
    }
    return 0;
}

794.高精度除法*

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

string sa;
int b;

int main()
{
    cin >> sa >> b;
    int la = sa.size();
    int r = 0;
    vector ans;
    for(int i = 0; i < la; ++ i)
    {
        int x = sa[i]-'0';
        r = r*10+x;
        int resBit = r/b;
        r = r%b;
        if(ans.size() == 0 && resBit == 0)
        {
            continue;
        }
        ans.push_back(resBit);
    }
    if(ans.size() == 0)
    {
        cout << 0 << endl;
    }
    else
    {
        for(int i = 0; i < ans.size(); ++ i)
        {
            cout << ans[i];
        }
        cout << endl;
    }
    cout << r << endl;
    return 0;
}

759.前缀和

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
int sum[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
       cin >> sum[i];
       sum[i] += sum[i-1];
    }
    while(m --)
    {
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l-1] << endl;
    }
    return 0;
}

796.子矩阵的和

#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m, q;

int sum[N][N];

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            int x;
            cin >> x;
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + x;
        }
    }
    while(q --)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] << endl;
    }
    return 0;
}

797.差分

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
int d[N];

void add(int l, int r, int x)
{
    d[l] += x;
    d[r+1] -= x;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        add(i, i, x);
    }
    while(m --)
    {
        int l, r, c;
        cin >> l >> r >> c;
        add(l, r, c);
    }
    for(int i = 1; i <= n; ++ i)
    {
        d[i] += d[i-1];
        cout << d[i] << " ";
    }
    return 0;
}

798.差分矩阵*

#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m, q;

int d[N][N];

void add(int x1, int y1, int x2, int y2, int c)
{
    d[x1][y1] += c;
    d[x1][y2+1] -= c;
    d[x2+1][y1] -= c;
    d[x2+1][y2+1] += c;
}

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            int x;
            cin >> x;
            add(i, j, i, j, x);
        }
    }
    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        add(x1, y1, x2, y2, c);
    }
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            d[i][j] = d[i][j] + d[i-1][j] + d[i][j-1] - d[i-1][j-1];
            cout << d[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

799.最长连续不重复子序列

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;
int num[N];
int cnt[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];   
    }
    int ans = 0;
    for(int i = 1, j = 0; i <= n; ++ i) //j是开区间
    {
        cnt[num[i]] ++;
        while(j < i && cnt[num[i]] > 1)
        {
            j ++;
            cnt[num[j]] --;
        }
        ans = max(ans, i-j);
    }
    cout << ans << endl;
    return 0;
}

800.数组元素的目标和

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m, x;
int num1[N], num2[N];

int main()
{
    cin >> n >> m >> x;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num1[i];
    }
    for(int i = 1; i <= m; ++ i)
    {
        cin >> num2[i];
    }
    for(int i = 1, j = m; i <= n && j >= 0; )
    {
        if(num1[i] + num2[j] > x)
        {
            j --;
        }
        else if(num1[i] + num2[j] < x)
        {
            i ++;
        }
        else
        {
            cout << i-1 << " " << j-1 << endl;
            break;
        }
    }
    return 0;
}

2816.判断子序列

#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
int num1[N], num2[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num1[i];
    }
    for(int i = 1; i <= m; ++ i)
    {
        cin >> num2[i];
    }
    bool ans = false;
    for(int i = 1, j = 1; i <= m && j <= n; ++ i) //注意题意
    {
        if(num2[i] == num1[j])
        {
            j ++;
        }
        if(j > n)
        {
            ans = true;
        }
    }
    if(ans)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

801.二进制中1的个数

#include 
#include 
#include 

using namespace std;

int n;

int lowbit(int x)
{
    return x&(-x);
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        int cnt = 0;
        while(x)
        {
            x -= lowbit(x);
            cnt ++;
        }
        cout << cnt << " ";
    }
    return 0;
}

802.区间和**

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
int addIdx[N];
int addNum[N];
int queryl[N], queryr[N];

int sum[N*3];

int main()
{
    cin >> n >> m;
    //set可以排序并且去重
    set S;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> addIdx[i] >> addNum[i];
        S.insert(addIdx[i]);
    }
    for(int i = 1; i <= m;  ++ i)
    {
        cin >> queryl[i] >> queryr[i];
        S.insert(queryl[i]);
        S.insert(queryr[i]);
    }
    map ha; //map建立索引映射,新坐标从1开始
    int idx = 1;
    for(auto t : S)
    {
        ha[t] = idx;
        idx ++;
    }
    //计算
    for(int i = 1; i <= n; ++ i)
    {
        sum[ha[addIdx[i]]] += addNum[i];
    }
    for(int i = 1; i < 3*N; ++ i)
    {
        sum[i] += sum[i-1];
    }
    for(int i = 1; i <= m; ++ i)
    {
        int l = ha[queryl[i]], r = ha[queryr[i]];
        cout << sum[r] - sum[l-1] << endl;
    }
    return 0;
}

803.区间和并

#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

int n;

vector area;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int l, r;
        cin >> l >> r;
        area.push_back({l, r});
    }
    sort(area.begin(), area.end());
    int L = area[0].x, R = area[0].y;
    int ans = 1;
    for(int i = 1; i < area.size(); ++ i)
    {
        if(area[i].x > R)
        {
            ans ++;
            L = area[i].x;
            R = area[i].y;
        }
        else
        {
            R = max(R, area[i].y);
        }
    }
    cout << ans << endl;
}

第二章数据结构

826.单链表

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int value[N];
int ne[N], idx=1; //从1开始计算节点， 0是表头结点

void addHead(int x)
{
    value[idx] = x;
    ne[idx] = ne[0];
    ne[0] = idx ++;
}

//删除第k个插入的数后面的数
void del(int k)
{
    ne[k] = ne[ne[k]];
}

void add(int k, int x)
{
    value[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}

int main()
{
    int M;
    cin >> M;
    while(M --)
    {
        char op[2];
        scanf("%s", op);
        if(op[0] == 'H')
        {
            int x;
            cin >> x;
            addHead(x);
        }
        else if(op[0] == 'D')
        {
            int k;
            cin >> k;
            del(k);
        }
        else
        {
            int k, x;
            cin >> k >> x;
            add(k, x);
        }
    }
    
    for(int i = 0; ne[i] != 0; i = ne[i])
    {
        cout << value[ne[i]] << " ";
    }
    return 0;
}

872.双链表*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

//idx==1是表头结点，idx==2是表尾节点, L,R==0表示无节点
int L[N], R[N], value[N], idx=3; 

void init()
{
    R[1] = 2;
    L[2] = 1;
    idx = 3;
}

// 最左侧插入一个数
void addHead(int x)
{
    value[idx] = x;
    L[idx] = 1; //指向表头结点
    R[idx] = R[1];
    L[R[1]] = idx;
    R[1] = idx;
    idx ++;
}

// 最右侧插入一个数
void addTail(int x)
{
    value[idx] = x;
    R[idx] = 2;
    L[idx] = L[2];
    R[L[2]] = idx;
    L[2] = idx;
    idx ++;
}

// 删除第k个插入的数,下标从3开始，所以是k-2
void del(int k)
{
    int t = k+2;
    R[L[t]] = R[t];
    L[R[t]] = L[t];
}

// 在第k个插入的数左边插入一个数
void addL(int k, int x)
{
    int t = k+2;
    value[idx] = x;
    R[idx] = t;
    L[idx] = L[t];
    R[L[t]] = idx;
    L[t] = idx;
    idx ++;
}


// 在第k个插入的数右边插入一个数
void addR(int k, int x)
{
    int t = k+2;
    value[idx] = x;
    L[idx] = t;
    R[idx] = R[t];
    L[R[t]] = idx;
    R[t] = idx;
    idx ++;
}

int main()
{
    init();
    int m;
    cin >> m;
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "L")
        {
            int x;
            cin >> x;
            addHead(x);
        }
        else if(op == "R")
        {
            int x;
            cin >> x;
            addTail(x);
        }
        else if(op == "D")
        {
            int k;
            cin >> k;
            del(k);
        }
        else if(op == "IL")
        {
            int k, x;
            cin >> k >> x;
            addL(k, x);
        }
        else if(op == "IR")
        {
            int k, x;
            cin >> k >> x;
            addR(k, x);
        }
    }
    for(int i = R[1]; i != 2; i = R[i])
    {
        cout << value[i] << " ";
    }
    return 0;
}

828.模拟栈

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int S[N], top = -1;

void push(int x)
{
    S[++top] = x;
}

void pop()
{
    if(top >= 0)
    {
        top --;
    }
}

bool empty()
{
    if(top < 0)
    {
        return true;
    }
    return false;
}

int query()
{
    if(top >= 0)
    {
        return S[top];
    }
}


int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "push")
        {
            int x;
            cin >> x;
            push(x);
        }
        else if(op == "pop")
        {
            pop();
        }
        else if(op == "empty")
        {
            if(empty())
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
        else
        {
            cout << query() << endl;
        }
    }
    return 0;
}

3302.表达式求值**

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

map priority = {{'(', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};

int getRes(int numL, int numR, char opera)
{
    if(opera == '+')
    {
        return numL + numR;
    }
    else if(opera == '-')
    {
        return numL - numR;
    }
    else if(opera == '*')
    {
        return numL * numR;
    }
    else if(opera == '/')
    {
        return numL/numR;
    }
}

stack num;
stack op;

int main()
{
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); ++ i)
    {
        if('0' <= s[i] && s[i] <= '9')
        {
            string tp;
            int t;
            for(t = i; t < s.size(); ++ t)
            {
                if('0' <= s[t] && s[t] <= '9')
                {
                    tp += s[t];
                }
                else
                {
                    break;
                }
            }
            i = t-1;
            int x = stoi(tp);
            num.push(x);
        }
        else if(s[i] == ')')
        {
            while(op.top() != '(')
            {
                int xR = num.top();
                num.pop();
                int xL = num.top();
                num.pop();
                num.push(getRes(xL, xR, op.top()));
                op.pop();
            }
            op.pop(); //弹出'('L
        }
        else if(s[i] == '(')
        {
            op.push('(');
        }
        else
        {
            while(op.size() > 0 && priority[s[i]] <= priority[op.top()])
            {
                int xR = num.top();
                num.pop();
                int xL = num.top();
                num.pop();
                num.push(getRes(xL, xR, op.top()));
                op.pop();
            }
            //放进去
            op.push(s[i]);
        }
    }
    while(op.size() > 0)
    {
        int xR = num.top();
        num.pop();
        int xL = num.top();
        num.pop();
        num.push(getRes(xL, xR, op.top()));
        op.pop();
    }
    cout << num.top() << endl;
    return 0;
}

829.模拟队列

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int Q[N], hh=0, tt = -1;

void push(int x)
{
    Q[++tt] = x;
}

void pop()
{
    if(hh <= tt)
    {
        hh ++;
    }
}

bool empty()
{
    return hh > tt;
}

int query()
{
    if(hh <= tt)
    {
        return Q[hh];
    }
}

int main()
{
    int m;
    cin >> m;
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "push")
        {
            int x;
            cin >> x;
            push(x);
        }
        else if(op == "pop")
        {
            pop();
        }
        else if(op == "empty")
        {
            if(empty())
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
        else
        {
            cout << query() << endl;
        }
    }
    return 0;
}

830.单调栈

#include 
#include 
#include 
#include 

using namespace std;

int n;

stack S;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        while(S.size() && S.top() >= x)
        {
            S.pop();
        }
        if(S.size())
        {
            cout << S.top() << " ";
        }
        else
        {
            cout << -1 << " ";
        }
        S.push(x);
    }
    return 0;
}

154.滑动窗口**

#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

const int N = 1e6+5;

int n, k;

int num[N];

//求窗口的最小值，递增 
deque> minQ; 
//求窗口的最大值，递减 
deque> maxQ;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    //求min
    for(int i = 1; i <= n; ++ i)
    {
        while(minQ.size() && minQ.back().x >= num[i])
        {
            minQ.pop_back();
        }
        minQ.push_back({num[i], i});
        if(minQ.back().y - minQ.front().y + 1 > k)
        {
            minQ.pop_front();
        }
        if(i >= k)
        {
            cout << minQ.front().x << " ";
        }
    }
    cout << endl;
    //求max
    for(int i = 1; i <= n; ++ i)
    {
        while(maxQ.size() > 0 && maxQ.back().x <= num[i])
        {
            maxQ.pop_back();
        }
        maxQ.push_back({num[i], i});
        if(maxQ.back().y - maxQ.front().y + 1 > k)
        {
            maxQ.pop_front();
        }
        if(i >= k)
        {
            cout << maxQ.front().x << " ";
        }
    }
    return 0;
}

831.KMP字符串**

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

string S, P; //模板串P

int n, m; //n: 模板串长度

int ne[N];

int main()
{
    cin >> n >> P;
    cin >> m >> S;
    P = " " + P; //从1开始
    S = " " + S; //从1开始
    //求ne[]
    //ne[1] = 0;
    for(int i = 2, j = 0; i <= n; ++ i) //求ne[i]
    {
        //不相等并且可以退
        while(j && P[i] != P[j+1])  j = ne[j];
        //相等：P[i] == P[j+1]
        if(P[i] == P[j+1])
        {
            ne[i] = j+1;
            j ++;
        }
        //else: ne[i] = 0
    }
    
    //S[i]与P[j+1]进行匹配
    for(int i = 1, j = 0; i <= m; ++ i)
    {
        //不相等并且可以退
        while(j && S[i] != P[j+1])   j = ne[j];
        //相等：S[i] == P[j+1]
        if(S[i] == P[j+1])
        {
            j ++;
            if(j == n)
            {
                cout << i-n+1 -1 << " "; //下标从1开始变换到从0开始
                j = ne[j];
            }
        }
    }
    return 0;
}

835.Trie字符串统计*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;

int son[N][26], idx = 1; //idx==0是表头结点或者指向空节点, 这里N是节点
int cnt[N];

void insert(string s)
{
    int p = 0;
    for(int i = 0; i < s.size(); ++ i)
    {
        int c = s[i]-'0';
        if(!son[p][c])
        {
            son[p][c] = idx ++;
        }
        p = son[p][c];
    }
    cnt[p] ++;
}

int query(string s)
{
    int p = 0;
    for(int i = 0; i < s.size(); ++ i)
    {
        int c = s[i]-'0';
        if(!son[p][c])
        {
            return 0;
        }
        p = son[p][c];
    }
    return cnt[p];
}

int main()
{
    cin >> n;
    while(n --)
    {
        string op, x;
        cin >> op >> x;
        if(op == "I")
        {
            insert(x);
        }
        else
        {
            cout << query(x) << endl;
        }
    }
    return 0;
}

143.最大异或对*

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5, M = N*32;

int n;

int son[M][2], idx = 1; //N是节点数, idx是待创建的节点索引, idx==0是根节点不需要创建
int cnt[M];

int num[N];

//求异或需要从高位往低位插入
//每个数有32位
void insert(int x)
{
    int p = 0;
    for(int i = 31; i >= 0; -- i)
    {
        int bit = (x>>i)&1;
        if(!son[p][bit])
        {
            son[p][bit] = idx ++;
        }
        p = son[p][bit];
    }
    //需要尾标记,直接记录值
    //注意这道题每条记录长度一样，所以可以记录0，否则值域需要变换
    cnt[p] = x;
}

//寻找与x异或值最大的元素
int find(int x)
{
    int p = 0;
    for(int i = 31; i >= 0; -- i)
    {
        int bit = (x>>i)&1;
        if(son[p][!bit])
        {
            p = son[p][!bit];
        }
        else
        {
            p = son[p][bit];
        }
    }
    return cnt[p];
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
        insert(num[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        ans = max(ans, find(num[i])^num[i]);
    }
    cout << ans << endl;
    return 0;
}

836.合并集合

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
int p[N]; //父节点

int init(int n)
{
    for(int i = 1; i <= n; ++ i)
    {
        p[i] = i;
    }
}

//寻找x的祖先节点
int find(int x)
{
    if(p[x] != x)
    {
        p[x] = find(p[x]);
    }
    return p[x];
}

int main()
{
    cin >> n >> m;
    init(n);
    while(m --)
    {
        string op;
        int a, b;
        cin >> op >> a >> b;
        int pa = find(a), pb = find(b);
        if(op == "M")
        {
            if(pa != pb)
            {
                p[pa] = pb; //pa认pb为父
            }
        }
        else if(op == "Q")
        {
            if(pa == pb)
            {
                cout << "Yes" << endl;    
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

837.连通块中点的数量

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;
//cnt[i]: 当i为祖先节点时，当前集合的元素个数
int p[N], cnt[N]; 

void init(int n)
{
    for(int i = 1; i <= n; ++ i)
    {
        p[i] = i;
        cnt[i] = 1;
    }
}

int find(int x)
{
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    init(n);
    while(m --)
    {
        string op;
        cin >> op;
        if(op == "C")
        {
            int a, b;
            cin >> a >> b;
            int pa = find(a), pb = find(b);
            if(pa != pb)
            {
                p[pa] = pb; //认pb为父
                cnt[pb] += cnt[pa];
            }
            
        }
        else if(op == "Q1")
        {
            int a, b;
            cin >> a >> b;
            int pa = find(a), pb = find(b);
            if(pa == pb)
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
        else if(op == "Q2")
        {
            int a;
            cin >> a;
            int pa = find(a);
            cout << cnt[pa] << endl;
        }
    }
    return 0;
}

240.食物链**

#include 
#include 
#include 

using namespace std;

const int N = 5e4+5;

int n, m;

//规定，在mod3内，0->1->2->0
//d[i]表示点i到父节点的距离，路径压缩之后表示到根节点的距离
int d[N], p[N];

void init(int n)
{
    for(int i = 1; i <= n; ++ i)
    {
        p[i] = i;
    }
}

//寻找祖先节点，压缩路径，更新d[x]为到祖先的距离
int find(int x)
{
    if(p[x] != x)
    {
        int t = find(p[x]);
        d[x] = d[x] + d[p[x]];
        d[x] %= 3; //优化
        p[x] = t;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;
    init(n);
    int ans = 0;
    while(m --)
    {
        int k, x, y;
        cin >> k >> x >> y;
        if(x > n || y > n)
        {
            ans ++;
        }
        else if(k == 2 && x == y)
        {
            ans ++;
        }
        else
        {
            int pa = find(x), pb = find(y);
            if(pa != pb) //不在同一个食物链，加入!
            {
                if(k == 1)
                {
                    p[pa] = pb; //pa认pb作父
                    d[pa] = (d[y]-d[x]+3)%3;
                }
                else if(k == 2)
                {
                    p[pa] = pb; //pa认pb作父
                    d[pa] = (d[y]-d[x]-1+3)%3;
                }
            }
            else //在一个食物链，判断真假
            {
                //这里d[x]、d[y]由于前面进行了find，所以是到根节点的距离
                if(k == 1 && d[x]%3 != d[y]%3) 
                {
                    ans ++;
                }
                else if(k == 2 && (d[x]%3+1)%3 != d[y]%3)
                {
                    ans ++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

838.堆排序

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n, m;

int num[N];

//小根堆
int tree[N], idx; //idx从1开始，也表示元素数量

void up(int i)
{
    //有根节点并且当前节点值比根节点小
    while(i/2 > 0 && tree[i] = 1)
    {
        swap(tree[1], tree[idx]);
        idx --;
        down(1);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        insert(x);
    }
    while(m --)
    {
        cout << tree[1] << " ";
        pop();
    }
    return 0;
}

839.模拟堆**

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;

int tree[N], idx; //idx从1开始，并且表示尾元素
int cntIns = 0;
map idxToOrd; //堆中下标映射到插入序号
map ordToIdx; //插入序号对应堆中下标


//交换下标为k1,k2的两个元素
void swapHeap(int k1, int k2)
{
    swap(ordToIdx[idxToOrd[k1]], ordToIdx[idxToOrd[k2]]);
    swap(idxToOrd[k1], idxToOrd[k2]);
    swap(tree[k1], tree[k2]);
}

void up(int i)
{
    while(i/2 > 0 && tree[i] < tree[i/2])
    {
        swapHeap(i, i/2);
        i = i/2;
    }
}

void down(int i)
{
    int t = i; //寻找最小的节点
    if(i*2 <= idx && tree[i*2] < tree[t])
    {
        t = i*2;
    }
    if(i*2+1 <= idx && tree[i*2+1] < tree[t])
    {
        t = i*2+1;
    }
    if(t != i)
    {
        swapHeap(t, i);
        down(t);
    }
}

void insert(int x)
{
    tree[++ idx] = x;
    ordToIdx[++cntIns] = idx;
    idxToOrd[idx] = cntIns;
    up(idx);
}

int top()
{
    return tree[1];
}

void pop()
{
    if(idx > 0)
    {
        swapHeap(1, idx);
        idx --;
        down(1);
    }
}

void del(int k)
{
    int pos = ordToIdx[k];
    swapHeap(pos, idx);
    idx --;
    up(pos); //只会执行up、down其中一个
    down(pos);
}

void update(int k, int x)
{
    int pos = ordToIdx[k];
    int v = tree[pos];
    tree[pos] = x;
    up(pos); //只会执行up、down其中一个
    down(pos);
}

int main()
{

    cin >> n;
    while(n --)
    {
        string op;
        cin >> op;
        if(op == "I")
        {
            int x;
            cin >> x;
            insert(x);
        }
        else if(op == "PM")
        {
            cout << top() << endl;
        }
        else if(op == "DM")
        {
            pop();
        }
        else if(op == "D")
        {
            int k;
            cin >> k;
            del(k);
        }
        else if(op == "C")
        {
            int k, x;
            cin >> k >> x;
            update(k, x);
        }
    }
    return 0;
}

840.模拟散列表

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5, null = 0x3f3f3f3f;

int n;

int h[N];

int find(int x)
{
    int t = (x%N+N)%N;
    while(h[t] != null && h[t] != x)
    {
        t ++;
        if(t == N)
        {
            t = 0;
        }
    }
    return t;
}

int main()
{
    memset(h, 0x3f, sizeof(h));
    cin >> n;
    while(n --)
    {
        string op;
        int x;
        cin >> op >> x;
        if(op == "I")
        {
            int pos = find(x);
            h[pos] = x;
        }
        else if(op == "Q")
        {
            int pos = find(x);
            if(h[pos] == x)
            {
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }
}

841.字符串哈希**

#include 
#include 
#include 
#include 

using namespace std;

typedef unsigned long long ULL;

const int N = 1e5+5, P = 131; //mod=2^64, 数据溢出会自动取模

int n, m;

string s;

ULL h[N], p[N]; //h[i]:字符串前缀哈希，p[i]:P的i次方

//未进行冲突判断，我们完全看运气, p==131或13331，mod=2^64效果最好
ULL get(int l, int r)
{
    return h[r] - h[l-1]*p[r-l+1]; //数据溢出会自动取模
}

int main()
{
    cin >> n >> m;
    cin >> s;
    s = " " + s;
    p[0] = 1;
    for(int i = 1; i <= n; ++ i)
    {
        p[i] = p[i-1]*P; //数据溢出会自动取模
        h[i] = h[i-1]*P+s[i]; //数据溢出会自动取模
    }
    while(m --)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(get(l1, r1) == get(l2, r2))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

第三章搜索与图论

842.排列数字

#include 
#include 

using namespace std;

const int N = 10;

int n;

int ans[N];

bool st[N]; //st[i]表示数i是否被使用

//已经选择了t个数
void dfs(int t)
{
    if(t >= n)
    {
        for(int i = 1; i <= n; ++ i)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
    else
    {
        for(int i = 1; i <= n; ++ i)
        {
            if(!st[i])
            {
                st[i] = true;
                ans[t+1] = i;
                dfs(t+1);
                ans[t+1] = 0;
                st[i] = false;
            }
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0;
}

#include 
#include 
#include 

using namespace std;

const int N = 12;

int n;

bool st[N]; //st[i]表示第i列有没有放

//dg[x]斜边x = i+j   rdg[x]反斜边x=i+(n+1-j), 从2开始
bool dg[N*2], rdg[N*2]; 

int ans[N], cnt;

//当前在第u行放棋子, u从1开始, 已经放了t个棋子
void dfs(int u, int t)
{
    if(u > n)
    {
        if(t == n)
        {
            if(cnt > 0)
            {
                cout << endl;
            }
            cnt++;
            for(int i = 1; i <= n; ++ i)
            {
                for(int j = 1; j <= n; ++ j)
                {
                    if(ans[i] == j)
                    {
                        cout << "Q";
                    }
                    else
                    {
                        cout << ".";
                    }
                }
                cout << endl;
            }
        }
        return;
    }
    for(int j = 1; j <= n; ++ j)
    {
        if(!st[j] && !dg[u+j] && !rdg[u+(n+1-j)])
        {
            st[j] = true;
            dg[u+j] = true;
            rdg[u+(n+1-j)] = true;
            ans[u] = j;
            dfs(u+1, t+1);
            ans[u] = 0;
            st[j] = false;
            dg[u+j] = false;
            rdg[u+(n+1-j)] = false;
        }
    }
}

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

844.走迷宫

#include 
#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

const int N = 105;

typedef pair PII;

int n, m;

int g[N][N]; //g[i][j]==1表示不可通过
int d[N][N]; //d[i][j]表示移动到(i, j)的需要移动的次数, -1表示未到达

void bfs(int x0, int y0)
{
    memset(d, -1, sizeof d);
    int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
    queue Q;
    Q.push({x0, y0});
    d[x0][y0] = 0; //访问过了
    while(Q.size())
    {
        PII t = Q.front();
        Q.pop();
        for(int i = 0; i < 4; ++ i)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m)    continue;
            if(g[a][b] == 1 || d[a][b] != -1) //不可达或者已到达
            {
                continue;
            }
            d[a][b] = d[t.x][t.y] + 1;
            Q.push({a, b});
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            cin >> g[i][j];
        }
    }
    bfs(1, 1);
    cout << d[n][m] << endl;
    return 0;
}

845.八数码*

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

//存状态对应的步数. 这题用map会超时，要用unordered_map
unordered_map d; 

string endState = "12345678x";

int bfs(string s0)
{
    queue Q;
    Q.push(s0);
    d[s0] = 0;
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    int step = 0;
    while(Q.size())
    {
        string t = Q.front();
        Q.pop();
        if(t == endState)
        {
            return d[t];
        }
        int idx = t.find('x');
        int x = idx/3, y = idx%3;
        for(int  i = 0; i < 4; ++ i)
        {
            int a = x+dx[i], b = y+dy[i];
            if(a < 0 || a >= 3 || b < 0 || b >= 3)
            {
                continue;
            }
            int newIdx = a*3+b;
            string tp = t;
            swap(tp[idx], tp[newIdx]);
            if(d.count(tp) > 0) //计算过了
            {
                continue;
            }
            d[tp] = d[t] + 1;
            Q.push(tp);
        }
    }
    return -1;
}

int main()
{
    string start = "";
    for(int i = 1; i <= 9; ++ i)
    {
        string tp;
        cin >> tp;
        start += tp;
    }
    cout << bfs(start) << endl;
    return 0;
}

846.树的重心*

#include 
#include 
#include 
#include 

using namespace std;

//无向边
const int N = 1e5+5, M = N*2, INF = 0x3f3f3f3f;

int n;

int h[N], e[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

bool st[N]; //st[i]表示dfs过程中i节点是否被访问过

int ans = INF; //求最小值

//返回以root为根的子树的的节点数量
//在遍历过程中，求删除该点的最大连通块点数，
//并更新全局结果ans, 求出最小的ans
int dfs(int root)
{
    st[root] = true;
    int totalCnt = 1, maxCnt = 0;
    for(int i = h[root]; ~i; i=ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        int sizej = dfs(j);
        maxCnt = max(maxCnt, sizej);
        totalCnt += sizej;
    }
    maxCnt = max(maxCnt, n-totalCnt);
    ans = min(ans, maxCnt);
    return totalCnt;
}

int main()
{
    init();
    cin >> n;
    for(int i = 1; i <= n-1; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

847.图中点的层次

#include 
#include 
#include 
#include 
#include 

using namespace std;

//有向图
const int N = 1e5+5, M = N;

int n, m;

int h[N], e[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int d[N]; //从1号点到i号点的距离, ==-1表示没被访问过

int bfs(int s)
{
    memset(d, -1, sizeof d);
    queue Q;
    d[s] = 0;
    Q.push(s);
    while(Q.size())
    {
        int t = Q.front();
        Q.pop();
        for(int i = h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            if(d[j] != -1)   continue; //访问过
            d[j] = d[t] + 1;
            Q.push(j);
        }
    }
    return d[n];
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs(1) << endl;
    return 0;
}

848.有向图的拓扑序列

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

//有向图
const int N = 1e5+5, M = N;

int n, m;

int h[N], e[M], ne[M] ,idx;
int din[N]; //入度

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void top()
{
    vector ans;
    queue Q;
    for(int i = 1; i <= n; ++ i)
    {
        if(din[i] == 0)
        {
            Q.push(i);
        }
    }
    //出栈顺序即为一个top序
    while(Q.size())
    {
        int t = Q.front();
        Q.pop();
        ans.push_back(t);
        for(int i = h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            din[j] --;
            if(din[j] == 0)
            {
                Q.push(j);
            }
        }
    }
    if(ans.size() < n)
    {
        cout << -1 << endl;
    }
    else
    {
        for(int i = 0; i < n; ++ i)
        {
            cout << ans[i] << " ";
        }
    }
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int a, b;
        cin >> a >> b; 
        //top可以去掉重边，top遇到自环直接失败
        add(a, b);
        din[b] ++;
    }
    top();
    return 0;
}

849.Dijkstra求最短路I

#include 
#include 
#include 
#include 

using namespace std;

const int N = 505, M = 1e5+5, INF = 0x3f3f3f3f;

int n, m;

int h[N], e[M], ne[M], w[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int d[N]; //d[i]表示第1个节点到第i个节点的距离
bool st[N]; //属于左边点的集合

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int T = 1; T <= n; ++ T)
    {
        //寻找不在st中的最小d的点
        int t = -1;
        for(int i = 1; i <= n; ++ i)
        {
            if(!st[i] && (t == -1 || d[i] < d[t]))
            {
                t = i;
            }
        }
        st[t] = true;
        //遍历所有t的邻边
        for(int i = h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
            }
        }
    }
    if(d[n] == INF)
    {
        return -1;
    }
    return d[n];
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int x, y, z;
        cin >> x >> y >> z; //dijkstra可以自己解决重边和自环
        add(x, y, z);
    }
    
    cout << dijkstra() << endl;
}

850.Dijkstra求最短路II

#include 
#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

//有向图
const int N = 1.5e5+5, M = N, INF = 0x3f3f3f3f;

typedef pair PII;

int n, m;

int h[N], e[M], w[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int d[N]; //从节点1到节点i的最短距离
bool st[N]; //st[i]表示点i是否加入左边集合

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    priority_queue, greater> heap;
    d[1] = 0;
    heap.push({d[1], 1});
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        if(st[t.y]) continue;
        st[t.y] = true;
        for(int i = h[t.y]; ~i; i=ne[i])
        {
            int j = e[i];
            if(d[j] > d[t.y] + w[i])
            {
                d[j] = d[t.y] + w[i];
                heap.push({d[j], j});
            }
        }
    }
    if(d[n] == INF)
    {
        return -1;
    }
    return d[n];
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z); //dijkstra可以解决重边和自环
    }
    cout << dijkstra() << endl;
    return 0;
}

853.有边数限制的最短路*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 505, M = 1e4+5, INF = 0x3f3f3f3f;

int n, m, k;

struct Edge
{
    int x, y, z;
}edge[M];

int d[N], backup[N];

int bf()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 1; i <= k; ++ i)
    {
        memcpy(backup, d, sizeof d);
        for(int j = 1; j <= m; ++ j)
        {
            int a = edge[j].x, b = edge[j].y, w = edge[j].z;
            d[b] = min(d[b], backup[a] + w);
        }
    }
    return d[n];
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1; i <= m; ++ i)
    {
        cin >> edge[i].x >> edge[i].y >> edge[i].z;
    }
    int ans = bf();
    if(ans > INF/2)
    {
        cout << "impossible" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}

851.spfa求最短路

#include 
#include 
#include 
#include 
#include 

using namespace std;

//有向边
const int N = 1e5+5, M = N, INF = 0x3f3f3f3f;

int n, m;

int h[N], e[M], ne[M], w[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int d[N];//表示点1到点i的最短距离
//st[i]表示点i是否在队列中，避免队列存在多个重复元素
bool st[N]; 
int spfa()
{
    queue Q;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    Q.push(1);
    st[1] = true;
    while(Q.size())
    {
        int t = Q.front();
        Q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if(!st[j])
                {
                    Q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return d[n];
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    int ans = spfa();
    if(ans == INF)
    {
        cout << "impossible" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}

852.spfa判断负环*

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 2005, M = 1e4+5;

int n, m;

int h[N], e[M], w[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int d[N]; //从超级源点到点i的最短距离
int cnt[N]; //对应的最短距离经过的边数
bool st[N]; //点i在不在队列中
int spfa()
{
    memset(d, 0x3f, sizeof d);
    queue Q;
    d[0] = 0;
    cnt[0] = 0;
    Q.push(0);
    st[0] = true;
    while(Q.size())
    {
        int t = Q.front();
        Q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i=ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] > n) //多了一个超级源点
                {
                    return true; //存在负环
                }
                if(!st[j])
                {
                    Q.push(j);
                }
            }
        }
    }
    return false;
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    for(int i = 1; i <= n; ++ i)
    {
        //建立超级源点，避免不连通
        //注意多建立一个点之后，最大边数变为了n
        add(0, i, 0);
    }
    if(spfa())
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

854.Floyd求最短路

#include 
#include 
#include 
#include 

using namespace std;

//有向边
const int N = 205, M = 2e4+5, INF = 0x3f3f3f3f;

int n, m, q;

int dist[N][N]; //邻接矩阵

void floyd()
{
    for(int k = 1; k <= n; ++ k)
    {
        for(int i = 1; i <= n; ++ i)
        {
            for(int j = 1; j <= n; ++ j)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main()
{
    cin >> n >> m >> q;
    memset(dist, 0x3f, sizeof dist);
    for(int i = 1; i <= n; ++ i)
    {
        dist[i][i] = 0; //防止自环
    }
    for(int i = 1; i <= m; ++ i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c); //防止自环、重边
    }
    floyd();
    while(q --)
    {
        int a, b;
        cin >> a >> b;
        if(dist[a][b] > INF/2) //负权边+不连通
        {
            cout << "impossible" << endl;
        }
        else
        {
            cout << dist[a][b] << endl;
        }
    }
    return 0;
}

858.Prim求最小生成树

#include 
#include 
#include 
#include 

using namespace std;

//无向边
const int N = 505, M = 2e5+5, INF = 0x3f3f3f3f;

int n, m;

int dist[N][N]; //稠密图，邻接矩阵

int d[N]; //d[i]表示点i到集合的距离
bool st[N]; //在不在集合中

int prim()
{
    int res = 0;
    memset(d, 0x3f, sizeof d);
     //每轮找一个距离集合最近的点
    for(int T = 1; T <= n; ++ T)
    {
        int t = -1;
        for(int i = 1; i <= n; ++ i)
        {
            if(!st[i] && (t == -1 || d[i] < d[t]))
            {
                 t = i;
            }
        }
        if(t != 1 && d[t] == INF)
        {
            return INF; //不连通
        }
        st[t] = true; //注意顺序，避免自身被负自环更新
        if(t != 1)  res += d[t]; //从第二个点开始
        //更新其他集合外的点
        for(int i = 1; i <= n; ++ i)
        {
            if(!st[i])
            {
                d[i] = min(d[i], dist[t][i]); 
            }
        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);
    for(int i = 1; i <= m; ++ i)
    {
        int a, b, c;
        cin >> a >> b >> c; //无向边
        dist[a][b] = min(dist[a][b], c); //去掉重边
        dist[b][a] = min(dist[b][a], c); //去掉重边
    }
    int ans = prim();
    if(ans == INF)
    {
        cout << "impossible" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}

859.Kruskal算法求最小生成树

#include 
#include 
#include 
#include 

using namespace std;

//无向图
const int N = 1e5+5, M = 4e5+5, INF = 0x3f3f3f3f;

int n, m;

int p[N]; //并查集

int find(int x)
{
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}

struct Edge
{
    int a, b, w;
    bool operator<(const Edge& e)const{
        return w < e.w;
    }
}edge[M];

void init(int n)
{
    for(int i = 1; i <= n; ++ i)
    {
        p[i] = i;
    }
}

int kruskal()
{
    int ans = 0;
    int cnt = 0;
    sort(edge, edge+m);
    for(int i = 0; i < m; ++ i)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int fa = find(a), fb = find(b);
        if(fa != fb)
        {
            ans += w;
            cnt ++;
            p[fa] = fb;
        }
    }
    if(cnt != n-1) //不连通
    {
        return INF;
    }
    return ans;
}

int main()
{
    cin >> n >> m;
    init(n);
    for(int i = 0; i < m; ++ i)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    }
    int ans = kruskal();
    if(ans == INF)
    {
        cout << "impossible" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    
    return 0;
}

860.染色法判定二分图

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5, M = 2*N;

int n, m;

int h[N], e[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int color[N]; //0表示没染色，1、2分别表示两种颜色

//从u点开始染色，染成c颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for(int i = h[u]; ~i; i=ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j, 3-c))
            {
                return false;
            }
        }
        else if(color[j] == c) //这个也可以判掉自环 
        {
            return false;
        }//注：前后两个if判断情况可以去掉重边
    }
    return true;
}

int main()
{
    cin >> n >> m;
    init();
    for(int i = 1; i <= m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    bool ans = true;
    for(int i = 1; i <= n; ++ i) //避免不连通
    {
        if(!color[i])
        {
            if(!dfs(i, 1))
            {
                ans = false;
                break;
            }
        }
    }
    if(ans)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

861.二分图的最大匹配*

#include 
#include 
#include 
#include 

using namespace std;

//有向边，从男生指向女生
const int N = 505, M = 1e5+5;

int n1, n2, m;

int h[N], e[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);    
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int match[N];
bool st[N];

bool find(int x)
{
    for(int i = h[x]; ~i; i=ne[i])//遍历所有喜欢的女孩子
    {
        int j = e[i];
        if(!st[j]) //没有考虑过
        {
            st[j] = true;
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }

    }
    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    init();
    for(int i = 1; i <= m; ++ i)
    {
        int a, b;
        cin >> a >> b;
        //因为ab属于不同的集合，并且方向单向，所以两个集合序号可以相同
        add(a, b); 
    }
    int ans = 0;
    for(int i = 1; i <= n1; ++ i)
    {
        memset(st, false, sizeof st); //所有女孩子都可以考虑
        if(find(i)) //找到女朋友
        {
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

第四章数学知识

866.试除法判断质数

#include 
#include 
#include 

using namespace std;

int n;

bool isPrime(int x)
{
    if(x < 2)   return false;
    for(int i = 2; i <= x/i; ++ i)
    {
        if(x%i==0)  return false;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        if(isPrime(x))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

867.分解质因数

#include 
#include 
#include 

using namespace std;

int n;

void divide(int x)
{
    for(int i = 2; i <= x/i; ++ i)
    {
        if(x%i==0)
        {
            int cnt = 0;
            while(x%i==0)
            {
                x /= i;
                cnt ++;
            }
            cout << i << " " << cnt << endl;
        }
    }
    if(x > 1)
    {
        cout << x << " " << 1 << endl;
    }
    cout << endl;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}

870.筛质数*

#include 
#include 
#include 

using namespace std;

const int N = 1e6+5;

int n;

int prime[N], cnt;
bool st[N]; //是否被筛掉

void getPrime(int n)
{
    for(int i = 2; i <= n; ++ i)
    {
        if(!st[i]) //质数
        {
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && prime[j] <= n/i; ++ j)
        {
            st[i*prime[j]] = true; //pj是pj*i的最小质因子
            if(i%prime[j] == 0) break; //pj是i的最小质因子
        }
    }
}

int main()
{
    cin >> n;
    getPrime(n);
    cout << cnt << endl;
    return 0;
}

869.试除法求约数

#include 
#include 
#include 
#include 

using namespace std;

int n;

vector getDivisors(int n)
{
    vector ans;
    for(int i = 1; i <= n/i; ++ i)
    {
        if(n%i==0)
        {
            ans.push_back(i);
            if(i != n/i)    ans.push_back(n/i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a;
        cin >> a;
        vector ans = getDivisors(a);
        for(int i = 0; i < ans.size(); ++ i)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

870.约数个数

#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

const int MOD = 1e9+7;

typedef long long LL;

int n;
unordered_map ha;

void divide(int n)
{
    for(int i = 2; i <= n/i; ++ i)
    {
        while(n%i==0)
        {
            ha[i] ++;
            n /= i;
        }
    }
    if(n > 1)   ha[n] ++;
}

int main()
{
    cin >> n;
    int ans = 1;
    for(int i = 1; i <= n; ++ i)
    {
        int a;
        cin >> a;
        divide(a);
    }
    for(auto prime: ha)
    {
        ans = (LL)ans*(prime.y+1)%MOD;
    }
    cout << ans << endl;
    return 0;
}

871.约数之和

#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

int n;

unordered_map ha;

void divide(int n)
{
    for(int i = 2; i <= n/i; ++ i)
    {
        while(n%i==0)
        {
            ha[i] ++;
            n /= i;
        }
    }
    if(n > 1)   ha[n] ++;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a;
        cin >> a;
        divide(a);
    }
    int ans = 1;
    for(auto prime: ha)
    {
        int p = prime.x, a = prime.y;
        int t = 1;
        while(a --)
        {
            t = ((LL)t*p+1)%MOD;
        }
        ans = (LL)ans*t%MOD;
    }
    cout << ans << endl;
    return 0;
}

872.最大公约数

#include 
#include 
#include 

using namespace std;

int n;

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }
    return 0;
}

873.欧拉函数

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1700;

int n;

int prime[N], cnt;

void divide(int n)
{
    cnt = 0;
    memset(prime, 0, sizeof prime);
    for(int i = 2; i <= n/i; ++ i)
    {
        if(n%i==0)
        {
            prime[cnt ++] = i;
            while(n%i==0)
            {
                n /= i;
            }
        }
    }
    if(n > 1)   prime[cnt++] = n;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a;
        cin >> a;
        divide(a);
        int ans = a;
        for(int i = 0; i < cnt; ++ i)
        {
            ans = ans/prime[i]*(prime[i]-1);
        }
        cout << ans << endl;
    }
    return 0;
}

874.筛法求欧拉函数**

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e6+5;

int n;

int prime[N], cnt;
int euler[N];
bool st[N];

void getEulers(int n)
{
    euler[1] = 1;
    for(int i = 2; i <= n; ++ i)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
            euler[i] = i-1;
        }
        for(int j = 0; j < cnt && prime[j] <= n/i; ++ j)
        {
            st[prime[j]*i] = true; //筛去
            if(i % prime[j] == 0)
            {
                euler[prime[j]*i] = euler[i]*prime[j];
                break;
            }
            else
            {
                euler[prime[j]*i] = euler[i]*(prime[j] - 1);
            }
        }
    }
}

int main()
{
    cin >> n;
    getEulers(n);
    LL ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        ans += euler[i];
    }
    cout << ans << endl;
    return 0;
}

875.快速幂

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n;

int qmi(int a, int b, int p)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = ((LL)ans*a)%p;
        b >>= 1;
        a = ((LL)a*a)%p;
    }
    return ans;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) << endl;
    }
    return 0;
}

876.快速幂求逆元*

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n;

int qmi(int a, int b, int p)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = ((LL)ans*a)%p;
        b >>= 1;
        a = ((LL)a*a)%p;
    }
    return ans;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, p;
        cin >> a >> p;
        //p必须是质数， 并且a不是p的倍数
        if(a%p==0)  cout << "impossible" << endl;
        else    cout << qmi(a, p-2, p) << endl;
    }
    return 0;
}

877.扩展欧几里得算法*

#include 
#include 
#include 

using namespace std;

int n;

int  exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y = y - a/b*x;
}


int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, b, x, y;
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << " " << y << endl;
    }
}

878.线性同余方程**

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n;

int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y = y - a/b*x;
    return d;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int a, b, m, x, y;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if(b%d==0)
        {
            cout << (LL)b/d*x%m << endl; //b随意给，所以注意这里会爆
        }
        else
        {
            cout << "impossible" << endl;
        }
    }
    return 0;
}

204.表达整数的奇怪方式***

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int n;

int exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        LL d = exgcd(b, a%b, y, x);
        y -= (a/b*x);
        return d;
    }
}

int main()
{
    cin >> n;
    LL lasta, lastm;
    cin >> lasta >> lastm;
    bool ans = true;
    for(LL i = 2; i <= n; ++ i)
    {
        LL a, m;
        cin >> a >> m;
        LL k1, k2;
        LL d = exgcd(lasta, -a, k1, k2);
        if((m-lastm)%d!=0)
        {
            ans = false;
            break;
        }
        k1 = k1*(m-lastm)/d;
        k2 = k2*(m-lastm)/d;
        LL t = a/d;
        k1 = (k1%t+t)%t;
        lastm = k1*lasta+lastm;
        lasta = abs(lasta*a/d);
    }
    if(ans)
    {
        cout << (lastm%lasta+lasta)%lasta << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

883.高斯消元解线性方程组**

#include 
#include 
#include 
#include 

using namespace std;

const int N = 105;
const double eps = 1e-4;

int n;

double a[N][N];

int gauss()
{
    int c = 1, r = 1; //r是当前需要工作的行数
    for(; c <= n; ++ c)
    {
        //找到c列绝对值最大的元素
        int idx = -1;
        for(int i = r; i <= n; ++ i)
        {
            if(idx == -1 || fabs(a[i][c]) > fabs(a[idx][c]))
            {
                idx = i;
            }
        }
        if(fabs(a[idx][c]) < eps) //最大为0
        {
            // cout << "!!!" << endl;
            continue;
        }
        if(r != idx) //idx行和r行交换
        {
            for(int j = 1; j <= n+1; ++ j)
            {
                swap(a[r][j], a[idx][j]);
            }
        }
        //将r行c列元素变成1
        for(int j = n+1; j >= c; -- j)
        {
            a[r][j] /= a[r][c];
        }
        for(int i = r+1; i <= n; ++ i) //i行开头变0
        {
            if(fabs(a[i][c]) < eps)  continue;
            for(int j = n+1; 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+1]) > eps)    return 1; //无解
        }
        return 2; //无穷多组解
    }
    for(int i = n; i > 0; -- i)
    {
        for(int j = n; j >= i+1; -- j)
        {
            a[i][n+1] -= a[i][j]*a[j][n+1];
        }
    }
    return 0;
}


int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= n+1; ++ j)
        {
            cin >> a[i][j];
        }
    }
    int ans = gauss();
    if(ans == 1)
    {
        cout << "No solution" << endl;
    }
    else if(ans == 2)
    {
        cout << "Infinite group solutions" << endl;
    }
    else
    {
        for(int i = 1; i <= n; ++ i)
        {
            printf("%.2f\n", a[i][n+1]);
        }
    }
    return 0;
}

884.高斯消元解异或线性方程组*

#include 
#include 
#include 

using namespace std;

const int N = 105;

int n;

int a[N][N];

int guass()
{
    int c = 1, r = 1;
    for(; c <= n; ++ c)
    {
        //找到开头最大行
        int idx = -1;
        for(int i = r; i <= n; ++ i)
        {
            if(idx == -1 || a[i][c] > a[idx][c])
            {
                idx = i;
            }
        }
        if(a[idx][c] == 0)
        {
            continue;
        }
        //换到第r行
        if(idx != r)
        {
            for(int j = c; j <= n+1; ++ j)
            {
                swap(a[idx][j], a[r][j]);
            }
        }
        for(int i = r+1; i <= n; ++ i)
        {
            if(a[i][c] == 1) //注意
            {
                for(int j = c; j <= n+1; ++ j)
                {
                    a[i][j] ^= a[r][j];
                }
            }

        }
        r ++;
    }
    if(r <= n)
    {
        for(int i = r; i <= n; ++ i)
        {
            if(a[i][n+1] != 0)  return 1; //无解
        }
        return 2; //无穷多组解
    }
    //反向求解
    for(int i = n; i > 0; -- i)
    {
        for(int j = i+1; j <= n; ++ j)
        {
            if(a[i][j] != 0)
            {
                a[i][n+1] ^= a[j][n+1]; //这里注意
            }
        }
    }
    return 0;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= n+1; ++ j)
        {
            cin >> a[i][j];
        }
    }
    int ans = guass();
    if(ans == 1)
    {
        cout << "No solution" << endl;
    }
    else if(ans == 2)
    {
        cout << "Multiple sets of solutions" << endl;
    }
    else
    {
        for(int i = 1; i <= n; ++ i)
        {
            cout << a[i][n+1] << endl;
        }
    }
    return 0;
}

885.求组合数I

#include 
#include 
#include 

using namespace std;

const int N = 2005, MOD = 1e9+7;

int n;

int C[N][N];

void init()
{
    for(int i = 0; i < N; ++ i)
    {
        for(int j = 0; j <= i; ++ j)
        {
            if(j == 0)  C[i][j] = 1;
            else C[i][j] = (C[i-1][j] + C[i-1][j-1])%MOD;
        }
    }
}

int main()
{
    cin >> n;
    init();
    for(int i = 1; i <= n; ++ i)
    {
        int a, b;
        cin >> a >> b;
        cout << C[a][b] << endl;
    }
    return 0;
}

886.求组合数II

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5+5, MOD = 1e9+7;

int n;

int fact[N], infact[N]; //阶乘与阶乘的逆元

int qmi(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = ((LL)ans*a)%MOD;
        b >>= 1;
        a = ((LL)a*a)%MOD;
    }
    return ans;
}

void init()
{
    fact[0] = 1;
    infact[0] = 1;
    for(int i = 1; i < N; ++ i)
    {
        fact[i] = ((LL)fact[i-1]*i)%MOD;
        infact[i] = qmi(fact[i], MOD-2);
    }
}

int main()
{
    cin >> n;
    init();
    while(n --)
    {
        int a, b;
        cin >> a >> b;
        cout << (LL)fact[a]*infact[b]%MOD*infact[a-b]%MOD << endl;
    }
    return 0;
}

887.求组合数III

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5+5;

int n;

int qmi(int a, int b, int p)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = (LL)ans*a%p;
        b >>= 1;
        a = (LL)a*a%p;
    }
    return ans;
}

int C(int a, int b, int p)
{
    int res = 1;
    for(int i = a-b+1; i <= a; ++ i)
    {
        res = (LL)res*i%p;
    }
    for(int i = 1; i <= b; ++ i)
    {
        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()
{
    cin >> n;
    while(n --)
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}

888.求组合数IV*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 5005;

int a, b;

int prime[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; ++ i)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && prime[j] <= n/i; ++ j)
        {
            st[i*prime[j]] = true;
            if(i%prime[j]==0)   break; //最小质因子筛
        }
    }
}

//数n!中含有多少个因子p
int get(int n, int p)
{
    int ans = 0;
    for(int t = p; t <= n; t = t*p) //不会爆
    {
        ans += n/t;
    }
    return ans;
}

vector mul(vector a, int b)
{
    vector ans;
    int r = 0;
    for(int i = 0; i < a.size(); ++ i)
    {
        r = a[i]*b+r;   //注意不能结果直接存到ans[i]
        ans.push_back(r%10);
        r /= 10;
    }
    while(r > 0)
    {
        ans.push_back(r%10);
        r /= 10;
    }
    return ans;
}

int main()
{
    cin >> a >> b;
    get_primes(a);
    for(int i = 0; i < cnt; ++ i)
    {
        sum[i] = get(a, prime[i]) - get(b, prime[i]) - get(a-b, prime[i]);
    }
    vector ans = {1}; //倒着存
    for(int i = 0; i < cnt; ++ i)
    {
        for(int j = 0; j < sum[i]; ++ j)
        {
            ans = mul(ans, prime[i]);
        }
    }
    for(int i = ans.size()-1; i >= 0; -- i)
    {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

889.满足条件的01序列

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int MOD = 1e9+7;

int n;

int qmi(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1) ans = (LL)ans*a%MOD;
        b >>= 1;
        a = (LL)a*a%MOD;
    }
    return ans;
}

int main()
{
    cin >> n;
    int ans = 1;    //卡特兰数公式：C(2n, n)-C(an, n-1) == C(2n, n)/(n+1)
    for(int i = 1; i <= 2*n; ++ i)
    {
        ans = (LL)ans*i%MOD;
    }
    int tp = 1;
    for(int i = 1; i <= n; ++ i)
    {
        tp = (LL)tp*i%MOD;
    }
    ans = (LL)ans*qmi(tp, MOD-2)%MOD;
    ans = (LL)ans*qmi(tp, MOD-2)%MOD;
    ans = (LL)ans*qmi(n+1, MOD-2)%MOD;
    cout << ans << endl;
    return 0;
}

890.能被整除的数

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 17;

int n, m;
int prime[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; ++ i)
    {
        cin >> prime[i];
    }
    int ans = 0;
    for(int i = 1; i < 1<>j&1)
            {
                if((LL)t*prime[j] <= n)
                {
                    cnt ++;
                    t = t*prime[j];
                }
                else
                {
                    yes = false;
                    break;
                }
            }
        }
        if(yes)
        {
            if(cnt%2==1)
            {
                ans += n/t;
            }
            else
            {
                ans -= n/t;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

891.Nim游戏

#include 
#include 
#include 

using namespace std;

int n;

int main()
{
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        ans ^= x;
    }
    if(ans!=0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

892.台阶-Nim游戏

#include 
#include 
#include 

using namespace std;

int n;

int main()
{
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        if(i%2==1)
        {
            ans ^= x;
        }
    }
    if(ans != 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

893.集合-Nim游戏*

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 105, M = 10005;

int k, n;
int s[N];

int dp[M];

int sg(int x)
{
    if(dp[x] != -1) return dp[x];
    set S; //求相邻的sg
    for(int i = 1; i <= k; ++ i)
    {
        if(x >= s[i])
        {
            S.insert(sg(x-s[i]));
        }
    }
    int i = 0;
    while(S.count(i)!=0)
    {
        i ++;
    }
    return dp[x] = i;
}

int main()
{
    cin >> k;
    for(int i = 1; i <= k; ++ i)
    {
        cin >> s[i];
    }
    cin >> n;
    int ans = 0;
    memset(dp, -1, sizeof dp); //求dp
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        ans = ans^sg(x);
    }
    if(ans!=0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

894.拆分-Nim游戏**

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 105;

int n;

int dp[N];

int sg(int x)
{
    if(dp[x] != -1) return dp[x];
    set S; //存放可达的状态的sg值
    for(int i = 0; i < x; ++ i)
    {
        for(int j = 0; j <= i; ++ j)
        {
            S.insert(sg(i)^sg(j)); //状态拆分求sg需要异或
        }
    }
    int i = 0; //状态选择求sg需要nem
    while(S.count(i))
    {
        i ++;
    }
    return dp[x] = i;
}

int main()
{
    cin >> n;
    int ans = 0;
    memset(dp, -1, sizeof dp);
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        ans ^= sg(x);
    }
    if(ans!=0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

第五章动态规划

2.01背包

#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m;

int v[N], w[N];

int dp[2][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 = 0; j <= m; ++ j)
        {
            dp[i%2][j] = dp[(i-1)%2][j]; //不选
            if(j >= v[i]) //可以选
            {
                dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j-v[i]]+w[i]);
            }
        }
    }
    cout << dp[n%2][m] << endl;
}

3.完全背包问题

#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m;

int v[N], w[N];

int dp[2][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 = 0; j <= m; ++ j)
        {
            dp[i%2][j] = dp[(i-1)%2][j];
            if(j >= v[i])   dp[i%2][j] = max(dp[i%2][j], dp[i%2][j-v[i]]+w[i]);
        }
    }
    cout << dp[n%2][m] << endl;
    return 0;
}

4.多重背包问题I

#include 
#include 
#include 

using namespace std;

const int N = 105;

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

int n, m;

int dp[2][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> v[i] >> w[i] >> s[i];
    }
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j <= m; ++ j)
        {
            dp[i%2][j] = dp[(i-1)%2][j];
            for(int k = 1; k <= s[i] && k*v[i] <= j; ++ k)
            {
                dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout << dp[n%2][m] << endl;
    return 0;
}

5.多重背包问题II*

#include 
#include 
#include 

using namespace std;

const int N = 1005*15, M = 2005;

int n, m;

int v[N], w[N];

int dp[2][M];

int main()
{
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; ++ i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int t = 1;
        while(t <= c)
        {
            cnt ++;
            v[cnt] = a*t;
            w[cnt] = b*t;
            c -= t;
            t = t*2;
        }
        if(c > 0)
        {
            cnt ++;
            v[cnt] = a*c;
            w[cnt] = b*c;
        }
    }
    for(int i = 1; i <= cnt; ++ i)
    {
        for(int j = 0; j <= m; ++ j)
        {
            dp[i%2][j] = dp[(i-1)%2][j];
            if(v[i] <= j)
            {
                dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j-v[i]]+w[i]);
            }
        }
    }
    cout << dp[cnt%2][m] << endl;
    return 0;
}

9.分组背包问题

#include 
#include 
#include 

using namespace std;

const int N = 105;

int n, m;

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

int dp[2][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        for(int j  =1; j <= s[i]; ++ j)
        {
            cin >> v[i][j] >> w[i][j];
        }
    }
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j <= m; ++ j)
        {
            //不选
            dp[i%2][j] = dp[(i-1)%2][j];
            for(int k = 1; k <= s[i]; ++ k)
            {
                if(v[i][k] <= j)
                {
                    dp[i%2][j] = max(dp[i%2][j], dp[(i-1)%2][j-v[i][k]]+w[i][k]);
                }
            }
        }
    }
    cout << dp[n%2][m] << endl;
    return 0;
}

898.数字三角形

#include 
#include 
#include 

using namespace std;

const int N = 505, INF = 0x3f3f3f3f;

int n;

int g[N][N], dp[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= i; ++ j)
        {
            cin >> g[i][j];
        }
    }
    dp[1][1] = g[1][1];
    for(int i = 2; i <= n; ++ i)
    {
        for(int j = 1; j <= i; ++ j)
        {
            if(j == 1)
            {
                dp[i][j] = dp[i-1][j] + g[i][j];
            }
            else if(i == j)
            {
                dp[i][j] = dp[i-1][j-1] + g[i][j];
            }
            else
            {
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+g[i][j];
            }
        }
    }
    int ans = -INF;
    for(int i = 1; i <= n; ++ i)
    {
        ans = max(ans, dp[n][i]);
    }
    cout << ans << endl;
    return 0;
}

895.最长上升子序列

#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n;

int num[N];

int dp[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    for(int i = 1; i <= n; ++ i)
    {
        dp[i] = 1;
        for(int j = 1; j < i; ++ j)
        {
            if(num[j] < num[i])
            {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++ i)
    {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
}

896.最长上升子序列II

#include 
#include 
#include 

using namespace std;

const int N = 1e5+5, INF = 0x3f3f3f3f;

int n;
int num[N];

//dp[i]表示所有长度为i的上升子序列中的最小结尾，递增
int dp[N], cnt; 

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> num[i];
    }
    dp[0] = -INF; //哨兵
    for(int i = 1; i <= n; ++ i)
    {
        int l = 0, r = cnt;
        while(l < r) //寻找严格小于num[i]的最大值的后一个
        {
            int mid = l+r+1>>1;
            if(dp[mid] < num[i])   l = mid;
            else r = mid-1;
        }
        dp[l+1] = num[i];
        cnt = max(cnt, l+1);
    }
    cout << cnt << endl;
    return 0;
}

897.最长公共子序列*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m;

string a, b;

int dp[N][N]; //从a的前i个中选，b的前j个中选，最大长度

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

902.最短编辑距离*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m;

string a, b;

int dp[N][N]; //a的前i个字母与b的前j个字母

int main()
{
    cin >> n >> a >> m >> b;
    a = " " + a;
    b = " " + b;
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        dp[i][0] = i;
    }
    for(int j = 1; j <= m; ++ j)
    {
        dp[0][j] = j;
    }
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1;
            if(a[i] == b[j])
            {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            }
            else
            {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

899.编辑距离*

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1005;

int n, m;

string s[N];

int dp[N][N];

int getDistance(string a, string b)
{
    //memset初始化可能会超时
    dp[0][0] = 0;
    for(int i = 1; i < a.size(); ++ i)
    {
        dp[i][0] = i;
    }
    for(int j = 1; j < b.size(); ++ j)
    {
        dp[0][j] = j;
    }
    for(int i = 1; i < a.size(); ++ i)
    {
        for(int j = 1; j < b.size(); ++ j)
        {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1; //避免了被原来的dp[i][j]影响
            if(a[i] == b[j])
            {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
            }
            else
            {
                dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
            }
        }
    }
    return dp[a.size()-1][b.size()-1];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        s[i] = " " + s[i]; 
    }
    while(m --)
    {
        string c;
        int t;
        cin >> c >> t;
        c = " " + c;
        int cnt = 0;
        for(int i = 1; i <= n; ++ i)
        {
               if(getDistance(s[i], c) <= t)
               {
                   cnt ++;
               }
        }
        cout << cnt << endl;
    }
    return 0;
}

282.石子合并

#include 
#include 
#include 

using namespace std;

const int N = 305, INF = 0x3f3f3f3f;

int n;
int sum[N];
int dp[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    for(int len = 2; len <= n; ++ len) //先算小区间的dp
    {
        for(int i = 1; i+len-1 <= n; ++ i)
        {
            int j = i+len-1;
            dp[i][j] = INF;
            for(int k = i; k < j; ++ k) //枚举分割的左区间右端点
            {
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
            }
            dp[i][j] += sum[j]-sum[i-1];
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

900.整数划分

#include 
#include 
#include 

using namespace std;

const int N = 1005, MOD = 1e9+7;

int n;

int dp[N][N];

int main()
{
    cin >> n;
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 0; j <= n; ++ j)
        {
            dp[i][j] = dp[i-1][j];
            if(j >= i)
            {
                dp[i][j] += dp[i][j-i];
                dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

338.计数问题***

#include 
#include 
#include 
#include 

using namespace std;

//计算整数n有多少位
int dgt(int n)
{
    int res = 0;
    while(n) ++ res, n /= 10;
    return res;
}

//计算1~n的整数中数字i出现的次数
int cnt(int n, int i)
{
    int res = 0, d = dgt(n);
    for(int j = 1; j <= d; ++ j) //从右到左的第j位数字i出现的次数
    {
        //l和r是左右两边的整数，dj是第j位的数字
        int p = pow(10, j-1), l = n/p/10, r = n%p, dj = n/p%10;
        if(i != 0)  
        {
            res += l*p; //左边为000~abc-1
        }
        else if(i == 0 && l != 0) //左边不能全为0
        {
            res += (l-1)*p; //左边为001~abc-1
        }
        //计算第j位左边的整数等于l的情况
        if((dj>i)&&(i||l)) //注意前缀不能都是0
        {
            res += p;
        }
        else if((dj==i)&&(i||l))
        {
            res += r+1; //0~r
        }
    }
    return res;
}

int main()
{
    int a, b;
    while(cin >> a >> b, a||b)
    {
        if(a > b)   swap(a, b);
        for(int i = 0; i <= 9; ++ i)
        {
            cout << cnt(b, i) - cnt(a-1, i) << " ";
        }
        cout << endl;
    }
    return 0;
}

291.蒙德里安的梦想**

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 12, M = 1< stateFrom[M]; //state[i][j]表示状态i可以从状态j转移过来

LL dp[N][M]; //查看第i列，在i-1列插入到i列的状态为j的情况下的方案

int main()
{
    while(cin >> n >> m, n||m)
    {
        for(int i = 0; i < 1<>j&1)==0)
                {
                    cnt ++;
                }
                else
                {
                    if(cnt%2==1)
                    {
                        flag = false;
                        break;
                    }
                    cnt = 0;
                }
            }
            if(cnt%2==1)
            {
                flag = false;
            }
            st[i] = flag;
        }
        //再筛选出状态i可以从哪些状态转移过来
        //也就是i-2列状态j插到i-1列状态i之后i-1列是否满足要求
        for(int i = 0; i < 1<


91.最短Hamilton路径*
#include 
#include 
#include 
#include 

using namespace std;

const int N = 22, M = 1<<21;

int n;

int dist[N][N];
//dp[i][j]表示当前经过的点的状态为i，现在在j这个点的路径长度
int dp[M][N]; 

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        for(int j = 0; j < n; ++ j)
        {
            cin >> dist[i][j];
        }
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int i = 0; i < 1<>j&1) //要保证经过的路径有这个点
            {
                //枚举中继节点
                for(int k = 0; k < n; ++ k)
                {
                    if(i>>k&1)
                    {
                        dp[i][j] = min(dp[i][j], dp[i-(1<

285.没有上司的舞会
#include 
#include 
#include 
#include 

using namespace std;

//有向边
const int N = 6005, M = N;

int h[N], e[M], ne[M], idx;

void init()
{
    memset(h, -1, sizeof h);
}

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int w[N]; //注意这里是点的权值，不是边的

bool st[N]; //表示有父节点

int n;

int dp[N][2];

//求dp[root][0]和dp[root][1]
void dfs(int root)
{
    //初始化
    dp[root][0] = 0;
    dp[root][1] = w[root];
    for(int i = h[root]; ~i; i=ne[i])
    {
        int j = e[i];
        dfs(j);
        dp[root][0] += max(dp[j][0], dp[j][1]);
        dp[root][1] += dp[j][0];
    }
}

int main()
{
    cin >> n;
    init();
    for(int i = 1; i <= n; ++ i)
    {
        int t;
        cin >> t;
        w[i] = t;
    }
    for(int i = 1; i < n; ++ i)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        st[a] = true;
    }
    int root = -1;
    for(int i = 1; i <= n; ++ i)
    {
        if(!st[i])
        {
            root = i;
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
    return 0;
}

901.滑雪
#include 
#include 
#include 
#include 

using namespace std;

const int N = 305;

int n, m;
int g[N][N];
//f[i][j]表示从i,j开始走过的最长长度,0表示未计算，至少为1
int f[N][N]; 

int dp(int x, int y)
{
    if(f[x][y]) return f[x][y];
    f[x][y] = 1;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    for(int i = 0; i < 4; ++ i)
    {
        int a = x+dx[i], b = y+dy[i];
        if(a<=0 || a>n || b<=0 || b>m || g[a][b]>=g[x][y])
        {
            continue;
        }
        f[x][y] = max(f[x][y], dp(a, b)+1);
    }
    return f[x][y];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            cin >> g[i][j];
        }
    }
    int res = 0;
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = 1; j <= m; ++ j)
        {
            res = max(res, dp(i, j));
        }
    }
    cout << res << endl;
    return 0;
}

第六章 贪心
905.区间选点
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;

struct Range{
    int l, r;
    bool operator<(const Range &ra) const{
        return r<=ra.r;
    }
}range[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> range[i].l >> range[i].r;
    }
    sort(range+1, range+n+1);
    int ans = 1;
    int lastNode = range[1].r;
    for(int i = 2; i <= n; ++ i)
    {
        if(range[i].l <= lastNode)
        {
            continue;
        }
        else
        {
            lastNode = range[i].r;
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

908.最大不相交区间数量
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;

struct Range{
    int l, r;
    bool operator<(const Range &ra) const{
        if(r != ra.r)
            return rra.l;
    }
}range[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> range[i].l >> range[i].r;
    }
    sort(range+1, range+n+1);
    int ans = 1;
    int R = range[1].r;
    for(int i = 2; i <= n; ++ i)
    {
        if(range[i].l > R)
        {
            ans ++;
            R = range[i].r;
        }
    }
    cout << ans << endl;
    return 0;
}

906.区间分组*
#include 
#include 
#include 
#include 
#include 

#define l first
#define r second

using namespace std;

typedef pair PII;

int n;

priority_queue, greater> heap; //组内最大右端点从小到大排序

vector range;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int l, r;
        cin >> l >> r;
        range.push_back({l, r});
    }
    sort(range.begin(), range.end());
    heap.push(range[0].r);
    for(int i = 1; i < range.size(); ++ i)
    {
        int R = heap.top();//小根堆
        if(range[i].l <= R) //比右端点最小的组的右端点还要小
        {
            heap.push(range[i].r);
        }
        else
        {
            if(range[i].r > R)
            {
                heap.pop();
                heap.push(range[i].r);
            }
        }
    }
    cout << heap.size() << endl;
    return 0;
}

907.区间覆盖*
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5, INF = 0x3f3f3f3f;

int n;
int start, tail;

struct Range{
    int l, r;
    bool operator<(const Range &Ra) const{
        return l <= Ra.l;
    }
}range[N];

int main()
{
    cin >> start >> tail;
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        cin >> range[i].l >> range[i].r;
    }
    sort(range, range+n);
    int ans = 0;
    bool success = false;
    for(int i = 0; i < n; ++ i) //枚举区间
    {
        int j = i;
        int maxR = -INF;
        while(j < n && range[j].l <= start)
        {
            maxR = max(maxR, range[j].r);
            ++ j;
        }
        if(maxR <= start)
        {
            success = false;
            break;
        }
        start = maxR;
        ans ++;
        if(maxR >= tail)
        {
            success = true;
            break;
        }
        i = j-1;
    }
    if(success)
    {
        cout << ans << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

148.合并果子
#include 
#include 
#include 
#include 

using namespace std;

int n;

priority_queue, greater> heap; //小根堆

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++ i)
    {
        int x;
        cin >> x;
        heap.push(x);
    }
    int ans = 0;
    while(heap.size() != 1)
    {
        int a1 = heap.top();
        heap.pop();
        int a2 = heap.top();
        heap.pop();
        ans += a1+a2;
        heap.push(a1+a2);
    }
    cout << ans << endl;
    return 0;
}

913.排队打水
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1e5+5;

int n;

int tim[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        cin >> tim[i];
    }
    sort(tim, tim+n);
    reverse(tim, tim+n); //从大到小排序
    LL ans = 0;
    for(int i = n-1; i >= 0; -- i)
    {
        ans += (LL)tim[i]*i;
    }
    cout << ans << endl;
    return 0;
}

104.货仓选址
#include 
#include 
#include 

using namespace std;

const int N = 1e5+5;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        cin >> a[i];
    }
    sort(a, a+n);
    int ans = 0; 
    for(int i = 0, j = n-1; i < j; ++ i, -- j)//if i==j说明货仓在这里，为0
    {
        ans += (a[j]-a[i]);
    }
    cout << ans << endl;
    return 0;
}

125.耍杂技的牛*
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 50005, INF = 0x3f3f3f3f;

int n;
PII cow[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; ++ i)
    {
        int w, s;
        cin >> w >> s;
        cow[i]= {w+s, w};
    }
    sort(cow, cow+n);
    int ans = -INF;
    int sum = 0; //sum_w
    for(int i = 0; i < n; ++ i)
    {
        int w = cow[i].y, s = cow[i].x - cow[i].y;
        ans = max(ans, sum-s);
        sum += w;
    }
    cout << ans << endl;
    return 0;
}


					
					
					
						相关
						
				
						
			
																
								
										2017 清北济南考前刷题Day 6 morning
									
									
								 

        
								
							
							

																
								
										面试随缘刷题--day7
									
									
								 

        
								
							
							

																
								
										C语言刷题笔记6
									
									
								 

        
								
							
							

																
								
										LeetCode刷题总结-数组篇（上）
									
									
								 

        
								
							
							

																
								
										C语言刷题笔记5
									
									
								 

        
								
							
							

																
								
										C语言刷题笔记4
									
									
								 

        
								
							
							

																
								
										[整理]qbxt周末刷题班 Day2总结
									
									
								 

        
								
							
							

																
								
										刷题记录——疫情问答积分（模拟）
									
									
								 

        
								
							
							

																
								
										Leetcode 刷题小抄 Java版
									
									
								 

        
								
							
							

																
								
										LeetCode刷题之DP算法
									
									
								 

        
								
							
							

																
								
										力扣每天刷题(2)
									
									
								 

        
								
							
							

																
								
										free code camp 刷题记录 js(ES6 箭头函数)

AcWing算法基础课

算法基础课

第一章 基础算法

785.快速排序

786.第k个数

787.归并排序

788.逆序对的数量*

789.数的范围

790.数的三次方根

791.高精度加法

792.高精度减法

793.高精度乘法

794.高精度除法*

759.前缀和

796.子矩阵的和

797.差分

798.差分矩阵*

799.最长连续不重复子序列

800.数组元素的目标和

2816.判断子序列

801.二进制中1的个数

802.区间和**

803.区间和并

第二章 数据结构

826.单链表

872.双链表*

828.模拟栈

3302.表达式求值**

829.模拟队列

830.单调栈

154.滑动窗口**

831.KMP字符串**

835.Trie字符串统计*

143.最大异或对*

836.合并集合

837.连通块中点的数量

240.食物链**

838.堆排序

839.模拟堆**

840.模拟散列表

841.字符串哈希**

第三章 搜索与图论

842.排列数字

844.走迷宫

845.八数码*

846.树的重心*

847.图中点的层次

848.有向图的拓扑序列

849.Dijkstra求最短路I

850.Dijkstra求最短路II

853.有边数限制的最短路*

851.spfa求最短路

852.spfa判断负环*

854.Floyd求最短路

858.Prim求最小生成树

859.Kruskal算法求最小生成树

860.染色法判定二分图

861.二分图的最大匹配*

第四章 数学知识

866.试除法判断质数

867.分解质因数

870.筛质数*

869.试除法求约数

870.约数个数

871.约数之和

872.最大公约数

873.欧拉函数

874.筛法求欧拉函数**

875.快速幂

876.快速幂求逆元*

877.扩展欧几里得算法*

878.线性同余方程**

204.表达整数的奇怪方式***

883.高斯消元解线性方程组**

884.高斯消元解异或线性方程组*

885.求组合数I

886.求组合数II

887.求组合数III

888.求组合数IV*

889.满足条件的01序列

第一章基础算法

第二章数据结构

第三章搜索与图论

第四章数学知识

第五章动态规划

第六章贪心