Codeforces Round #326（Div2）

CodeForces 588A

题意：Duff喜欢吃肉，想在接下来的n天，每天都有Ai斤肉吃，但每一天肉的单价Pi不定，肉可以保存不过期，现已知n天每天肉的斤数Ai，以及单价Pi，为了使每天都有想要的Ai斤肉吃，求最小花费。

思路：cost=Ai*min(pi) 1<=i<=n;

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn=1e5+;

 const int inf=0x3f3f3f3f;

 int cost[maxn],p[maxn];

 int main()

 {

     int d,minn,res;

     while(~scanf("%d",&d))

     {

         res=;minn=inf;

         for(int i=;i<d;i++)

         {

             scanf("%d%d",&cost[i],&p[i]);

             if(p[i]<minn)

                 minn=p[i];

             res+=cost[i]*minn;

         }

         printf("%d\n",res);

     }

     return ;

 }

CodeForces 588B

题意：有一个数n,有多个因子，例如12={1,2,4,6,12}，满足可爱数的条件是：为n的因子，并且这个数的因子数不能被开方。现求最大可爱数。

思路：数据较大1e12.

方案一、暴力+用sqrt减少循环次数。使时间复杂度达到根号n*根号根号n,即1e9.

方案二、打一个素数表，整数可以拆分成任意素数的乘积。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 using namespace std;

 long long n;

 bool deal(long long x)

 {

     long long y=sqrt(x)+;

     for(long long i=;i<=y;i++)

         if(x%(i*i)==)

             return ;

     return ;

 }

 int main()

 {

     while(~scanf("%lld",&n))

     {

         long long m=sqrt(n);int flag=;

         long long res;

         for(long long i=;i<=m+;i++)

         {

             if(n%i==&&deal(n/i))

             {

                 flag=;

                 res=n/i;

                 break;

             }

         }

         if(!flag)

         {

             for(long long i=m;i>=;i--)

             {

                 if(n%i==&&deal(i))

                 {

                     res=i;

                     break;

                 }

             }

         }

         printf("%lld\n", res);

     }

     return ;

 }

CodeForces 587A

题意：n个数，A1,A2.....An。选k（k<=n）个数,构成2^a1+2^a2+...2^ak=2^x(可为任意)，算一次，一个数只能被选一次。求数全被选完最少需要多少次。

思路：可发现：2^2=2^1+2^1

2^3=2^2+2^2

2^4=2^3+2^3

......

2^n=2^(n-1)+2^(n-1)

由于n个数任意取，并且2^n=2^（n-1）+2^(n-1). 只看指数，即Ai，(1,1)=2, (2,2)=3, (n-1,n-1)=n

为了尽少次数的到底2^x. 需要统计Ai的个数。然后(1,1)=2, (2,2)=3, (n-1,n-1)=n,

一直合成到最大。合成后剩下的次数即为result.

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn=1e6+;

 int f[*maxn],a[maxn];

 int n,res,maxx;

 void deal()

 {

     res=;

     for(int i=;i<=maxn;i++)

     {

         if(f[i]%==)

         {

             f[i+]+=(f[i]-)/;

             res++;

         }

         else

             f[i+]+=f[i]/;

     }

 }

 int main()

 {

     while(~scanf("%d",&n))

     {

         memset(f,,sizeof(f));

         maxx=-;

         for(int i=;i<n;i++)

         {

             scanf("%d",&a[i]);

             maxx=max(maxx,a[i]);

             f[a[i]]++;

         }

         deal();

         printf("%d\n",res);

     }

     return ;

 }

剩下题目待补，革命尚未成功，同志仍需努力！

巴特西

Codeforces Round #326（Div2）

最新文章

热门文章