NOIP 鸡王争霸赛

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
",ans1[x]);
    }
}

Problem C:三级头（helmet.c/cpp/pas）

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


捡到三级甲不久后，老王发现了一个空投，走进发现周围全是尸体，而且每
个尸体上都有不同破烂程度的三级头，而且所有尸体又恰好构成了一棵树形结构，
老王正奇怪，突然从箱子背后跳出一个吉利服男子问老王问题，如果打对了就把
装备送给老王：最开始以 1 号尸体为根，有两种操作，

(1)询问以 i 为根的子树中

三级头耐久度严格大于 k 的有几个；

(2)指定 i 为根；

(3)修改 i 号尸体的三级头耐

久度为 x。为了帮助老王吃鸡，请你来回答这个问题！
Input
第一行两个正整数 n、 m 分别表示尸体个数和操作次数；
第二行 n 个整数 wj分别表示每个尸体上三级头的耐久度；
接下来 n-1 行每行两个整数 i、 j，表示 i、 j 之间有边相连；
一个空行之后， 接下来 m 行，每行表示一次操作：
若是第一种操作，则有三个整数： 1、 i、 k；
若是第二种操作， 则有两个整数： 2、 i；
若是第三种操作，则有三个整数： 3、 i、 x。

Output
输出行数与 1 类型操作次数相等，每行表示对应操作的答案

Example

Sample Input1

5 3
15 18 20 8 10
4 3
4 2
3 1
2 5
1 4 8
3 2 1
1 3 10

Sample Output1

2

1

Sample Input2

7 4
26 22 8 5 21 28 5
6 1
6 3
1 7
1 4
4 2
7 5
1 3 22
1 1 10
2 7
1 4 5

Sample Output2

0

4

1

Notes
有20%的数据， n, m ≤ 2000。
另有40%的数据， 没有 3 类型操作
对于100%的数据， n, m ≤ 100000， 1 ≤ wj≤10^9

20 分做法：随你怎么做
60 分做法： 没有三类型操作，这就意味着权值是恒定的，离
线即可。处理出每一个询问时相应的根，并将询问按照询问
的权值排序， dfs 序+树状数组解决即可（如果新根在子树外，
dfs 序区间无影响，若在子树内，则分为前后两个区间）
100 分做法： dfs 序后分块， 并维护块内有序， 这样询问时，
到对应的块中二分查找一下即可，多出来的暴力处理即可，
时间复杂度O(nt logt) 

 1 #include<stdio.h>
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 struct node
 5 {
 6     int to;
 7     int next;
 8 }edge[300000];
 9 int head[100005],num;
10 long long a[100005],dep[100005],fa[100005],A[100005];
11 int n,q,aa,bb,xx,yy;
12 void add(int x,int y)
13 {
14     edge[++num].to=y;
15     edge[num].next=head[x];
16     head[x]=num;
17 }
18 void dfs(int u,int Fa)
19 {
20     fa[u]=Fa;
21     dep[u]=dep[Fa]+1;
22     for(int i=head[u];i;i=edge[i].next)
23     {
24         int v=edge[i].to;
25         if(v!=Fa)
26         dfs(v,u);
27     }
28 }
29 bool OK()
30 {
31 int cnt=0;
32     while(xx!=yy)
33     {
34         if(dep[xx]<dep[yy])swap(xx,yy);
35         A[++cnt]=a[xx];
36         xx=fa[xx];
37         if(cnt>36)return 1;
38     }
39     A[++cnt]=a[xx];
40     if(cnt<4)return 0;
41     sort(A+1,A+cnt+1);
42    for(int i=4;i<=cnt;i++)
43    if(A[i]<A[i-1]+A[i-2]+A[i-3])return 1;
44     return 0;
45 }
46     
47 int main()
48 {
49     ios::sync_with_stdio(false);
50     cout.tie(NULL);
51     cin>>n;
52     for(int i=1;i<=n;i++)
53     cin>>a[i];
54     for(int i=1;i<n;i++)
55     {
56         cin>>aa>>bb;
57         add(aa,bb);
58         add(bb,aa);
59     }
60     dfs(1,0);
61     cin>>q;
62     for(int i=1;i<=q;i++)
63     {
64         cin>>aa;
65         if(aa==1)
66         {
67             cin>>xx>>yy;
68             a[xx]=yy;
69         }
70         if(aa==2)
71         {
72             cin>>xx>>yy;
73             if(OK())cout<<"Yes"<<endl;
74             else cout<<"No"<<endl;
75         }
76     }
77 }
78     
79
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/CXYscxy/p/11758046.html