个人总结易错点及方法

boy♂Next♂dooor · 2024-12-21 09:15:05 · 个人记录

！开LONGLONG！

1. 线段树query操作return 时,注意query(lc,l,r)和query(rc,l,r)都只用算一遍，保证O(logn)。否则TLE

2. 不影响时间复杂度的操作不必过度贪心 增加讨论难度

3.1ULL/1UL/1L区别 注意2^64-1级别的要开unsigned long long才够，而且还要配上lull. 要开全！

4.对负数取模，不应该用 (a+mod)%mod，而是 (a%mod+mod)%mod，否则可能会有a<-Mod从而错误

只要%mod前有“ - ”。不要分析了，直接+mod再%mod,杜绝负数取模任何一丝可能！

5.数学题尝试打表找规律

6.多次操作 考虑线段树的lazytag思想优化复杂度

7.大样例检验： if(!system("fc call3.ans c3.ans")) cout<<"AC"; else cout<<"WA";

8.if(!stk.empty()&&s[i]==stk.top())调用stk.top()要保证栈非空，不然会段错误，其它STL同理

if()的两个条件不能反 才能保证不对空的容器取top

9.看清多组数据 多测不清空是罪恶的！！临时变量也要重置！注意是在组外读数，还是组内读数！dp数组也要清空！

记得每组处理前的初始化。 如 清空数组，max=INF,min=-INF

不要在处理时使用return 0!

10.定义局部变量千万要初始化！如 void f() { int a =0 ;}

11.搜索思路之一：贪心简单情况，搜索复杂情况

12.技巧：搜索的各状态个数会有影响，可以给每个状态定义一个cnt.如 每次操作一个cnt++,一个cnt--

13.搜索要回溯

14.线段树warning

• 结构体里不要int p;
• add(p)=0//下传完记得清除父节点懒标记
• num(p)+=len(p)k;//每次累计新加的贡献 不能 add(p)，会重复之前的贡献
• if(l(p)>r||r(p)<l)//要用||
• 线段树上二分：O(logn)

  int query(int p,int l,int r,int m)//找>=m的最小前缀和
  {
  if(l == r) return l;
  //if(l(p)>r||r(p)<l) return 0;
  //if(l<=l(p)&&r>=r(p)) return num(p);
  down(p);
  int mid=l+(r-l)/2;
  if(m<=num(lc)/**mul*/) return query(lc,l,mid,m);
  else return query(rc,mid+1,r,m-num(lc)/**mul*/);//记得-num(lc)
  }

  15. 判二分图warning：

• return dfs(y,3-c) (×)

  if(!dfs(3-c)) return 0; √

  因为染色过程，一错全错，但不是一对全对好吧

  • 二分图是无向图！

  16.对于类似 多次操作 的题目，要注意不同操作之间的互相影响，比如覆盖/合并等（说的就是你 三值逻辑）

  17.基底{a[1].a[2],...a[n]},若数i能被表示出来，那么i+a[j]一定能被表示出来(筛法/dp转移）

  18.注意dp数组不要爆数据范围，数组不要越界

  19.发现要讨论的情况太多时，考虑更普适性的算法

  20.代码简化：

  • 集合中要进行操作的子集不一定要预处理存起来，可以要操作时再判条件
  • 搜索问题不要沉迷建图。。。等到搜索的时候再建"边"就好

  21.多测不要用break来跳过一组！用continue

  22.考虑到浮点数的误差，能用long long最好别用double

  23.序列问题，考虑子序列可能dp，状态设计为dp[i][j] 第i位为开头/结尾，保留j位(子序列长度) 时的答案

  例 关键：转化答案为求子序列使得删掉节约代价最大

24.写部分分，注意n<=1e3,不代表都是三位数

25.int型数组在128MB内存下最大开到2500 0000是比较保险的（占100MB内存） long long: 1e7左右

26.v[i]类flag不要放到循环结束条件里 应该是if(v[i]) continue;

for(int i=1;i<=k&&!v[i];i++) ×

27.

for(i 1..n)
    for(j 1..m)
        if..break

虽然最坏可能有O(nm),但数据不卡的话也不是不行
spfa式的算法

28.优先队列对于一些要按顺序操作的题有优化奇效

一个不够，可以用2个

29.取q.top()，往往要q.pop() 如BFS的时候！运行超时首先考虑这个！

30.小根堆: priority_queue<int,vector<int,int>,greater<int> > q

31.重载运算符/自定义cmp

bool operator < (const node&a) const{
    return a.x>a;
}

bool cmp(node a,node b) return a.x>b.x;

32.100000~500000——NlogN

33.传递闭包bitset优化 循环顺序即floyd循环顺序

f[k][i][j] :i到j经过1..k点是否到达，k表示了状态划分，所以一定要在外层。k由k-1转移而来

f(k,1,n)
    f(i,1,n)
        if(a[i][k]) a[i]|=a[k];

35.可以暴力算出的量，不一定要直接数学得出（特别是还包含浮点数的）

36.别死磕T1 （不爆零要紧）

37.BIT区修 区查 两棵树的操作只能分开

int a[N],tr[N][2];//0:差分数组 1:tr0[i]*(i-1)
void change(int x,int d,int tp)
{
    for(;x<=n;x+=lb(x))  tr[x][tp]+=d;//debug2:只有末尾+k(r-1) tr[x][1]+=d*(x-1);
}
int query(int x,int tp)
{
    int ans=0;
    //debug:for(;x<=n;x+=lb(x)) 
    for(;x;x-=lb(x)) ans+=tr[x][tp];
    return ans;
}

cin>>op>>l>>r;
        if(op==1)
        {
            cin>>k;
            change(l,k,0),change(r+1,-k,0);
            change(l,(l-1)*k,1),change(r+1,-k*r,1);
        }
        else cout<<(query(r,0)*r-query(r,1))-(query(l-1,0)*(l-1)-query(l-1,1))<<'\n';

• 记得sum[l..r]=query(r)-**query(l-1)**;//-1!!!!

38.Dp优化方法：要去掉最内层循环，可以考虑在外层循环，预处理好pre数据，用于下一次循环

rf(y,h,0)//到高度y
    {
        f(x,1,n)//到树x
        {
            dp[x][y]=max(dp[x][y+1],pre[y+d])+a[x][y];
            pre[y]=max(dp[x][y],pre[y]);//pre[y]:高度y最大ans   
//如不预处理，则每个x都要遍历一次dp[x][y+d]
        }
    }   

39.不要轻易对INT＿ＭＡＸ做运算　会溢出

INT_MAX + 1 = INT_MIN

INT_MIN - 1 = INT_MAX

abs(INT_MIN) = -INT_MIN = INT_MIN

40.数据结构优化dp：每次转移前贪心一下，用单调队列/堆维护一下min/max，下个状态计算时就可以直接利用较小的决策集合

41.ST表：循环顺序

for(int j=1;j<=log(n)/log(2);j++)//一步两步四步条的状态划分，必须外层循环！！
  for(int i=1;i+(1<<j)-1<=n;j++)
        ...

return max(f[l][k],f[r-(1<<k)+1][k]);//下标2都是K！

42. 二选一问题还是加个bool 判断数组好一些

43. if(x)应该是x!=0的意思。。而不是x>0

1. ans*=s[i]%mod;改*ans = ans s[i] % mod;** 避免上溢

2. 0/1分数规划：假设原式<=Ans,转化为***<=0,设F(Ans)<=0,二分找最大Ans使得F(Ans)最大值<=0

3. *关于scanf()格式化输入中换行： \r 是回车，return

\n 是换行，newline

windows环境下 换行符是\r\n ,linux 下才是\n

所以windows环境下本地调试这样格式化输入是不行的啊啊

47.段错误：因为上面那个f(i,0,g[x].size()-1)。 C++vector 的size函数返回vector大小，返回值类型为unsigned int型，unsigned int的取值范围为0~2^32 -1。

这就是问题所在了。unsigned类型的变量是没有-1这种东西的，如果g[x].size()=0，那么g[x].size()-1就会发生下溢，返回一个异常大的值（实测返回18446744073709551615），从而导致段错误。

所以只能用 for(int i=0;i<g[x].size();i++)

48.反向跑图思想：

有向图求P个点各自到S点最短距离，可建反向图，以S为起点Dij

49.一条路径上的问题，可考虑取两个路径上的点进行分析

50.分层图最短路

for(int i=1;i<=k;i++)
       {
           add(x+(i-1)*n,y+i*n,0);//add(x,y+i*n,0);
           //add(y+i*n,x+(i-1)*n,0);  免费了一条边到了下一层就不能回头了，所以没有回边
           add(y+(i-1)*n,x+i*n,0);//保证从1到k层不往回 
           add(x+i*n,y+i*n, z);//一开始忘了在每一层自己里面都要建边：用d[x,p]更新d[x.1+p]
           add(y+i*n,x+i*n, z);
       }

51.除非T组数据之类的，不要轻易用while(T–)来操作！！

52. 离散化

    sort(a+1,a+1+n);
    int len=unique(a+1,a+1+n)-(a+1);
    for(int i=1;i<=n;i++) h[i]=lower_bound(a+1,a+1+len,h[i])-a

53.循环顺序注意 倒序 要用 >= 和 --j

54.初始化字符串数组：memset(a, '\0', sizeof(a));

55.一个deque,q.front()=q.back()&&q.size()>1 →首尾匹配

56.对于一筹莫展的序列构造题：考虑用栈/队列/双端队列等配合贪心来思考？

57.区间覆盖问题一定要用lst存上一处测速仪/雷达(使用过的右端点),不能直接用上一个区间的右端点(不一定用了) ，考虑相邻区间右左端点能否重合取

58.惨痛的CSPST2教训：打好部分分后想改成正解，记得 备份 !!

59.避免浮点数误差的一种手段：转整型，考虑向上/下取整

60.一些预处理操作要注意边界值：如设置a[0]=0 a[maxn]=l+1等

61.开GDB对应不到具体语句的segf：可能是浮点数溢出 （ /0 )

62.结合特殊条件看是否遗漏情况

63.pair数组不要用memset清空，循环赋值就好

64.想要获取 "最近的点" 这样的量，不必从每个点往后找。考虑预处理数轴上每个数字x前后最近的点对lr[x]，用于查询即可，O(值域)

65.数组N直接开到上界，不要为了省一点点空间而对不同的数组开不同长度，RE的风险往往高于MLE

66.如果组数为1答案对，组数大于1就错，警醒自己是不是 多测未清空？or 循环中用的全局变量没有在每次循环中重定义 ？

67.思考dp的转移，要大胆猜想贪心，对于序列问题常用lst[i]等记录上一个xx的位置。如CSPT3 关键：贪心出转移的性质，用来转移的一定是前面最近同值数，lst[i]和i之间应该填满其它颜色

68.运行未响应多半是RE了，检查数组是否开小？尤其注意 桶类数组，长度不应是数据个数，而是值域大小

69.对于一些答案具有“对称性”，可以只考虑一半 从而降低时间复杂度

70.枚举warning/trick（剪枝卡暴力分）

• 下面写法仅当i,j,k可轮换 / 满足升序时

for i 1..n if(被排除的答案） continue; for j i+1..n//若仅i,k对称可剪枝：j=1..n , k=i+1..n(即不妨设k>i)
if(j==i) continue; if(被排除的答案） continue; for k j+1..n if(k==j||k==i) continue;//去重：注意j和i都要判！

- **记忆化思想** ：比如多次询问一个数后面最近的满足某条件的数，可以再每次回答时往后遍历标记出ans[i]=t（满足条件否？）。下一次回答时，遍历碰到i,直接回答 t , then , break!

- 记忆化搜索warning:最好用有返回值的dfs函数,开够传入参数(即dp的维数）

    什么时候用？ 搜到的状态空间会重复，即**搜索树有重边**
- **埃式筛思想**：
 若一次循环开始的起点得到答案集合是之前的一个的子集，就直接跳过

71.随机访问vector下标不要访问越界到>=v.size()处

72.搜索优化时不要把临界状态直接优化没了（尤其是Bfs，还能正常结束，错误比较隐蔽）

73.对于想贪心一些担心重复/最优解可能不合法的情况，可考虑取前X优解(X=cnt(重复情况）+1）

74.BFS流程记住！
```cpp
Init;
q.push(st);
while(q.size())
{
    int x=q.top();
    q.pop();
    from(x)_move(y);
    if(check(y)) q.push(y);
}

75.打了暴力测大样例时很慢不要直接关掉，挂机先写别的。不要放弃测试，避免白骗分(CSPS惨痛教训）

76.二维数组memset(a,0x3f,sizeof(a)); a[i][j]!=0x3f3f3f3f 因为存储方式不同了，要确定INF，最好就是输出来看一下多大copy上

77.大根堆变小根堆如果要写CMP 或 重载运算符 ，记得不是按 < 写，而是按 > 。（因为要和原来比较规则相反

78.多层循环时注意：外层的一个变量如果内层两个并列循环，避免出现变量第一次操作后无法回头，使得第二个操作使其错误/导致越界的情况 e.g.

dis[i].size()=3
debug5: if(dis[i][t]==j) t++;  t在循环外,可能导致t超了3而不能往回
                int h=0;
                debug6:while(dis[j][h]==i||dis[j][h]==v) h++;
                while (1ull*h < dis[j].size())
                    if(dis[j][h] == i || dis[j][h] == v) h++;

79.用优先队列时，注意分析用if OR while( q.size(）)

80. 答案包含"序号""编号" "第几个" + 程序包含sort ：注意sorted_array下标变化了，要struct { int dat , id ; }存编号

81. umap键值对不能含pair！ unordered_map<PI,int> id; (×）

82. 易搞混的变量最好用顾名思义的变量名

83. Input:

    001
    010
    000
    000

    不能直接用int a[i][j]输入，因为会把010识别为同一个数。 所以只能按 char a[i][j] 读入。

84. 巧用悬线法，在沿一个方向遍历计算的同时维护前缀和sum等量，可简化代码。

85. 打了骗分情况和正解（暴力），切记要对拍，避免特殊情况想错了导致把分骗没

86. 矩阵类题目，记得看清哪个是行，哪个是列

87.打搜索记得回溯，特别是在循环里提前return的情况要记得回溯

88. 枚举时dfs(int x) x=1...n 返回条件：if(x==n+1)//记得+1 否则漏掉x=n的情况

89. 不存在割边 ≠ 图连通

90. 多次查询，若离线回答，不能直接对输入的数据开桶存bool query[]; （因为可能有重复的查询输入数据）

91. 筛数时，注意边界问题

92. 注意一个正整数不能有前导0

93. 有多种选择不知道哪个最优时，要考虑这几种选择情况其实可以化归为同一种处理。e.g. 出炸弹和出三带1，都可以化归为任意带的1牌种类的三带1。

94. 带格子问题注意：1.能否化为点图求解？2.二维搜索不一定要队列存pair,可以分别存x和y队列 3.搜索可能要用两个方向数组分别表示到所在点、到所在的格子编号（可以左上角的点编号为编号）

95. 边权0,1DAG求最短路可以考虑双端队列BFS（贪心放前/放后,少了用pq的 logn 复杂度）

96. 求逆拓扑序，可以直接建反图跑正常toposort

97. BFS 探路只需要一个循环就能获取对应的dx[i],dy[i]

98. 用了deque不要写嗨了然后push_back和push_front不分了

99. 由于'\'是转义字符，比如'\n'是换行，如果要用到'\'这个字符的时候，我们需要用'\\'来表示

100. BFS求最短路原理：最先搜到，即最少步数

101. n行m列走对角 (n+m)为奇数时无法从左上角走到右下角

102. 拓扑排序起点如果已知，就不必循环判入度入队了

103. 拓扑排序，先入度-1，再判入度为0的点入队！

104. 打完程序一定先检查有没有写输入

105. cout保留位数输入 ： cout<<fixed<<setprecision(2)<<dp[1];

106. DFS中, if(v[i]) continue; 只有在对重复点不进行操作的情况下用！ 如果只是不再dfs下去，但要用该点所含信息进行操作则只能在dfs函数开头写 if(v[x]) return;//只跳出dfs
     ( 这也是为什么tarjan算法中不是 if(dfn[y]) continue; ）

107. 如果时间复杂度在1e8处徘徊，可以考虑能否用bitset 使复杂度/w,w=64 or 32

     bitset<N> a;
     a.count()
     a.set(): 将整个 bitset 设置成 true。
     any(): 若存在某一位是 true 则返回 true，否则返回 false。
     none(): 若所有位都是 false 则返回 true，否则返回 false。 

108. 左右移<<还是>>不要打错了，没有卡常需求的话还是*2 /2比较好

109. 快速幂warning:

     • a=a*a%mod;不是res自乘！！考虑幂次为偶数，那么res=1,res就恒等于1了! 只有最后剩下一个奇数时才res*=a

• 传入的参数保险起见也要取模

110. 用费马小定理求乘法逆元 注意保证指数p和底数a互质

111. 分解质因子：先2~\sqrt{n} 试除，n/=i.剩下一个＞\sqrt{n}的大质因数不要忘记了

112. 0-1 Trie: Insert时是从高到低，还是反过来取决于问题所需要的贪心思路。 e.g.最长异或路径，尽可能高位取1，所以从高到底插入。

trie的空间不要开小,建议直接开到上界得了

113. gcd传参考虑有没有负数.如果有,就要改为： int Gcd(int a,int b){ return b ? Gcd(b,a%b) : abs(a) ;}//a取绝对值（因为取模运算结果的正负是由左操作数(a)的正负决定的） 比如传入的是差分值的时候

114. gcd() ,int128 前面是两条下划线！

115. gcd(a,b)=gcd(a,b-a) 推广至多维。即区修区查gcd问题考虑差分区查gcd

116. 差分区间加操作：记得 r+1处要 -d ！ 不是+d !!

117. 复制定义处的数组记得把数组下标给改了 不要保留了a[N] 来输入

118. 运算过程中如果有/,不能边算边取模了，要求乘法逆元

119. 求a^n不是 a=aa ; 而是 an=aa. 注意变量在运算过程中发生的变化

120. 搜索转移时注意当前点的初态，可能是0或者1或者其他

121. 种类并查集常规套路：不是开多个或多维并查集数组，而是扩大并查集规模