Komorebi-blog

六月打卡6/22 打卡 6/23 打卡 6/24 打卡 6/25 打卡 6/26 打卡 6/27 打卡 6/29 打卡 7/1 打卡 7/2 打卡

算法基础课

[USACO1.5] [IOI1994]数字三角形 Number Triangles题目描述观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中，从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大权值。 输入格式第一个行一个正整数 $r$ ,表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 输出格式单独的一行,包含那个可能得到的最大的和。 样例 #1样例输入 #1123456573 88 1 02 7 4 44 5 2 6 5 样例输出 #1130 提示【数据范围】对于 $100\%$ 的数据，$1\le r \le 1000$，所有输入在 $[0,100]$ 范围内。 题目翻译来自NOCOW。 USACO Training Section 1.5 IOI1994 Day1T1 题解思路记忆化搜索：mem存储重复的。DP；状态转化方程：f[i][j]=max(f[i+1][j],f[i+1][j+1])+g[i][j];要倒着推。因为dfs递归 ...

[USACO1.5] 八皇后 Checker Challenge题目描述一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。 上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下： 行号 $1\ 2\ 3\ 4\ 5\ 6$ 列号 $2\ 4\ 6\ 1\ 3\ 5$ 这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出，解按字典顺序排列。请输出前 $3$ 个解。最后一行是解的总个数。 输入格式一行一个正整数 $n$，表示棋盘是 $n \times n$ 大小的。 输出格式前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。 样例 #1样例输入 #116 样例输出 #112342 4 6 1 3 53 6 2 5 1 44 1 5 2 6 34 提示【数据范围】对于 $100\%$ 的数据，$6 \le n \le 13$。 ...

数列分段 Section II题目描述对于给定的一个长度为N的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。 关于最大值最小： 例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。 将其如下分段： [4\ 2][4\ 5][1]第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。 将其如下分段： [4][2\ 4][5\ 1]第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。 并且无论如何分段，最大值不会小于 $6$。 所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。 输入格式第 $1$ 行包含两个正整数 $N,M$。 第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。 输出格式一个正整数，即每段和最大值最小为多少。 样例 #1样例输入 #1125 34 2 4 5 1 样例输出 #116 提示对于 $20\%$ 的数据， ...

最大正方形题目描述在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。 输入格式输入文件第一行为两个整数 $n,m(1\leq n,m\leq 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。 输出格式一个整数，最大正方形的边长。 样例 #1样例输入 #1123454 40 1 1 11 1 1 00 1 1 01 1 0 1 样例输出 #112 题解思路二维前缀和公式：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i]j。通过求二维数组的前缀和，当前缀和大于等于要求正方形的边长平方，则输出，否则不输出。二分搜索优化：选择输入边长最小的为边界，然后边长从0开始增加遍历。 代码123456789101112131415161718192021222324#include <bits/stdc++.h>using namespace std;int n, m, ans = 0, x, f[205][205];int main()
...

[USACO1.3] 混合牛奶 Mixing Milk题目描述由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。 Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格可能相同。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。 给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。 注：每天所有奶农的总产量大于 Marry 乳业的需求量。 输入格式第一行二个整数 $n,m$，表示需要牛奶的总量，和提供牛奶的农民个数。 接下来 $m$ 行，每行两个整数 $p_i,a_i$，表示第 $i$ 个农民牛奶的单价，和农民 $i$ 一天最多能卖出的牛奶量。 输出格式单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。 样例 #1样例输入 #1123456100 55 209 403 108 806 ...

【模板】排序题目描述将读入的 $N$ 个数从小到大排序后输出。 输入格式第一行为一个正整数 $N$。 第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。 输出格式将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。 样例 #1样例输入 #11254 2 4 5 1 样例输出 #111 2 4 4 5 提示对于 $20\%$ 的数据，有 $1 \leq N \leq 10^3$； 对于 $100\%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。 题解思路 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include <iostream>#include <vector>using namespace std;// 分区函数，将数组分成两部分，左边的元素小于等于 ...

[NOIP2003 普及组] 乒乓球题目背景国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 $11$ 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 $11$ 分制和 $21$ 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。 题目描述华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 $11$ 分制和 $21$ 分制下，双方的比赛结果（截至记录末尾）。 比如现在有这么一份记录，（其中 $\texttt W$ 表示华华获得一分，$\texttt L$ 表示华华对手获得一分）： $\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}$ 在 $11$ 分制下，此时比赛的结果是华华第一局 $11$ 比 $0$ 获胜，第二局 $11$ 比 $0$ 获胜，正在进行第三局，当前比分 $1$ 比 $1$。而在 $21$ 分制下，此时比赛结果是华华第一局 $21$ 比 $0$ 获 ...

排序冒泡排序思想冒泡排序是一个基于交换的排序。每一轮将序列中的最大值放到序列的尾部。循环每次先确定结尾length的值，然后从头遍历到最后寻找最大值，然后length再减减。 代码1234567891011121314151617181920212223242526272829303132333435363738394041#include <iostream>#include <algorithm> #include <cstdlib>#include <ctime>#define MAXSIZE 10void initArr(int arr[], int length) { for (int i = 0; i < length; i++) { arr[i] = std::rand() % 20; }}void showArr(int arr[], int length) { for (int i = 0; i < length; i++) ...