巢穴

題解

題目名稱    二進(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
時(shí)間限制    1秒                 1秒             1秒                 1秒
內(nèi)存限制    32M                 32M             32M                 32M
測試點(diǎn)      10個(gè)                10個(gè)            10個(gè)                10個(gè)
分值        100分               100分           100分               100分

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

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

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

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

輸入樣例
1010101010
111000

輸出樣例
1010

時(shí)間限制
    各測試點(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ù)
    輸入一個(gè)正整數(shù)n。

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

輸入樣例
11

輸出樣例
10

時(shí)間限制
    各測試點(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))這個(gè)公式.可以直接求出x^x的位數(shù).然后二分..糾結(jié)的是我二分竟然寫錯(cuò)了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個(gè)函數(shù)，分別為F1,F2,...,Fn。定義Fi(x)=Ai*x^2+Bi*x+Ci(x∈N*)。給定這些Ai、Bi和Ci，請求出所有函數(shù)的所有函數(shù)值中最小的m個(gè)（如有重復(fù)的要輸出多個(gè)）。

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

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

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

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

時(shí)間限制
    各測試點(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
矩陣乘法

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

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

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

樣例輸入
3
10 100
100 5
5 50

樣例輸出
7500

樣例說明
    順序計(jì)算總耗時(shí)7500；先算后兩個(gè)總耗時(shí)75000。

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

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

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

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

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