codeforces #381 div2
http://codeforces.com/contest/740
A:现在有n个某种物品，要买k个使得n+k是4的倍数，可以的购买方案为a元1个，b元2个，c元3个，每种方案都可以买无限多。
思路：需要注意买多个未必比买少个贵..
所以分情况讨论：n%4==0，输出0
n%4==1，需要买3+4k个，
可以的方案为，买1个c，或者3个a，或者1个a 1个b（此处用价钱指代方案，下同）
n%4==2时，需要买2+4k个
可以的方案为：2个a，或者1个b，或者2个c
n%4==3时，需要买4K+1个
可以的方案为：1个a,或者1个b+1个c，或者3个c
注意要开long long.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月24日 星期四 08时09分32秒
4File Name :code/cf/#381/A.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int main()
34{
35 #ifndef ONLINE_JUDGE
36 freopen("code/in.txt","r",stdin);
37 #endif
38 LL n,a,b,c;
39 cin>>n>>a>>b>>c;
40 LL mn = 0 ;
41 if (n%4==0)
42 {
43 mn = 0 ;
44 }
45 else if (n%4==1)
46 {
47 mn = min(3LL*a,a+b);
48 mn = min(mn,c);
49 }else if (n%4==2)
50 {
51 mn = min(2LL*a,b);
52 mn = min(mn,2*c);
53 }else if (n%4==3)
54 {
55 mn = a;
56 mn = min(mn,b+c);
57 mn = min(mn,3LL*c);
58 }
59 printf("%lld\n",mn);
60
61 #ifndef ONLINE_JUDGE
62 fclose(stdin);
63 #endif
64 return 0;
65}
B:
题意：给出n个数，以及m个子串，从中选若干个（可以不选或者全选），女孩的幸福值的计算方法为：a[i]*cnt[i]，a[i]为值，cnt[i]为第i个数在选中的子串里出现了几次（只考虑位置，相同的值算成不同的数）
思路：n,m很小，一个子串如果最后收益为正，就选，否则不选，暴力即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月24日 星期四 08时09分46秒
4File Name :code/cf/#381/B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n,m;
35int a[N];
36int sum[N];
37int main()
38{
39 #ifndef ONLINE_JUDGE
40 freopen("code/in.txt","r",stdin);
41 #endif
42 ms(sum,0);
43 cin>>n>>m;
44 for ( int i = 1 ; i <= n ; i++) cin>>a[i];
45 for ( int i = 1; i <= m ; i++)
46 {
47 int l,r;
48 scanf("%d%d",&l,&r);
49 for ( int j = l ; j <= r ; j++) sum[i] = sum[i] + a[j];
50 }
51 int ret = 0 ;
52 for ( int i =1 ; i <= m ; i++) if (sum[i]>0) ret = ret + sum[i];
53 cout<<ret<<endl;
54
55
56 #ifndef ONLINE_JUDGE
57 fclose(stdin);
58 #endif
59 return 0;
60}
c:题意：m个区间，要求构造一个长度为n的数组，满足m个区间中，每个区间的mex值中的最小值最大。
s思路：很容易想到的是…这个最大的mex 不可能超过每一组区间长度，假设最小的区间长度为mn
那么是否一定可以构造出mex为mn的数组呢？
是的。
只需要按照
0,1,2…mn-1,0,1….的方式构造即可。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月24日 星期四 09时00分04秒
4File Name :code/cf/#381/C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,m;
35struct node
36{
37 int l,r;
38 int len;
39 bool operator < ( node b)const
40 {
41 if (r==b.r) return l<b.l;
42 return r<b.r;
43 }
44}a[N];
45int ans[N];
46int main()
47{
48 #ifndef ONLINE_JUDGE
49 freopen("code/in.txt","r",stdin);
50 #endif
51 scanf("%d%d",&n,&m);
52 int mx = inf ;
53 for ( int i = 1; i <= m ; i++)
54 {
55 scanf("%d%d",&a[i].l,&a[i].r);
56 a[i].len = a[i].r-a[i].l+1;
57 mx = min(mx,a[i].len);
58 }
59 printf("%d\n",mx);
60 int cur = 0 ;
61 for ( int i = 1 ; i <= n ; i++)
62 {
63// cout<<"miao"<<endl;
64 ans[i] = cur;
65 cur++;
66 cur = cur % mx;
67 }
68 for ( int i = 1; i <= n ; i++) printf("%d ",ans[i]);
69 printf("\n");
70
71
72 #ifndef ONLINE_JUDGE
73 fclose(stdin);
74 #endif
75 return 0;
76}
d:题意：一棵树，给出边权和点权，定义点v控制点u，当且仅当u是v的子树中的点，并且dis(u,v)<=a[u]，其中dis(u,v)为点u到点v路径上的边权和，a[u]为点u的点权，现在问对于每个节点v，其能控制的点有多少个。
思路：先写了个rmq+dfs的lca。。。那么任意两个点的距离都可以O(1)得到了。然后不会了233333.
upd:和lca没有什么关系，因为一个点能控制另一个点这两个点一定在一条通向根的链上，因此距离直接减一下就好了。
机智的做法：dfs的时候维护一个栈，对于栈中序列，后面一半是对当前点有贡献的。问题时求对于每个v统计其能控制多少个u，现在我们固定u，考虑能控制他的v。这些v在树上的形态时一条链 ，借助第二类前缀和的思想，对于u标记+1，对于u往上的离根最近的且能统治u的v上面的一个标记-1，然后dfs后序遍历（也就是链的起点时距离根远的那一边），距离处理的时候，只需要在递归之后更新ans就好了。
栈里面维护，到哪个节点，从根下来，边权和最大，找边权和>=当前边权和-a[u]的地方。
启示：由于两个存在统治关系的点在一条链上，边权都为正，边权和具有单调性，单调的东西，容易想到二分处理。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月24日 星期四 09时17分48秒
4File Name :code/cf/#381/D.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=2E5+7;
32int n;
33int a[N];
34LL dis[N];
35vector< pair<int,LL> >edge[N];
36vector< pair<LL,int> >path;
37int ans[N];
38void dfs( int u,int pre)
39{
40 ans[u]++;
41 int idx = lower_bound(path.begin(),path.end(),make_pair(dis[u]-a[u],-1))-path.begin()-1;
42 if (idx>=0) ans[path[idx].sec]--;
43 path.push_back(make_pair(dis[u],u));
44 for ( auto x : edge[u])
45 {
46 int v = x.first;
47 if (v==pre) continue;
48 dis[v] = dis[u] + x.sec;
49 dfs(v,u);
50 ans[u]+=ans[v];//后序遍历...链的起点原理根，终点靠近根
51 }
52 path.pop_back();
53}
54int main()
55{
56 #ifndef ONLINE_JUDGE
57 freopen("code/in.txt","r",stdin);
58 #endif
59 cin>>n;
60 ms(dis,0);
61 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
62 for ( int i =2 ; i <= n ; i++)
63 {
64 int u,v;
65 LL w;
66 u = i ;
67 scanf("%d%lld",&v,&w);
68 edge[u].push_back(make_pair(v,w));
69 edge[v].push_back(make_pair(u,w));
70 }
71 dfs(1,0);
72 for ( int i = 1 ; i <= n ; i++) printf("%d ",ans[i]-1);
73 #ifndef ONLINE_JUDGE
74 fclose(stdin);
75 #endif
76 return 0;
77}
e:题意：那个数，定义hill为一段连续的区间，满足该区间为严格单峰。现在有若干操作，每个操作是对某段区间的数同时增加一个数，问每次操作后，所有的hill中，宽度最大的（区间长度最大）的是多少。
思路：同时增加一个数很线段树。。。但是要维护什么呢。。。？
猜测：肯定要维护一个区间中hill的最大宽度…
但是合并的时候要怎么办呢。。。
考虑两个方向的合并。。。
所以还要维护一个区间中，包含右端点的向左单调减延伸的长度，以及左端点的值。
同理，要维护一个区间中，包含左端点的向右单调增延伸的长度，以及右端点的值。
那么每次pushup的时候，就是两个区间hill的最大值，以及两个方向合并的最大值中取最大。。。
。。。上面是我口胡的。。。