错题集
搜索:
luogu P1162 填涂颜色：
作为一道简单的bfs搜索题，竟然把临界条件给弄错了(开始时候写成了(x >= 0 && x <= n+1 && x >= 0 && y <= n+1))，最后显示暴空间浪费了大量的时间，实在是不应该。
11.19 牛客校赛总结：(2/6/9)花了大量的时间写b,c,d三道题，结果却几乎都是tle，写了一下i题。用的bfs写，结果先是爆栈，又是超时，或许应该考虑双广优化。其次是b题，据说要用到线段树或者树状数组，纯纯のhash表自然鉴定为t。c题用的Omn遍历，结果也是超时，事实上是有On的算法的。d题用到floyd，我没有学，dfs硬存最短路劲，直接费。
鉴定为寸寸地飞舞。
1 要好好地研究时间复杂度和内存空间的问题，这应该是一个算法竞赛er的基本功
2 考虑到双向广搜的优化，关键是如何处理相交的地点
3 可以开始研究floyd了，发现会bfs的大概有3/4不会floyd，可以提高自己的竞争力
4 对于时间的把控理解不是很到位，都到倒数十分钟了，都还有一道签到题没有开，竞赛中这样极其不妥
5 等到一定时间就把线段树给学了。
6 dp还不是很了解，据说有人用dp敲了c，我只能感叹牛皮，最近重点掌握dp。
11.25 牛客D题火车路径问题：
学了floyd了之后又写了一遍，结果又RE了
floyd一般来说需要套三层循环，是On^3的算法，暴力出奇迹，三层k，i，j分别对应中间点，起始点，最终点，一般来说如果插入了一条新的路径，就需要用这个路径的起点和终点作为中间点进行两次二层循环。如果k，i，j的顺序颠倒了，就会产生re，这就是我磨了半小时的原因
P2895 [USACO08FEB]Meteor Shower S：
竟然忘记了处理初始位置的特例，直接导致我百分之29的测试点过不去。
P3879 [TJOI2010] 阅读理解：
写的第一道字典树…注意最后一个节点的tag【u】处理的方式。然后居然吧ijk搞错了，粗心。
11.24 acwing 多重背包问题1：
第三层的for循环写错了，本来是k * v[j] <= j，写成了k * s[j] <= j，粗心出错
进行降维的时候，将j逆序遍历，相当于是01背包的扩展
11.24 acwing 多重背包问题2：
初步学习运用了vector，了解auto关键字在for循环体中可以直接进行遍历(也就是进行偷懒)比如：
for(auto g : goods) //auto代表遍历goods整个容器，其中g代表goods[i];
然后可以运用结构体来声明vector，和结构体queue基本上没有什么太大的区别。
注意在添加元素的时候需要这样写
goods.push_back({v * k, w * k});
其次有关01优化，非常需要注意循环的时候要s -= k，上限和循环变量同步进行变化。
11.24 acwing 混合背包问题。
对于vector思路没有扩展开，没有想到可以把3种所有的情况都放入到同一个vector里，导致浪费了大量的时间，其中不乏是因为对二维姐沟通的vector的声明和操作的理解不到位的原因，但也学到了一些知识，比如auto关键字不能直接用在vec【i】上，尽管这在维度上来说有点反直觉，其次我们仍然可以像vec【i】【j】一样对向量进行操作，size()可以获取vector的长度，vector<vector
11.25 acwing 数字三角形
问题挖坑，负数。要将ans初始化为-0x3f3f3f3f,初始化为-0x3f3f3f过不去。
-0x3f3f3f3f = -1044266559(一般来说就是初始化为这个叼毛数字)
-0x3f3f3f = -4144959
-0x3f3f = -16191
-0x3f = -63
11.26 acwing 二维费用的背包问题
无他，相比一维的背包问题多套两层循环就过去了
11.27 acwing 分组背包问题
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 120;
int dp[N],n,m;
int v[N],w[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
int s;
cin >> s;
// for(int j = 1; j <= s; j++)
// {
// int v , w;
// cin >> v >> w;
// for (int k = m; k >= v; k--)
// {
// dp[k] = max (dp[k] , dp[k - v] + w);
// }
// }
//错误的原因，这种循环方式虽然看起来符合01背包的直觉，但是实际上却是转换为了多重背包问题
// for(int j = 1; j <= s; j++) cin >> v[j] >> w[j];
// for(int j = 1; j <= s; j++)//先获得每一个组
// for(int k = m; k >= v[j]; k--)//将该组的*所有*(不是严格的所有)状态按照逆序进行遍历(01背包)
// {
// dp[k] = max(dp[k] , dp[k - v[j]] + w[j]); //将会出现问题：这压根就是01背包，事实上组内的物品已经取了k次了
// }
for(int j = 1; j <= s; j++) cin >> v[j] >> w[j];
for(int j = m; j >= 0; j--) //将j也就是最大体积作为集合
for(int k = 1; k <= s; k++) //每一个状态用组进行逆序遍历(01背包)
{
if(j >= v[k]) //如果当前最优解的体积最大值 大于 第j组的物品体积，那么将状态转移进行下去
dp[j] = max(dp[j], dp[j - v[k]] + w[k]);//出现一个情况，一次遍历下来不同状态将取不同组的最优解
}
}
cout << dp[m] << endl;
return 0;
};11.25 acwing 最长上升子序列问题(线性dp)
这类问题的状态表示为 第i个数字为结尾的上升子序列长度
状态属性为最大值
闫氏dp分析法：状态计算：可以将dp问题分割成求各个小上升子序列长度的问题
11.26 acwing 合并区间
上了周娟教练的课，对于并查集这一数据结构有了更加清晰的认识。做起这道题目来还算是比较熟练的。
注意在写代码的过程中遇到的几个点：
puts我平时很少用，今天用了一次发现它在输出字符串的同时会在结尾结束处自动加上换行符号。
首先注意要在开始初始化的时候将rep【x】 = x，也就是指向自己
然后注意find()函数的定义，使用rep【x】 = find【rep【x】】这个赋值语句来寻找父节点，这样子做的好处是可以在每一次查找的过程当中对查找的路径进行压缩，这就也是并查集的精妙之处之一
11.26 acwing dijkstra问题1
dijkstra最短路的搜索算法：
一般的dijkstra：
首先要注意存图，我们一般要求最短路径的时候都要先将存图用的二维数组初始化成inf极大值，然后再根据点的个数对dis【i】【i】进行初始化，然后存图的过程中注意是有向图还是无向图，是否两个节点之间有路径重复。
然后就是dijkstra的核心，它与floyd不同事实上只传入了一个点，求的某个点到另一个某个点的最短距离：
下面是dijkstra的模板
‘’’
const int N = 505;
int d[N][N],dist[N];
bool vis[N];
int n,m;
void dijkstra()
{
memset(dist,0x3f,sizeof(dist));
memset(vis,false,sizeof vis);
for(int j = 1; j <= n; j++) dist[j] = d[1][j];
dist[1] = 0; //自己到自己的距离为0
for(int j = 1; j <= n; j++)
{
int t = -1 , mi = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
if( ( t == -1 || dist[i] < dist[t] ) && vis[i] == false) // vis【j】检测这个节点是否被优化掉了
{
t = i;
}
vis[t] = true;
for(int i = 1 ; i <= n; i++)
{
dist[i] = min( dist[t] + d[t][i] , dist[i] );
}
}
}
‘’’
卡住的原因是初始化的问题，把初始化的对象搞错了，本质还是对dijkstra的不熟悉
还是要多去靠自己慢慢琢磨
存在负权回路的图是不可能求出最短路的，因为只要这这上面兜圈子，路径就可以任意的小。
11.26
牛客大连竞赛
A鬼特么知道卡了什么鬼数据，比赛的时候在这上面浪费了一大堆的时间，最后居然直接用ifelse就过去了
B用的字符哈希，结果特么又爆栈，最后发现是stack这个吊容器不能在为empty的时候pop，不然牛客会报段错误，最后看别人的题解居然贪心就能过。。。我的哈希只是时间少了13ms而已。。。
C是啥来着，循环遍历，神特么搞错了条件又浪费了一堆的时间，注意处理邻边的时候可以用4个if来处理边际情况
D递增数列，掉了一个情况(最大的数同时在开头和结尾的时候)，没过去
E是期望题，没有发现规律，没什么好说的，观察能力不够，这题其实观察使用例就可看出应该怎么做
F第一的大牛用到了set这一stl里面的容器，1分钟半就ac了，本蒻还在用最朴素的算法算了大半天。注意count()方法在set中只会返回0或1，它其实很有用。
G
H把结果判断的条件弄错了,要用flag标记shu，结果真输光光了(笑)
I一个结论(i&1 == 1)可以替代(i%2 == 1)
J不会
K
11.27
蓝桥模拟赛：
1,二进制，可以发现这是我的弱项
2,你需要知道求余的时候不能%0
3,你需要知道reverse函数需要传入开头和结尾的指针，strcat貌似只能用在字符数组上面
对操作字符串的其它指令并不是很熟悉
4,set插入元素的同时会完成排序
11.28
pair优先以左端点排序，然后再以右端点排序
acwing 建立trie注意trie数组是int而不是char类型
acwing 试除法求质数注意i <= x/i 比 i*i <= x 更加快
acwing KMP注意两个字符串的下标从1开始而不是从0开始
acwing floyd不可以求最大路径，会发生累加效应（圣诞老人）（待办）
11.29
堆是一个完全二叉树
如果把同步流关闭，而在代码当中使用了流输入输出和格式化输入输出的话，会优先流输入输出，然后再格式化输入输出。所以在写代码的时候关闭了同步流的话，就不要再混合使用了
格式化输入输出包括scanf，putchar，puts之流
C语言中的数组是在程序运行之前提前向系统申请了内存空间，没有申请空间不允许读写。所以如果数组长度是变量，不能提前申请空间，所以不能用变量来设置动态数组。
但可以利用malloc函数来动态分配空间，实现数组的不定长声明。
11.30
在c++中，*和&在不同的地方有着不同的意义。那么就开门见山先说解引用——解释引用，说的通俗一点就是，直接去寻找指针所指的地址里面的内容，此内容可以是任何数据类型，当然也可以是指针。
华东交通大学2021选拔赛：
被A题卡住了，结果其实就是一个贪心加上双指针，算不上是一个多么难的题，说明我对于贪心算法的理解还是缺少了。
12.1
写了一堆的水题，没啥提升
重新学了双指针，学了快速幂
bellmanford算法：
spfa算法：
12.2
acwing高精度算法：
传入vector数组作为返回值的时候，需要声明vector的数据类型
其次，在与size()进行比较的时候，不推荐使用unsigned的数据类型，尽管size()返回unsigned，因为当数据小于0的时候有一些编译器会报错
链表，邻接表；
结构体+指针，需要用到new，非常慢，比赛不推荐使用
acwing：有向图的拓扑序列，将所有入度为0的点入队。枚举t的所有初边t -> j，d[j]–, if(d[j])
一个有向无环图，一定存在一个入度为0的点
acwing图论：
1.
12.3
ecjtu2022选拔赛：
A题前缀和竟然忘记了在加上数值的时候取模，我吐了
B题完全背包求方案数量
C题，如果出题人没给数据范围全部当作long long处理
D题，太慢了
E题，搞下标对应的时候出了错，奶奶滴
F题，思路很清晰，不可能用高精
G题，BFS，永远滴痛，首先忘了可以存size来实现记录步数，然后有把manyan的顺序搞反了
12.10
acwing食物链问题：变量名写错了浪费了半个小时，扣大分，报错是这样的a[int] = int
"message": "表达式必须包含指向对象的指针类型，但它具有类型 \"int\"",
acwing二分图：
当且仅当图当中不含有奇数环是二分图
yxc：“数组越界了之后，什么错误都有可能发生”
12.13
unordered_map第一个数字对应下标，第二个数字对应的是数量
注意使用ans *= a 与 ans = ans * a的区别，当ans 和 a的数据类型不一样的时候建议使用后者
注意+号与%号的优先级
lowerbound与upperbound的使用方式需要铭记在心
lowerbound返回最左边，upperbound返回最右边
字符串哈希的方式：
ABCD = (1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p^0) mod Q
一般情况下：p 取成131或者13331
Q取成2^64, 这样有%99.99概率不会发生冲突
12.14
https://www.luogu.com.cn/problem/P2872
用结构体储存边后再使用克鲁斯卡尔，因为有排序边的需求
https://www.luogu.com.cn/problem/P1991
无线通讯网（瓶颈生成树）
constexpr 是 C++ 11 标准新引入的关键字
定义变量时可以用 constexpr 修饰，从而使该变量获得在编译阶段即可计算出结果的能力。
12.16
acwing1027. 方格取数
注意数字三角形模型当中如果求的是最小值，极大可能要对矩阵边缘作出特殊化处理
int &x = f[k][i1][i2];这样可以起到节省代码的作用。
12.17
acwing八皇后问题：
可以用横坐标+纵坐标表示第几个对角线
反对角线n - y + x表示。
acwing八数码问题：
通过字符串来表示八数码的状态，x / 3表示行，x % 3表示列
acwing数论
约数
对于数对a,b
有gcd(a, b) = gcd(b , a % b)
且当b = 0的时候，最大公约数为a
线性筛法的核心：n只会被最小质因子筛掉
埃氏筛法与线性筛在10^6的情况下，计算的速度差不多，而在10^7的情况下速度相差了一倍
欧拉函数 - 容斥原理
欧拉筛
欧拉定理：只要a与n互质，设t为n的欧拉函数后的值，则a的t次方取余n等于1
费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。
裴蜀定理
12.18
编辑距离
博弈论
区间贪心
哈夫曼树与贪心，两个最小权值的点一定在树的最下面并且是互为兄弟的，通过解局部最优解得出全局最优解
12.19
有关记忆化搜索问题
有关组合数学：
Cba=Cb−1a−1+Cba−1
12.20
有关异或运算：
将下面的算式进行异或运算
00001000
01000000
01000000
00000000
result1：00001000
00010000
01111000
00000000
00000000
result2：01101000
10010000
10010110
10000100
10010000
result3：00010010
12.21
lcm()求最大公倍数,如果要求两个数a1,a2的最大公倍数，可以使用a1*a2/gcd(a1,a2)来计算
注意对longlong使用scanf输入的时候需要使用%lld不然容易出现不会报错的错误
蒙德里安的梦想：傻缺了
if(表达式1 && 表达式2)
else
与
if(表达式1)
if(表达式2)
else
不一样
