个人题解

T1

题意：给定一个环状数组，求否存在一个长度为n的递增区间

思路：

破环成链，复制多一份，然后逆序枚举，当长度为n的时候就输出YES

#include <iostream>
using namespace std;
const int N=2e5+7;
int n;
int a[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    int len=1;
    int end=a[2*n];
    for(int i=2*n-1;i>=1;i--){
        if(a[i]<=a[i+1])len++;
        else{
            len=1;
            end=a[i];
        }
        if(len==n){
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int _;
    cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

T2

题意：分组背包模板题，注意输入顺序。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e4+7;
const int M=1e9+7;
typedef long long ll;
typedef vector<int> vt;
int n,m,k;
string s,t;
ll ans;
int cost[N],val[N];
int len;
int f[N];
//已知阴阳师有N个模式可以操作，模式i有ai种操作，但每种模式每日只能选用一种操作，可以不选。操作j能收益vj，但需要花费体力wj点。xinjun每日拥有体力M点，求他每日最多能得到多少收益。
void solve(){
    cin>>n>>m;
    memset(f,0,sizeof f);
    memset(cost,0,sizeof cost);
    memset(val,0,sizeof val);
    for(int i=1;i<=n;i++){ //前i个分组
        cin>>len;
        for(int j=1;j<=len;j++){ //每次枚举当前分组的开销和价值
            cin>>val[j];
        }
        for(int j=1;j<=len;j++){
            cin>>cost[j];
        }
        for(int j=m;j>=0;j--){
            for(int k=1;k<=len;k++){
                if(j>=cost[k])f[j]=max(f[j],f[j-cost[k]]+val[k]);
            }
        }
    }
    cout<<f[m]<<"\n";
    return;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

T3

不会，打个暴力得25分走人，搜了一下是提高/省选的题目，当年安徽OI省选的题目，不知道拿这种题目放机试模拟上来何意味

T4

经典老题，luogu上有，记 $f[i][j]$ 为数字i分成j份的方案数

#include <iostream>
using namespace std;
int n,k;
int f[207][10];

int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        f[i][1]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=2;j<=k;j++){
            if(i>=j)f[i][j]=f[i-1][j-1]+f[i-j][j];
        }
    }
    cout<<f[n][k];
}

T5

思路：贪心，我们每次选最小能装入的，如果有多个能装入的选（奖励-体积）最大的，有点像安全性检测算法，在实现上可以用set或者排序，这里我写蠢了别学我

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=2e5+7;
const int M=1e9+7;
typedef long long ll;
typedef vector<int> vt;
int n,m;
struct node{
    int cost,val;
    bool operator < (const node a) const {
        if(cost!=a.cost)return cost<a.cost;
        else return val-cost>a.val-a.cost;
    }
};


multiset<node> tmp;
void solve(){
    cin>>n>>m;
    tmp.clear();
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        tmp.insert({x,y});
    }
    for(auto& x:tmp){
        if(x.cost>m){
            cout<<"no\n";
            return;
        }
        else m+=x.val-x.cost;
    }
    cout<<"yes\n";
    return;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}