巢穴

題解

題目名稱    二進(jìn)制除法          奇怪的函數(shù)      最小函數(shù)值          矩陣乘法
源文件名稱  binary.(pas/c/cpp)  xx.(pas/c/cpp)  minval.(pas/c/cpp)  matrix.(pas/c/cpp)
輸入文件名  binary.in           xx.in           minval.in           matrix.in
輸出文件名  binary.out          xx.out          minval.out          matrix.out
時間限制    1秒                 1秒             1秒                 1秒
內(nèi)存限制    32M                 32M             32M                 32M
測試點(diǎn)      10個                10個            10個                10個
分值        100分               100分           100分               100分

Problem 1 : binary
二進(jìn)制除法

問題描述
    二進(jìn)制數(shù)n mod m的結(jié)果是多少？

輸入數(shù)據(jù)
    第一行輸入一個二進(jìn)制數(shù)n。
    第二行輸入一個二進(jìn)制數(shù)m。

輸出數(shù)據(jù)
    輸出n mod m的結(jié)果。

輸入樣例
1010101010
111000

輸出樣例
1010

時間限制
    各測試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?2MB的運(yùn)行空間

數(shù)據(jù)規(guī)模
    n的長度（二進(jìn)制數(shù)的位數(shù)）<=200 000；
    m的長度（二進(jìn)制數(shù)的位數(shù)）<=20。

題解:  進(jìn)制轉(zhuǎn)換,當(dāng)然,直接用二進(jìn)制去做也是可以的

#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
using namespace std;

ifstream fin("binary.in");
ofstream fout("binary.out");

string str1;
string str2;
int len1,len2;
int num1,num2;
long StrToInt(string str)
{
    
     long reNum=0;
     int len=str.length();
     int p=0;
     for (int i=len-1;i>=0;i--)
     {
         int u=(int)pow(2,p);p++;
         switch(str[i])
         {
          case '1':reNum+=u;break;
          default:break;
         }
     }
     return reNum;
}
string IntToStr(int value)
{
       string str="";
       while (value!=0)
       {
             int x=value%2;
             if (x==0) str='0'+str; else str='1'+str;
             value=value/2;
       }
       return str;
}
void readp()
{
     fin>>str1;
     fin>>str2;
     num2=StrToInt(str2);
}
void solve()
{
     string str="";
     for (int i=0;i<str1.length();i++)
     {
         str+=str1[i];
         num1=StrToInt(str);
         if (num1>=num2)
         {
          int x=num1-num2;
          str=IntToStr(x);
         }
     }
     fout<<str<<endl;
}
int main()
{
    readp();
    solve();
    return 0;
}

 Problem 2 : xx
奇怪的函數(shù)

問題描述
    使得x^x達(dá)到或超過n位數(shù)字的最小正整數(shù)x是多少？

輸入數(shù)據(jù)
    輸入一個正整數(shù)n。

輸出數(shù)據(jù)
    輸出使得x^x達(dá)到n位數(shù)字的最小正整數(shù)x。

輸入樣例
11

輸出樣例
10

時間限制
    各測試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?2MB的運(yùn)行空間

數(shù)據(jù)規(guī)模
    n<=2 000 000 000

題解:  關(guān)鍵是trunc((x*log10(x)/log10(10)+1))這個公式.可以直接求出x^x的位數(shù).然后二分..糾結(jié)的是我二分竟然寫錯了2次..

#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
using namespace std;

ifstream fin("xx.in");
ofstream fout("xx.out");

const long maxn=250000000;
long n;

void readp()
{
     fin>>n;
     
}
long digit(long x)
{
     if (x==0) return 0;
     return trunc((x*log10(x)/log10(10)+1));
}
void solve()
{
 
     long left=0;
     long right=maxn;
     long mid=0;
     while (true)
     {
      mid=(right+left)/2;
      if (digit(mid-1)>=n) right=mid-1; 
      else
      if (digit(mid)<n) left=mid+1;
      else
      break;
     }
    
     fout<<mid<<endl;
     
}
int main()
{
    readp();
    solve();
    return 0;
}

 
Problem 3 : minval
最小函數(shù)值

問題描述
    有n個函數(shù)，分別為F1,F2,...,Fn。定義Fi(x)=Ai*x^2+Bi*x+Ci(x∈N*)。給定這些Ai、Bi和Ci，請求出所有函數(shù)的所有函數(shù)值中最小的m個（如有重復(fù)的要輸出多個）。

輸入數(shù)據(jù)
    第一行輸入兩個正整數(shù)n和m。
    以下n行每行三個正整數(shù)，其中第i行的三個數(shù)分別位Ai、Bi和Ci。輸入數(shù)據(jù)保證Ai<=10，Bi<=100，Ci<=10 000。

輸出數(shù)據(jù)
    輸出將這n個函數(shù)所有可以生成的函數(shù)值排序后的前m個元素。
    這m個數(shù)應(yīng)該輸出到一行，用空格隔開。

樣例輸入
3 10
4 5 3
3 4 5
1 7 1

樣例輸出
9 12 12 19 25 29 31 44 45 54

時間限制
    各測試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?2MB的運(yùn)行空間

數(shù)據(jù)規(guī)模
    n,m<=10 000

題解: 用小頭堆來維護(hù)這些函數(shù)的值..每次取出最小的保存.然后對其更新..O(m log n)

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("minval.in");
ofstream fout("minval.out");

const int MAXNM=10001;
int n,m;
int a[MAXNM],b[MAXNM],c[MAXNM];
int fcNum[MAXNM],fcId[MAXNM],fcT[MAXNM];
int answer[MAXNM];
int len=0;
void swap(int &x,int &y)
{
     int temp;
     temp=x;x=y;y=temp;
}


void insert(int num,int id,int t)
{
     len++;
     fcNum[len]=num;
     fcId[len]=id;
     fcT[len]=t;
       int x=len;
       while (x>1)
       {
             if (fcNum[x]<fcNum[x/2])
             {
                                      
                swap(fcNum[x],fcNum[x/2]);
                swap(fcId[x],fcId[x/2]);
                swap(fcT[x],fcT[x/2]);
                x=x/2;
             }
             else
                break;
       }
}
void update()
{
     int id=fcId[1];
     fcT[1]++;
     fcNum[1]=a[id]*fcT[1]*fcT[1]+b[id]*fcT[1]+c[id];
     
     int x=1;
     while (x*2<=n)
     {
           int left=x*2,right=x*2+1,u;
           if (right>n) u=left;
           else
           {
               if (fcNum[left]<=fcNum[right]) u=left;
               else
               {
                   u=right;
               }
           }
           if (fcNum[x]>fcNum[u])
           {
              swap(fcNum[u],fcNum[x]);
              swap(fcId[u],fcId[x]);
              swap(fcT[u],fcT[x]);
              x=u;
           }
           else
               break;
     }
}
void readp()
{
     
     fin>>n>>m;
     for (int i=1;i<=n;i++)
     {
         fin>>a[i]>>b[i]>>c[i];
         int num,id,t;
         num=a[i]+b[i]+c[i];
         id=i;
         t=1;
         insert(num,id,t);
     }
}
void solve()
{
     for (int i=1;i<=m;i++)
     {
         answer[i]=fcNum[1];
         
         update();
     }
}
void writep()
{
     for (int i=1;i<=m;i++)
     {
         if (i==m) {fout<<answer[i];continue;}
         fout<<answer[i]<<" ";
     }
}
int main()
{
    readp();
    solve();
    writep();
    return 0;
}

Problem 4 : matrix
矩陣乘法

問題描述
    一個A x B的矩陣乘以一個B x C的矩陣將得到一個A x C的矩陣，時間復(fù)雜度為A x B x C。矩陣乘法滿足結(jié)合律（但不滿足交換律）。順序給出n個矩陣的大小，請問計算出它們的乘積的最少需要花費(fèi)多少時間。

輸入數(shù)據(jù)
    第一行輸入一個正整數(shù)n，表示有n個矩陣。
    接下來m行每行兩個正整數(shù)Xi,Yi，其中第i行的兩個數(shù)表示第i個矩陣的規(guī)模為Xi x Yi。所有的Xi、Yi<=100。輸入數(shù)據(jù)保證這些矩陣可以相乘。

輸出數(shù)據(jù)
    輸出最少需要花費(fèi)的時間。

樣例輸入
3
10 100
100 5
5 50

樣例輸出
7500

樣例說明
    順序計算總耗時7500；先算后兩個總耗時75000。

時間限制
    各測試點(diǎn)1秒

內(nèi)存限制
    你的程序?qū)⒈环峙?2MB的運(yùn)行空間

數(shù)據(jù)范圍
    n<=100。

題解:  動態(tài)規(guī)劃,最小代價子母樹 

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

const int MAXN=101;
int n;


int le[MAXN],ri[MAXN];
int dpl[MAXN][MAXN],dpr[MAXN][MAXN],dp[MAXN][MAXN];
void readp()
{
     fin>>n;
     for (int i=1;i<=n;i++)
       fin>>le[i]>>ri[i];
}


void solve()
{
     for (int j=1;j<=n;j++)
     {
         for (int i=1;i<=n;i++)
         {         
            if (j==1) {dpl[i][i]=le[i];dpr[i][i]=ri[i];dp[i][i]=0;continue;}
            int k=i+j-1;
            if (k>n) continue;
            int min=10000000;
            for (int l=i;l<k;l++)
            {
                int u=dpl[i][l]*dpr[i][l]*dpr[l+1][k]+dp[i][l]+dp[l+1][k];
                if (min>u)
                {
                   dpl[i][k]=dpl[i][l];
                   dpr[i][k]=dpr[l+1][k];
                   min=u;
                   dp[i][k]=u;
                }
                
            }
         
                   
                 
         }
     }
     fout<<dp[1][n]<<endl;
}
int main()
{
    readp();
    solve();
    return 0;
}