Codeforces #381(div2)

A.题目：http://codeforces.com/contest/740/problem/A

　题意：现有n本书，买一本书需要花a元，两本书b元，三本书c元，问买够书是4的倍数所需要的最小花费

　思路：n%4=1的时候可以3a a+b c n%4=2 2a b 2c n%4==3 a b+c 3c 取个最小值就好了

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int main(){
 7     long long  n,a,b,c;
 8     while(scanf("%lld %lld %lld %lld",&n,&a,&b,&c)!=EOF){
 9         long long ans;
10         if(n%4==0){
11             printf("0
");
12             continue;
13         }
14         else if(n%4==1){
15             ans=min(3*a,c);
16             ans=min(a+b,ans);
17         }
18         else if(n%4==2){
19             ans=min(2*a,b);
20             ans=min(ans,c*2);
21         }
22         else if(n%4==3){
23             ans=min(a,b+c);
24             ans=min(ans,3*c);
25         }
26         printf("%lld
",ans);
27     }
28     return 0;
29 }

B：题目：http://codeforces.com/contest/740/problem/B

　　题意：有n朵花每朵花有自己的价值ai，正或者负，现在有m个建议的区间，选择其中一些区间，计算花被选中的次数ki,求s=(a1*k1+a2*k2...+an*kn)的最大值

　　思路：最后总的值是看每个区间的贡献，也就是区间的价值如果大于0就加上去

　　代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn=110;
 7 int a[maxn];
 8 int n,m;
 9 struct node{
10     int l,r;
11 };
12 node num[maxn];
13 int main(){
14     while(scanf("%d %d",&n,&m)!=EOF){
15         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
16         int sum=0;
17         for(int i=1;i<=m;i++){
18             scanf("%d %d",&num[i].l,&num[i].r);
19             int val=0;
20             for(int j=num[i].l;j<=num[i].r;j++){
21                 val+=a[j];
22             }
23             if(val>0) sum+=val;
24         }
25         printf("%d
",sum);
26     }
27     return 0;
28 }

C：题目：http://codeforces.com/contest/740/problem/C

　　题意：有m个区间，构造一个长度为n的序列，使得m个区间中的mex(a[i]..a[j])的最小值最大，mex(a[i]..a[j])代表i到j这个区间中最小的没有出现过的非负整数

　　思路：m个区间中最小mex肯定是看区间长度最小的那一个并且mex=区间长度，之后的区间长度都大于或者等于它，而我们只需要mex最小的尽量大就行了，也就是其他区间的只要一定有区间长度最小的那个区间里面的数就行了，那么我们循环输出最小的区间长度，那么m个区间里面肯定都会包括这些数

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn=1e5+10;
int n,m;
int a[maxn];
set<int> s;
struct node{
    int l,r;
    int len;
};
node num[maxn];
bool cmp(const node&a,const node&b){
    return a.len<b.len;
}
bool cmp1(const node&a,const node&b){
    return a.l<b.l;
}
int main(){
    while(scanf("%d %d",&n,&m)!=EOF){
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d %d",&x,&y);
            num[i].l=x,num[i].r=y;
            num[i].len=y-x+1;
        }
        sort(num+1,num+1+m,cmp);
        int tmp=num[1].len;
        printf("%d
",tmp);
        for(int i=1;i<=n;i++){
            printf("%d%c",i%tmp,i==n?'
':' ');
        }

    }
    return 0;
}

D：题目：http://codeforces.com/contest/740/problem/D

　　题意：有n个节点的树，以1为根，每个点有权值a[i],每条边也有权值w[i]，如果v是u的父亲节点并且dis(u,v)<=a_u 则表示v能控制u点，输出每个点能控制多少个点

　　思路：注意到u是儿子节点，也就是找到最远能控制u的父亲节点v，那么这一条路上所有的u的父亲都能控制u，也就是给这条路径上所有的节点+1，那么输出的时候只要统计每个节点的子树和就行了，当前节点是u，最远的能控制u的父亲节点v，假设v的父亲节点是v0，dfs序给树编号，那么一棵子树的编号肯定都是连着的，用树状数组维护和，查询v能控制多少个节点的时候只要查询v的子树和，但v0控制不了u，也就是在v0的位置-1，倍增找节点。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn=2e5+10;
 8 struct node{
 9     int u;
10     int v;
11     long long dis;
12 };
13 vector<node> G[maxn];
14 int id[maxn];
15 int outId[maxn];
16 int fa[maxn][25];
17 long long  dis[maxn];
18 long long  tree[maxn<<1];
19 int n;
20 void add(int i,int k){
21     for(;i<=maxn;i+=(i&(-i))) tree[i]+=k;
22 }
23 long long query(int i){
24     long long sum=0;
25     for(;i>0;i-=(i&(-i))) sum+=tree[i];
26     return sum;
27 }
28 int cnt=0;
29 void dfs(int x){
30     id[x]=++cnt;
31     for(int i=1;i<=20;i++){
32         fa[x][i]=fa[fa[x][i-1]][i-1];
33     }
34     for(int i=0;i<G[x].size();i++){
35         int v=G[x][i].v;
36         if(fa[v][0]) continue;
37         fa[v][0]=x;
38         dis[v]=dis[x]+G[x][i].dis;
39         dfs(v);
40     }
41     outId[x]=cnt;
42 }
43 int a[maxn];
44 int main(){
45     scanf("%d",&n);
46     cnt=0;
47     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
48     for(int i=2;i<=n;i++){
49         int x,y;
50         scanf("%d %d",&x,&y);
51         node tmp;
52         tmp.dis=y,tmp.v=i;
53         G[x].push_back(tmp);
54     }
55     fa[1][0]=1;
56     dis[1]=0;
57     dfs(1);
58     long long Dis;
59     for(int i=1;i<=n;i++){
60         int now=i;
61         add(id[i],1);
62         for(int j=20;j>=0;j--){
63             if (dis[i]-dis[fa[now][j]]<=a[i]) now=fa[now][j];
64         }
65         if (now!=1) add(id[fa[now][0]],-1);
66     }
67     for(int i=1;i<=n;i++){
68         printf("%lld ",query(outId[i])-query(id[i]-1)-1);
69     }
70     printf("
");
71 }

不用倍增二分栈的写法

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <vector>
 6 using namespace std;
 7 const int maxn=2e5+10;
 8 long long stk[maxn];
 9 struct node{
10     int v;
11     long long dis;
12 };
13 int a[maxn];
14 long long dis[maxn];
15 int ans[maxn];
16 int stkid[maxn];
17 vector<node> G[maxn];
18 void dfs(int x,int cnt){
19     stk[cnt]=dis[x];
20     stkid[cnt]=x;
21     int v0=lower_bound(stk,stk+cnt+1,dis[x]-a[x])-stk-1;
22     ans[x]++,ans[stkid[v0]]--;
23     for(int i=0;i<G[x].size();i++){
24         node it=G[x][i];
25         dis[it.v]=dis[x]+it.dis;
26         dfs(it.v,cnt+1);
27         ans[x]+=ans[it.v];
28     }
29 }
30 int main(){
31     int n;
32     while(scanf("%d",&n)!=EOF){
33         memset(ans,0,sizeof(ans));
34         for(int i=1;i<=n;i++){
35             scanf("%d",&a[i]);
36             G[i].clear();
37         }
38         for(int i=2;i<=n;i++){
39             int x;
40             node tmp;
41             tmp.v=i;
42             scanf("%d %lld",&x,&tmp.dis);
43             G[x].push_back(tmp);
44         }
45         dis[1]=0;
46         dfs(1,1);
47         for(int i=1;i<=n;i++){
48             printf("%d ",ans[i]-1);
49         }
50         printf("
");
51     }
52     return 0;
53 }

E，F留坑