T1给我一张凳子

正确代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    //freopen("step.in","r",stdin);
    //freopen("step.out","w",stdout);
    int n;
    cin>>n;
    vector<long long> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    long long t=0,cnt=0;
    for(int i=0;i<n;i++){
        cnt=max(cnt,a[i]);
        t+=cnt-a[i];
    }
    cout<<t;
    return 0;
}

T2枚举是不可能枚举的

解决方案

数学题:容斥原理+lcm+gcd

1. 总数t=b-a+1
2. cntc: b/c - (a-1)/c
3. cntd: b/d - (a-1)/d
4. BothCD: b/lcm(c,d)-(a-1)/lcm(c,d);
5. ans=1-2-3+4

正确代码

#include <bits/stdc++.h>
using namespace std;
typedef long long l;
l gcd(l a,l b){
    if(b == 0)return a;
    return gcd(b, a % b);
}
l f(l x,l y){
    return x/y;
}
int main() {
    //freopen("div.in","r",stdin);
    //freopen("div.out","w",stdout);
    l a,b,c,d;
    cin>>a>>b>>c>>d;
    l t=b-a+1;
    l cntc=f(b,c)-f(a-1,c);
    l cntd=f(b,d)-f(a-1,d);
    l g=gcd(c,d);
    l m=(c/g)*d;
    l cntm=0;
    if (m<=b||m>=a){
        cntm=f(b,m)-f(a-1,m);
    }
    l ans=t-(cntc+cntd-cntm);
    cout<<ans;
    return 0;
}

T3起遇质数

解决方案

1. 质数筛预处理范围内所有质数
2. 桶数组计数cnt[i]表示1~i之间满足条件的数的个数
3. l~r之间满足的个数为：cnt[r]-cnt[l-1];

正确代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int main(){
    //freopen("qy.in","r",stdin);
    //freopen("qy.out","w",stdout);
    vector<bool> ok(N,1);
    vector<int> sum(N,0);
    ok[0]=ok[1]=0;
    for(int i=2;i<N;i++){
        if(ok[i]){
            for(int j=i*2;j<N;j+=i){
                ok[j]=0;
            }
        }
    }
    sum[0]=0;
    for(int x=1;x<N;x++){
        sum[x]=sum[x-1];
        if(x%2==1){
            if(ok[x]){
                if(ok[(x+1)/2]){
                    sum[x]++;
                }
            }
        }
    }
    int q;
    cin>>q;
    while (q--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

T4魔法咒语

正确代码

#include <bits/stdc++.h>
using namespace std;
using l = long long;
int main() {
    //freopen("mana.in","r",stdin);
    //freopen("mana.out","w",stdout);
    l h,n;
    cin>>h>>n;
    vector<pair<l,l>> s(n);
    for(auto& [a,b]:s) cin>>a>>b;
    vector<l> dp(h+1,1e18);
    dp[0]=0;
    for (l j=0;j<=h;j++){
        for (const auto& [a,b]:s){
            l p = max(0LL,j-a);
            dp[j]=min(dp[j],dp[p]+b);
        }
    }
    cout<<dp[h];
    return 0;
}

T5简单路径统计

解决方案

DFS模板题

1. 存图，邻接表 vectoradj[N]
2. 从顶点1出发，遍历所有可能的路径
3. 需要vis数组标记走过的点，不能重复走
4. 注意边界判定，路径数>=10^6 停止。

正确代码

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
int cnt=0;
const int MAX=1e6;
void dfs(int u){
    if (cnt>=MAX) return;
    cnt++;
    vis[u]=1;
    for (int v:adj[u]){
        if (!vis[v]){
            dfs(v);
        }
    } 
    vis[u] =0;
}
int main(){
    int n,m;
    cin>>n>>m;
    adj.resize(n+1);
    vis.resize(n+1,0);
    for (int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    cout<<min(cnt,MAX);
    return 0;
}

T6自助餐

解决方案

对于每道菜，我们可以考虑将它作为最后一道菜，然后在剩下的时间（即使超过T-1）内吃完它。

正确代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    //freopen("free.in","r",stdin);
    //freopen("free.out","w",stdout);
    int n,t,dp[3010],ans=0;
    cin>>n>>t;
    pair<int,int> w[3010];
    for(int i=0;i<n;i++){
        cin>>w[i].first>>w[i].second;
    }
    sort(w,w+n);
    for(int i=0;i<n;i++){
        int a=w[i].first,b=w[i].second;
        if(t-1>=0) ans=max(ans,dp[t-1]+b);
        for(int j=t-1;j>=a;j--){
            dp[j]=max(dp[j],dp[j-a]+b);
        }
    }
    ans=max(ans,dp[t-1]);
    cout<<ans;
    return 0;
}

注：所有freopen已注释