怅乐集训DAY7

考试25，改后300

选课管理

完全背包板子，看错题（无数次看成一次），10分
附AC代码

#include
using namespace std;
long long m,n,w[1000002],c[1000002],dp[10000002];
int main(){
    freopen("class.in", "r", stdin);
    freopen("class.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0); 
    cin>>n>>m;
    for(int i=1;i>w[i]>>c[i];
    }
    for(int i=1;i<=n;i++){
        for(int v=w[i];v<=m;v++){
            dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
        }
    }
    cout<<dp[m];
    return 0;
}

足球比赛

考试代码没交上，第二天代码还丢了
思路差不多，干脆交了标程

优质序列

考试15，改后100
倍长，单调队列维护即可，否则n²只可以得60-

#include
using namespace std;
#define ll long long
struct Mon_queue_top{
    ll ad,num;
}top[3000002];
inline void read(ll &x) {
    x = 0;
    ll f = (ll)1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) {
        if (c == '-')
            f = -f;
    }
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
ll n,a[2000004],ans,l=1,r;
int main(){
    freopen("genes.in", "r", stdin);
    freopen("genes.out", "w", stdout);
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n-1;i++){
        a[i]+=a[i-1];
    }
    for(int i=1;i<=2*n-1;i++){
        while(l<=r&&top[l].ad<(i-n)){
            l++;
        }
        while(la[i]){
            r--;
        }
        r++;
        top[r].ad=i;
        top[r].num=a[i];
        if(i>=n&&top[l].num-a[i-n]>=0){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

矩阵求交

线段树

总结

怅