Problem_A(588A):
题意：
Duff 很喜欢吃肉， 每天都要吃，然而她又懒得下楼。 可以买很多放在家里慢慢吃。然而肉价每天都在变化，现给定一个n， 表示有多少天，然后第i天吃ai kg的肉， 当天的价格为pi。
问满足Duff的要求， 最少需要多少钱。
思路：
稍稍分析， 可以得知， 应该维护一个最小价格。然后按照最小价格去买那一段区间的肉。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000000
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n;
int a, p; int main()
{
scanf("%d", &n);
int sum = , min_p = INF, num = ;
for(int i = ; i < n; i ++)
{
scanf("%d %d", &a, &p);
if(p < min_p)
{
sum = sum + num * min_p;
min_p = p;
num = a;
}
else
num += a;
}
if(num) sum = sum + num * min_p;
printf("%d\n", sum);
return ;
}
Problem_B(588B):
题意：
给一个数n， 在它所有的约数里(包括1和它自身)， 找到这样一个最大的数：不能被某个数的平方整除。例如：8能被4整除， 而4是2的平方 所以不行。
思路：
任何一个数， 都能将其写成质因子分解的形式，从质因子分解式就能看出一个规律， 如果把所有的质因子全部乘起来恰好是满足题意的最大的数。 如果幂超过1， 则只算一个。
因为再多乘任何一个数， 得到的都会是某个平方的倍数(嗯哼， 你多乘的那个质因子)。 So， 答案就出来了。
由于对称的性质， 10^12， 只需要打10^6的素数表就OK了。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 10000010
#define MAXM 1000010
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
LL n;
LL p[MAXN], cnt = ;
bool a[MAXN]; void Prime2()
{
memset(a, , sizeof(a));
int i, j;
for (i = ; i < MAXN; ++i)
{
if (!(a[i])) p[cnt ++] = i;
for (j = ; (j < cnt && i * p[j] < MAXN); ++j)
{
a[i * p[j]] = ;
if (!(i % p[j])) break;
}
}
} LL get_ans(LL x)
{
LL ans = ;
for(int i = ; i < cnt ; i ++)
{
if(x == ) return ans;
if(x % p[i] == )
{
x /= p[i];
ans = ans * p[i];
while(x % p[i] == )
x /= p[i];
}
}
return ans * x;
} int main()
{
Prime2();
scanf("%I64d", &n);
printf("%I64d\n", get_ans(n));
return ;
}
Problem_C(587A):
题意：
题意是给一个长度为n的序列， 其代表的含义是第i个表示 重量为2^w[i]的一个物品。
而Duff 每次能举起这样一堆物品：这堆物品的和为2^x。
求举完所有的物品所有的最小次数。
思路：
简单分析后能得到一个结论：两个一样的数能合成一个比它大一的数，so 答案就出来了。 排序后不停的往上合成就行了。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 1000100
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int n;
int w[MAXN]; int main()
{
int x, ans = ;
scanf("%d", &n);
mes(w, );
for(int i = ; i < n; i ++)
{
scanf("%d", &x);
w[x] ++;
}
for(int i = ; i < MAXN; i ++)
if(w[i])
{
w[i + ] = w[i + ] + w[i] / ;
if(w[i] % ) ans ++;
}
printf("%d\n", ans);
return ;
}