NOIP 鸡王争霸赛

竞赛时间： 2018 年 8 月 23 日
By –老王
最终测试均打开 O2 优化

bag	vest	helmet
bag.in	vest.in	helmet.in
bag,out	vest.out	helmet.out
2s	2s	2s
512MB	512MB	512MB
忽略行末空格和 回车	忽略行末空格和 回车	忽略行末空格和 回车
传统	传统	传统

Problem A:三级包（bag.c/cpp/pas）

Input file: bag.in
Output file: bag.out
Time limit: 2 seconds
Memory limit: 512 megabytes

老王被同学拉去吃鸡，一落地就捡到了三级包，同时地上还有很多其他老王
想要带走的东西， M416、 5.56 子弹、垂直握把、 8 倍镜等等，但是显然老王不
能带走所有的东西。老王的三级包比较奇特，不仅有重量限制，而且有物品个数
限制。地上的每一种装备个数都记为 1 并有自己的重量，老王想要在不超过限制
的情况下带走尽可能重的东西，为了帮助老王吃鸡，请你来完成这个问题。
Input
第一行两个正数 n、 m 分别表示三级包的个数限制和容量限制
第二行一个整数 k 表示地上的装备数量
接下来一行 k 个整数， 第 i 个整数

Output
输出一共一行一个整数， 表示老王能带走的最大重量

Example

Sample Input1

5 100
8
8 64 17 23 91 32 17 12

Sample Output1

99

Sample Input2

5 10
3
99 99 99

Sample Output2

0

Notes
有30%的数据，满足k ≤ 15。
另有20%的数据，满足k ≤ 20。
另有20%的数据，满足n ≤ 6。
对于100%的数据， k ≤ 40， n ≤ 35， 未提及的数据均是1到10^9之间的整数。

30 分解法： 2 ^n爆搜即可
50 分解法： 30 分做法随便剪枝优化一下
70 分解法： 因为n ≤ 6，可以从1~n枚举选取物品个数，然后
爆搜， C[k][6]也没多大，所以跑过毫无压力(+50 分做法)

100 分解法：
先预处理前一半物品， 枚举这部分物品的所有选取集合， 并
用 set 存下来 S[i]里面存放选取物品数量不超过 i 的所有权值
集合。同样，枚举后一半物品的所有选取集合，并到对应的
set 里面二分查找满足要求的最大权值即可，时间复杂度
O(tlogt)

感谢黄学长（神犇）原代码

//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int w[50],n,m,k;
int cnt1[1<<21],cnt2[1<<21];
ll sum1[1<<21],sum2[1<<21],ans;
vector<ll> v[50];
int lowbit(int x)
{
    return x&-x;
}
int main()
{
     cin>>n>>m>>k;
    for(int i=1;i<=k;i++)cin>>w[i];
    if(k==1)
    {
        if(w[1]<=m)cout<<w[1];
        else cout<<0;
        return 0;
    }
    int mid=k/2;
    int tot=(1<<mid)-1;
    for(int i=1;i<=mid;i++)sum1[1<<i-1]=w[i];//压缩1集合 
    for(int s=1;s<=tot;s++)
    {
        sum1[s]=sum1[s^lowbit(s)]+sum1[lowbit(s)];//s集合为sum1[s^lowbit(s)]的集合（s去掉lowbits位）情况加上lowbit位的情况 （lowbits位为一） 
        cnt1[s]=cnt1[s^lowbit(s)]+1;//个数限制 
        if(sum1[s]<=m&&cnt1[s]<=n)//满足条件 
        {
            ans=max(ans,sum1[s]);
            v[cnt1[s]].push_back(sum1[s]);//在选择cnt1个物品的情况下的一个代价 
        }
    }
    for(int i=1;i<=mid;i++)sort(v[i].begin(),v[i].end());
    for(int i=1;i+mid<=k;i++)sum2[1<<i-1]=w[i+mid];//压缩2集合 
    mid=k-mid;
    tot=(1<<mid)-1;
    vector<ll>::iterator it;
    for(int s=1;s<=tot;s++)
    {
        sum2[s]=sum2[s^lowbit(s)]+sum2[lowbit(s)];
        cnt2[s]=cnt2[s^lowbit(s)]+1;
        if(cnt2[s]<=n&&sum2[s]<=m)
        {
            ans=max(ans,sum2[s]);
            for(int j=1;j<=n-cnt2[s];j++)//和一集合匹配 
            if(!v[j].empty())
            {
                it=upper_bound(v[j].begin(),v[j].end(),m-sum2[s]);//二分查找满足要求的最大权值 
                if(it!=v[j].begin())
                {
                    it--;
                    ans=max(ans,(*it)+sum2[s]);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

Problem B:三级甲（vest.c/cpp/pas）

Input file: vest.in
Output file: vest.out
Time limit: 2 seconds
Memory limit: 512 megabytes

在皮卡多捡到了一件三级甲的老王非常兴奋， 想马上测试一下三级甲的性能，
于是老王走到了加油站旁边的空地上跳俄舞，不一会儿身上就被打了一排子弹，
老王躲起来后脱下三级甲，发现这一排弹孔深度不一，聪明的老王想到了一个量
化计算性能的方法，给定一个 k(k ≤ n)，计算出所有长度为 k 的区间的弹孔深度
的最小值的和，当然 k 值不同，得到的性能值也不同，所以老王会取不同的 k 进
行计算，为了帮助老王吃鸡，这个问题就交给你来解决。
Input
第一行两个正数 n、 m 分别表示弹孔个数和询问次数
第二行共 n 个整数，表示这一排每个弹孔的深度

Output
输出共 m 行，每行输出一个整数表示对应询问的答案

Example

Sample Input1

2 2
1 1
1

2

Sample Output1

2

1

Sample Input2

5 3
10 3 20 30 11

2

4

5

Sample Output2

37

6

3

Sample Input3

9 5
11 33 78 55 26 100 200 89 98
2

3

4

5

6

Sample Output3

429

300

204

115

89

30 分解法：随便怎么做
50 分解法：分析每一个元素对于不同询问区间长度的贡献，
l 为它到左边第一个比他小元素的距离， r 为它到右边第一个
比他小元素的距离，那么可以发现，贡献呈这种趋势“
于是可以预处理每个元素的 l， r， O(1)即可得到每个元素对
所询问区间长度的贡献，于是O(  n^2)

60 分解法： 50 分+送的 10 分
100 分解法： 注意到，所询问就是如上图中多个梯形，在某
一个 x 处的权值和，而上述梯形又显然可分成三段，两段公
差为 1 的等差数列和一段常数数列，于是三段分开前缀后缀
之类的O(n)预处理一下，每个询问O(1)，于是最终复杂度
O(n)

//
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
    char ch=nc();
    int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
typedef long long ll;
ll ans1[1000005],ans2[1000005];
int n,m;
int a[1000005],l[1000005],r[1000005];
stack<int> s;
int main()
{
    n=rd(),m=rd();
    for(int i=1; i<=n; i++)
    {
        a[i]=rd();
    }
    s.push(0);
    for(int i=1; i<=n; i++)
    {
        while(!s.empty()&&a[s.top()]>a[i])//如果a[i]小于栈顶元素
        {
            r[s.top()]=i-1; //栈顶最右不能超过a[i]
            s.pop();
        }
        if(!s.empty()&&a[s.top()]==a[i])//特判相等
        {
            l[i]=l[s.top()];//左取小于等于 
            r[s.top()]=i-1;//右不取
            s.pop();
        }
        else l[i]=s.top()+1;//栈顶元素小于a[i]，a[i]最左不能超过顶元素
        s.push(i);//i号入栈
    }
    while(!s.empty())r[s.top()]=n,s.pop();// 栈内还有元素则说明没有a[i]小于等于栈顶元素，则栈顶元素最小，最右影响到n号
    int L,R;
    for(int i=1; i<=n; i++)//讨论i号点的贡献
    {
        L=i-l[i]+1;//L到R区间分情况讨论
        R=r[i]-i+1;
        if(L<=R)
            //if(k<=L)ans+=k*a[i];梯形左边
            //if(L<k<R)ans+=L*a[i];梯形上边
            //if(R<=k<=R+L)ans+=(R+L-k)*a[i];梯形右边
            //分有无k进行差分
        {
            if(L>1)
            {
                ans2[1]+=a[i];//差分ans2:a[i] 
                ans2[L]-=a[i];
            }
            ans1[L]+=1ll*L*a[i];
            ans1[R+1]-=1ll*L*a[i];
            if(R+1<=L+R-1)
            {
                ans1[R+1]+=1ll*(R+L)*a[i];
                ans1[L+R]-=1ll*(R+L)*a[i];
                ans2[R+1]-=a[i];
                ans2[L+R]+=a[i];
            }
        }
        else
        {
            if(R>1)
            {
                ans2[1]+=a[i];
                ans2[R]-=a[i];
            }
            ans1[R]+=1ll*R*a[i];
            ans1[L+1]-=1ll*R*a[i];
            if(L+1<=L+R-1)
            {
                ans1[L+1]+=1ll*(L+R)*a[i];
                ans1[L+R]-=1ll*(L+R)*a[i];
                ans2[L+1]-=a[i];
                ans2[L+R]+=a[i];
            }
        }
    }
    int x;
    for(int i=1; i<=n; i++)ans1[i]+=ans1[i-1],ans2[i]+=ans2[i-1];
    for(int i=1; i<=n; i++)ans1[i]+=ans2[i]*i;//补回 k*a[i]
    while(m--)
    {
        x=rd();
        printf("%lld\n",ans1[x]);
    }
}