伥乐集训DAY3

考试100，改后200

石子合并

优先队列板题

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
priority_queue<ull,vector<ull>,greater<ull> > q;
ull ans,n,a,b;
int main(){
    freopen("gouli.in","r",stdin);
    freopen("gouli.out","w",stdout); 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        ull k;
        cin>>k;
        q.push(k);
    }   
    while(q.size()>=2){
        a=q.top();
        q.pop();
        b=q.top();
        q.pop();
        ans+=(a*b);
        q.push(a+b);
    }
    cout<<ans<<endl;
    return 0;
}

货物收集

二分

糖果分配

简单分析后预处理，之后可以利用DP解决
改后AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
ll n,c,f[402][402],f2[402][402],l[402],r[402],cc;
inline int pw(ll n,ll m){
    ll ans=1;
    while(m>0){
        if(m&1){
            ans=ans*n;
        }
        m>>=1;
        n*=n;
    }
    return ans;
}
inline void read(ll& a){
    ll s=0,w=1;
    char ch=getchar();
    while(ch<&#039;0&#039;||ch>&#039;9&#039;){
        if(ch==&#039;-&#039;){
            w=-1;
        }
        ch=getchar();
    }
    while(ch>=&#039;0&#039;&&ch<=&#039;9&#039;){
        s=s*10+ch-&#039;0&#039;;
        ch=getchar();
    }
    a=s*w;
}
int main(){
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    read(n);read(c);
    for(int i=1;i<=n;i++){
        read(l[i]);
    }
    for(int i=1;i<=n;i++){
        read(r[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=l[i];j<=r[i];j++){
            cc=1;
            for(int k=0;k<=c;k++){
                f2[i][k]+=cc;
                f2[i][k]%=mod;
                cc*=j;
                cc%=mod;
            }
        }
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=c;j++){
            for(int k=0;k<=j;k++){
                f[i][j]+=((f[i-1][j-k]%mod)*(f2[i][k]%mod))%mod;
                f[i][j]%=mod;
            }
        }
    }
    cout<<f[n][c]%mod;
    return 0;
}

雨中池塘

数学问题+栈维护

In a word

相当不错