codeforces round 169 div2 题解
http://codeforces.com/problemset/problem/276/A
A：题意：有n家餐馆，a[1]~a[n],在每家餐馆有一个欢乐度fi和时间ti，给你一个常数k，对于每家餐馆若ti>k,则获得fi-（ti-k）点欢乐度，否则增加fi点欢乐度，问在哪家餐馆吃饭获得的欢乐度最大。。。。
思路：SB题，直接枚举不解释。。。
http://codeforces.com/contest/276/problem/B
B:题意：首先给一个字符串，博弈，两个人轮流从字符串中随意删除一个元素，当一个人取之前，当前字符串是一个回文串时，这个人取得胜利，问对于给定的字符串，事先取的人必胜还是后取的人必胜。
思路：首先，要搞明白什么样的字符串是回文串，设字符串的长度为len，因为回文串是左右对称的，则若len为偶数，则字符串的每个字符个数均为偶数，若len为奇数，则除了中间的那个字符的总个数为奇数外，其他也均为偶数，所以游戏就是要避免达到总个数为奇数的字符的个数为0或1（。。。有点拗口哈。。。），我们一开始把所有字符的个数求出来，找出其个数为奇数的字符的个数，设为num,若num为0或1，则显然先手必胜，否则，我们先考虑num=2，这时先手若取走一个字符使num-1，则这时后手就胜利了，所以先手不能使num-1，只能去一个字符使num+1，这时后手就可以去一个字符将num-1，这时又回到了开始的状态，我们一直这样取下去，因为字符越来越少，最后会变成只剩下2个字符个数为奇数，其他都为0，这时先手不得不去掉一个字符使num=1，这时还是后手胜利，所以对于num=2时是后手必胜，我们可以一直按这个策略，则对于num>=2，num为偶数时，后手必胜，否则先手必胜。
http://codeforces.com/contest/276/problem/C
C:题意：给你n个数，q个询问，询问在[l,r]区间数的总和，要求重新排列这n个数，使得这q个询问所得到的总和最大。
思路：贪心即可，显然，对于询问越频繁的位置设的数越大越好，可以用线段树将每个位置询问的次数求出来，将原数列排序之后，找到询问数最大的位置将答案加上询问次数*当前最大数，然后将这个位置清零，继续寻找最大值即可。
#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>#define maxn 100010using namespace std;#define mid ((t[p].l+t[p].r)>>1)#define ls (p<<1)#define rs (ls|1)//以下为树状数组int c[maxn];int lowbit(int x){ return x&(-x);}void addval(int x,int val,int n){ while(x<=n) { c[x]+=val; x+=lowbit(x); }}int getsum(int x){ int sum=0; while(x>0) { sum+=c[x]; x-=lowbit(x); } return sum;} //以下为线段树struct node{ int l,r; int val;}t[maxn<<2];void pushdown(int p){ if(t[p].val) { t[ls].val+=t[p].val; t[rs].val+=t[p].val; t[p].val=0; }}void build(int p,int l,int r){ t[p].l=l,t[p].r=r; t[p].val=0; if(l==r) { return; } build(ls,l,mid); build(rs,mid+1,r);}void add(int p,int l,int r,int val){ if(t[p].l==l&&t[p].r==r) { t[p].val+=val; return; } pushdown(p); if(r<=mid) add(ls,l,r,val); else if(l>mid) add(rs,l,r,val); else { add(ls,l,mid,val); add(rs,mid+1,r,val); }}int getval(int p,int x){ if(t[p].l==t[p].r) return t[p].val; pushdown(p); if(x>mid) return getval(rs,x); else return getval(ls,x);}//以下是建树struct edge{ int to; int next;}e[maxn<<1];int box[maxn],cnt;void init(){ memset(box,-1,sizeof(box)); cnt=0;}void add(int from,int to){ e[cnt].to=to; e[cnt].next=box[from]; box[from]=cnt++;}int dep[maxn],pre[maxn],child[maxn],scc=0;int max(int a,int b){ return a>b?a:b;}void dfs(int now,int deep){ dep[now]=deep; pre[now]=++scc; child[now]=scc; int tt,w; for(tt=box[now];tt+1;tt=e[tt].next) { w=e[tt].to; if(!pre[w]) { dfs(w,deep+1); child[now]=max(child[now],child[w]); } }}int inout[maxn];int min(int a,int b){ return a<b?a:b;}int main(){ freopen("dd.txt","r",stdin); int n,q,i,a,b,root,tmp=0; memset(c,0,sizeof(c)); memset(inout,0,sizeof(inout)); scanf("%d%d",&n,&q); init(); for(i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); inout[a]++; inout[b]++; } for(i=1;i<=n;i++) { if(inout[i]>tmp) { tmp=inout[i]; root=i; } } dfs(root,0); build(1,1,n); while(q--) { int t,v,x,d; scanf("%d",&t); if(t) { scanf("%d",&v); int ans=getval(1,pre[v])+getsum(n+1-dep[v]); printf("%d\n",ans); } else { scanf("%d%d%d",&v,&x,&d); if(v!=root) add(1,pre[v],min(child[v],pre[v]+d),x); if(dep[v]>d) { add(1,pre[v]-d,pre[v]-1,x); } else { if(pre[v]-dep[v]+1<=pre[v]-1) add(1,pre[v]-dep[v]+1,pre[v]-1,x); addval(n+1-d+dep[v],x,n+1); if(v!=root&&pre[v]-dep[v]+1<=min(child[v],pre[v]-2*dep[v]+d)) add(1,pre[v]-dep[v]+1,min(child[v],pre[v]-2*dep[v]+d),-x); } } } return 0;}