QMKS PTA(KKK)

5-1测量算法的运行时间

time.h

clock()

clock()

(t2-t1)/(double)CLOCKS_PER_SEC

5-2插入排序

25, 47, 87, 36, 90, 18, 65, 31, 79, 58

5-3Insertion Sort

i>0 && A[i-1]>Tmp

A[i] = Tmp

5-4KMP

j == 0 || S[i] == T[j]

j=next[j]

return i-T[0]

5-5快速排序（分治法）

low

low=pivotkey

low

Partition(L,low,high)

QSort(L,low,pivotloc-1)

QSort(L,pivotloc+1,high)

5-6单链表结点和（递归法）

L==NULL

L->data+Sum(L->next)

5-7数组中的最大值（递归法）

a[0]

max(fmax(a,i-1),a[i-1])

5-8查找第K小元素（分治法）

s

a[i]

Kminselect(a,s,i-1,k)

Kminselect(a,i+1,t,k)

5-9二分搜索（分治法）

mid=(low+high)/2

return binsearch(A,key,low,mid-1)

return binsearch(A,key,mid+1,high)

5-10求解棋盘覆盖问题1（分治法）

tr,tc,dr,dc,s

tr,tc,tr+s-1,tc+s-1,s

tr,tc+s,dr,dc,s

tr,tc+s,tr+s-1,tc+s,s

tr+s,tc,dr,dc,s

tr+s,tc,tr+s,tc+s-1,s

tr+s,tc+s,dr,dc,s

tr+s,tc+s,tr+s,tc+s,s

0,0,dr,dc,size

5-11最大次大问题（分治法）

max(a[low],a[high])

min(a[low],a[high])

max1max2(a,low,mid,lmax1,lmax2)

max1max2(a,mid+1,high,rmax1,rmax2)

max1max2(A,0,n-1,max1,max2)

5-12归并排序

return;

(start + end) / 2

mergeSort(Array, start, mid);

mergeSort(Array, mid + 1, end);

merge(Array, start, mid, end);

temp[k++] = Array[i++];

temp[k++] = Array[j++];

temp[k++] = Array[i++];

temp[k++] = Array[j++];

copy(temp.begin(), temp.end(), Array.begin()+start);

5-13求解最长递增子序列问题（动态规划法）

max = dp[j]+1

maxindex

x[maxindex][k]

x[i][max-1]= a[i]

5-14求解整数拆分问题（动态规划法）

dp[i][j]=1

dp[i][j]=dp[i][i]

dp[i][j]=dp[i][j-1]+1

dp[i][j-1]+dp[i-j][j]

5-15求解会议安排问题（动态规划）

dp[i-1]

A[i].length

dp[i-1]

dp[low-1]+A[i].length

5-16最小生成树（普里姆算法）

min > closedge[i].lowcost && closedge[i].lowcost != 0

u

G.arcs[k][j]

0

Min(G)

0

G.vexs[k]

G.arcs[k][j]

5-17求解最优装载问题（贪心法）

sort(w+1,w+n+1)

i<=n &&  w[i].wi<=restw

maxw+w[i].wi

5-18部分背包问题（贪心法）

A[i].w<=weight

weight-=A[i].w

i++

weight/A[i].w

5-19求解简单装载问题（回溯法）

maxw=tw

x[j]=op[j]

num+1,tw+w[i],rw-w[i],op,i+1

num,tw,rw-w[i],op,i+1

0,0,rw,op,1

5-20求解n皇后问题（递归回溯法）

return false

return true

place(i,j)

queen(i+1,n)

5-210/1背包问题（回溯法）

tw==W&&tv>maxv

j=1;j<=n;j++

i+1,tw+w[i],tv+v[i],rw-w[i],op

tw+rw>W

i+1,tw,tv,rw-w[i],op

### 6-1 矩阵置零

void fun0 (int **A,int M,int N)

{

int flagrow[200] = { 0 };

int flagcol[200] = { 0 };

int m = 0;

int n = 0;

for (int i=0; i < M; i++)

{

for (int j = 0; j < N; j++)

{

if (A[i][j] == 0)

{

flagrow[i] = 1;

flagcol[j] = 1;

}

}

}

for (int i = 0; i < M; i++)

{

if (flagrow[i] == 1)

{

for (int j = 0; j < N; j++)

{

A[i][j] = 0;

if (flagcol[j] == 1)

{

for (int k = 0; k < M; k++)

{

A[k][j] = 0;

}

}

}

}

}

}

```

### 6-2 矩阵就地旋转

void fun(int **Mat, int N){

      for (int i = 0; i < N; i++) {

            for (int j = 0; j < i; j++) {

                int tmp = *(*(Mat+i)+j);

                *(*(Mat+i)+j) = *(*(Mat+j)+i);

                *(*(Mat+j)+i) = tmp;

            }

        }

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N/2; j++) {

                int tmp = *(*(Mat+i)+(N-1)-j);

                *(*(Mat+i)+(N-1)-j) = *(*(Mat+i)+j);

                *(*(Mat+i)+j) = tmp;

            }

        }

     return 0;

}

```

### 6-3 直接插入排序

int cmp(const void *a,const void *b)

{

    return *(int*)a>=*(int*)b;

}

void  InsertSort(SqList L){

  qsort(L.elem+1,L.Length,sizeof(int),cmp);

}

```

### 6-4 单链表插入排序

void insertion_sort(LinkNode *&L)

    

{

    LinkNode *i=L->next->next,*j,*pre,*m,*r=L->next;

    while(i)

    {

        j=L->next;

        pre=L;

        while(j!=i)

        {

            if(i->datadata)

            {

                pre->next=i;

                m=i->next;

                i->next=j;

                i=m;

                r->next=i;

                break;

            }

            else

            {

                j=j->next;

                pre=pre->next;

            }

        }

        if(j==i) i=i->next,r=j;

    }

}

```

### 6-5 求子串*

char* StrMid(char *dst, const char *src, int start, int len)

{

    int i=0,j=0;

    char str[2001];

    if(len<0)

        len=0;

    if(start <0||start > strlen(src))

    {

       dst[0]='';

        return dst;

        }

    for(i =start; src[i]!=''; i++)

    {

        if(i>=start&&i

        {dst[j++] = src[i];

    }}

    dst[j] = '';

    return dst;

}

```

### 6-6 字符串整理*

char* StrTrim(char *str){

int start = 0, end = 0, k = 0, i, j;

while(isspace(str[start])){

start++;

}

i = start;

while(str[end] != ''){

end++;

}

for(k = end-1; k >= 0; k--){

if(isspace(str[k])){

str[k] = '';

}

else

break;

}

for(j = 0; i <= k; j++,i++){

str[j] = str[i];

}

while(str[j] != ''){

str[j] = '';

j++;

}

return str;

}

```

### 6-7 KMP算法

void get_nextval(char T[], int next[])

{

    int m = strlen(T);

for (int i = 2 , j = 0 ; i < m ; i ++ )

{

while(j && T[i] != T[j+1]) j = next[j];

if(T[i] == T[j+1]) j ++ ;

next[i] = j;

}

}

int Index_KMP(char S[], char T[], int pos, int next[])

{

    int n = strlen(S);

    int m = strlen(T);

    int f = 0;

    m --;

for (int i = 1 , j = 0 ; i < n ; i ++ )

{

while(j && S[i] != T[j+1]) j = next[j];

if(S[i] == T[j+1]) j ++ ;

if(j == m)

{

f = i - m + 1;

break;

}

}

return f;

}

```

### 6-8 二分搜索（分治法）

int binsearch(int A[],int key,int low,int high){

    for(int i = low;i<=high;i++)

    {

        if(A[i]==key)

        {

            return i;

        }

    }

}

### 6-9 归并排序

void merge(vector& Array, int start, int mid, int end){

    

    vector temp = vector(end - start + 1);

    int leftStart = start;

    int rightStart = mid + 1;

    int index = 0;

    

    while(leftStart <= mid && rightStart <= end){

        if(Array[leftStart] <= Array[rightStart])

            temp[index++] = Array[leftStart++];

        else

            temp[index++] = Array[rightStart++];

    }

    

    while(leftStart <= mid) temp[index++] = Array[leftStart++];

    while(rightStart <= end) temp[index++] = Array[rightStart++];

    for(int i = 0; i < index; ++i) Array[start+i] = temp[i];

}

void mergeSort(vector& Array, int start, int end){

    

    if(start < end){

        int mid = (start + end) / 2;

        mergeSort(Array, start, mid);

        mergeSort(Array, mid+1, end);

        merge(Array, start, mid, end);

    }

}

```

### 6-10 Quick Power

int Power(int N, int k)

{

    int ans = 1;

    N %= MOD;

    if(k==0)

        return 1;

    while(k>0)

    {

        if(k&1)

        {

            ans = ans * N % MOD;

        }

        N = N * N % MOD;

        k>>=1;

    }

    return ans;

}

```

### 6-11 查找第K小元素（分治法）

#include

int Kminselect(int a[],int s,int t,int k){

    sort(a,a+t);

    int cnt = 0;

    int now = -200000000;

    for(int i = 0;i < t;i++)

    {

        if(a[i]>=now)

        {

            cnt++;

            now = a[i];

        }

        if(cnt == k)

            break;

    }

    return now;

}

### 6-12 循环日程安排问题（分治法）

void Plan(int a[][N],int k){

    a[1][1] = 1; a[1][2] = 2;

    a[2][1] = 2; a[2][2] = 1;

    if(k>1)

        for(int t=1;t

        {

            for(int i=1+pow(2.0,t);i<=pow(2.0,t+1);i++)

            {

                for(int j=1;j<=pow(2.0,t);j++)

                {

                    a[i][j] = a[i-(int)pow(2.0,t)][j] + (int)pow(2.0,t);

                }

            }

            for(int i=1;i<=pow(2.0,t);i++)

            {

                for(int j=1+pow(2.0,t);j<=pow(2.0,t+1);j++)

                {

                    a[i][j] = a[i][j-(int)pow(2.0,t)] + (int)pow(2.0,t);

                }

            }

            for(int i=1+pow(2.0,t);i<=pow(2.0,t+1);i++)

            {

                for(int j=1+pow(2.0,t);j<=pow(2.0,t+1);j++)

                {

                    a[i][j] = a[i-(int)pow(2.0,t)][j-(int)pow(2.0,t)];

                }

            }

        }

    else    ;

}

### 6-13 最长公共子序列

void lcs(int i, int j, int [][]b) {

    String S1 = s1.toString();

    char[] ss1=S1.toCharArray();

    if (i == 0 || j == 0) {

        return;

    }

    if (b[i][j] == 1) {

        lcs(i - 1, j - 1, b);

        s3.append(ss1[i - 1]);

    } else if (b[i][j] == 2) {

        lcs(i - 1, j, b);

    } else lcs(i, j - 1, b);

}

void subsequenceOrder() {

    int m = s1.length();

    int n = s2.length();

    int c [][] = new int[m+1][n+1];

    int b [][] = new int[m+1][n+1];

    String S1 = s1.toString();

    char[] ss1=S1.toCh

### 6-14 求解拆分集合为相等的子集合问题（动态规划法）

int split(int n)

{

    int sum = n * (n + 1) / 4;

    dp[0][0] = 1;

    for(int i = 1;i <= n;i ++){

        for(int k = 0;k <= sum;k ++){

            if(i > k)

                dp[i][k] = dp[i - 1][k];

            else

                dp[i][k] = dp[i - 1][k] + dp[i - 1][k - i];

        }

    }

    return dp[n][sum] / 2;

}

### 6-15 求解整数拆分问题（动态规划法）

void Split(int n, int k)

{

for (int i = 1; i <= n; i++)

for (int j = 1; j <= k; j++)

{

if (i == 1 || j == 1)

dp[i][j] = 1;

else if (i < j)

dp[i][j] = dp[i][i];

else if (i == j)

dp[i][j] = dp[i][j - 1] + 1;

else

dp[i][j] = dp[i][j - 1] + dp[i - j][j];

}

}

### 6-16 求解最长递增子序列问题（动态规划法）

void IncreaseOrder(int a[],int dp[],int x[][N],int n)

{

int i, j, k, index;

for (i = 0; i < n; i++)

{

dp[i] = 1;

x[i][0] = a[i];

int max = 1;

int maxindex=i;

for (j=0; j< i;j ++) {

if ((a[j] < a[i]) && (max

max = dp[j]+1 ;

maxindex=j ;

}

}

if(maxindex!=i){

dp[i] = max;

for (k = 0; k < max-1; k++)

x[i][k] = x[maxindex][k] ;

x[i][max-1]= a[i] ;

}

}

}

### 6-17最短路径（迪杰斯特拉算法）

void ShortestPath_DIJ(AMGraph G, int v0){

   

    int v , i , w , min;

int n = G.vexnum;                    

for(v = 0; v < n; ++v){             

S[v] = false;                  

D[v] = G.arcs[v0][v];           

if(D[v] < MaxInt)  Path [v] = v0;  

else Path [v] = -1;                 

}

S[v0]=true;                      

D[v0]=0;                        

for(i = 1;i < n; ++i){

        min= MaxInt;

        for(w = 0; w < n; ++w)

if(!S[w] && D[w] < min){  

v = w;

min = D[w];

}        

S[v]=true;                   

for(w = 0;w < n; ++w)             

if(!S[w] && (D[v] + G.arcs[v][w] < D[w])){

D[w] = D[v] + G.arcs[v][w];   

Path [w] = v;                

}

    }

}

```

### 6-18部分背包问题（贪心法）

void Knap()

{

    for(int i = 1;i <= n;i ++){

        if(W >= A[i].w){

            W -= A[i].w;

            A[i].x = 1;

            V += A[i].v;

        }else{

            A[i].x = W/A[i].w;

            V += A[i].v * A[i].x;

            break;

        }

    }

}

```

### 6-19求解流水作业调度问题（贪心法）

int solve(){

int i,j,k;

NodeType c[N];

for(i=0;i

c[i].no=i;

c[i].group=(a[i]<=b[i]);

c[i].time=a[i]<=b[i]?a[i]:b[i];

}

sort(c,c+n);

j=0;k=n-1;

for(i=0;i

if(c[i].group==1) best[j++]=c[i].no;

else best[k--]=c[i].no;

}

int f1=0;

int f2=0;

for(i=0;i

f1+=a[best[i]];

f2=max(f2,f1)+b[best[i]];

}

return f2;

}

```

### 6-20哈夫曼树即编码

pair Min1AndMin2(int k) {

    int mn1 = -1, mn2 = -1;

    for (int i = 0; i < k; ++i)

        if (ht[i].parent == -1) {

            mn1 = i;

            break;

        }

    for (int i = 0; i < k; ++i)

        if (ht[i].parent == -1 && ht[mn1].weight > ht[i].weight)

            mn1 = i;

    for (int i = 0; i < k; ++i)

        if (ht[i].parent == -1 && i != mn1) {

            mn2 = i;

            break;

        }

    for (int i = 0; i < k; ++i)

        if (ht[i].parent == -1 && i != mn1 && ht[mn2].weight > ht[i].weight)

            mn2 = i;

    return {mn1, mn2};

}

void CreateHTree() {

    for (int i = 0; i < 2 * n - 1; ++i)

        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;

    for(int i = n; i < 2*n-1; ++i)

    {

        pair p = Min1AndMin2(i);

        ht[p.first].parent = i;

        ht[p.second].parent = i;

        ht[i].lchild = p.first;

        ht[i].rchild = p.second;

        ht[i].weight = ht[p.first].weight + ht[p.second].weight;

    }

}

string ss[105];

void GetCode(int k, string t)

{

    if(ht[k].parent != -1) ss[k] += ss[ht[k].parent];

    ss[k] += t;

    if(ht[k].lchild != -1) GetCode(ht[k].lchild, "0");

    if(ht[k].rchild != -1) GetCode(ht[k].rchild, "1");

    return ;

}

void CreateHCode() {

    GetCode(2 *  n - 2, "");

    for (int i = 0; i < n; ++i) {

        htcode[ht[i].data] = ss[i];

    }

}

```

### 6-21 0/1背包问题（回溯法）

void dfs(int i,int tw,int tv,int rw,int op[])

{  

   int j;

   if (i>n)

   {  if (tw==W && tv>maxv)

      {  maxv=tv;

         for (j=1;j<=n;j++)

            x[j]=op[j];

      }

   }

   else

   {  if (tw+w[i]<=W)

      {  op[i]=1;

         dfs(i+1,tw+w[i],tv+v[i],rw-w[i],op);

      }

      if (  tw+rw-w[i]>=W )

      {  op[i]=0;

          dfs(i+1,tw,tv,rw-w[i],op);

      }

   }

}

```

### 6-22 求解简单装载问题（回溯法）

void dfs(int num,int tw,int rw,int op[],int i){

if(i>n){  //i>n说明所有的集装箱都判断完了

if(tw==W&&num

maxw=tw;

minnum=num;

for(int j=1;j<=n;j++){

x[j]=op[j];  //把最优解的值依次赋给最优解向量

}

}

}else{  //没到最后一个集装箱则需要判断当前这个集装箱是选还是不选

op[i]=1;  //如果选择

if(tw+w[i]<=W){  //判断剪枝条件

dfs(num+1,tw+w[i],rw-w[i],op,i+1);

}

op[i]=0;  //如果不选

if(tw+rw-w[i]>=W){  //判断剪枝条件

dfs(num,tw,rw-w[i],op,i+1);

}

}

}

```

### 6-23 求解n皇后问题（非递归回溯法）

void Queens(int n)

{

int i = 1;

q[i] = 0;

while (i >= 1)

{

q[i]++;

while (q[i] <= n && !place(i))

q[i]++;

if (q[i] <= n)

{

if (i == n)

dispasolution(n);

else

{

i++;

q[i] = 0;

}

}

else

i--;

}

}

```

### 6-24 求解流水作业调度问题（回溯法）

void dfs(int i){

if(i>n){

if(f2[n]

bestf=f2[n];

for(int j=1;j<=n;j++){

bestx[j]=x[j];   

}

}

}else{  

for(int j=i;j<=n;j++){  

swap(x[i],x[j]);  

f1+=a[x[i]];     

f2[i]=max(f1,f2[i-1])+b[x[i]];  

if(f2[i]

dfs(i+1);   

}

f1-=a[x[i]];

swap(x[i],x[j]);

}

}

}

```

## 编程题

### 7-1 多项式求和

#include

using namespace std;

double p[100001];

int main()

{

    int n;

    double  x0;

    cin>>n>>x0;

    for(int i = n;i>=0;i--)

    {

        cin>>p[i];

    }

    double sum = 0;

    for(int i = 0;i<=n;i++)

    {

        sum+=p[i]*pow(x0,i);

    }

    printf("%.3lfn",sum);

}

```

### 7-2 快速幂运算

#include

using namespace std;

int mod = 1000;

int QuickPower(int a,int b)

{

    int res =1;

    if(b==0)return 1;

    a%=mod;

    while(b>0)

    {

        if(b%2==1)

        {

            res = res*a%mod;

        }

        b >>=1;

        a = a*a%mod;

    }

    return res;

}

int main()

{

    int a,b;

    cin>>a>>b;

    cout<

}

```

### 7-3 n以内素数个数

#include

  #include

using namespace std;

  const int SIZE = 1e8+100;

 int prime[SIZE];         

 bool is_prime[SIZE];   

 int slove(int n)

 {

     long long p = 0;

     for(int i = 0; i <= n; i++)

         is_prime[i] = true;           

     is_prime[0] = is_prime[1] = false;    

     for(int i = 2; i <= n; i++)

     {

         if(is_prime[i])            

         {

             prime[p++] = i;          

             for(int j = 2 * i; j <= n; j += i)

                 is_prime[j] = false;

         }

     }

     return p;

 }

 int main()

 {

     long long n;

     while(cin >> n)

     {

         int res = slove(n);

         cout << res << endl;

     }

 }

```

### 7-4 特别数的和

#include

#include

bool check(int x){

    int t;

    while(x){

        t=x%10;

        if(t==2||t==0||t==1||t==9){

            return true;

        }

        x/=10;

    }

    return false;

}

int main(){

    int n,sum=0;

    scanf("%d",&n);

    for(int i=0;i<=n;i++){

        sum += i*check(i);

    }

    printf("%d",sum);

}

```

### 7-5 插入排序还是归并排序

#include

#include

#include

using namespace std;

const int N=110;

int a[N],b[N];

int main()

{

    int n;

    cin>>n;

    for(int i=0;i

        cin>>a[i];

    for(int i=0;i

        cin>>b[i];

    int j,i;

    //     判断是不是插入排序

    for(i=0;i

    for(j=i+1;j

    

    if(j==n)

    {

        puts("Insertion Sort");

        sort(a,a+i+2);

    }

    else

    {

        puts("Merge Sort");

        int flage=1,k=1;

        while(flage)

        {

            flage=0;

            for(int i=0;i

          

            k=k<<1; //  k*=2;

            for(int i=0;i

            

            sort(a+(n/k)*k,a+n);

        }

    }

    cout<

    for(int i=1;i

        cout<<' '<

}

```

### 7-6 改写二分搜索算法

#include

using namespace std;

int a[1000000];

int main()

{

    int n,x;

    cin>>n>>x;

    int flag = 0;

    int num = 0;

    int t = -1;

    int sum = 0;

    for(int i = 0; i < n; i ++) {

        cin>>a[i];

        if(a[i] < x){

            num ++;

            t = i;

        }

        if(a[i] == x){

            flag = 1;

            sum = i;

        }

    }

    if(flag == 1) {

        cout<

    }else if(num == n){

        cout<

    }else if(num == 0){

        cout<<"-1 0"<

    }else {

        cout<

    }

}

```

### 7-7 古老的汉诺塔

#include

using namespace std;

int n,cou=0;

void hanio(int n,char a,char b,char c) //b为中间

{

cou++;

if(n==1)

{

printf("%c-->%cn",a,c);

}

else

{

hanio(n-1,a,c,b);

printf("%c-->%cn",a,c);

hanio(n-1,b,a,c);

}

}

int main()

{

cin>>n;

hanio(n,'A','B','C');

printf("%dn",cou);

return 0;

}

```

### 7-8 棋盘覆盖

#include

using namespace std;

int cover[100][100];

int title=1;

void board_cover(int tr,int tc,int dr,int dc,int size){

    if(size==1){

        return ;

    }

    int num=title++;

    size =size/2;

    if(dr

        board_cover(tr,tc,dr,dc,size);

    else{

        cover[tr+size-1][tc+size-1]=num;

        board_cover(tr,tc,tr+size-1,tc+size-1,size);

    }

    if(dr=tc+size)

    board_cover(tr,tc+size,dr,dc,size);

    else{

        cover[tr+size-1][tc+size]=num;

        board_cover(tr,tc+size,tr+size-1,tc+size,size);

    }

    if(dr>=tr+size&&dc>=tc+size)

    board_cover(tr+size,tc+size,dr,dc,size);

    else{

        cover[tr+size][tc+size]=num;

        board_cover(tr+size,tc+size,tr+size,tc+size,size);

    }

    if(dr>=tr+size&&dc

    board_cover(tr+size,tc,dr,dc,size);

    else{

        cover[tr+size][tc+size-1]=num;

        board_cover(tr+size,tc,tr+size,tc+size-1,size);

    }

}

int main(){

    int dr,dc,length;

    cin>>dr>>dc>>length;

    cover[dr][dc]=0;

    board_cover(1,1,dr,dc,length);

    for(int i=1;i<=length;i++){

        for(int j=1;j<=length;j++){

            printf("%4d",cover[i][j]);

        }

        cout<

    }

}

```

### 7-9 数的三次方根

#include

using namespace std;

int main()

{

    double n;

    cin>>n;

    if(n>=0)

    printf("%.6lfn",pow(n,1.0/3));

    else{

        printf("-%.6lfn",pow(-n,1.0/3));

    }

}

```

### 7-10 斐波那契数列（III）

#include

#define Max 998244353

struct juzhen

{

unsigned long long M[2][2];

};

struct juzhen mul(struct juzhen A, struct juzhen B)

{

struct juzhen C;

for (int i = 0; i < 2; i++)

{

for (int j = 0; j < 2; j++)

{

C.M[i][j] = 0;

for (int k = 0; k < 2; k++)

{

C.M[i][j] = C.M[i][j] + A.M[i][k] * B.M[k][j];

C.M[i][j] = C.M[i][j] % Max;

}

}

}

return C;

}

struct juzhen qul(unsigned long long t, struct juzhen a)

{

struct juzhen res;

res.M[0][0] = 1; res.M[0][1] = 0;

res.M[1][0] = 0; res.M[1][1] = 1;

while (t > 0)

{

if (t % 2)

res = mul(res, a);

a = mul(a, a);

t = t>>1;

}

return res;

}

int main()

{

unsigned long long N, sum = 0;

scanf("%llu", &N);

struct juzhen A;

struct juzhen D;

A.M[0][0] = 1;

A.M[0][1] = 1;

A.M[1][0] = 1;

A.M[1][1] = 0;

if (N == 1 || N == 2) printf("1");

else

{

D = qul(N - 2, A);

sum = (D.M[0][0] + D.M[0][1]) % Max;

printf("%llu", sum);

}

return 0;

}

```

### 7-11 矩阵连乘问题

#include

using namespace std;

const int MAX = 1005;

int p[MAX];

int m[MAX][MAX];

int n;

void  matrix()

{

    int i,j,r,k;

    memset(m,0,sizeof(m));

    for(r = 2; r<=n; r++)

    {

        for(i = 1; i<=n-r+1; i++)

        {

            j = i+r-1;

            m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];

            for(k = i+1; k

            {

                int t = m[i][k] +m[k+1][j]+p[i-1]*p[k]*p[j];

                if(t

                {

                    m[i][j] = t;

                }

            }

        }

    }

}

int main()

{

    cin>>n;

    for(int i=0; i

        cin>>p[i];

    matrix();

    cout<

    return 0;

}

```

### 7-12 数字三角问题

#include

using namespace std;

int main(){

int n;

cin>>n;

int num[101][101] ={0};

for(int i=1;i<=n;i++){

for(int j=1;j<=i;j++){

cin>>num[i][j];

}

}

int m[101][101]={0};

for(int j=1;j<=n;j++){

m[n][j]=num[n][j];

}

for(int i=n-1;i>0;i--){

for(int j=1;j<=i;j++){

m[i][j]=num[i][j]+max(m[i+1][j],m[i+1][j+1]);

}

}

cout<

}

```

### 7-13 01背包问题

#include

using namespace std;

int N,V;

int v[1005],w[1005],dp[1005];

int main() {

cin>>N>>V;

for(int i=1; i<=N; i++) {

cin>>v[i]>>w[i];

}

for(int i=1; i<=N; i++) {

for(int j=V; j>=v[i]; j--) {

dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

}

}

cout<

return 0;

}

```

### 7-14 流水作业调度

#include

using namespace std;

const int N = 110,M = 2100;

pairp[N];

typedef pair PII;

int main()

{

    int n;

    

    cin >> n;

    int s1 = 0,s2 = 0;

    vectorv1,v2;

    

    for(int i = 1;i <= n;i ++)

    {

        cin >> p[i].first >> p[i].second;

        if(p[i].first < p[i].second){

            v1.push_back({p[i].first,p[i].second});

        }else{

            v2.push_back({p[i].first,p[i].second});

        }

    }

    sort(v1.begin(),v1.end(),[](PII p1,PII p2){

        return p1.first < p2.first;

    });

    sort(v1.begin(),v1.end(),[](PII p1,PII p2){

        return p1.second < p2.second;

    });

    

    vectorvec;

    for(auto &x : v1){

        vec.push_back(x);

    }

    

    for(auto &x : v2){

        vec.push_back(x);

    }

    

    s1 += vec[0].first;

    s2 += vec[0].first + vec[0].second;

    

    for(int i = 1;i < vec.size();i ++){

        s1 += vec[i].first;

        if(s1 > s2){

            s2 = s1 + vec[i].second;

        }else{

            s2 = s2 + vec[i].second;    

        }

        

    }

    

    cout << s1 << ' ' << s2 << endl;

    

    return 0;

}

```

### 7-15 最优二分检索树（未完成）

#include

#include

#include

int p[5500],q[5500];

int c[5200][5200],w[5200][5200];

int R[5200][5200];

int n;

int a[5500];

typedef struct BiTNode{

        int num;

        BiTNode* Lc;

        BiTNode* Rc;

}BiTNode, *BiTree;

void input()

{

     int i;

     scanf("%d",&n);

     for(i=0;i

        a[i] = i+1;

     p[0]=-1;

     for(i=1;i<=n;i++)

        scanf("%d",&p[i]);

     for(i=0;i<=n;i++)

        scanf("%d",&q[i]);

}

void OBST( )

{

     int i,j,m,k,l;

     float tmp,tmp1;

     for(i=0;i

     {

           w[i][i]=q[i];

           c[i][i]=0;

           R[i][i]=0;

           w[i][i+1]=q[i+1]+p[i+1]+q[i];

           R[i][i+1]=i+1;

           c[i][i+1]=q[i+1]+p[i+1]+q[i];

     }

     w[n][n]=q[n];

     R[n][n]=0;

     c[n][n]=0;

     for(m=1;m<=n;m++)

     {

         for(i=0;i<=n-m;i++)

         {

             j=i+m;

             w[i][j]=w[i][j-1]+q[j]+p[j];

             tmp=c[i][i]+c[i+1][j];

             k=i+1;

             //for(l=i+2;l<=j;l++)

             for(l = R[i][j-1];l<=R[i+1][j];l++)

             {

                  tmp1=c[i][l-1]+c[l][j];

                  if(tmp1

                  {

                     tmp=tmp1;

                     k=l;

                  }

             }

             c[i][j]=w[i][j]+c[i][k-1]+c[k][j];

             R[i][j]=k;

         }

     }

}

BiTree buildtree(int i,int j)

{

       if(i>=j)

          return NULL;

       BiTree Tr;

       Tr=(BiTree)malloc(sizeof(BiTNode));

       if(!Tr)

          return NULL;

       Tr->num=R[i][j];

       Tr->Lc=buildtree(i,R[i][j]-1);

       Tr->Rc=buildtree(R[i][j],j);

       return Tr;

}

void preTree(BiTree T)

{

     if(T)

     {

        printf("%dn",a[T->num-1]);

        preTree(T->Lc);

        preTree(T->Rc);

     }

}

int main(int argc, char *argv[])

{

   BiTree BT;

   input();

   OBST();

   BT=buildtree(0,n);

   preTree(BT);

   return 0;

}

### 7-16 求解资源分配问题

#include

using namespace std;

#define Max_N 101

int m, n;

int arr[Max_N][Max_N];

int res[Max_N][Max_N];

int dp[Max_N][Max_N];

int run() {

    for (int i = 1; i <= m; ++i) {

        for (int j = 1; j <= n; ++j) {

            for (int k = 1; k <= j; ++k) {

                int sum = dp[i - 1][j - k] + arr[i][k];

                if (sum >= dp[i][j]) {

                    dp[i][j] = sum;

                    res[i][j] = k;

                }

            }

        }

    }

    return dp[m][n];

}

int main() {

    cin >> m >> n;

    for (int i = 0; i <= m; ++i) {

        for (int j = 0; j <= n; ++j) {

            cin >> arr[i][j];

        }

    }

    int sum = run();

    for (int i = m; i > 0; --i) {

        cout << i << " " << res[i][n] << endl;

        n -= res[i][n];

    }

    cout << sum;

    return 0;

}

```

### 7-17 0-1背包（加强版，输出物体编号）

#include

#include

#include

#include

#include

using namespace std;

const int maxx=1500;

int v[maxx]={0},w[maxx]={0};

int dp[maxx][maxx];

int main(){

    int n,vp;

    scanf("%d %d",&vp,&n);

    for(int i=1;i<=n;i++){

        scanf("%d %d",&v[i],&w[i]);

    }

   for(int i=0;i<=n;i++){

        for(int j=0;j<=vp;j++){

            dp[i][j]=0;

        }

   }

   int flag[1500];

    int k=0;

    for(int i=1;i<=n;i++){

        for(int j=vp;j>=0;j--){

            if(j-v[i]>=0){

                dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

            }else

                dp[i][j]=dp[i-1][j];

        }

    }

    printf("%dn",dp[n][vp]);

    int x=n,y=vp;

    for(int i=n;i>=1;i--){

        if(dp[i][y]>dp[i-1][y]){

            flag[k++]=i;

            y-=v[i];

        }

    }

    sort(flag,flag+k);

    for(int i=0;i

        printf("%d ",flag[i]);

    }

}

```

### 7-18 最长公共子序列

#include

using namespace std;

const int N=1010;

int n,m;

char a[N],b[N];

int f[N][N]={0};

int main()

{

    cin>>n>>m;

  for(int i=1;i<=n;i++)

      cin>>a[i];

    for(int i=1;i<=m;i++)

        cin>>b[i];

    

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            f[i][j]=max(f[i-1][j],f[i][j-1]);

            

            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);

        }

    cout<

    return 0;

}

```

### 7-19 月饼

#include

#include

#define Max 1010

using namespace std;

struct yuebin{

    double space;

    double value;

    double all;

}a[Max];

bool cmp(yuebin a,yuebin b)

{

    return a.value>b.value;

}

int main()

{

    int N,D;

    scanf("%d%d",&N,&D);

    int i;

    for(i=0;i

    {

        scanf("%lf",&a[i].space);

    }

    for(i=0;i

    {

        scanf("%lf",&a[i].all);

        a[i].value=a[i].all/a[i].space;

    }

    sort(a,a+N,cmp);

    double money=0;

    for(int i=0;i

    {

        if(a[i].space<=D)

        {

            D-=a[i].space;

            money+=a[i].all;

        }

        else

        {

           money+=D*a[i].value;

           D=0;

        }

        if(D==0)break;

    }

    printf("%.2f",money);

}

```

### 7-20 会场安排问题

#include

#include

using namespace std;

int a[100], b[100];

void shu(int k, int start[], int end[]) {

int count = 0;

int j = 0;

for (int i = 0; i < k; i++) {

if (start[i] < end[j]) {

count++;

}

else {

j++;  

}

}

cout << count;

}

int main() {

int k;

cin >> k;

for (int i = 0; i < k; i++) {

cin >> a[i] >> b[i];

}

sort(a, a + k);

sort(b, b + k);

shu(k, a, b);

}

```

### 7-21 最优合并问题

#include

#include

using namespace std;

#define N 10000

bool cmp(int a,int b){

    return a>b;

}

int max(int a[],int k){

sort(a,a+k,cmp);

int maxs=a[0]+a[1]-1;

int t=a[0]+a[1]-1;

for(int i=2;i

    t+=a[i];

maxs+=t;

}

return maxs;

}

int min(int a[],int k){

     sort(a,a+k);

 int mins=0;

 for(int i=0;i

     mins+=a[i]+a[i+1]-1;

 a[i]=a[i]+a[i+1];

 a[i+1]=0;

 sort(a,a+k);

 }

 return mins;

}

int main(){

     int k,m,n;

 int a[N];

 scanf("%d",&k);

 for(int i=0;i

     scanf("%d",&a[i]);

 }

 m=max(a,k);

 n=min(a,k);

 printf("%d %dn",m,n);

}

```

### 7-22 多参加活动，生活才精彩

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

const ll maxn = 1e9+7;

const int N = 400000;

int num[N];

struct pe{

    int s,e,f;

}p[110];

bool cmp(pe a,pe b){

    

        return a.e < b.e;

}

int main()

{

   int n;

   cin >> n;

   for(int i = 0;i < n;i++){

        cin >> p[i].s >> p[i].e >> p[i].f;

   }

   sort(p,p+n,cmp);

   int star = 0;

   int num = 0;

   int sum = 0;

   for(int i = 0;i < n;i++){

        if(star <= p[i].s){

            star = p[i].e;

            sum+= p[i].f;

            num++;

        }

   }

   cout << num << " " << sum << endl;

}

```

### 7-23 Activity selection problem(Activities sorted)

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

const ll maxn = 1e9+7;

const int N = 400000;

int num[N];

struct pe{

    int s,e;

}p[110];

bool cmp(pe a,pe b){

    return a.e < b.e;

}

int main()

{

   int n;

   cin >> n;

   for(int i = 0;i < n;i++){

        cin >> p[i].s;

   }

   for(int i = 0;i < n;i++){

        cin >>  p[i].e ;

   }

   sort(p,p+n,cmp);

   int star = 0;

   int num = 0;

   for(int i = 0;i < n;i++){

        if(star <= p[i].s){

            star = p[i].e;

            num++;

        }

   }

   cout << num << endl;

}

```

### 7-24 h0154.加勒比海盗——最优装载问题

#include

using namespace std;

int p[100001] = {0};

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int c,n;

        cin>>c>>n;

        int cnt = 0;

        int w[n+1];

        for(int i = 1;i<=n;i++)

        {

            cin>>w[i];

        }

        sort(w+1,w+n+1);

        int tt = c;

        for(int i = 1;i <= n;i++)

        {

            if(tt>=w[i])

            {

                cnt++;

                tt-=w[i];

            }

            else{

                break;

            }

        }

        cout<

    }

}

```

### 7-25 求解汽车加油问题

#include

using namespace std;

int p[100001] = {0};

int main()

{

    int d,k;

    cin>>d>>k;

    int dis[k+2] = {0};

    for(int i = 1;i<=k;i++)

        cin>>dis[i];

    int cnt = 0;

    int now = 0;

    int t = d;

    int flag = 1;

    for(now = 0;now

    {

        t-=dis[now+1];

        if(t<0)

        {

            flag = 0;

            break;

        }

        else{

            if(t

            {

                cnt++;

                t = d;

            }

        }

    }

    if(flag)

    {

        cout<

    }

    else cout<<"No Solution!"<

}

```

### 7-26 从小到大

```python

print("True")

```

### 7-27 八皇后问题（*）

#include

#include

#include

#include

using namespace std;

int n, *x,m=1;

long num;

char a[80000][50];

bool check(int k) {

for (int j = 1; j < k; j++) {

if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k]))

{

return false;

}

}

return true;

}

void backtrack(int k) {

int i;

if (k > n) {

num++;

for ( i = 1; i <= n; i++)

{

a[m][x[i]] = 'Q';

m++;

}

}

else

{

for ( i = 1; i <= n; i++)

{

x[k] = i;

if (check(k))

{

backtrack(k + 1);

}

}

}

}

int main() {

memset(a, '.', sizeof(a));

cin >> n;

x = new int[n + 1];

backtrack(1);

for (int i = 1; i < m; i++)

{   

for (int j = 1; j <= n; j++)

{

cout << a[i][j];

if (j < n)cout << " ";

}

cout << endl;

if (i%n == 0&&i!=m-1) { cout << endl; }

}

if (num == 0)

cout << "None";

delete[]x;

return 0;

}

```

### 7-28 旅行销售员

#include

using namespace std;

int INF=999999999;

const int N=100;  //const  初始化

int maps[N][N];   //存储图

int n,m;         //n表示顶点数，m表示边数

int bestw;

struct Node

{

    int x[N];

    int cl;

    int id;

};

bool operator<(const Node &a,const Node &b){

    return a.cl>b.cl;

}

void bfs()

{

    priority_queueq;

 Node node;

 node.cl = 0;

    for(int i=1;i<=n;i++){

        node.x[i]=i;

    }

    q.push(node);

    while(!q.empty()){

        Node newnode=q.top();

        q.pop();

        int t;

        t = newnode.id;

        if(t==n){

            if(maps[newnode.x[t-1]][newnode.x[n]] != INF

&& maps[newnode.x[n]][newnode.x[1]] != INF ){

             if(newnode.cl + maps[newnode.x[t-1]][newnode.x[n]]

                   + maps[newnode.x[n]][newnode.x[1]] < bestw){

                   bestw = newnode.cl+maps[newnode.x[t-1]][newnode.x[n]]

                   + maps[newnode.x[n]][newnode.x[1]];//更新bestw;

                } else{

                 continue;

}

            }else{

             continue;

}

        }

        if(newnode.cl >= bestw) continue;

        for(int j = t; j <= n; j++){

    if(newnode.cl + maps[newnode.x[t-1]][newnode.x[j]] < bestw){

                int c = newnode.cl + maps[newnode.x[t-1]][newnode.x[j]];

                Node node;

                node.cl = c;

                node.id = t+1;

                for(int i = 1; i <= n; i++)

                    node.x[i] = newnode.x[i];

                swap(node.x[t],node.x[j]);

                q.push(node);

            }

        }

    }

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){

     for(int j = 1; j <= n; j++)   {

     int w;

    cin >> w;

    if(w == 0)

     maps[i][j] = INF;

    else

     maps[i][j] = w;

}

    }

    bestw=INF;

    bfs();

    cout << bestw;

}

### 7-29 全排列（回溯，字典集）

#include

using namespace std;

int main()

{

    int n;

    cin>>n;

    int a[n];

    for(int i = 0;i < n;i++)

    {

        a[i] = i+1;

    }

    int cnt = 0;

    do{

        if(cnt==0){

            cnt++;

        }

        else{

            cout<

        }

        for(int i = 0;i < n;i++)

        {

            cout<

        }

    }while(next_permutation(a,a+n));

}

```

### 7-30 圆排列问题

#include

#include

#include

using namespace std;

const int N=20;

double minlen=1000,x[N],r[N];

double bestr[N];

double center(int t)

{

double temp=0;

for(int j=1;j

{

double xvalue=x[j]+2.0*sqrt(r[t]*r[j]);

if(xvalue>temp)

temp=xvalue;

}

return temp;

}

void compute(int n)

{

double low=0,high=0;

for(int i=1;i<=n;++i)

{

if(x[i]-r[i]

low=x[i]-r[i];

if(x[i]+r[i]>high)

high=x[i]+r[i];

}

if(high-low

{

minlen=high-low;

for(int i=1;i<=n;++i)

bestr[i]=r[i];

}

}

void backtrack(int t,int n)

{

if(t==n+1)

{

compute(n);

}

else

{

for(int j=t;j<=n;++j)

{

swap(r[t],r[j]);

double centerx=center(t);

if(centerx+r[t]+r[1]

{

x[t]=centerx;

backtrack(t+1,n);

}

swap(r[t],r[j]);

}

}

}

int main()

{

int n;

cin >> n;

for(int i=1;i<=n;++i)

cin >> r[i];

backtrack(1,n);

printf("%.4fn",minlen);

for(int i=1;i<=n;++i)

cout<

cout<

return 0;

}