巢穴

題解

題目名稱    二進制除法          奇怪的函數      最小函數值          矩陣乘法
源文件名稱  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秒
內存限制    32M                 32M             32M                 32M
測試點      10個                10個            10個                10個
分值        100分               100分           100分               100分

Problem 1 : binary
二進制除法

問題描述
    二進制數n mod m的結果是多少？

輸入數據
    第一行輸入一個二進制數n。
    第二行輸入一個二進制數m。

輸出數據
    輸出n mod m的結果。

輸入樣例
1010101010
111000

輸出樣例
1010

時間限制
    各測試點1秒

內存限制
    你的程序將被分配32MB的運行空間

數據規模
    n的長度（二進制數的位數）<=200 000；
    m的長度（二進制數的位數）<=20。

題解:  進制轉換,當然,直接用二進制去做也是可以的

#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
奇怪的函數

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

輸入數據
    輸入一個正整數n。

輸出數據
    輸出使得x^x達到n位數字的最小正整數x。

輸入樣例
11

輸出樣例
10

時間限制
    各測試點1秒

內存限制
    你的程序將被分配32MB的運行空間

數據規模
    n<=2 000 000 000

題解:  關鍵是trunc((x*log10(x)/log10(10)+1))這個公式.可以直接求出x^x的位數.然后二分..糾結的是我二分竟然寫錯了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
最小函數值

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

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

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

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

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

時間限制
    各測試點1秒

內存限制
    你的程序將被分配32MB的運行空間

數據規模
    n,m<=10 000

題解: 用小頭堆來維護這些函數的值..每次取出最小的保存.然后對其更新..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的矩陣，時間復雜度為A x B x C。矩陣乘法滿足結合律（但不滿足交換律）。順序給出n個矩陣的大小，請問計算出它們的乘積的最少需要花費多少時間。

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

輸出數據
    輸出最少需要花費的時間。

樣例輸入
3
10 100
100 5
5 50

樣例輸出
7500

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

時間限制
    各測試點1秒

內存限制
    你的程序將被分配32MB的運行空間

數據范圍
    n<=100。

題解:  動態規劃,最小代價子母樹 

#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;
}