2022

 #include<iostream>
 using namespace std;
 typedef long long LL;
 LL f[2400][11][2400];
 int main()
 {
   for(int i=0;i<=2022;i++)f[i][0][0]=1;
   for(int k=1;k<=2022;k++)
    for(int i=1;i<=10;i++)
     for(int j=1;j<=2022;j++)
     {
       f[k][i][j]=f[k-1][i][j];
       if(j>=k)f[k][i][j]+=f[k-1][i-1][j-k];
     }
   cout<<f[2022][10][2022]<<endl;
   return 0;
 }
//类似于二维01背包 从1到2022选 次数不超过10 总和不超过2022的方案数
#include<iostream>
using namespace std;
typedef long long LL;
LL f[11][2400];
int main()
{
  f[0][0]=1;
   for(int k=1;k<=2022;k++)
    for(int i=10;i>=1;i--)
     for(int j=2022;j>=k;j--)
     f[i][j]+=f[i-1][j-k];
    cout<<f[10][2022]<<endl;
    return 0;
}

钟表

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main() 
{
    for(int s=0;s<=6;s++)
        for(int f=0;f<60;f++)
            for(int m=0;m<60;m++)
            {
                if(s==0&&f==0&&m==0) continue;
                double dm = m / 60.0 * 360; // 与0刻的角度
                double df = f / 60.0 * 360 + dm / 60; // 一分钟60秒 多出来的度数也要算
                double ds = s / 12.0 * 360 + df / 12; // 同理
                double A = abs(df - ds), B = abs(df - dm); // 绝对值
                // 取小的角度 因为要小于180
                A = min(A, 360 - A);
                B = min(B, 360 - B);
                if(fabs(A - 2 * B) <= 1e-10)
                    printf("%d %d %d\n", s, f, m);
            }
    return 0;
}

卡牌

//直接暴力 每遍历一张牌，就拿走，拿不了就补，补不了就退出， 中途没有退出就说明能凑一套牌
#include<iostream>
#include<cstdio>
using namespace std; 
typedef long long LL;
const int N=200010;
int a[N];
int b[N];
int main()
{
    int n;
    LL m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)scanf("%d", &a[i]);
    for (int i = 0; i < n; i++)scanf("%d", &b[i]);
    LL res = 0;
    bool st=true;
    while (st)
    {
        for (int i = 0; i < n; i++)
        {
            if (a[i])a[i]--;
            else if (b[i] > 0 && m > 0)
            {
                b[i]--;
                m--;
            }
            else
            {
                st=false;
                break;
            }
        }
        if (st)res++;
    }
    printf("%lld", res);
}

二分

#include <iostream>
using namespace std;
const int N = 200010;
typedef long long LL;
int n, m;
int a[N], b[N];
// 检查是否能凑出 k 套牌
bool check(int k)
 {
    int s = 0;
    for (int i = 0; i < n; i++) 
    {
        if (a[i] < k) 
        {
            int need = k - a[i];//还需要多少个 
            if (need > b[i]) return false;
            s += need;
        }
    }
    return s <= m;
}

int main() 
{
    cin>>n>>m;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);

    int l = 0, r = 1e9;
    // 二分查找最大能凑出的套牌数
    while (l < r) 
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//找到右边最大 
        else r = mid - 1;
    }
    printf("%d\n", l);
    return 0;
}    

最大数字

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
int a,b;
string s;
LL ans; 
void dfs(int u,LL sum)
{    
    // 将当前位置 u 对应的字符转换为整数 t
    int t=s[u]-'0';    
    if(u<s.size())
    {          
        // 计算当前位置使用 1 号操作能增加的最大数值 c
        // 取 a（剩余 1 号操作次数）和 9 - t（使当前数字变为 9 所需的 1 号操作次数）中的较小值
        int c=min(a,9-t);
        a-=c;
        dfs(u+1,sum*10+t+c);
        // 递归调用 dfs 函数，处理下一个位置
        // 将当前部分结果 an 乘以 10 并加上 t + c，得到新的部分结果
        a+=c;//回溯 
        if(b>t)
        {
            b=b-t-1;//b用了t+1次 使变成9 
            dfs(u+1,sum*10+9);
            b=b+t+1;//回溯 
        }
    }
    // 如果已经处理完所有位置（s[u] 为 '\0'），则更新最大结果 ans
    else ans=max(ans,sum);
}

int main()
{
    cin>>s>>a>>b;
    dfs(0,0); 
    cout<<ans;
    return 0;
}

出差

djs

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N=1010;
int g[N][N];
int dist[N];
bool st[N];
int a[N];
int n,m;
int djs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
         if(!st[j]&&(t==-1||dist[t]>dist[j]))
          t=j;
        st[t]=true;
        for(int j=1;j<=n;j++)
         dist[j]=min(dist[j],dist[t]+g[t][j]+a[j]);
         //其实这里是更新1后面的 不包括1 上面dist[1]=0 也更新不了 
    }
    return dist[n]-C[n];//最后到了不用算隔离时间 
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=min(g[x][y],z);
        g[y][x]=min(g[y][x],z);
    }
    cout<<djs()<<endl;
    return 0;
}

spfa

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;

const int N=1010,M=20010,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int a[N];
int n,m;

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

void spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i]+a[j])
            {
                dist[j]=dist[t]+w[i]+a[j];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)cin>>a[i];
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    spfa();
    cout<<dist[n]-a[n]<<endl;
    return 0;
}

费用报销

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010; // 最大票据数
const int M = 5010; // 最大报销金额
int n, m, k;
int dp[N][M]; // dp[i][j] 表示前 i 张票据中，金额不超过 j 时的最大报销金额
struct Bill 
{
    int t; // 日期（转换为一年中的第几天）
    int v; // 票据金额
    bool operator<(const Bill&w)const
    {
        return t<w.t;
    }
} bills[N];
// 将月份和日期转换为一年中的第几天
int toDay(int m, int d) 
{
    int ms[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int s = 0;
    for (int i = 1; i < m; i++) 
        s += ms[i];
    return s + d;
}

int main()
{
    cin>>n>>m>>k;
    // 输入票据信息并转换为一年中的第几天
    for (int i = 1; i <= n; i++) 
    {
        int m, d, v;
        scanf("%d%d%d", &m, &d, &v);
        bills[i].t = toDay(m, d);
        bills[i].v = v;
    }

    // 按日期排序
    sort(bills + 1, bills + n + 1);

    // 动态规划求解
    for (int i = 1; i <= n; i++)
    {
        // 使用二分查找找到 左边 最大的一个 满足条件的 
        int l = 0, r = i - 1;
        while (l < r) 
        {
             int mid = l + r +1 >> 1;
             if (bills[i].t - bills[mid].t >= k) l = mid;
             else r = mid - 1;
        }
        int last = l;
        // 更新 dp 数组
        for (int j = 0; j <= m; j++) 
        {
            // 不选第 i 张票据
            f[i][j] = f[i - 1][j];
            // 选第 i 张票据（需满足金额条件）
            if (j >= bills[i].v) 
            {
                f[i][j] = max(f[i][j], f[last][j - bills[i].v] + bills[i].v);
                //特别注意这里不是dp[i-1] 
            }
        }
    }
    // 输出结果
    printf("%d\n", dp[n][m]);
    return 0;
}

一维

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

using namespace std;

const int N = 1010; // 最大票据数
const int M = 5010; // 最大报销金额

int n, m, k;
int f[M]; //f[j]表示金额不超过 j 时的最大报销金额
struct Bill 
{
    int t; // 日期（转换为一年中的第几天）
    int v; // 票据金额
    bool operator<(const Bill&w)const
    {
        return t<w.t;
    }
} bills[N];

// 将月份和日期转换为一年中的第几天
int toDay(int m, int d) 
{
    int ms[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int s = 0;
    for (int i = 1; i < m; i++) 
        s += ms[i];
    return s + d;
}

int main() 
{
    cin>>n>>m>>k;

    // 输入票据信息并转换为一年中的第几天
    for (int i = 1; i <= n; i++)
     {
        int m, d, v;
        scanf("%d%d%d", &m, &d, &v);
        bills[i].t = toDay(m, d);
        bills[i].v = v;
    }

    // 按日期排序
    sort(bills + 1, bills + n + 1);

    // 动态规划求解
    for (int i = 1; i <= n; ++i) 
    {

        int l = 0, r = i - 1;
        while (l < r)
         {
            int mid = l + r + 1 >> 1;// 找到最近的一个与当前票据日期差大于等于 k 的票据
            if (bills[i].t - bills[mid].t >= k) l = mid;
            else r = mid - 1;
        }
        // 更新 dp 数组
        for (int j = m; j >= bills[i].v; j--) 
            f[j] = max(f[j], f[l] + bills[i].v);
    }

    // 输出结果
    printf("%d\n", f[m]);

    return 0;
}

故障

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 45;
const int M = 25;
double p[N];
// p 数组存储每种故障原因出现的初始概率
double mp[N][M];
// mp 数组存储相关性矩阵，mp[i][j] 表示故障原因 i 出现故障现象 j 的概率
int n, m, k;
// n 表示故障原因的数量，m 表示故障现象的数量，k 表示出现的故障现象数量
bool st[M];
// st 数组标记哪些故障现象出现了，st[j] 为 true 表示故障现象 j 出现
struct Node 
{
    int id; // 故障原因编号
    double t; // 故障原因出现的概率
    bool operator<(const Node&w)const
    {
        if(t!=w.t)return t>w.t;
        else return id<w.id;
    }
    // 使用 lambda 表达式进行排序
    // 若两个故障原因概率差值大于 1e - 6，则概率大的在前
    // 若概率相同，则编号小的在前
};

int main() 
{
    cin>>n>>m;
    for (int i = 1; i <= n; i++) 
    {
        scanf("%lf", &p[i]);// 循环读取每种故障原因出现的初始概率，并将其转换为小数形式
        p[i] /= 100;
    }
    // 双重循环读取相关性矩阵，即每种故障原因对应每种故障现象的概率
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) 
            scanf("%lf", &mp[i][j]);

    scanf("%d", &k);//读取出现的故障现象数量 k
    for (int i = 1; i <= k; i++) 
    {
        int x;
        scanf("%d", &x);
        st[x] = true;//循环读取出现的故障现象编号，并标记到 st 数组中
    }

    // 用于存储所有故障原因在当前故障现象下的概率总和
    double sum = 0;
    // 计算每种故障原因在当前故障现象下的概率
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++) 
        {
            if (st[j])  p[i] *= mp[i][j] / 100;
            // 如果故障现象 j 出现，将故障原因 i 的概率乘以该故障原因出现该现象的概率
            else p[i] *= (100 - mp[i][j]) / 100;
            // 如果故障现象 j 未出现，将故障原因 i 的概率乘以该故障原因不出现该现象的概率
        }
        // 累加每种故障原因的概率
        sum += p[i];
    }

    // 存储每种故障原因的编号和最终概率
    Node res[N];
    // 计算每种故障原因的最终概率，并存储到 res 数组中
    for (int i = 1; i <= n; i++) 
    {
        res[i].id = i;
        res[i].t = p[i] / sum;
    }
    sort(res+1,res+1+n);
    // 循环输出每种故障原因的编号和最终概率，保留两位小数
    for (int i = 1; i <= n; i++) 
        printf("%d %.2lf\n", res[i].id, res[i].t * 100);
    return 0;
}    

机房

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 100100; // 最大节点数
const int M = N * 2; // 最大边数
int n, m;
int h[N], e[M], ne[M], idx; // 链式前向星建图
int degree[N]; // 每个节点的度数（延迟）
int st[N]; // 标记节点状态
int parent[N]; // 记录每个节点的父节点
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 使用 BFS 找到从 u 到 v 的路径
vector<int> bfs(int u, int v)
{
    queue<int> q;
    q.push(u);
    st[u] = 1; // 标记节点 u 已访问
    parent[u] = -1; // 起点的父节点为 -1

    while (q.size())
    {
        int t = q.front();
        q.pop();

        if (t == v) // 找到目标节点 v
        {
            // 回溯路径
            vector<int> path;
            while (t != -1)
            {
                path.push_back(t);
                t = parent[t];
            }
            reverse(path.begin(), path.end()); // 反转路径，使其从 u 到 v
            return path;
        }

        // 遍历邻居
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j] = 1; // 标记节点 j 已访问
                parent[j] = t; // 记录父节点
                q.push(j);
            }
        }
    }

    return {}; // 未找到路径
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    // 输入网络连接
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
        degree[a]++, degree[b]++; // 更新度数
    }

    // 处理每个查询
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);

        // 初始化
        memset(st, 0, sizeof st);
        memset(parent, -1, sizeof parent);

        // 找到从 u 到 v 的路径
        vector<int> path = bfs(u, v);

        if (path.size())
        {
            // 计算路径上的总延迟
            int delay = 0;
            for (int node : path)
            {
                delay += degree[node];
            }
            printf("%d\n", delay);
        }
        else
        {
            printf("-1\n"); // 未找到路径
        }
    }

    return 0;
}

齿轮

#include <iostream>
using namespace std;

const int N = 200010; 
int a[N];
int s[N]; // 统计每个半径出现的次数
bool st[N]; // 记录是否存在某种倍数关系
int main() 
{
    int n, m;
    cin >> n >> m; 
    for (int i = 0; i < n; i++) 
        cin >> a[i]; // 输入每个齿轮的半径

    for (int i = 0; i < n; i++) 
        s[a[i]]++; // 统计半径 a[i] 出现的次数

    for (int i = 0; i < n; i++) 
    {
        if (s[a[i]] >= 2) //至少2个 
            st[1] = true; // 如果有重复半径，则 q=1 是可行的

        int j = a[i] * 2; // 检查倍数关系 从q=2开始 
        while (j <= 200000)
        {
            if (s[j]) st[j / a[i]] = true; // 如果存在 j，则 q = j / a[i] 是可行的
            j += a[i]; // 继续检查下一个倍数
        }
    }
    // 处理每个询问
    for (int i = 0; i < m; i++) 
    {
        int q;
        cin >> q; // 输入询问 q
        if (st[q])
          cout << "YES" << endl; // 如果 q 可行，输出 YES
        else  
          cout << "NO" << endl; // 否则输出 NO
    }
    return 0;
}

搬砖

#include<iostream>
#include<algorithm>
#define x first
#define y second 
using namespace std;
const int N=1010,M=20*1010;
typedef pair<int,int>PII;
PII wv[N];
int f[N][M];
int main() 
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) 
    {
        int w,v;
        cin>>w>>v;
        wv[i]={w+v,v};
    }
    sort(wv+1,wv+1+n);
    int ans = 0;
    for (int i = 1; i <= n; i++) 
    {
        int w=wv[i].x-wv[i].y,v=wv[i].y;
        for (int j=0; j<=M;j++) 
        {
            f[i][j]=f[i-1][j];//不选 
            if (j >=w && v>= j-w) 
            {
                f[i][j] = max(f[i][j], f[i-1][j - w] + v);
                ans = max(ans, f[i][j]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}