实验一-分治算法

说明：全文题目后面的 * 表示可能有点难度的题目。

A – 众数问题

桶排就完事了！

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int tong[maxn];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d",&x);
        tong[x] ++;
    }
    int Max = -1, ans ;
    for(int i = 0; i < maxn; i++) {
        if(Max < tong[i]) {
            Max = tong[i];
            ans = i; 
        }
    }
    printf("%d\n%d\n",ans,Max);
    return 0;
}

B – 整数因子分解问题*

将分解问题看成，以某个数字开头的分解有多少种，比如12可以看成以2开头的式子有几个，以3开头的有几个，4开头的有几个，6开头的有几个…
其中以2开头的分解式为例，可以看成12 = 2 * 6，即分析6有多少种分解方式，就是有多少个2开头的式子。

#include <bits/stdc++.h>
const int maxn = 1e7 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
LL dp[maxn];
LL dfs(LL x) {
    if (x < maxn && dp[x]) return dp[x];
    LL cnt = 1;
    for (LL i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            cnt += dfs(i);
            if (i * i != x) cnt += dfs(x / i);
        }
    }
    if (x < maxn) dp[x] = cnt;
    return cnt;
}

int main(int argc, char const *argv[]) {
    LL x;
    cin >> x;
    printf("%lld", dfs(x));
    return 0;
}

C – 顺序表应用7：最大子段和之分治递归法*

最大字段和一共有三种可能：

• 左边的一段
• 右边的一段
• 中间的一段

所以分治思想，每次取中间点，求一下左边最大值，右边最大值，中间子段最大值，取max。

其中，中间子段最大值等于，从中间开始到最右边的子段中的最大值加上从中间开始到最左端的子段中的最大值。

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int a[maxn];
int cnt;
int dfs(int l, int r) {
    cnt++;
    if (l == r) {
        return max(a[l], 0);
    }
    int mid = l + r >> 1;
    int sum = -1;
    sum = max(dfs(l, mid), sum);
    sum = max(dfs(mid + 1, r), sum);
    int lsum = 0, rsum = 0, lmax = -1, rmax = -1;
    for(int i = mid; i >= l; i-- ) {
        lsum += a[i];
        lmax = max(lmax, lsum);
    }
    for(int i = mid + 1; i <= r; i++ ) {
        rsum += a[i];
        rmax = max(rmax, rsum);
    }
    return max(sum, lmax+rmax);
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        scanf("%d",a+i);
    }
    int ans = dfs(0, n-1);
    printf("%d %d\n", ans , cnt);
    return 0;
}

D – 骨牌铺方格*

经典斐波那契数列，写成递归+记忆化而已。

hit：2 * n的格子可以看成最左端横着放两个占据一个2 * 2 的格子，和竖着放一个占据 2 * 1 的一个格子两种方案。

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
LL dp[111];
LL dfs(int n) {
    if(dp[n]) return dp[n];
    if(n == 1 || n == 0) return 1;
    return dp[n] = dfs(n-1) + dfs(n-2);
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    printf("%lld\n", dfs(n));
    return 0;
}

非递归版本：

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
LL f[1111] = {0, 1, 2};
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    printf("%lld\n", f[n]);
    return 0;
}

实验二-动态规划

A – 高数Umaru系列（9）——哈士奇

经典01背包不解释。

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int val[111], w[111];
int dp[1111];
int main(int argc, char const *argv[]) {
    int n, m;
    while(cin >> n >> m) {
        memset(dp, 0, sizeof dp);
        for (int i = 1; i <= n; i++) scanf("%d %d", w + i, val + i);
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}

B – 最少硬币问题

分组背包（多重背包）即可。

#include <bits/stdc++.h>
const int maxn = 2e4+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int v[maxn], has[maxn];
int dp[maxn];
int main(int argc, char const *argv[]) {
    int n, m;
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d %d",v+i, has+i);
    cin >> m;
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= v[i]; j--) {
            for(int k = 0; k <= has[i]; k++) {
                if(j - k * v[i] >= 0)
                dp[j] = min(dp[j], dp[j - k * v[i]] + k);
            }
        }
    }
    printf("%d\n", dp[m] == inf ? -1 : dp[m]);
    return 0;
}

C – 数字三角形问题

每个格子可以看成从上方或者左上方过来的，就可以写出转移方程。注意边界情况，如果数组从0开始存，会发生越界，从1开始存即可。

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int dp[111][111], a[111][111];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            scanf("%d",&a[i][j]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
            ans = max(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

D – 石子合并问题*

环形区间DP，转换成一条2 * n 的链即可

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int a[222];
int dp1[222][222], dp2[222][222], sum[222];
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    memset(dp2, 0x3f, sizeof dp2);
    for(int i = 1; i <= n; i++) scanf("%d",a+i), a[i+n] = a[i];
    for(int i = 1; i <= n*2; i++) {
        sum[i] = sum[i-1] + a[i];
        dp1[i][i] = dp2[i][i] = 0;
    }
    for(int len = 2; len <= n; len ++) {
        for(int l = 1; l + len - 1 <= 2 * n; l ++) {
            int r = l + len - 1;
            for(int k = l; k < r; k++) {
                dp1[l][r] = max(dp1[l][k] + dp1[k+1][r] + sum[r] - sum[l-1], dp1[l][r]);
                dp2[l][r] = min(dp2[l][k] + dp2[k+1][r] + sum[r] - sum[l-1], dp2[l][r]);
            }
        }
    }
    int ans1 = -1, ans2 = inf;
    for(int i = 1; i <= n; i++) {
        ans1 = max(ans1, dp1[i][i+n-1]);
        ans2 = min(ans2, dp2[i][i+n-1]);
    }
    printf("%d\n%d\n",ans2, ans1);
    return 0;
}

E – 最长公共子序列问题*

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
char x[555], y[555];
int dp[555][555];
int main(int argc, char const *argv[]) {
    while(~scanf("%s%s",x+1,y+1)) {
        memset(dp, 0, sizeof dp);
        int n = strlen(x+1), m = strlen(y+1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (x[i] == y[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        printf("%d\n", dp[n][m]);
    }

    return 0;
}

实验三-贪心算法

A – 汽车加油问题*

只要油不够到达下一个加油站了就选择加油，如果某段路程大于最大可行驶路程，则无解。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int a[maxn];
int main(int argc, char const *argv[]) {
    int n, p;
    cin >> p >> n;
    n++;
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    int ans = 0, now = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > p) {
            puts("No Solution!");
            exit(0);
        }
        if (now + a[i] > p) {
            ans++;
            now = 0;
        }
        now += a[i];
    }
    printf("%d\n", ans);
    return 0;
}

B – 多元Huffman编码问题*

通过优先队列可以实现 $O(logn)$ 的复杂度实现动态取出当前数组的最值，支持插入新的数。

最大花费，考虑每次只取最少数量，即两个，且设法使得每次取的两个花费最大，即当前数量最大的两堆，依次合并直到只剩一堆。

最小花费，考虑每次选取数量最小的 k 堆，依次合并直到只剩一堆。注意，每次取k个合并成一堆，相当于使得总堆数减少 $k-1$​​ 堆，那么只有总堆数 n % (k-1) == 1 才能使得每次可以选 k 堆，如果不满足条件则添加石子个数为0的石子堆，直到满足条件。注意，如果不满足 n % (k-1) == 1 的话，必须通过加入数量为0的石子堆才行，不能在每次选取时判断是否少于k堆，两者虽然都能保证程序合法，但是不等效，如下为错误代码片段：

while(qs.size() > 1) {
        LL temp = 0;
        for(int i = 0; i < k; i++) {
            if(qs.size() == 0) break;
            temp -= qs.top();
            qs.pop();
        }
        ans2 += temp;
        qs.push(-temp);
}

正确代码：

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

int main(int argc, char const *argv[]) {
    int n, k;
    cin >> n >> k;
    priority_queue<LL> qb, qs;
    for(int i = 0; i < n; i++) {
        LL x;
        scanf("%lld",&x);
        qb.push(x);
        qs.push(-x);
    }
    LL ans1 = 0, ans2 = 0;
    while(qb.size() > 1) {
        LL x = qb.top();
        qb.pop();
        LL y = qb.top();
        qb.pop();
        ans1 += x + y;
        qb.push(x + y);
    }
    while(qs.size()%(k-1)!=1)  qs.push(0);
    while(qs.size() > 1) {
        LL temp = 0;
        for(int i = 0; i < k; i++) {

            temp -= qs.top();
            qs.pop();
        }
        ans2 += temp;
        qs.push(-temp);
    }
    printf("%lld %lld\n", ans1, ans2);
    return 0;
}

C – 装船问题

程设2的题，不讲。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
struct node {
    int p, w;
    double bi;
    bool operator<(const node &t) const { return bi > t.bi; }
} a[1211];

int main(int argc, char const *argv[]) {
    int m;
    cin >> m;
    for (int i = 0; i < 10; i++)
        scanf("%d %d", &a[i].p, &a[i].w), a[i].bi = a[i].p * 1.0 / a[i].w;
    sort(a, a + 10);
    int ans = 0;
    for (int i = 0; i < 10; i++) {
        if (m - a[i].w >= 0) {
            ans += a[i].p;
            m -= a[i].w;
        } else {
            ans += a[i].bi * m;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D – 活动选择

程设2的题，不讲。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
struct node {
    int id, st, ed;
    bool operator<(const node &t) const {
        if(ed == t.ed) return id < t.id;
        return ed < t.ed;
    }
} a[1211];

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%d %d", &a[i].st, &a[i].ed), a[i].id = i + 1;
    sort(a,a+n);
    int now = 0;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        if(now <= a[i].st) {
            ans.push_back(a[i].id);
            now = a[i].ed;
        }
    }
    for(int i = 0; i < ans.size(); i++) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ',');
    return 0;
}

E – 最优合并问题

B题的easy version

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    priority_queue<int> q1, q2;
    for(int i = 0; i < n; i++ ){
        int x; scanf("%d",&x);
        q1.push(-x);
        q2.push(x);
    }
    int ans1 = 0, ans2 = 0;
    while(q1.size() > 1) {
        int x = q1.top();
        q1.pop();
        int y = q1.top();
        q1.pop();
        ans1 -= x + y + 1;
        q1.push(x+y);
    }
    while(q2.size() > 1) {
        int x = q2.top();
        q2.pop();
        int y = q2.top();
        q2.pop();
        ans2 += x + y - 1;
        q2.push(x+y);
    }
    printf("%d %d\n",ans2, ans1);
    return 0;
}

F – 区间覆盖问题

#include <bits/stdc++.h>
const int maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int a[maxn];
int main(int argc, char const *argv[]) {
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++) scanf("%d", a + i); 
    sort(a,a+n);
    int now = a[0], cnt = 1;
    for(int i = 1; i < n; i++ ) {
        if(now + k >= a[i]) continue;
        now = a[i];
        cnt++;
    }
    printf("%d",cnt);
    return 0;
}

实验四-搜索算法

A – 子集和问题*

#include <bits/stdc++.h>
const int maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int n, c;
int ans[maxn], a[maxn], m, f;
void dfs(int i, int sum, int pos){
    if(sum > c || f == 1) return;
    if(sum == c) {
        f = 1;
        for(int i = 0; i < pos; i++) printf("%d%c", ans[i], i == pos - 1 ? '\n' : ' ');
        return;
    }
    for(; i < n; i++) {
        if(a[i] + sum <= c) {
            ans[pos] = a[i];
            dfs(i + 1, sum + a[i], pos + 1);
        }
    }
}
int main(int argc, char const *argv[]) {
    cin >> n >> c;
    int sum = 0;
    for(int i = 0; i < n; i++) scanf("%d", a + i), sum += a[i];
    if(sum < c) puts("No Solution!");
    else {
        dfs(0,0,0);
        if(!f) puts("No Solution!");
    }
    return 0;
}

B – 运动员最佳匹配问题*

经典的dfs搜索恢复现场操作

#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int ans, vis[111], sum;
int n;
int p[111][111], q[111][111], a[111];

void dfs(int i) {
    if(i == n) {
        ans = max(ans, sum);
        return;
    }
    int temp = 0;
    for(int j = i; j < n; j++) {
        temp += a[j];
    }
    if(sum + temp <= ans) return;
    for(int j = 0; j < n; j++) {
        if(vis[j] == 0) {
            ////////////////////////////  恢复现场
            vis[j] = 1;
            sum += p[i][j] * q[j][i];
            dfs(i+1);
            sum -= p[i][j] * q[j][i];
            vis[j] = 0;
            ////////////////////////////  恢复现场
        }
    }
}
int main(int argc, char const *argv[]) {
    cin >> n;
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < n; j++) {
            scanf("%d", &p[i][j]);
        }
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < n; j++) scanf("%d", &q[i][j]);
    for(int i = 0; i < n; i++) 
        for(int j = 0; j < n; j++) a[i] = max(a[i], p[i][j] * q[j][i]);
    dfs(0);
    printf("%d",ans);
    return 0;
}

C – 工作分配问题

B题 easy version

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int n;
int a[111][111], b[111], ans = inf, vis[111], sum;
void dfs(int i) {
    if (i == n) {
        ans = min(sum, ans);
        return;
    }
    int temp = 0;
    for (int j = i; j < n; j++) temp += b[j];
    if (temp + sum >= ans) return;
    for (int j = 0; j < n; j++) {
        if (!vis[j]) {
            vis[j] = 1;
            sum += a[i][j];
            dfs(i + 1);
            vis[j] = 0;
            sum -= a[i][j];
        }
    }
}
int main(int argc, char const *argv[]) {
    cin >> n;
    memset(b, 0x3f, sizeof b);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]), b[i] = min(b[i], a[i][j]);
    dfs(0);
    printf("%d", ans);
    return 0;
}

D – 整数变换问题*

注意下标。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII;
int ans;
int n, m;
char s[maxn];
bool dfs(int sum, int ceng) {
    if (ceng + 1 > ans) return 0;
    if (sum * 3 == m || dfs(sum * 3, ceng + 1)) {
        s[ceng] = 'f';
        return 1;
    }
    if (sum / 2 == m || dfs(sum / 2, ceng + 1)) {
        s[ceng] = 'g';
        return 1;
    }
    return 0;
}
int main(int argc, char const *argv[]) {
    cin >> n >> m;
    while (!dfs(n, 0)) ans++;
    printf("%d\n", ans);
    for (int i = ans - 1; i >= 0; i--) printf("%c", s[i]);
    return 0;
}