Codeforces Round #326 div2
Codeforces Round #326 div2
若羽
发布于 2019-07-14 13:46:49
发布于 2019-07-14 13:46:49
Problem_A(588A):
题意：
Duff 很喜欢吃肉， 每天都要吃，然而她又懒得下楼。 可以买很多放在家里慢慢吃。然而肉价每天都在变化，现给定一个n， 表示有多少天，然后第i天吃ai kg的肉， 当天的价格为pi。
问满足Duff的要求， 最少需要多少钱。
思路：
稍稍分析， 可以得知， 应该维护一个最小价格。然后按照最小价格去买那一段区间的肉。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int a, p;
37
38 int main()
39 {
40 scanf("%d", &n);
41 int sum = 0, min_p = INF, num = 0;
42 for(int i = 0; i < n; i ++)
43 {
44 scanf("%d %d", &a, &p);
45 if(p < min_p)
46 {
47 sum = sum + num * min_p;
48 min_p = p;
49 num = a;
50 }
51 else
52 num += a;
53 }
54 if(num) sum = sum + num * min_p;
55 printf("%d\n", sum);
56 return 0;
57 }Problem_B(588B):
题意：
给一个数n， 在它所有的约数里(包括1和它自身)， 找到这样一个最大的数：不能被某个数的平方整除。例如：8能被4整除， 而4是2的平方 所以不行。
思路：
任何一个数， 都能将其写成质因子分解的形式，从质因子分解式就能看出一个规律， 如果把所有的质因子全部乘起来恰好是满足题意的最大的数。 如果幂超过1， 则只算一个。
因为再多乘任何一个数， 得到的都会是某个平方的倍数(嗯哼， 你多乘的那个质因子)。 So， 答案就出来了。
由于对称的性质， 10^12， 只需要打10^6的素数表就OK了。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 10000010
23 #define MAXM 1000010
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 LL n;
36 LL p[MAXN], cnt = 0;
37 bool a[MAXN];
38
39 void Prime2()
40 {
41 memset(a, 0, sizeof(a));
42 int i, j;
43 for (i = 2; i < MAXN; ++i)
44 {
45 if (!(a[i])) p[cnt ++] = i;
46 for (j = 0; (j < cnt && i * p[j] < MAXN); ++j)
47 {
48 a[i * p[j]] = 1;
49 if (!(i % p[j])) break;
50 }
51 }
52 }
53
54 LL get_ans(LL x)
55 {
56 LL ans = 1;
57 for(int i = 0; i < cnt ; i ++)
58 {
59 if(x == 1) return ans;
60 if(x % p[i] == 0)
61 {
62 x /= p[i];
63 ans = ans * p[i];
64 while(x % p[i] == 0)
65 x /= p[i];
66 }
67 }
68 return ans * x;
69 }
70
71
72 int main()
73 {
74 Prime2();
75 scanf("%I64d", &n);
76 printf("%I64d\n", get_ans(n));
77 return 0;
78 }Problem_C(587A):
题意：
题意是给一个长度为n的序列， 其代表的含义是第i个表示 重量为2^w[i]的一个物品。
而Duff 每次能举起这样一堆物品：这堆物品的和为2^x。
求举完所有的物品所有的最小次数。
思路：
简单分析后能得到一个结论：两个一样的数能合成一个比它大一的数，so 答案就出来了。 排序后不停的往上合成就行了。
代码：
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 <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000100
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int w[MAXN];
37
38 int main()
39 {
40 int x, ans = 0;
41 scanf("%d", &n);
42 mes(w, 0);
43 for(int i = 0; i < n; i ++)
44 {
45 scanf("%d", &x);
46 w[x] ++;
47 }
48 for(int i = 0; i < MAXN; i ++)
49 if(w[i])
50 {
51 w[i + 1] = w[i + 1] + w[i] / 2;
52 if(w[i] % 2) ans ++;
53 }
54 printf("%d\n", ans);
55 return 0;
56 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-05-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读