专栏首页Code思维奇妙屋Codeforces Round #326 div2

Codeforces Round #326 div2

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #359 div2

    Problem_A(CodeForces 686A): 题意: \[ 有n个输入, +\space d_i代表冰淇淋数目增加d_i个, -\space...

    若羽
  • Codeforces Round #360 div2

      有d天, n个人。如果这n个人同时出现, 那么你就赢不了他们所有的人, 除此之外, 你可以赢他们所有到场的人。

    若羽
  • LightOj_1317 Throwing Balls into the Baskets

      每个人进球数的期望为:E = sigma (i * C(K, i) * p ^ i * (1 - p) ^ (k - i));

    若羽
  • Codeforces Round #359 div2

    Problem_A(CodeForces 686A): 题意: \[ 有n个输入, +\space d_i代表冰淇淋数目增加d_i个, -\space...

    若羽
  • Codeforces Round #360 div2

      有d天, n个人。如果这n个人同时出现, 那么你就赢不了他们所有的人, 除此之外, 你可以赢他们所有到场的人。

    若羽
  • Codeforces Round #315 (Div. 2)

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

    若羽
  • 四则运算、幸福来敲门、求一次方程解ax+b=0

    /* 功能:四则运算 日期:2013-03-16 */ #include<stdio.h> #include<stdlib.h>

    汐楓
  • cf540D. Bad Luck Island(概率dp)

    还是想复杂了啊,我列的状态时$f[i][j], g[i][j],t[i][j]$分别表示第$i$天,$j$个$s, r, p$活着的概率

    attack
  • Python的内置函数(四十八)、setattr()函数

    setattr() 函数对应函数 getattr(),用于设置属性值,该属性不一定是存在的。

    于小勇
  • 数据哪里找?奉上社会发展类公开数据清单:6千万条数据

    公开数据能帮助记者找到好故事、验证信息。来自34个国家的24万数据如何一搜可得?有哪些关于社会发展议题的权威门户可以将数据一网打尽?遇到海量数据,想批量转换格式...

    华章科技

扫码关注云+社区

领取腾讯云代金券