Codeforces Round #299 (Div. 2) 题解

A、题意：输入0~99的数字，输出对应的英文拼写

解：注意一下30、40什么的不要输出thirty-zero就好了T_T

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/6/18 星期四 14:49:44
 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 int s;
17 string str[]={"zero",
18 "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
19 "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen",
20 "eighteen", "nineteen",
21 "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"
22 };
23 int main() {
24 #ifndef ONLINE_JUDGE
25     //freopen("in", "r", stdin);
26     //freopen("out", "w", stdout);
27 #endif
28     while(~scanf("%d", &s)) {
29         if(s<=20) cout<<str[s]<<endl;
30         else {
31             int b=s%10;
32             int a=s/10;
33             if(b==0) cout<<str[a+19-1]<<endl;
34             else cout<<str[a+19-1]<<"-"<<str[b]<<endl;
35         }
36     }
37     return 0;
38 }

View Code

B、题意：每个数位上仅包含4和7的十进制数称为lucky number，现在给你一个lucky number，问你它是第几个lucky number（1 based）

解：简单的组合数学

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/6/18 星期四 15:02:19
 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 int n;
17 int main() {
18 #ifndef ONLINE_JUDGE
19     freopen("in", "r", stdin);
20     //freopen("out", "w", stdout);
21 #endif
22     while(~scanf("%d", &n)) {
23         int base=1, ans=0;
24         while(n) {
25             int tmp=n%10; n/=10;
26             ans+=base*(tmp==7?2:1);
27             base<<=1;
28         }
29         printf("%d
", ans);
30     }
31     return 0;
32 }

View Code

C、题意：给你一个序列 h （1 based）代表一列某蔬菜的高度 h[i]=A+(i-1)*B（A，B均为正整数，已经给出）

然后给你一个位置 l ，问你做t次 m-bite 操作能将[l, r]区间内的蔬菜全吃光的最大r（如果[l, l]都吃不掉的话输出-1）

m-bite操作：同时吃不同的m个蔬菜一口（使他们的高度减一）

*注意：询问之间互不影响

解：一个有意思的yy：t*m>=区间内蔬菜高度和就一定能吃光

然后二分搜答案

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/6/18 星期四 15:14:14
 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 int64 A, B, N;
19 int64 L, T, M;
20 int main() {
21 #ifndef ONLINE_JUDGE
22     freopen("in", "r", stdin);
23     //freopen("out", "w", stdout);
24 #endif
25     while(~scanf("%I64d%I64d%I64d", &A, &B, &N)) {
26         for(int i=0; i<N; i++) {
27             scanf("%I64d%I64d%I64d", &L, &T, &M);
28             int64 base=A+(L-1)*B;
29             if(base>T) {
30                 puts("-1");
31                 continue;
32             }
33             int l=L, r=(T-A)/B+2;
34             while(l<r) {
35                 int m=(l+r)>>1;
36                 int64 top=A+(m-1)*B;
37                 if((top+base)*(m-L+1)/2<=T*M) l=m+1;
38                 else r=m;
39             }
40             printf("%d
", l-1);
41         }
42     }
43     return 0;
44 }

View Code

D、题意：给你一个串p，已知在全部由小写字母组成的串s上有一些位置i满足 s[i, i+|p|-1]==p，问你有多少种s存在，答案对1e9+7取模

解：KMP.问题实际是p串长度为i的前缀是否和长度为i的后缀相同，KMP的next数组可以方便的预处理出这个东西，注意M为0时的情况

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/6/19 星期五 14:32:37
 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 MOD=1e9+7;
19 
20 const int MaxA=1e6+7;
21 
22 int N, M;
23 int arr[MaxA];
24 char str[MaxA];
25 int len;
26 int nt[MaxA];
27 bool flag[MaxA]; ///flag[x]:p串的x长度前缀是否和x长度后缀相等
28 void getNext(char *str, int *nt) {
29     nt[0]=-1;
30     for(int i=0, j=1; str[j]; ) {
31         if(i==-1 || str[i]==str[j]) {
32             nt[++j]=++i;
33         } else {
34             i=nt[i];
35         }
36     }
37 }
38 int pow(int n) {
39     int64 ans=1;
40     int64 tmp=26;
41     while(n) {
42         if(n&1) ans=(ans*tmp)%MOD;
43         tmp=(tmp*tmp)%MOD;
44         n>>=1;
45     }
46     return ans;
47 }
48 int main() {
49 #ifndef ONLINE_JUDGE
50     freopen("in", "r", stdin);
51     //freopen("out", "w", stdout);
52 #endif
53     while(~scanf("%d%d", &N, &M)) {
54         scanf("%s", str);
55         for(int i=1; i<=M; i++) {
56             scanf("%d", &arr[i]);
57         }
58         len=strlen(str);
59         getNext(str, nt);
60         memset(flag, 0, sizeof(flag));
61         int pos=len;
62         while(pos!=-1) {
63             flag[pos]=1;
64             pos=nt[pos]; 
65         }
66         bool ok=1;
67         int cnt=0;
68         arr[0]=0;
69         for(int i=1; i<=M; i++) {
70             int dx=arr[i]-arr[i-1]-1;
71             if(dx<0) {
72                 if(!flag[-dx]) {
73                     ok=0; break;
74                 }
75             } else {
76                 cnt+=dx;
77             }
78             arr[i]+=len-1;
79             if(arr[i]>N) {
80                 ok=0; break;
81             }
82         }
83         cnt=M==0?N:cnt+N-arr[M];
84         printf("%d
", ok?pow(cnt):0);
85     }
86     return 0;
87 }

View Code

E、题意：比赛跑步+游泳，两个赛道长度分别是R和S，给你参赛选手的跑步速度ri和游泳速度si，问你在R、S不明确的情况下都有哪些选手可能获得冠军（完成全程用时最短）

解：将选手的速度坐标（1/ri, 1/si）画在平面直角坐标系下，由任何一个选手的比赛时间t=(S, R)*(1/ri, 1/si)，我们可以得出，速度点围成凸包的左下角又成为冠军的可能（投影最短），如下图所示：

*一个错误的思路：一开始想（ri， si）做点，求右上角凸包，凸包上的点就是答案。。。然而并不是，想一下数据：

 1 /*
 2  * Problem:  
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/6/20 星期六 14:37:58
 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=2e5+7;
19 
20 struct Point {
21     int id;
22     int64 x, y;
23     Point() {}
24     Point(int x, int y):x(x), y(y) {}
25     bool operator==(const Point& rhs) const {
26         return x==rhs.x && y==rhs.y;
27     }
28 } p[MaxA];
29 
30 int N;
31 int stk[MaxA], top;
32 int ans[MaxA], num;
33 bool cmp(const Point& A, const Point& B) {
34     return A.x>B.x || (A.x==B.x && A.y>B.y);
35 }
36 bool judge(Point a, Point b, Point o) {
37     return b.x*(o.x-a.x)*a.y*(o.y-b.y)
38         <a.x*(o.x-b.x)*b.y*(o.y-a.y);
39 }
40 int main() {
41 #ifndef ONLINE_JUDGE
42     freopen("in", "r", stdin);
43     //freopen("out", "w", stdout);
44 #endif
45     while(~scanf("%d", &N)) {
46         for(int i=0; i<N; i++) {
47             scanf("%I64d%I64d", &p[i].x, &p[i].y);
48             p[i].id=i+1;
49         }
50         sort(p, p+N, cmp);
51         top=0;
52         for(int i=0; i<N; i++) {
53             if(top>=1 && p[i].y<=p[stk[top]].y) continue;
54             while(top>=2 && judge(p[stk[top]], p[i], p[stk[top-1]])) top--;
55             stk[++top]=i;
56         }
57         num=0;
58         int pos=0;
59         for(int i=1; i<=top && pos<N; i++) {
60            // if(i>1 && p[stk[i]].y<=p[stk[i-1]].y) continue;
61             while(pos<N && cmp(p[pos], p[stk[i]])) pos++; 
62             while(pos<N && p[pos]==p[stk[i]]) ans[num++]=p[pos++].id; 
63         }
64         sort(ans, ans+num);
65         for(int i=0; i<num; i++) {
66             printf("%d%c", ans[i], " 
"[i==num-1]);
67         }
68     }
69     return 0;
70 }

View Code