个人总结易错点及方法

！开LONGLONG！

1. 线段树query操作return 时,注意query(lc,l,r)和query(rc,l,r)都只用算一遍，保证O(logn)。否则TLE
2. 不影响时间复杂度的操作不必过度贪心 增加讨论难度

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

• 结构体里不要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) (×)

• 二分图是无向图！

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

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

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

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

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

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

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

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

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!!!!

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]
		}
	}	

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！

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

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);
       }

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

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

• 下面写法仅当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的维数）
  什么时候用？ 搜到的状态空间会重复，即搜索树有重边
• 埃式筛思想： 若一次循环开始的起点得到答案集合是之前的一个的子集，就直接跳过

Init;
q.push(st);
while(q.size())
{
	int x=q.top();
	q.pop();
	from(x)_move(y);
	if(check(y)) q.push(y);
}

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++;

80. 答案包含"序号""编号" "第几个" + 程序包含sort ：注意sorted_array下标变化了，要struct { int dat , id ; }存编号
81. umap键值对不能含pair！ unordered_map<PI,int> id; (×）
82. 易搞混的变量最好用顾名思义的变量名
83. Input:

001
010
000
000

84. 巧用悬线法，在沿一个方向遍历计算的同时维护前缀和sum等量，可简化代码。
85. 打了骗分情况和正解（暴力），切记要对拍，避免特殊情况想错了导致把分骗没
86. 矩阵类题目，记得看清哪个是行，哪个是列

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，所以从高到底插入。

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. 种类并查集常规套路：不是开多个或多维并查集数组，而是扩大并查集规模