hdu 5170 5171

hdu 5170 5171

hdu 5170題意： 給定四個整數 a,b,c,d; 要比較a^b 與c^d的大小，
如果數據小的話直接搞就行，現在數據比較大，可以兩邊同取對數比較；
但是要注意精度問題！

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
int a,b,c,d;

int main()
{
    while(cin>>a>>b>>c>>d)
    {
       double tmp1=b*log10(a*1.0);
       double tmp2=d*log10(c*1.0);

       if(tmp1-tmp2>1e-9)
            printf(">\n");
       else if(tmp2-tmp1>1e-9)
            printf("<\n");
       else
            printf("=\n");
    }
    return 0;
}

hdu 5171 題意: 給定一個集合,裡面的數可能會有重復，現在每次可以從中取出兩個數a,b，再將a+b加入這個集合中，這個操作可以重復k次
最終集合表述為A={A1,A2,A3…..An}；
求sum=A1+A2+A2+A3+……+An的最大值；
貪心處理即可，即每次取出來的都是原來集合中的最大值和次大值，數據小直接模擬即可，現在數據有點大，遞推公式：
用a1,b1分別表示原來集合中的最大值，次大值

第一次操作 a1+b1 加入集合
第二次操作 2a1+b1加入集合
第三次操作 3a1+2b1加入集合
第四次擦做 5a1+3b1加入集合
.
.
.
.
.
發現是fib數列，矩陣加速求前k項的和即可；

#include 
#include 
#include 
#include 
#include 
const int MOD=1e7+7;
using namespace std;
typedef long long ll;
int a[100100];

struct matrix
{
  ll f[5][5];
};
matrix Co; //系數矩陣

matrix mul(matrix a,matrix b)
{
    matrix c;
    memset(c.f,0,sizeof(c.f));
    for(int i=0;i<4;i++)
     for(int j=0;j<4;j++)
      for(int k=0;k<4;k++)
        {
          c.f[i][j]+=(a.f[i][k]*b.f[k][j])%MOD;
          c.f[i][j]%=MOD;
        }
    return c;
}

matrix quick_mod(matrix a,int b)
{
   matrix s;
   memset(s.f,0,sizeof(s.f));
   for(int i=0;i<4;i++)s.f[i][i]=1;
   while(b)
   {
     if(b&1)s=mul(s,a);
     b>>=1;
     a=mul(a,a);
   }
   return s;
}

int main()
{
   int n,k;
   Co.f[0][0]=1,Co.f[0][1]=1,Co.f[0][2]=0;
   Co.f[1][0]=1,Co.f[1][1]=0,Co.f[1][2]=0;
   Co.f[2][0]=1,Co.f[2][1]=1,Co.f[2][2]=1;

   while(cin>>n>>k)
   {
      ll ans=0;
      int a1,b1;
      for(int i=1;i<=n;i++)
      {
        scanf("%d",&a[i]);
        ans=(ans+a[i])%MOD;
      }
      sort(a+1,a+1+n);
      a1=a[n],b1=a[n-1]; //最大值 次大值

      matrix tmp=Co;
             tmp=quick_mod(tmp,k);
      ll left=tmp.f[2][0]*1%MOD+tmp.f[2][1]*0%MOD+tmp.f[2][2]*0%MOD;
         ans=(ans+left*a1%MOD)%MOD;

             tmp=Co;
             tmp=quick_mod(tmp,k-1);
      ll right=tmp.f[2][0]*1%MOD+tmp.f[2][1]*0%MOD+tmp.f[2][2]*0%MOD;
         ans=(ans+(right+1)*b1%MOD)%MOD;
      printf("%I64d\n",ans);
   }
   return 0;
}