题目链接

A.打怪

题意：





题解：

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=3e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int h,a,H,A;
        cin>>h>>a>>H>>A;
        if(a>=H)cout<<-1;
        else {
            int k=(H-1)/a;
            int p=A*k;
            cout<<(h-1)/p;
        }
        cout<<endl;
    }


    return 0;
}

B.吃水果

题意：




题解：

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=3e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int a,b;
        cin>>a>>b;
        int ans=0;
        if(a>b)swap(a,b);
        while(1){
            if(a==b){cout<<ans+a<<endl;break;}
            if(a*2<=b)a*=2,ans++;
            if(a*2>b)a--,b--,ans++;
        }
    }


    return 0;
}

C.四个选项

题意：



题解：

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=3e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

vector<int> v;
int a,b,c,d,m,n;
int fa[20],cnt[20],ans;
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void dfs(int i,int xa,int xb,int xc,int xd){
    if(xa==a&&xb==b&&xc==c&&xd==d)ans++;
    if(i==n)return;
    if(xa+v[i]<=a)dfs(i+1,xa+v[i],xb,xc,xd);
    if(xb+v[i]<=b)dfs(i+1,xa,xb+v[i],xc,xd);
    if(xc+v[i]<=c)dfs(i+1,xa,xb,xc+v[i],xd);
    if(xd+v[i]<=d)dfs(i+1,xa,xb,xc,xd+v[i]);
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    cin>>a>>b>>c>>d>>m;

    for(int i=1;i<=12;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        int p=find(x),q=find(y);
        fa[p]=q;
    }
    for(int i=1;i<=12;i++)cnt[find(i)]++;
    for(int i=1;i<=12;i++)
        if(cnt[i])v.pb(cnt[i]);
    n=v.size();
    dfs(0,0,0,0,0);
    cout<<ans;
    return 0;
}

D.最短路变短了

题意：



题解：

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct edge{
    ll u,v,w;
}e[200010];
int n,m;
vector<pll> g1[maxn],g2[maxn];
ll d1[maxn],d2[maxn];
void dij(ll dis[],vector<pll> g[],int s){
    for(int i=1;i<=n;i++)dis[i]=inf*inf;
    dis[s]=0;
    priority_queue<pll,vector<pll>,greater<pll> > q;
    q.push(mp(0,s));
    while(!q.empty()){
        pll p=q.top();
        q.pop();
        int u=p.se;
        if(dis[u]<p.fi)continue;
        for(auto i:g[u]){
            int v=i.fi;
            ll w=i.se;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(mp(dis[v],v));
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        g1[u].pb(mp(v,w));
        g2[v].pb(mp(u,w));
        e[i]={u,v,w};
    }
    dij(d1,g1,1);dij(d2,g2,n);
    int q;cin>>q;
    while(q--){
        ll x;
        cin>>x;
        if(d1[e[x].v]+d2[e[x].u]+e[x].w<d1[n])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}