https://ac.nowcoder.com/acm/contest/94879#question
A

#include <bits/stdc++.h>
using namespace  std;
const int N=1e5+10;
int n,x,y,z,t;
int a[N],b[N],c[N];
int main()
{
    cin>>n>>x>>y>>z>>t;
    for(int i=1;i<=n;i++)
    {
    cin>>a[i]>>b[i]>>c[i];    
    }
    int mx=0,res=x+y,ans=0;
    for(int i=1;i<=n;i++)
    {
    if(t>=c[i])
    {
    mx=max(mx,res+a[i]+b[i]);
    }
    }
    for(int i=1;i<=n;i++)
    {
    if(t+z>=c[i])
    {
    ans=max(ans,a[i]+b[i]);
    }
    }
    cout<<max(ans,res);
}

B

# include <bits/stdc++.h>
using namespace std;
#define ld double
int main()
{
   ld p[5];
    for(auto& v:p)cin>>v;
    ld p0=p[0]+p[1]+p[2];
    ld p1=p[3]+p[4];
    ld P0=pow(p0,10);
    ld P1=10*pow(p1,1)*pow(p0,9);
    cout<<fixed<<setprecision(12);
    cout<<1-P0-P1;
}

C
考虑二分 我们考虑三种操作的顺序：1操作对所有人造成伤害，2操作我们尽可能对于连续的敌人造成伤害，3操作放到最后使用

#include <iostream>
using namespace std;
const int N = 1e5+10;
int n;
int a[N],b[N];

bool check(int x)
{
        b[0]=0;
        int x1=x;
        for(int i=1;i<=n;i++)
        {
        b[i]=a[i]-x;
        if(b[i]>0&&b[i-1]>0)
        {
        int t=min(b[i],b[i-1]);
        t=min(t,x1);
        x1-=t;
        b[i]-=t;
        b[i-1]-=t;
        }
        }
        int x2=x1+x,i=1;
        for(;i<=n;i++)
        {
        if(b[i]>0)
        {
        x2-=b[i];
        b[i]=0;
        }
        if(x2<0)
        break;
        }
        if(x2>=0&&i==n+1)
        return true;
        return false;
}

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

E
本题大致题意是，给出打击柱子数量即打击次数，然后给出每次打击中可能的目标对象，然后确定一个合理的打击序列，这让我们想到了基于二分图匹配的匈牙利算法：确定一个元素的匹配值，如果匹配值已经有其他元素占领，那么让占领此匹配值的元素换一个匹配值，最终达到一个合理的匹配。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
//int a[N][3];
int e[N<<1],ne[N<<1],h[N],idx,match[N<<1];
bool st[N];
void add(int a,int b)//链式前向星存图
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])//找邻接点
    {
        int j=e[i];
        if(st[j])continue;//已经被访问
        st[j]=true;
        if(!match[j]||dfs(match[j]))//未匹配或者可以让已经占领此柱子的元素换一个匹配值
        {
            match[j]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int w;
            cin>>w;
            add(w,i);   //柱子w可以在第i次打
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
         memset(st,false,sizeof st);//每次都要把标记数组复原
        if(dfs(i))ans++;//记录匹配数量
    }
    if(ans!=n)//只有匹配数量为n时，才能有合理的匹配的结果
    {
        puts("kou is angry");
        return 0;
    }
    for(int i=1;i<=n;i++)cout<<match[i]<<" ";
    return 0;
}

F
对于这个题目而言：我们可以首先先假设如果没有传送门的话最值是多少？

第一个点肯定要杀怪 体力：x - 1后续的话肯定是要把回到 1 这个点的路程考虑到，过去一个点消耗1， 杀怪消耗1，回来消耗1。 那么数量就是: min(n, (x - 1) / 3 + 1)

我们先计算一下能杀多少怪 (就是算有多少点) cnt = dep[A]（A路径的点） + depB - dep[lca(A, B)]（把不是A 、B路径的点去掉）+ 1（起始点房间的怪物）

然后计算一下体力的消耗 cur = cnt（杀怪的数量） + depA + depB + 1（传送阵的消耗）

那么只需要去遍历一遍这个 a[i] 数组求一下最值即可

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int dep[N], fa[N][20], a[N];
vector<int> e[N];

int n, x;

void dfs(int u, int pa){
    dep[u] = dep[pa] + 1;
    fa[u][0] = pa;
    for(int i = 1; i < 20; i++){ 
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    for(auto v : e[u]){
        if(v == pa) continue;
        dfs(v, u);
    }
}

int lca(int A, int B){
    if(dep[A] < dep[B]) swap(A, B);
    for(int i = 19; i >= 0; i--){
        if(dep[A] - (1 << i) >= dep[B]){
            A = fa[A][i];
        }
    }
    if(A == B) return A;

    for(int i = 19; i >= 0; i--){
        if(fa[A][i] != fa[B][i]){
            A = fa[A][i];
            B = fa[B][i];
        }
    }
    return fa[A][0];
}

int main()
{
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v), e[v].push_back(u);
    }

    dep[0] = -1;
    dfs(1, 0);

    int ans = min(n, (x - 1) / 3 + 1);
    for(int i = 1; i <= n; i++){
        int A = i, B = a[i];
        if(A == B) continue;
        int pa = lca(A, B);
        int cnt = dep[A] + dep[B] - dep[pa] + 1;
        int cur = cnt + dep[A] + dep[B] + 1;
//         cout << A << " " << B << endl;
        if(x >= cur) ans = max(ans, min(n, cnt + (x - cur) / 3));
    }

//     for(int i = 1;i <= n;i ++){
//         cout << dep[i] << " ";
//     }
//     cout << endl;
    cout << ans << endl;
    return 0;
}