Codeforces Round #312 (Div. 2) 题解

题意：在一条数轴上有n棵苹果树，给你每棵苹果树的位置和树上的苹果数。现在你在坐标0点，你可以选一个方向采集该方向上第一个没访问过的苹果树上的所有苹果，采集完后后调头做相同的事，知道目前方向上没有苹果树，问你最多能采集多少苹果

解：按坐标排序，肯定要把苹果树数目最少一侧的苹果树采集完

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/14 星期二 22:50:29
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long int64;
17 
18 const int MaxA=100+7;
19 
20 int n;
21 pair<int, int> p[MaxA];
22 int main() {
23 #ifndef ONLINE_JUDGE
24     freopen("in", "r", stdin);
25     //freopen("out", "w", stdout);
26 #endif
27     while(~scanf("%d", &n)) {
28         for(int i=0; i<n; i++) {
29             scanf("%d%d", &p[i].first, &p[i].second);
30         }
31         sort(p, p+n);
32         int pos=0;
33         while(pos<n && p[pos].first<0) pos++;
34         int b=n-pos, a=n-b;
35         int64 ans=0;
36         if(a>b) {
37             for(int i=pos; i<n; i++) {
38                 ans+=p[i].second;
39             }
40             b++;
41             for(int i=pos-1; b-- && i>=0; i--) {
42                 ans+=p[i].second;
43             }
44         } else {
45             for(int i=pos-1; i>=0; i--) {
46                 ans+=p[i].second;
47             }
48             a++;
49             for(int i=pos; a-- && i>=0; i++) {
50                 ans+=p[i].second;
51             }
52         }
53         printf("%I64d
", ans);
54     }
55     return 0;
56 }

View Code

B、Amr and The Large Array

题意：我们称一个数组中某数字出现最多次数为性质A的程度，如（{1， 1， 2， 2， 1}的性质A的程度为3， {1， 2， 1， 2}为2），问你和原数组性质A程度相同的最短子段的长度

解：~

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/14 星期二 22:50:29
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <map>
14 #include <vector>
15 
16 using namespace std;
17 
18 typedef long long int64;
19 
20 const int MaxA=1e5+7;
21 
22 int n;
23 int arr[MaxA];
24 int main() {
25 #ifndef ONLINE_JUDGE
26     freopen("in", "r", stdin);
27     //freopen("out", "w", stdout);
28 #endif
29     while(~scanf("%d", &n)) {
30         map<int, vector<int> > M;
31         for(int i=0; i<n; i++) {
32             scanf("%d", &arr[i]);
33             M[arr[i]].push_back(i);
34         }
35         map<int, int> vis;
36         int tmp=-1;
37         for(const auto& u : M) {
38             if((int)u.second.size()>tmp) {
39                 vis.clear();
40                 tmp=(int)u.second.size();
41                 vis[u.first]=1;
42             } else if((int)u.second.size()==tmp) {
43                 vis[u.first]=1;
44             }
45         }
46         int ans=0x7f7f7f7f;
47         int st, ed;
48         for(int i=0; i<n; i++) {
49             if(vis.find(arr[i])!=vis.end()) {
50                 vector<int>& u=M[arr[i]];
51                 if(u.back()-u[0]<ans) {
52                     ans=u.back()-u[0];
53                     st=u[0];
54                     ed=u.back();
55                 }
56             }
57         }
58         printf("%d %d
", st+1, ed+1);
59     }
60     return 0;
61 }

View Code

C、Amr and Chemistry

题意：给你n个数，你可以花费1对任一个数x进行（a、x=2*x b、x=x/2 整除）两种操作，问你最小花费多少使得所有数等大

解：将数字化成二进制，取最长公共前缀，然后消去后面不齐的，问题就变成了n个有长有短的木棒，你可以进行花费来增减任一木棒的长度。。。那么变成所有木棒的中位数长度花费最小了

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/14 星期二 22:50:29
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <map>
14 #include <vector>
15 
16 using namespace std;
17 
18 typedef long long int64;
19 
20 const int MaxA=1e5+7;
21 
22 int n;
23 int arr[MaxA];
24 vector<int> lis[MaxA];
25 int main() {
26 #ifndef ONLINE_JUDGE
27     freopen("in", "r", stdin);
28     //freopen("out", "w", stdout);
29 #endif
30     while(~scanf("%d", &n)) {
31         for(int i=0; i<n; i++) {
32             scanf("%d", &arr[i]);
33             lis[i].clear();
34             int x=arr[i];
35             do {
36                 lis[i].push_back(x&1);
37                 x>>=1;
38             } while(x);
39         }
40         for(int i=0; i<n; i++) reverse(lis[i].begin(), lis[i].end());
41         int ed=-1;
42         for(int j=0; ed==-1; j++) {
43             if(j==(int)lis[0].size()) {
44                 ed=j;
45                 break;
46             }
47             int tmp=lis[0][j];
48             for(int i=1; i<n; i++) {
49                 if(j==(int)lis[i].size() || tmp!=lis[i][j]) {
50                     ed=j;
51                     break;
52                 }
53             }
54         }
55         int64 ans=0;
56         int64 sum=0;
57         for(int i=0; i<n; i++) {
58             int pos=-1;
59             for(int j=ed; j<(int)lis[i].size(); j++) {
60                 if(lis[i][j]!=0) {
61                     pos=j;
62                     break;
63                 }
64             }
65             if(pos!=-1) {
66                 int cnt=(int)lis[i].size()-pos;
67                 ans+=cnt;
68                 arr[i]=lis[i].size()-cnt;
69             } else  arr[i]=(int)lis[i].size();
70             sum+=arr[i];
71         }
72         sort(arr, arr+n);
73         int64 x;
74         if(n&1) x=arr[n>>1];
75         else x=(arr[n>>1]+arr[n/2-1])>>1;
76         for(int i=0; i<n; i++) ans+=abs(x-arr[i]);
77         printf("%I64d
", ans);
78     }
79     return 0;
80 }

View Code

D、Guess Your Way Out! II

题意：题目好长~所幸不是很难懂。。。看原题吧

解：把操作区间全部化成最后一层，然后排排序乱搞的，这题主要考察码力吧？优雅的写法能省很多功夫

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/7/14 星期二 22:50:29
 5  * File Name: 233.cpp
 6  * State: 
 7  * Memo: 
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <map>
14 #include <vector>
15 
16 using namespace std;
17 
18 typedef long long int64;
19 
20 const int MaxA=1e5+7;
21 
22 int h, q;
23 pair<int64, int64> p[MaxA];
24 int level, op;
25 int64 L, R, l, r;///[l, r)为通过肯定判断得出的解区间
26 int n;
27 int main() {
28 #ifndef ONLINE_JUDGE
29     freopen("in", "r", stdin);
30     //freopen("out", "w", stdout);
31 #endif
32     while(~scanf("%d%d", &h, &q)) {
33         n=0;
34         l=1LL<<(h-1); r=1LL<<h;
35         bool ok=1;
36         for(int i=0; i<q; i++) {
37             scanf("%d%I64d%I64d%d", &level, &L, &R, &op);
38             if(!ok) continue;
39             L<<=h-level;
40             R=(R+1)<<(h-level);
41             if(op) {
42                 l=max(L, l); r=min(R, r);
43             } else {
44                 p[n++]=make_pair(L, R);        //左闭右开区间
45             }
46         }
47         p[n++]=make_pair(r, r);    ///加入这个会降低代码量
48                                 ///而且[r, r)为空区间，不影响
49         sort(p, p+n);
50         int flag=-1;
51         int64 ans=-1;
52         for(int i=0; i<n; i++) {
53             int64 x=p[i].first, y=p[i].second;
54             if(r<=l) break;
55             if(y<=l) continue;
56             if(l<x) {
57                 if(l+1<x || ans!=-1) {
58                     flag=0;
59                     break;
60                 }
61                 ans=l;
62             }
63             l=y;
64         }
65         if(flag==0) puts("Data not sufficient!");
66         else if(ans==-1) puts("Game cheated!");
67         else printf("%I64d
", ans);
68     }
69     return 0;
70 }

View Code

E、A Simple Task

题意：给你一个串，和一些操作，操作是选定串上的一段区间把他们按升序或降序排序，要你输出在这些操作过后的串

解：由于字符集只有26，对每一种字符，统计它的位置，然后每次排序后修改，用线段树完成统计修改

具体是建26棵线段树，每棵对应一种字符，线段树结点保存该字符在某区间内的出现次数

  1 /*
  2  * Problem:  
  3  * Author:  SHJWUDP
  4  * Created Time:  2015/7/16 星期四 12:22:59
  5  * File Name: 233.cpp
  6  * State: 
  7  * Memo: 
  8  */
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13 
 14 using namespace std;
 15 
 16 const int MaxA=1e5+7;
 17 
 18 struct SegmentTree {
 19     struct Node {
 20         int cnt, flag;
 21     } tree[26][MaxA<<2];
 22 
 23     Node* c;
 24     int id;
 25 #define lson l, m, rt<<1
 26 #define rson m+1, r, rt<<1|1
 27 #define INIT Node& u=c[rt]; Node& ls=c[rt<<1]; Node& rs=c[rt<<1|1];
 28 
 29     void chID(int _id) {
 30         id=_id;
 31         c=tree[id];
 32     }
 33 
 34     void pushUp(int rt) {
 35         INIT
 36         u.cnt=ls.cnt+rs.cnt;
 37     }
 38 
 39     void pushDown(int l, int m, int r, int rt) {
 40         INIT
 41         if(~u.flag) {
 42             ls.flag=u.flag; ls.cnt=(m-l+1)*u.flag;
 43             rs.flag=u.flag; rs.cnt=(r-m)*u.flag;
 44             u.flag=-1;
 45         }
 46     }
 47 
 48     void build(char* s, int l, int r, int rt) {
 49         c[rt].flag=-1;
 50         if(l==r) {
 51             c[rt].cnt=s[l]==(id+'a');
 52         } else {
 53             int m=(l+r)>>1;
 54             build(s, lson);
 55             build(s, rson);
 56             pushUp(rt);
 57         }
 58     }
 59 
 60     int query(int L, int R, int l, int r, int rt) {
 61         if(L<=l && r<=R) {
 62             return c[rt].cnt;
 63         } else {
 64             int m=(l+r)>>1;
 65             pushDown(l, m, r, rt);
 66             int res=0;
 67             if(L<=m) res+=query(L, R, lson);
 68             if(m<R) res+=query(L, R, rson);
 69             return res;
 70         }
 71     }
 72 
 73     void update(int L, int R, int x, int l, int r, int rt) {
 74         if(L<=l && r<=R) {
 75             c[rt].flag=x;
 76             c[rt].cnt=(r-l+1)*x;
 77         } else {
 78             int m=(l+r)>>1;
 79             pushDown(l, m, r, rt);
 80             if(L<=m) update(L, R, x, lson);
 81             if(m<R) update(L, R, x, rson);
 82             pushUp(rt);
 83         }
 84     }
 85 } st;
 86 
 87 int n, q;
 88 char str[MaxA];
 89 int cnt[26];
 90 int main() {
 91 #ifndef ONLINE_JUDGE
 92     freopen("in", "r", stdin);
 93     //freopen("out", "w", stdout);
 94 #endif
 95     while(~scanf("%d%d", &n, &q)) {
 96         scanf("%s", str);
 97         for(int i=0; i<26; i++) {
 98             st.chID(i); st.build(str, 0, n-1, 1);
 99         }
100         while(q--) {
101             int L, R, op;
102             scanf("%d%d%d", &L, &R, &op); L--; R--;
103             if(op) {
104                 int cnt=0;
105                 for(int i=0; i<26; i++) {
106                     st.chID(i); int tmp=st.query(L, R, 0, n-1, 1);
107                     if(!tmp) continue;
108                     st.update(L, R, 0, 0, n-1, 1);
109                     st.update(L+cnt, L+cnt+tmp-1, 1, 0, n-1, 1);
110                     cnt+=tmp;
111                 }
112             } else {
113                 int cnt=0;
114                 for(int i=25; i>=0; i--) {
115                     st.chID(i); int tmp=st.query(L, R, 0, n-1, 1);
116                     if(!tmp) continue;
117                     st.update(L, R, 0, 0, n-1, 1);
118                     st.update(L+cnt, L+cnt+tmp-1, 1, 0, n-1, 1);
119                     cnt+=tmp;
120                 }
121             }
122         }
123         for(int i=0; i<n; i++) {
124             for(int j=0; j<26; j++) {
125                 st.chID(j);
126                 if(st.query(i, i, 0, n-1, 1)) {
127                     putchar('a'+j);
128                     break;
129                 }
130             }
131         }
132         puts("");
133     }
134     return 0;
135 }

View Code