巢穴

题解

题目名称    二进制除法          奇怪的函数      最小函数值          矩阵乘法
源文件名称  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;
}