日记/随记
日记/随记2024.9.72024.9.7,今天多云转小雨。今天迎新早起很累,每次想着早点起都会给自己一段缓冲的时间,又是三个闹钟才把自己叫醒。在b站看到了大佬做的基于树莓派4b的语音助手,感觉真的很厉害,看了他的博客(是不是厉害的人博客都很赞?!附上大佬的博客链接:https://colorfulife.site/后面填在自己的友链上吧。)也是看了大佬的博客想着把自己很久没有更新的博客也更一下,试着学大佬一样随便记录自己想要的内容,也当作一种宣泄自己情绪的地方。总是感慨别人很厉害,自己又老是深陷内耗之中。想做数学又想看看树莓派的项目,加了大佬的微信,询问了up大佬是怎么一个月完成的树莓派项目,果然编程是需要兴趣和肝的。有时候老是不知道如何处理或者说是与异性聊天?感觉很难搞,也是不知道自己为啥会这么想。希望自己不要再内耗了,本来计划今天晚上看看大佬写的项目的代码,想了解下语音转文本和星火模型api怎么用。但是太困了,晚上背单词的时候感觉都要睡着了,背单词还是很枯燥的,最烦的是每次背了好几天的单词到了下一天还是记不住。只能多看反复看,让我这愚笨的大脑记住好了。感觉总是希望自己会很多东西, ...
算法基础课
算法基础课
动态规划习题
[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\%$ 的数据, ...
前缀和and差分习题
最大正方形题目描述在一个 $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$ 获 ...
每日一练
技能升级题目详细小蓝最近正在玩一款 RPG游戏。
他的角色一共有 N个可以加攻击力的技能。
其中第 i个技能首次升级可以提升 Ai点攻击力,以后每次升级增加的点数都会减少 Bi。
⌈Ai/Bi⌉(上取整)次之后,再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M次技能,他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力?
输入格式输入第一行包含两个整数 N和 M。
以下 N行每行包含两个整数 Ai和 Bi。
输出格式输出一行包含一个整数表示答案。
数据范围对于 40%的评测用例,1≤N,M≤1000;对于 60%的评测用例,1≤N≤104,1≤M≤107;对于所有评测用例,1≤N≤105,1≤M≤2×109,1≤Ai,Bi≤106。
输入样例:12343 610 59 28 1
输出样例:147
题解思路这道题采用二分和多路归并的思想。二分体现在加多少攻击力上,它的范围是0~1e6,不断缩小范围就行。如何缩小,需要推导公式,首先我们想象加攻击力是n个数组(将数组中的数看作等差数列,每个数列其实存的是一种攻击力,但是每种攻击力会等差缩小),每个数组都是从大到小排 ...