Codeforces Round #315 (Div. 2)

这次可以说是最糟糕的一次比赛了吧，心没有静下来好好的去思考，导致没有做好能做的题。

Problem_A:

题意：

　　你要听一首时长为T秒的歌曲，你点击播放时会立刻下载好S秒，当你听到没有加载到的地方时，就会重头听，直到可以听完整首歌，

　　由于网络堵塞，你在q秒内只有q-1秒用于下载，问需要重新多少次，第一次点击播放也算。

思路：

　　由题意可知，下载速度为(q - 1) / q ，假设t秒后听歌的进度和下载的进度一样，即听到没有下载的地方or已经下载完。

　　可以得到方程：

　　　　　　　　　　(q - 1) / q * t + s = t

　　　　　　　　　　化简得：t / q = (t - s) / (q - 1)

　　　　　　　　　　求解得：t = q * s

　　即此时进度为t, 当t >= T时，即下载完，模拟即可。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 1000000
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define p(x) printf("%d
", x)
25 #define pd(x) printf("%.7lf
", x)
26 #define k(x) printf("Case %d: ", ++x)
27 #define s(x) scanf("%d", &x)
28 #define sd(x) scanf("%lf", &x)
29 #define mes(x, d) memset(x, d, sizeof(x))
30 #define do(i, x) for(i = 0; i < x; i ++)
31 #define dod(i, x, l) for(i = x; i >= l; i --)
32 #define doe(i, x) for(i = 1; i <= x; i ++)
33 int T, S, q;
34 
35 int main()
36 {
37     scanf("%d %d %d", &T, &S, &q);
38     int ans = 0;
39     while(S < T)
40     {
41         S *= q;
42         ans ++;
43     }
44     printf("%d
", ans);
45     return 0;
46 }

View Code

Problem_B:

题意：

　　给一个数n，再给n个数a[i]，a[i]中会有重复或者大于n的数。

　　要求你给出一个1~n的排列。

思路：

　　求一个排列，那么将不符合的数用符合的数代替即可。

　　将a[i]中大于n 和小于等于n 且重复的数的编号index记录下来

　　然后用1~n中没有出现过的数替换掉即可。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 100010
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define p(x) printf("%d
", x)
25 #define pd(x) printf("%.7lf
", x)
26 #define k(x) printf("Case %d: ", ++x)
27 #define s(x) scanf("%d", &x)
28 #define sd(x) scanf("%lf", &x)
29 #define mes(x, d) memset(x, d, sizeof(x))
30 #define do(i, x) for(i = 0; i < x; i ++)
31 #define dod(i, x, l) for(i = x; i >= l; i --)
32 #define doe(i, x) for(i = 1; i <= x; i ++)
33 int n;
34 int a[MAXN];
35 int ans[MAXN];
36 int ord[MAXN];
37 bool vis[MAXN];
38 
39 int main()
40 {
41     int x;
42     int cnt, t;
43     scanf("%d", &n);
44     cnt = 0;
45     t = 0;
46     mes(ans, 0);
47     mes(ord, 0);
48     mes(vis, false);
49     for(int i = 0; i < n; i ++)
50     {
51         scanf("%d", &a[i]);
52         if(vis[a[i]] || a[i] > n) ord[cnt ++] = i;
53         else if(!vis[a[i]])
54             vis[a[i]] = true;
55     }
56     int k1 = 0;
57     for(int i = 1; i <= n; i ++)
58         if(!vis[i]) a[ord[k1 ++]] = i;
59     for(int i = 0; i < n; i ++)
60         printf("%d ", a[i]);
61     printf("
");
62     return 0;
63 }

View Code

Problem_C:

题意：

　　给两个数， p, q。求满足π(n) ≤ A * rad(n) 的n 的最大取值。

　　π(n)是小于等于n的素数个数， rad(n)是小于等于n的回文数的个数， A = p / q。

思路：

　　首先，回文数比较少，200w以内也只有2998个，而 A 最大为42， 2998 * 42 = 125916

　　而200W以内的素数有148933个 > 125916，而越往上， n越大，素数越来越多，而且增长幅度大于回文数，所以，最大数只能是在200W以内寻找。

　　将所有的素数和回文数预处理出来，然后循环寻找最大的n，复杂度为O(2 * 10 ^ 5)， q可以乘过去，避免处理浮点数。

代码：

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <ctime>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <queue>
10 #include <string>
11 #include <vector>
12 #include <fstream>
13 #include <iterator>
14 #include <iostream>
15 #include <algorithm>
16 using namespace std;
17 #define LL long long
18 #define INF 0x3f3f3f3f
19 #define MOD 1000000007
20 #define eps 1e-6
21 #define MAXN 2000000
22 #define MAXM 100
23 #define dd cout<<"debug"<<endl
24 #define p(x) printf("%d
", x)
25 #define pd(x) printf("%.7lf
", x)
26 #define pa {system("pause");}
27 #define k(x) printf("Case %d: ", ++x)
28 #define s(x) scanf("%d", &x)
29 #define sd(x) scanf("%lf", &x)
30 #define mes(x, d) memset(x, d, sizeof(x))
31 #define do(i, x) for(i = 0; i < x; i ++)
32 #define dod(i, x, l) for(i = x; i >= l; i --)
33 #define doe(i, x) for(i = 1; i <= x; i ++)
34 bool prime[MAXN];
35 int pm[MAXN];
36 int rm[MAXN];
37 int p, q;
38 bool is_ok(int n);
39 void init()
40 {
41     prime[0] = prime[1] = false;
42     prime[2] = true;
43     for(int i = 3; i <MAXN; i ++)
44         prime[i] = (i % 2 == 0? false : true);
45     int t = (int)sqrt(MAXN * 1.0);
46     for(int i = 3; i <= t; i ++)
47         if(prime[i])
48             for(int j = i + i; j < MAXN; j += i)
49                 prime[j] = false;
50     for(int i = 1; i < MAXN; i ++)
51     {
52         pm[i] = pm[i -1] + (prime[i]? 1 : 0);
53         rm[i] = rm[i -1] + (is_ok(i)? 1: 0);
54     }
55 }
56 bool is_ok(int n)
57 {
58     int m = n;
59     int s = 0;
60     while(m)
61     {
62         s = s * 10 + m % 10;
63         m /= 10;
64     }
65     if(s == n)
66         return true;
67     return false;
68 }
69 
70 int main()
71 {
72     init();
73     while(scanf("%d %d", &p, &q) != EOF)
74     {
75         int ans = 1;
76         for(int i = 1; i < MAXN; i ++)
77             if(q * pm[i] <= p * rm[i]) ans = i;
78         p(ans);
79     }
80     return 0;
81 }

View Code