成绩：CB组国一

试题 A: 2022

// 不会

试题 B: 钟表

#include<bits/stdc++.h>
using namespace std;


int main()
{
    for(int i = 0;i < 6;i ++)
        for(int j = 0;j < 60;j ++)
            for(int k = 0;k < 60;k ++)
            {
                int s1 = i * 3600 + j * 60 + k;
                int s2 = j * 60 + k;
                int s3 = k;
                int a = min(abs(s1 - s2 * 12), 360 * 120 - abs(s1 - s2 * 12));
                int b = min(abs(s2 * 12 - s3 * 72), 360 * 120 - abs(s2 * 12 - s3 * 72));
                if(a == b * 2)
                    cout<<i<<" "<<j<<" "<<k<<endl;
            }
    return 0;
}

试题 C: 卡牌

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

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

bool check(int x)
{
    int sum = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(x - a[i] > b[i]) return false;
        if(x > a[i]) sum += x - a[i];
    }
    return sum <= m;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 1;i <= n;i ++) cin>>a[i];
    for(int i = 1;i <= n;i ++) cin>>b[i];
    int l = 0, r = n * 4;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout<<l<<endl;
    return 0;
}

试题 D: 最大数字

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    string n; cin>>n;
    int A, B; cin>>A>>B;
    string res;
    for(int i = 0;i < (1 << 17);i ++)
    {
        string temp = "";
        int a = A, b = B;
        for(int j = 0;j < n.length();j ++)
        {
            int tot = n[j] - '0';
            if((i >> j) & 1)
            {
                int neda = min(a, 9 - tot);
                temp += '0' + tot + neda;
                a -= neda;
            }
            else
            {
                int nedb = tot + 1;
                if(b >= nedb)
                {
                    temp += '9';
                    b -= nedb;
                }
                else
                    temp += '0' + tot;
            }
        }
        res = max(res, temp);
    }
    cout<<res<<endl;
    return 0;
}

试题 E: 出差

#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 10;

int c[N];
vector<pair<int, int>> e[N];
int dis[N];
bool vis[N];

void dij()
{
    memset(dis, 0x3f, sizeof dis);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({0, 1});
    dis[1] = 0;
    while(!heap.empty())
    {
        int u = heap.top().second; heap.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = 0;i < e[u].size();i ++)
        {
            int v = e[u][i].first, w = e[u][i].second;
            if(dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                heap.push({dis[v], v});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m; cin>>n>>m;
    for(int i = 1;i <= n;i ++) cin>>c[i];
    c[n] = 0;
    for(int i = 1;i <= m;i ++)
    {
        int u, v, w; cin>>u>>v>>w;
        e[u].push_back({v, w + c[v]});
        e[v].push_back({u, w + c[u]});
    }
    dij();
    cout<<dis[n]<<endl;
    return 0;
}

试题 F: 费用报销

#include<bits/stdc++.h>
using namespace std;
const int N = 5000 + 10;

bool f[400][N];
vector<int> e[N];

int main()
{
    ios::sync_with_stdio(false);
    int mon[] = {0, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};
    for(int i = 1;i <= 12;i ++) mon[i] += mon[i - 1];

    int n, m, k; cin>>n>>m>>k;
    for(int i = 1;i <= n;i ++)
    {
        int a, b, c; cin>>a>>b>>c;
        int tot = mon[a] + b;
        e[tot].push_back(c);
    }

    for(int i = 1;i <= 365;i ++)
    {
        for(int j = 1;j <= m;j ++)
            f[i][j] = f[i - 1][j];
        for(auto &p : e[i])
        {
            f[i][p] = true;
            if(i > k)
            {
                for(int j = 1;j + p <= m;j ++)
                {
                    if(f[i - k][j])
                        f[i][j + p] = true;
                }
            }
        }
    }

    for(int i = m;i >= 0;i --)
    {
        if(f[365][i])
        {
            cout<<i<<endl;
            break;
        }
    }

    return 0;
}

试题 G: 故障

// 不会

试题 H: 机房

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

vector<int> e[N];
int d[N];
int depth[N], fa[N][16], sum[N];

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> que;
    que.push(root);
    while(!que.empty())
    {
        int u = que.front(); que.pop();
        for(auto &v : e[u])
        {
            if(depth[v] > depth[u] + 1)
            {
                depth[v] = depth[u] + 1;
                que.push(v);
                fa[v][0] = u;
                for(int i = 1;i <= 15;i ++)
                    fa[v][i] = fa[fa[v][i - 1]][i - 1];
            }
        }
    }
}

void dfs(int u, int fa)
{
    sum[u] = sum[fa] + d[u];
    for(auto &v : e[u])
    {
        if(v == fa) continue;
        dfs(v, u);
    }
}

int lca(int x, int y)
{
    if(depth[x] < depth[y]) swap(x, y);
    for(int i = 15;i >= 0;i --)
        if(depth[fa[x][i]] >= depth[y])
            x = fa[x][i];
    if(x == y) return x;
    for(int i = 15;i >= 0;i --)
        if(fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m; cin>>n>>m;
    for(int i = 1;i < n;i ++)
    {
        int u, v; cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u] ++, d[v] ++;
    }
    bfs(1);
    dfs(1, 0);
    for(int i = 1;i <= m;i ++)
    {
        int u, v; cin>>u>>v;
        int la = lca(u, v);
        cout<<sum[u] - sum[la] + sum[v] - sum[la] + d[la]<<endl;
    }
    return 0;
}

试题 I: 齿轮

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    int n, q; cin>>n>>q;
    for(int i = 1;i <= n;i ++) cin>>a[i];

    sort(a + 1, a + n + 1);
    int m = 0;
    for(int i = 1;i <= n;i ++)
    {
        int j = i;
        while(j <= n && a[j] == a[i]) j ++;
        a[++ m] = a[i];
        i = j - 1;
    }

    map<int, bool> mp;
    map<int, bool> ans;

    for(int i = 1;i <= m;i ++)
    {
        for(int j = 1;j * j <= a[i];j ++)
        {
            if(a[i] % j == 0)
            {
                 if(mp[a[i] / j]) ans[j] = true;
                 if(mp[j]) ans[a[i] / j] = true;
            }
        }
        mp[a[i]] = true;
    }

    while(q --)
    {
        int x; cin>>x;
        if(x == 1)
        {
            if(m < n) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else
        {
            if(ans[x]) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }

    return 0;
}

试题 J: 搬砖

#include<bits/stdc++.h>
using namespace std;
const int N = 1000 + 10, M = 20000 + 10;

pair<int, int> a[N];
int f[M];

signed main()
{
    ios::sync_with_stdio(false);
    int n; cin>>n;
    for(int i = 1;i <= n;i ++)
    {
        int w, v; cin>>w>>v;
        a[i] = {w, v};
    }
    sort(a + 1, a + n + 1);

    for(int i = 1;i <= n;i ++)
    {
        int w = a[i].first, v = a[i].second;

        for(int j = v;j >= 0;j --)
            f[j + w] = max(f[j + w], f[j] + v);
    }

    int res = 0;
    for(int i = 0;i < M;i ++) res = max(res, f[i]);

    cout<<res<<endl;

    return 0;
}