2018-team7-CF26

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

状态不好，打得很糟糕，寝室里不敢写代码，跑到外面楼道写- -

遇到一题区间覆盖WA成dog

D题傻吊题

本意是按照题意模拟 从前往后背包

实际上不是 你会发现很难判断一个背包之前是不是不能再放了，如果继续放会让答案出错

因此就必须倒着做
错误代码示例

{{{
#!c
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[202000];
ll weight[202000];
ll a[202000];
int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    int now=1;//first box
    bool ok=false;//I know...
    for(int i=1;i<=n;++i){
        if(weight[now]+a[i]<=k){
            weight[now]+=a[i];
            cnt[now]++;
        }
        else{
            now++;
            if(now==m+1){
                now=1;
            }
            if(weight[now]){
                cnt[now]=0;
                weight[now]=0;
            }
            i--;
        }
    }
    for(int i=1;i<=m;++i) ans+=cnt[i];
    cout<<ans<<endl;
    return 0;
}
}}}

状态不好，打得很糟糕，寝室里不敢写代码，跑到外面楼道写- -

遇到一题区间覆盖WA成dog

D题傻吊题

本意是按照题意模拟 从前往后背包

实际上不是 你会发现很难判断一个背包之前是不是不能再放了，如果继续放会让答案出错

因此就必须倒着做

错误代码示例

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cnt[202000];
ll weight[202000];
ll a[202000];
int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    int now=1;//first box
    bool ok=false;//I know...
    for(int i=1;i<=n;++i){
        if(weight[now]+a[i]<=k){
            weight[now]+=a[i];
            cnt[now]++;
        }
        else{
            now++;
            if(now==m+1){
                now=1;
            }
            if(weight[now]){
                cnt[now]=0;
                weight[now]=0;
            }
            i--;
        }
    }
    for(int i=1;i<=m;++i) ans+=cnt[i];
    cout<<ans<<endl;
    return 0;
}