[数据结构与算法]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<high

low<high&&L.r[high].key>=pivotkey

low<high&&L.r[low].key<=pivotkey

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<t

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->data<j->data)

????????????{

????????????????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]='\0';

????????return dst;

????????}

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

????{

????????if(i>=start&&i<start+len)

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

????}}

????dst[j] = '\0';

????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] != '\0'){

end++;

}

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

if(isspace(str[k])){

str[k] = '\0';

}

else

break;

}

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

str[j] = str[i];

}

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

str[j] = '\0';

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<int>& Array, int start, int mid, int end){

????

????vector<int> temp = vector<int>(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<int>& 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<algorithm>

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<k;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 <dp[j]+1)) {

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<n;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<n;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<n;i++){

f1+=a[best[i]];

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

}

return f2;

}

```

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

pair<int, int> 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<int, int> 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<minnum){ //满足这个条件即为最优解，则覆盖之前的解

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){

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]<bestf){

dfs(i+1); ??

}

f1-=a[x[i]];

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

}

}

}

```

## 编程题

### 7-1 多项式求和

#include<bits/stdc++.h>

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("%.3lf\n",sum);

}

```

### 7-2 快速幂运算

#include<bits/stdc++.h>

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<<QuickPower(a,b);

}

```

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

#include <iostream>

??#include <cstdio>

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<stdio.h>

#include<stdbool.h>

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<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=110;

int a[N],b[N];

int main()

{

????int n;

????cin>>n;

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

????????cin>>a[i];

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

????????cin>>b[i];

????int j,i;

????// ????判断是不是插入排序

????for(i=0;i<n-1&&b[i]<=b[i+1];i++);

????for(j=i+1;j<n&&b[j]==a[j];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<n;i++) if(a[i]!=b[i]){flage=1;break;} ?

??????????

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

????????????for(int i=0;i<n/k;i++) sort(a+i*k,a+(i+1)*k);

????????????

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

????????}

????}

????cout<<a[0];

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

????????cout<<' '<<a[i];

}

```

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

#include<iostream>

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<<sum<<" "<<sum<<endl;

????}else if(num == n){

????????cout<<n-1<<" "<<n <<endl;

????}else if(num == 0){

????????cout<<"-1 0"<<endl;

????}else {

????????cout<<t<<" "<<t+1<<endl;

????}

}

```

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

#include<bits/stdc++.h>

using namespace std;

int n,cou=0;

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

{

cou++;

if(n==1)

{

printf("%c-->%c\n",a,c);

}

else

{

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

printf("%c-->%c\n",a,c);

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

}

}

int main()

{

cin>>n;

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

printf("%d\n",cou);

return 0;

}

```

### 7-8 棋盘覆盖

#include<bits/stdc++.h>

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<tr+size&&dc<tc+size)

????????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<tr+size&&dc>=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<tc+size)

????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<<endl;

????}

}

```

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

#include<bits/stdc++.h>

using namespace std;

int main()

{

????double n;

????cin>>n;

????if(n>=0)

????printf("%.6lf\n",pow(n,1.0/3));

????else{

????????printf("-%.6lf\n",pow(-n,1.0/3));

????}

}

```

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

#include<stdio.h>

#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 <bits/stdc++.h>

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<j; k++)

????????????{

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

????????????????if(t<m[i][j])

????????????????{

????????????????????m[i][j] = t;

????????????????}

????????????}

????????}

????}

}

int main()

{

????cin>>n;

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

????????cin>>p[i];

????matrix();

????cout<<m[1][n];

????return 0;

}

```

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

#include <bits/stdc++.h>

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<<m[1][1];

}

```

### 7-13 01背包问题

#include <bits/stdc++.h>

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<<dp[V];

return 0;

}

```

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

#include <bits/stdc++.h>

using namespace std;

const int N = 110,M = 2100;

pair<int,int>p[N];

typedef pair<int,int> PII;

int main()

{

????int n;

????

????cin >> n;

????int s1 = 0,s2 = 0;

????vector<PII>v1,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;

????});

????

????vector<PII>vec;

????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 <stdio.h>

#include <stdlib.h>

#include <string.h>

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<n;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<n;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)

??????????????????{

?????????????????????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("%d\n",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 <bits/stdc++.h>

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<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

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("%d\n",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<k;i++){

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

????}

}

```

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

#include<bits/stdc++.h>

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<<f[n][m]<<endl;

????return 0;

}

```

### 7-19 月饼

#include<bits/stdc++.h>

#include<algorithm>

#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<N;i++)

????{

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

????}

????for(i=0;i<N;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<N;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<iostream>

#include<algorithm>

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<stdio.h>

#include<algorithm>

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<k;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<k-1;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<k;i++){

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

?}

?m=max(a,k);

?n=min(a,k);

?printf("%d %d\n",m,n);

}

```

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

#include <iostream>

#include <algorithm>

#include <cmath>

#include <string>

#include <cstring>

#include <map>

#include <queue>

#include <sstream>

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 <iostream>

#include <algorithm>

#include <cmath>

#include <string>

#include <cstring>

#include <map>

#include <queue>

#include <sstream>

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<bits/stdc++.h>

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<<cnt<<endl;

????}

}

```

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

#include<bits/stdc++.h>

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<k;now++)

????{

????????t-=dis[now+1];

????????if(t<0)

????????{

????????????flag = 0;

????????????break;

????????}

????????else{

????????????if(t<dis[now+2])

????????????{

????????????????cnt++;

????????????????t = d;

????????????}

????????}

????}

????if(flag)

????{

????????cout<<cnt<<endl;

????}

????else cout<<"No Solution!"<<endl;

}

```

### 7-26 从小到大

```python

print("True")

```

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

#include<stdio.h>

#include<math.h>

#include<iostream>

#include<string.h>

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<bits/stdc++.h>

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_queue<Node>q;

?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<bits/stdc++.h>

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<<endl;

????????}

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

????????{

????????????cout<<a[i]<<" ";

????????}

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

}

```

### 7-30 圆排列问题

#include<iostream>

#include<cmath>

#include<algorithm>

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<t;++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)

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

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

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

}

if(high-low<minlen)

{

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]<minlen)

{

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("%.4f\n",minlen);

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

cout<<bestr[i]<<' ';

cout<<endl;

return 0;

}