【Codeforces #169 Div2】Solutions

　　转载请注明出处：http://www.cnblogs.com/Delostik/archive/2013/02/25/2932004.html

　　做了仨题还掉分简直没天理了TAT...不过第四题没写对真是可惜，看来是变不紫了...

【A.Lunch Rush】

　　http://www.codeforces.com/contest/276/problem/A

　　题目大意：求ans=max{f[i]-max(0,t[i]-k)}

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n,k,ans=-2147483640,a,b;
 5 
 6 int main(){
 7     cin>>n>>k;
 8     for(int i=1;i<=n;i++){
 9         cin>>a>>b;
10         ans=max(ans,a-max(0,(b-k)));
11     }
12     cout<<ans<<endl;
13     return 0;
14 }

【B.Little Girl and Game】

　　http://www.codeforces.com/contest/276/problem/B

　　题目大意：给定字符串s，两人轮流操作，每次从中拿走一个字符。当某一方在拿走之前可将字符串重组成回文串即获胜。问是否先手必胜。

　　构成回文串的条件是：最多存在一个字母出现了奇数次，这样出现偶数次的字母就可以对称放在两侧。设当前出现奇数次的字母有n个：

　　当n=0、1时为先手必胜态；

　　n=2时先手必败；

　　n=3时，先手可以通过拿走一个出现奇数次的字母，使对方出现必败态；

　　n=4时，先手可以拿偶数次的字母使n'=5，但对方也可以拿这个字母使先手继续面对n=4；但先手如果拿奇数次字母使n'=3，则对方面临必胜态。

　　综上......这是个水题......

View Code

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 string s;
 6 int cnt,a[30];
 7 
 8 int main(){
 9     cin>>s;
10     int len=s.length();
11     for(int i=0;i<len;i++)
12         a[s[i]-'a']++;
13     for(int i=0;i<26;i++)
14         if(a[i]&1) cnt++;
15     if(!cnt || cnt&1) cout<<"First"<<endl;
16     else cout<<"Second"<<endl;
17     return 0;
18 }

【C.Little Girl and Maximum Sum】

　　http://www.codeforces.com/contest/276/problem/C

　　题目大意：有若干对区间和的查询，问如何重组数组使查询结果的和最大。

　　显然查询次数最多的点让他权值最大就好了（排序不等式），关键是怎么统计每个点的查询次数...

　　方法1：前缀和，这是博主推荐的方法

View Code

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int n,q,l,r;
 6 long long a[200010],t[200010],ans;
 7 
 8 int main(){
 9     cin>>n>>q;
10     for(int i=0;i<n;i++)
11         cin>>a[i];
12     sort(a,a+n);
13     for(int i=0;i<q;i++){
14         cin>>l>>r;
15         t[l-1]++,t[r]--;
16     }
17     for(int i=1;i<n;i++)
18         t[i]+=t[i-1];
19     sort(t,t+n);
20     for(int i=0;i<n;i++)
21         ans+=a[i]*t[i];
22     cout<<ans;
23     return 0;
24 }

　　方法2：线段树，要是非想这么做博主当然也不拦着...

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #define lch(x) x<<1
 7 #define rch(x) (x<<1)+1
 8 using namespace std;
 9 
10 int n,q,l,r,c,a[200010],b[200010];
11 char sym[2];
12 long long ans;
13 
14 struct T_node{
15     int sum,add;
16     int l,r,size;
17 }tree[800010];
18 
19 void build(int v,int l,int r){
20     tree[v].l=l,tree[v].r=r;
21     if(l==r) tree[v].size=1;
22     else{
23         build(lch(v),l,(l+r)>>1);
24         build(rch(v),((l+r)>>1)+1,r);
25         tree[v].sum=tree[lch(v)].sum+tree[rch(v)].sum;
26         tree[v].size=tree[lch(v)].size+tree[rch(v)].size;
27     }
28 }
29 
30 void pushdown(int v){
31     if(tree[v].l!=tree[v].r){
32         tree[lch(v)].add+=tree[v].add,tree[lch(v)].sum+=tree[v].add*tree[lch(v)].size;
33         tree[rch(v)].add+=tree[v].add,tree[rch(v)].sum+=tree[v].add*tree[rch(v)].size;
34     }
35     tree[v].add=0;
36 }
37 
38 void modify(int v,int l,int r){
39     pushdown(v);
40     if(l==tree[v].l && r==tree[v].r) tree[v].add+=1,tree[v].sum+=tree[v].size;
41     else{
42         int mid=(tree[v].l+tree[v].r)>>1;
43         if(r<=mid) modify(lch(v),l,r);
44         else if(l>mid) modify(rch(v),l,r);
45         else{
46             modify(lch(v),l,mid);
47             modify(rch(v),mid+1,r);
48         }
49         tree[v].sum=tree[lch(v)].sum+tree[rch(v)].sum;
50     }
51 }
52         
53 int query(int v,int x){
54     pushdown(v);
55     if(x==tree[v].l && x==tree[v].r) return tree[v].sum;
56     int mid=(tree[v].l+tree[v].r)>>1;
57     if(x<=mid) return query(lch(v),x);
58     else if(x>mid) return query(rch(v),x);
59 }
60 
61 int main(){
62     cin>>n>>q;
63     for(int i=1;i<=n;i++)
64         cin>>a[i];
65     sort(a+1,a+1+n);
66     build(1,1,n);
67     for(int t=1;t<=q;t++){
68         cin>>l>>r;
69         modify(1,l,r);
70     }
71     for(int i=1;i<=n;i++)
72         b[i]=query(1,i);
73     sort(b+1,b+1+n);
74     for(int i=1;i<=n;i++){
75         ans+=(long long)a[i]*(long long)b[i];
76     }
77     cout<<ans<<endl;
78     return 0;
79 }

【D.Little Girl and Maximum XOR】

　　http://www.codeforces.com/contest/276/problem/D

　　题目大意：在区间[l,r]中找到ans=max{a^b}，l≤a,b≤r。

　　先找打l和r最高的不同的那一位，设a≥b，那么a一定是1XXXXXXX，b一定是0XXXXXXX，在区间[l,r]内最优解便是a=1000000，b=01111111 = =!

View Code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long l,r,i;
 5 
 6 int main(){
 7     cin>>l>>r;
 8     for(i=63;i>=0;i--)
 9         if((l^r)&(1LL<<i)) break;
10     cout<<(1LL<<(i+1))-1;
11     return 0;
12 }

【E.Little Girl and Problem on Trees】

　　http://www.codeforces.com/contest/276/problem/E

　　题目大意：给定一棵树，操作1：将以节点v为中心，与v距离不超过d的节点权值都+w；操作2，查询某一节点权值。

　　题目中有一句话说每个节点的度不超过2，也就意味着，去掉根节点后，树将变成若干条链。对每一条链分别进行维护，使用树状数组或线段树。

　　但是可能出现需要更新很多条链的情况，这样一来每次操作就完全退化成O(n)，所以需要一个额外的树状数组，维护相同深度的节点的增加值。

　　感谢wyl8899讲解~另外下面代码没A掉，大概是指针比较慢的缘故，改成数组模拟就能A了。。。

View Code

 1 #include <cstdio>
 2 #include <vector>
 3 #define mm 200010
 4 #define mn 100010
 5 #define lowbit(x) ((x)&(-x))
 6 using namespace std;
 7 
 8 struct EDGE{
 9     int pnt;
10     EDGE *pre;
11     EDGE(){}
12     EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
13 }Edge[mm],*SP=Edge,*edge[mn];
14 
15 inline void addedge(int a,int b){
16     edge[a]=new(++SP)EDGE(b,edge[a]);
17 }
18 
19 int n,q,x,y,v,w,d,tot,opt,root,bng[mn],pos[mn],len[mn],fa[mn],son[mn];
20 vector<int> tree[mn];
21 
22 void add(vector<int> &c,int x,int key){
23     for(;x<c.size();x+=lowbit(x)) c[x]+=key;
24 }
25 
26 int get(vector<int> c,int x){
27     int res=0;
28     for(;x>0;x-=lowbit(x)) res+=c[x];
29     return res;
30 }
31 
32 void dfs(int x,int father){
33     fa[x]=father;
34     for(EDGE *j=edge[x];j;j=j->pre)
35         if(j->pnt!=father){
36             son[x]=j->pnt;
37             dfs(j->pnt,x);
38         }
39 }
40 
41 void build_tree(){
42     for(EDGE *j=edge[1];j;j=j->pre,tot++){
43         dfs(j->pnt,1);
44         for(int i=j->pnt;i;i=son[i])
45             bng[i]=tot,pos[i]=++len[tot];
46         tree[tot].resize(len[tot]+1);
47     }
48     tree[tot].resize(n+1);
49 }
50 
51 int main(){
52     scanf("%d%d",&n,&q);
53     for(int i=1;i<n;i++){
54         scanf("%d%d",&x,&y);
55         addedge(x,y),addedge(y,x);
56     }
57     build_tree();
58     while(q--){    
59         scanf("%d",&opt);
60         if(opt){
61             scanf("%d",&v);
62             if(v==1) printf("%d\n",root);
63             else printf("%d\n",get(tree[bng[v]],pos[v])+get(tree[tot],pos[v]));
64         }else{
65             scanf("%d%d%d",&v,&w,&d);
66             if(v==1){
67                 root+=w;
68                 add(tree[tot],1,w);
69                 add(tree[tot],d+1,-w);
70             }else{
71                 add(tree[bng[v]],max(pos[v]-d,1),w);    //向上
72                 add(tree[bng[v]],pos[v]+d+1,-w);        //向下
73                 if(d>=pos[v]){
74                     root+=w;
75                     if(d>pos[v]){
76                         add(tree[tot],1,w);add(tree[tot],d-pos[v]+1,-w);
77                         add(tree[bng[v]],1,-w);add(tree[bng[v]],d-pos[v]+1,w);
78                     }
79                 }
80             }
81         }
82     }
83     return 0;
84 }