苏晓辉の云端作业备份
第十一周 众数问题#include#include #include #include using namespace std; const int N = 1e5 + 7; int a[N]; int zs, cs; // 1 2 2 2 4 5 void range(int *a, int n, int &l, int &r) { // L=2 R=5 -=3没毛病（存储位置-1） int mid = n / 2; for (l = 0; l < n; l++) if (a[l] == a[mid]) break; for (r = l + 1; r < n; r++) if (a[r] != a[mid]) break; } void asd(int *a, int n) { int l, r, mid = n >> 1; range(a, n, l, r); int same = r - l; if (same > cs) cs = same, zs = a[mid]; if (l > cs) asd(a, l); if (n - r > cs) asd(a + r, n - r); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n), asd(a, n); printf("众数：%d 总个数(重数)：%dn", zs, cs); return 0; }
我不知道我对边界的思考是不是对的，我看网络上同学们采用L+1>CS的写法
在我的思考中我认为L是不用+1的，举例子在注释中
//划分思想：左侧残部（共l个）如果比当前【最大重数】大
//才有存在更大重数的可能性，才向下递归
//关于范围 1 2 2 2 4 5 距离
// L=1 R=4（实际要搜1 45两块）
// a:最左侧开始 l=1 搜1
// a+r: 4号位置开始 n-r=2搜45
#include#include int res = 0, n; void asd(int n) { if (n == 1) res++; for (int i = 2; i <= n; i++) if (n % i == 0) //可以整除就向下分解 asd(n / i); } int main() { printf("输入正整数:"); scanf("%d", &n), asd(n); printf("分解总数:%dn", res); return 0; }
这个是看能整除就往下走，如果能多给个数组是有能力输出分解方案的
这里是从小到大枚举拆分方案（例如12从 2*2*3 到3*4）；同时涉及全排列问题
（在递归过程中自动解决）
#include#include #include using namespace std; const int N = 1e3 + 7; int n, f[N], a[N], res; //此处F含义：以【第i个数】结尾的上升子序列的最长长度 int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]), f[i] = 1; //长度至少=1，只有一个数字的情况 //【枚举·上一个数字】 for (int j = 1; j < i; j++) if (a[j] < a[i]) //如果是【上升】 f[i] = max(f[i], f[j] + 1); } for (int i = 1; i <= n; i++) res = max(res, f[i]); printf("%d", res); return 0; }
#include#include #include using namespace std; const int N = 1e5 + 7; int n, a[N], q[N]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int len = 0; //当前最长序列长度 for (int i = 1; i <= n; i++) { int l = 0, r = len; //在所有可能的前子串长度中进行寻找 //也可能自己太小了，导致为0也是可能的s while (l < r) { // r和l是长度的下标 int mid = l + r + 1 >> 1; if (q[mid] < a[i]) //末端更小，可以接入 l = mid; //为什么可以选到mid的最大值？ //单调性？二分的思想？ //二分属性会找到第一个符合这个属性的元素位置 //此时对应的r就是最大的长度 else r = mid - 1; } //寻找接入位置 // printf("%d %dn", l, r); //【bug预检】：修改左侧二分会出bug len = max(len, r + 1); //是否更新len q[r + 1] = a[i]; // r+1位置末端min更新为ai } printf("%d", len); return 0; }
// f[x]：以第x个数结尾的最长上升子序列的长度（改进版本或不涉及）
// q[x]：长度为x的子序列的最小结尾数值是谁（具有递增性质）
//搜索过程采用二分
//【接入措施】：希望前面子序列与当前ai的 “距离” 尽可能近
//也就是在前面找到一个 【小于ai】且【数值最大】 的进行接入
//以此保证接入合法，且对于ai的序列最长
//独立任务最优调度问题 #include3-9圈乘运算 补充の例题 分治#include #include #include using namespace std; const int N = 1e4 + 7; int a[N], b[N], f[N][N]; int time_a, n, min_t = 0x3f3f3f; int dp() { for (int i = 1; i <= n; i++) //每个作业 for (int j = 0; j <= time_a; j++) // A机器所有时间状态 f[i][j] = j < a[i] ? f[i - 1][j] + b[i] : min(f[i - 1][j - a[i]], f[i - 1][j] + b[i]); //状态不合法：由B转移得来， 否则：AB中取得min进行转移 // f[i-1][j-a[i]]：第I作业给到A处理，B机器总用时不变，延承 // f[i-1][j]+b[i]：第I作业给到B处理，A机器总用时不变，加上B处理第I作业的情况 for (int i = 0; i <= time_a; i++) //扫描，处理完成N个作业时候， { int t = max(f[n][i], i); // A B机器中最大耗时为真实时间 if (min_t > t) //取得真实时间的最小值 min_t = t; } return min_t; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), time_a += a[i]; for (int i = 1; i <= n; ++i) scanf("%d", &b[i]); printf("%dn", dp()); return 0; }
T7-棋盘覆盖
//【P20 2.6棋盘覆盖】 #include#include #include using namespace std; int num = 0, map[500][500]; void cover(int x, int y, int hx, int hy, int size) { if (size == 1) //自棋盘大小=1，没得玩 return; int s = size / 2, cx = s + x, cy = s + y, t = ++num; //【黑点坐标·左上块】 if (hx < cx && hy < cy) cover(x, y, hx, hy, s); else { map[cx - 1][cy - 1] = t; cover(x, y, cx - 1, cy - 1, s); } //【黑点坐标·右上块】 if (hx < cx && hy >= cy) cover(x, cy, hx, hy, s); else { map[cx - 1][cy] = t; cover(x, cy, cx - 1, cy, s); } //【黑点坐标·左下块】 if (hx >= cx && hy < cy) cover(cx, y, hx, hy, s); else { map[cx][cy - 1] = t; cover(cx, y, cx, cy - 1, s); } //【黑点坐标·右下块】 if (hx >= cx && hy >= cy) cover(cx, cy, hx, hy, s); else { map[cx][cy] = t; cover(cx, cy, cx, cy, s); } } int main() { printf("棋盘覆盖，输入【棋盘大小】【黑点坐标】："); int n, x, y; scanf("%d%d%d", &n, &x, &y); map[--x][--y] = 0; cover(0, 0, x, y, n); for (x = 0; x < n; x++) { for (y = 0; y < n; y++) printf("%dt", map[x][y]); printf("nnn"); } return 0; }
// s：中间位置（左上块の最右下角）（+1后转 右下块の最左上角）
// x y：当前棋盘最左上角位置，在实际棋盘中的坐标
// cx cy：右下块，最左上坐标 t：本次放置的三角块の编号
// x是行（往下走），y是列（往右走）
//以下，会发生 3个if和 1个else；不存在黑点的，部署三角块
//存在黑点的，往此方向进行递归
T8-归并排序
//【归并排序】 #include#include using namespace std; void asd(int *a, int left, int right, int mid) //两个有序数列，合成一个有序数列 { int x, y, z; // right=0 left=5 总长度6 int b[right - left + 1]; for (x = left; x <= right; x++) //乱序的，先存下来 b[x - left] = a[x]; //【指针部署】 //【左区间首部x】 【右区间首部y】 //【左右两区】是有序的，依次写回a x = left; // mid在【左半区】の末尾 y = mid + 1; for (z = left; z <= right; z++) //区间写回 { if (x > mid) //【左区间】部署完成，全空 a[z] = b[y++ - left]; else if (y > right) //【右区间】部署完成，全空 a[z] = b[x++ - left]; else if (b[x - left] > b[y - left]) //【右区间】更小 a[z] = b[y++ - left]; else if (b[x - left] < b[y - left]) a[z] = b[x++ - left]; } } void merge(int *a, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; merge(a, left, mid); merge(a, mid + 1, right); asd(a, left, right, mid); //合并！ } int main() { int a[105] = {7, 25, 43, 18, 67, 71, 76, 24, 30, 19, 85, 64, 17, 75, 42, 53, 86, 41}, n = 18, i; merge(a, 0, n - 1); for (i = 0; i < n; i++) printf("%d ", a[i]); return 0; }
T9-快排
#include#include using namespace std; #define N 100010 int node[N], n; void swap(int &s1, int &s2) { int k = s1; s1 = s2, s2 = k; } void asd(int a[], int l, int r) { if (l >= r) return; int x = a[l + r >> 1], s1 = l - 1, s2 = r + 1; while (s1 < s2) { do s1++; while (a[s1] < x); //左侧靠近 do s2--; while (a[s2] > x); //右侧靠近 if (s1 < s2) //没有溢出 swap(a[s1], a[s2]); } asd(a, l, s2), asd(a, s2 + 1, r); } int main() { scanf("%d", &n); for (int x = 0; x < n; x++) scanf("%d", &node[x]); asd(node, 0, n - 1); for (int x = 0; x < n; x++) printf("%d ", node[x]); return 0; }
T10-循环赛程
//【循环赛日程表P35 2.11】 #include#include using namespace std; int main() { //循环赛日程表 //整体是从上往下按照【行の拓展】，每轮行数*2 int k, n = 1, a[513][513] = {}, m = 1; int x, y, i, j, t; printf("循环赛日程表，输入选倍数："); scanf("%d", &k); for (x = 1; x < k; x++) n *= 2; t = n * 2; for (x = 1; x <= n * 2; x++) a[1][x] = x; for (x = 1; x <= k; x++) // 总轮次 { // x=1 n=4（需要处理的小块个数） m（工作区中点） // y（当前正在处理の小块标号） for (y = 1; y <= n; y++) //本次需要处理的方块总数 { for (i = m + 1; i <= 2 * m; i++) { for (j = m + 1; j <= 2 * m; j++) //上半区域对下半区域开展覆盖 { // ij下注模拟【小块四分后の右下块】坐标 // x=1 y=3（处理第三个方块） n=4 m=1 // m恰好是【四分块】小块的长度 a[i][j + (y - 1) * m * 2] = a[i - m][j + (y - 1) * m * 2 - m]; //（左上方四分块给到右下角） a[i][j + (y - 1) * m * 2 - m] = a[i - m][j + (y - 1) * m * 2]; //（右上方四分块给到左下角） //左侧是【右下角四分块】 //减去一个四分块长度即可 //乘以2是因为你要跨越大块，而不是四二分之一块 } } } n /= 2; m *= 2; } for (x = 1; x <= t; x++) { for (y = 1; y <= t; y++) printf("%dt", a[x][y]); printf("nnn"); } return 0; }
T11-最大子段
//【最大子段问题】·分治算法P58 #include#include using namespace std; int a[666], n; void init() { printf("几个数字："); scanf("%d", &n); for (int x = 1; x <= n; x++) scanf("%d", &a[x]); } int max(int x, int y) { int sum = 0, c, left, right; if (x == y) sum = a[x] > 0 ? a[x] : 0; //不给负数？ else { c = (x + y) / 2; left = max(x, c); //【左半区】 right = max(c + 1, y); //【右半区】 //【中区】 int xmax = 0, xsum = 0; //中区左半部分最大值 for (int i = c; i >= x; i--) { xsum += a[i]; if (xmax < xsum) xmax = xsum; } int ymax = 0, ysum = 0; //中区有半部分最大值 for (int i = c + 1; i <= y; i++) { ysum += a[i]; if (ymax < ysum) ymax = ysum; } sum = xmax + ymax; if (sum < left) sum = left; if (sum < right) sum = right; } return sum; } int main() { //最大子段问题·分治算法 O（nlogn） // Day68 P58 init(); printf("最大和；%d", max(1, n)); return 0; }
T12-根号划分
#include#include #include #include using namespace std; #define s(a, l, r) sort(a + l, a + r + 1); #define g(a, l, r) sort(a + l, a + r + 1, greater ()); const int N = 1e6 + 7; int a[N], b[N], n; void show() { for (int x = 1; x <= n; x++) printf("%d ", a[x]); } void fire() { s(a, 1, n); show(); printf("n"); g(a, 1, n); show(); } void merge(int *a, int l, int r) { if (l < r) { int t = (int)sqrt(l - r + 1); //例如 l=1 r=16 出来结果应该是4 if (t > 1) //至少2元素 { //再往下分割成merge for (int x = 0; x < t; x++) //这里t是向下取整的，要么=4刚好全跑完 merge(a, l + x * t, l + (x + 1) * t); merge(a, l + t * t, r); //要么就是有剩余一部分尾巴收尾处理 //注意！末尾特判，因为可能不够凑出整个sqrt } s(a, l, r); //改成g就是从大到小排序 } } int main() { printf("输入启动：n"), scanf("%d", &n); for (int x = 1; x <= n; x++) //从1开始存 scanf("%d", &a[x]); // fire(); // STL排序，复杂度nlogn merge(a, 1, n), show(); return 0; }
T13-整数因子分解
#include#include int res = 0, n; void asd(int n) { if (n == 1) res++; for (int i = 2; i <= n; i++) if (n % i == 0) //可以整除就向下分解 asd(n / i); } int main() { printf("输入正整数:"); scanf("%d", &n), asd(n); printf("分解总数:%dn", res); return 0; }
T13-众数问题
#include动态规划#include #include #include using namespace std; const int N = 1e5 + 7; int a[N]; int zs, cs; // 1 2 2 2 4 5 void range(int *a, int n, int &l, int &r) { // L=2 R=5 -=3没毛病（存储位置-1） int mid = n / 2; for (l = 0; l < n; l++) if (a[l] == a[mid]) break; for (r = l + 1; r < n; r++) if (a[r] != a[mid]) break; } void asd(int *a, int n) { int l, r, mid = n >> 1; range(a, n, l, r); int same = r - l; if (same > cs) cs = same, zs = a[mid]; if (l > cs) asd(a, l); if (n - r > cs) asd(a + r, n - r); //划分思想：左侧残部（共l个）如果比当前【最大重数】大 //才有存在更大重数的可能性，才向下递归 //关于范围 1 2 2 2 4 5 距离 // L=1 R=4（实际要搜1 45两块） // a:最左侧开始 l=1 搜1 // a+r: 4号位置开始 n-r=2搜45 } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n), asd(a, n); printf("众数：%d 总个数(重数)：%dn", zs, cs); return 0; }
T1-矩阵连乘
//【矩阵连乘】·P46 动态规划 3.1 #include#include using namespace std; #define max 0xfffffff #define N 2745 int n, p[N + 1], dp[N + 1][N + 1], way[N + 1][N + 1]; void init() { printf("输入【矩阵个数】："); scanf("%d", &n); int x, y; for (x = 0; x <= n; x++) //《初始化》 { for (y = 0; y <= n; y++) { way[x][y] = 0; dp[x][y] = max; } } printf("输入【行列情况】："); //共【n+1】个数字 for (x = 0; x <= n; x++) { scanf("%d", &p[x]); dp[x][x] = 0; //自己不能乘以自己 } } void test() { int x, y; for (x = 1; x <= n; x++) { for (y = 1; y <= n; y++) { if (dp[x][y] == max) printf("Tt"); else printf("%dt", dp[x][y]); } printf("nnn"); } printf("nnn"); for (x = 1; x <= n; x++) { for (y = 1; y <= n; y++) { printf("%dt", way[x][y]); } printf("nnn"); } } void Find_Answer() { int x, y, z, t, min, temp; for (x = 2; x <= n; x++) //【分区大小】从2到n { for (y = 1; y <= n; y++) //【分区块·起始点】··结束点位置或出现溢出情况 { z = x + y - 1; //例如n=5 x=3 y=2 起始点2分3点即234 结束点4=3+2-1 // z【分区块·末端点 】 if (z > n) //末端点·溢出 break; for (t = y; t < z; t++) //【寻找·切入位置】【切入起始点后方】y-z之间，寻找t后切入 { min = dp[y][z]; //【前端行】【切入区】【后端列】 temp = dp[y][t] + dp[t + 1][z] + p[y - 1] * p[z] * p[t]; if (min > temp) { min = dp[y][z] = temp; way[y][z] = t; } } } } printf("最小乘积次数：%dn", dp[1][n]); } void Find_Way(int x, int y) { if (x == y) return; int k = way[x][y]; Find_Way(x, k); Find_Way(k + 1, y); printf("A[%d,%d] * A[%d,%d]n", x, k, k + 1, y); } int main() { init(); Find_Answer(); test(); Find_Way(1, n); return 0; }
最长公共子序列
//【最长公共子序列】P54 3.3 #include#include #include using namespace std; char a[500], b[500], dp[500][500] = {}, way[500][500]; void work() { printf("启动输入："); scanf("%s%s", &a, &b); for (int x = 1; x <= strlen(a); x++) { for (int y = 1; y <= strlen(b); y++) { if (a[x - 1] == b[y - 1]) { dp[x][y] = dp[x - 1][y - 1] + 1; way[x][y] = 1; } else if (dp[x - 1][y] > dp[x][y - 1]) { dp[x][y] = dp[x - 1][y]; way[x][y] = 2; } else { dp[x][y] = dp[x][y - 1]; way[x][y] = 3; } } } } void Find_road(int x, int y) { if (x == 0 || y == 0) return; if (way[x][y] == 1) { Find_road(x - 1, y - 1); printf("%c ", a[x - 1]); } else if (way[x][y] == 2) Find_road(x - 1, y); else Find_road(x, y - 1); } void show() { for (int x = 1; x <= strlen(a); x++) { for (int y = 1; y <= strlen(b); y++) { printf("%dt", dp[x][y]); } printf("nnn"); } printf("n"); for (int x = 1; x <= strlen(a); x++) { for (int y = 1; y <= strlen(b); y++) { printf("%dt", way[x][y]); } printf("nnn"); } printf("子串情况："); Find_road(strlen(a), strlen(b)); } int main() { work(); show(); return 0; }
最大连续子段和 3种版本
//【拓展·最大子矩阵】暴力·制作测试样例使用 #include#include using namespace std; int main() { printf("输入启动："); int m, n, a[20][20]; scanf("%d%d", &m, &n); for (int x = 1; x <= m; x++) for (int y = 1; y <= n; y++) scanf("%d", &a[x][y]); int max = (1 << 31), sum, t[4]; for (int x = 1; x <= m; x++) { for (int y = 1; y <= n; y++) //确定起点 { for (int x1 = x; x1 <= m; x1++) { for (int y1 = y; y1 <= n; y1++) //确定终点 { sum = 0; for (int i = x; i <= x1; i++) for (int j = y; j <= y1; j++) sum += a[i][j]; if (sum > max) { t[0] = x; t[1] = y; t[2] = x1; t[3] = y1; max = sum; } } } } } printf("%d <%d %d>--<%d %d>", max, t[0], t[1], t[2], t[3]); return 0; }
//【最大连续字段和P57 3.4】启用dp #include#include #include #include using namespace std; int main() { //最大子段和，动态规划 int n, a[666]; printf("输入总数："); scanf("%d", &n); for (int x = 1; x <= n; x++) scanf("%d", &a[x]); int b[666] = {}, max = 0, k, q; //【sum】是局部的求和，小于0时候被丢弃 int dp[666] = {}; for (int x = 1; x <= n; x++) { if (dp[x - 1] > 0) //【简化】dp[x-1]+a[x]>a[x] dp[x] = dp[x - 1] + a[x]; //【延续·最大序列和】 else //【更迭·更好的启发点】 { dp[x] = a[x]; q = x; //起发点 } //否则，丢弃sum，更新为当前值 if (dp[x] > max) { max = dp[x]; k = x; //用于存放最大值所处位置 } } printf("最大值：%d，起发点%d，终点%d", max, q, k); return 0; }
//【最大の连续子段和】·动态规划·不存于dp #include#include #include #include using namespace std; int main() { int n, a[666]; printf("输入总数："); scanf("%d", &n); for (int x = 1; x <= n; x++) scanf("%d", &a[x]); int b[666] = {}, sum = 0, max = 0, k, q; //【sum】是局部的求和，小于0时候被丢弃 for (int x = 1; x <= n; x++) { if (sum > 0) sum += a[x]; //如果大于0，加上当前值 else { sum = a[x]; q = x; //起发点 } //否则，丢弃sum，更新为当前值 if (sum > max) { max = sum; k = x; //用于存放最大值所处位置 } } printf("最大值：%d，起发点%d，终点%d", max, q, k); return 0; }
最大子矩阵
//【最大子矩阵】动态规划 多维度转一维 #include#include using namespace std; int m, n, a[50][50]; int dp1[50][50] = {}; int xy[4] = {}, maxx = (1 << 31); //起始点·终止点坐标；最大值 void test() { printf("nn【DP1·辅助数组情况】n"); for (int x = 1; x <= m; x++) { for (int y = 1; y <= n; y++) printf("%dt", dp1[x][y]); printf("nnn"); } } void init() { printf("输入参数："); scanf("%d%df", &m, &n); for (int x = 1; x <= m; x++) for (int y = 1; y <= n; y++) scanf("%d", &a[x][y]); //辅助矩阵生成 for (int x = 1; x <= m; x++) { for (int y = 1; y <= n; y++) { dp1[x][y] += dp1[x - 1][y] + a[x][y]; //上一行加来 } } // test(); } void work() { for (int x = 1; x <= m; x++) //【起始行】 { for (int y = x; y <= m; y++) //【终末行】 { int t[n + 1]; //每列情况 for (int z = 1; z <= n; z++) t[z] = dp1[y][z] - dp1[x - 1][z]; //【局部转化·为一维状态】 //下面就和一维处理一样了 int dp[n + 1] = {}, yy; for (int z = 1; z <= n; z++) { if (dp[z - 1] > 0) //简化判断式P59 dp[z] = dp[z - 1] + t[z]; //【延续】 else { yy = z; dp[z] = t[z]; //【更迭·启动点】 } if (dp[z] > maxx) { maxx = dp[z]; xy[0] = x; //行·起始 xy[1] = yy; //列·起始 xy[2] = y; //行·终末 xy[3] = z; //列·终末 } } } } } void ans() { printf("最大矩阵和：%d <%d %d>--<%d %d>n", maxx, xy[0], xy[1], xy[2], xy[3]); } int main() { init(); work(); ans(); return 0; }
