2022 跳坑（或妙计）记录

标签：node 妙计跳坑 long int 2022 ll qwq define

P7143 [THUPC2021 初赛] 线段树

有恒等式

\[\sum_{i=1}^n i(n+1-i)=\binom{n+2}{3} \]

左式为 \(n\) 长度所有子串长度和。

组合理解：

我们将 \([0,n+1]\) 共 \(n+2\) 个位置设为可以放置的，我们共要放 \(3\) 个石子（每个位置只能放一个）。

先放最左和最右的石子，设位置为 \(0\le x<z\le n+1\)，则我们选择的子串为 \([x+1,z-1]\)。

若 \(z-x=1\)，则 \(y\) 无地放，贡献为 \(0\)，否则，\(y\) 的可放置位置数正好为子串的长度，原式得证。

P6630 [ZJOI2020] 传统艺能

传统艺能：指两个小时调两个没有取模的 sb 错误。

P4097 [HEOI2013]Segment

把带 eps 的浮点比较返回 -1,0,1 的函数写成 bool 类型。

P3388 【模板】割点（割顶）

一行带空格输出的东西不要换行输出，注意输出格式。

P5491 【模板】二次剩余

//We'll be counting stars.
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
	node(int xx=0,int yy=0){ x=xx,y=yy; }
	friend bool operator==(node x,node y){ return x.x==y.x && x.y==y.y; }
};
signed main(){
	node tmp=1;
	cout<<(tmp==1)<<endl;//Yes
	cout<<(tmp==2)<<endl;//No
return 0;}

这是可以编译过的。/jy

CF1712D Empty Graph

二分答案 \([1,2\times 10^9]\) 时 mid=(l+r)>>1; 得开 long long，不然祖宗。

P3332 [ZJOI2013]K大数查询

对拍的时候一定要保证 make.cpp 造出来的数据是合法的。/ll

P3249 [HNOI2016] 矿区

mkp(read(),read()) 是会反过来的。

但是 (node){read(),read()} 是正的。

构造函数 node(read(),read()) 又是反的。

对于计算几何知道向量 \((x,y)\) 求与 \(x\) 轴正方向夹角，用 atan2(y,x)（结果为弧度）不会有除数为 \(0\) 的问题。

P2617 Dynamic Rankings

不要把函数命名为 move()，std 有了这个函数了，而且好像不报错。

arc145_d Non Arithmetic Progression Set

long long 、祖宗、懂？

CF1250N Wires

离散化后解决后输出方案时记得还原回离散化前的值！

P2481 [SDOI2010]代码拍卖会

\(f(x)=10x+1\bmod p\) 一直递归可能不是环，而是 \(\rho\) 形的，所以环长不等于总长度。

然后还要判余数，和 \(n\) 根本走不到 \(\rho\) 的环的情况，反正难调 + 对拍长 + 写得丑。

P1997 faebdc 的烦恼

不要把小于号给重定义成小于等于啊啊啊，会有 TLE 到 WA 不等的蜜汁错误。

gym/103687/problem/M

不要把前缀和数组直接单点求值来取单点的值 qwq。

P4238 【模板】多项式乘法逆

做多项式题输入数组和输出数组尽量不要相同，说不定打架了，况且不好调试。

P3307 [SDOI2013]项链

新科技：Lambda 匿名函数

P4980 【模板】Pólya 定理

将一个数 \(n\) 用 \(O(\sqrt{n})\) 质因数分解算法后记得判 \(n'\ne 1\) 的情况。

P5356 [Ynoi2017] 由乃打扑克

一道分块题。

块长设为 \(B=400\)，数列长度为 \(10^5\)，开了 \(N=10^5+3\)。

然后存每一个块的 delta，数组开了 \(\frac{N}{B}\)，但是从 \(1\) 开始下标，少开一位！一——位——啊——！（调了 4h 写了对拍）。

下次再这种 sb 错误我就是歌姬。

P4569 [BJWC2011]禁忌

kasumi 前建初始矩阵时要 += 不能 =（懂我意思吧）。

也就是说，AC 自动机上可能有重边，需要累加。

P2444 [POI2000]病毒

AC 自动机判断子串要从 x->fail 传向 x。

P3215 [HNOI2011]括号修复 / [JSOI2011]括号序列

这里 splay 指针版不需要记录每个元素的指针，要记录 root，因为有区间 reverse，会改变，查找时直接二分（BST）就行。

而 LCT 中却正好反过来，因为我们要记录点的标号，而且 reverse 操作不会影响标号。不用记录 root。

P6327 区间加区间sin和

由欧拉公式

\[e^{ix}=\cos x+i\sin x \]

得到

\[\begin{matrix} &(\cos \alpha &+i&\sin \alpha ) \\ \times &(\cos \beta &+i&\sin \beta ) \\ =&(\cos(\alpha+\beta)&+i&\sin(\alpha+\beta)) \end{matrix} \]

就是高一的和差角公式了。

这样我们线段树维护这个复数、复数乘 lazy tag 即可。

P1486 [NOI2004] 郁闷的出纳员

平衡树 pushup 时 rt.sz 不是 +1 而是 +rt.cnt。

P2272 [ZJOI2007]最大半连通子图

vector 存有向图删重边：

sort(e[i].begin(),e[i].end());
e[i].erase(unique(e[i].begin(),e[i].end()),e[i].end());

P2045 方格取数加强版

网络流边的 tot 初始为 \(1\)！！！！！！！！！！！！！！！！！！！！！！

太久没写网络流了，调了 114514 年。

P4013 数字梯形问题

网络流拆点，点的数组没开两倍。

P2770 航空路线问题

显然每条原边 \(u\leftrightarrow v(u<v)\) 在费用流中建 \(u'\to v\)，费用为 \(0\)。

但是容量为多少呢？我当时以为每个点最多只能走一次，所以写了容量为 \(1\)，就快乐 WA 了。

原因：\(1\leftrightarrow n\)，可以 \(1\to n\to 1\) 这样游，这条边经过 \(2\) 次。

所以我们得建容量为 \(1\) 的边两遍 qwq。

P5610 [Ynoi2013] 大学

一道 Ynoi，肥肠卡常，搞了两天（做法放在简思短解）。

真正的跳坑：

无序插入的数组不排序直接二分 lower_bound（甚至调了半天）/qd。
被排除的忘记判断直接做了，导致错误。

介绍卡常：

将 vector 改用前向星。
将两次前向星改为一次，时空均减。
改用 scanf。
函数加 inline，将不必要的函数直接拆开。
去掉冗余的树状数组查询，以及 que(x)-que(x-1)（因单点修改区间询问，直接存原序列求单点）。
将前向星改为指针版的（首次尝试这样写），不过好像还变慢了？？
将数组大小更接近真实值。
将树状数组 que 中 x-=low(x) 改为 x^=low(x)，不过效果不明显。
改 long long，不需要 64 位的用 32 位。
将求两次 lower_bound 求区间后遍历改为一次左端点二分，遍历时判断是否越右端点（效果显著）。
改用 buf 快读（首次尝试）。
此时已经 517ms（时限 500ms），将编译从 c++14 O2 改成 c++98 O2 就蜜汁过了（不可思议）。

最后附上代码（非指针版前向星）

点击查看代码

//Said no more counting dollars. We'll be counting stars.
#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define N 100002
#define V 500002
#define C 20000002
#define ll long long
#define low (x&(-x))
char buf[1<<21],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define rg register
inline int read() {
  rg int x=0,f=1;
  rg char c=gc();
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=gc();}
  return x*f;
}
inline long long lread() {
  rg long long x=0,f=1;
  rg char c=gc();
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
  while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=gc();}
  return x*f;
}
int n,m,g[N],lim=0;
ll c[N];
inline void add(int x,int y){
	while(x<=n){
		c[x]+=y;
		x+=low;
	}
}
inline ll que(int x){
	ll res=0;
	while(x){
		res+=c[x];
		x-=low;
	}
	return res;
}
struct node{int nxt,id;}e[N];
int head[V],tot=0,d[C],cnt[V],L[V],R[V],f[C];
inline int gf(int x){return (x^f[x])?f[x]=gf(f[x]):x;}
#define lb lower_bound
inline void work(int l,int r,int w){
	int i=gf(lb(d+L[w],d+R[w],l)-d),val; 
	while(d[i]<=r && i<R[w]){
		val=g[d[i]];
		if(val%w){
			f[i]=gf(i+1);
		}else{
			add(d[i],val/w-val);
			g[d[i]]=val/w;
		}
		i=gf(i+1);
	}
}
int main(){
	n=read();m=read();
	int x;
	For(i,1,n){
		g[i]=x=read();
		if(!x) continue;
		if(lim<x) lim=x;
		add(i,x);
		cnt[x]++;
		e[++tot]=(node){head[x],i};head[x]=tot;
	} 
	For(i,1,lim)
		for(int j=i;j<=lim;j+=i)
			L[i+1]+=cnt[j];
	For(i,2,lim) L[i]+=L[i-1];
	For(i,1,lim) R[i]=L[i];
	For(i,1,lim)
		for(int j=i;j<=lim;j+=i)
			for(int k=head[j];k;k=e[k].nxt)
				d[R[i]++]=e[k].id;
	For(i,1,lim) sort(d+L[i],d+R[i]);
	For(i,0,R[lim]) f[i]=i;
	int opt;
	ll lst=0,l,r,w;
	while(m--){
		opt=read();l=lread()^lst;r=lread()^lst; 
		if(opt==1){
			w=lread()^lst; 
			if(w==1) continue;
			work(l,r,w);
		}else{
			lst=que(r)-que(l-1);
			printf("%lld\n",lst);
		}
	}
return 0;}

CF1674E Breaking the Wall

给定两个数 \(a,b\)，每次可以将一个 \(-1\)，另一个 \(-2\)，求使得两个均非正的最小次数。

我们不妨设 \(a\le b\)。

若 \(2a\le b\)，则我们每次都把 \(-2\) 给 \(b\)，这样答案是 \(\lceil\frac{b}{2}\rceil\)。

否则，我们先给 \(b\) 每次 \(-2\)，\(a\) 每次 \(-1\)，直到使得 \(a=b\)。我们再用两种消减方式 \(\{-1,-2\},\{-2,-1\}\) 交替搞 \(a,b\)。

通过分类讨论剩余 \(\%3\)，设 \(c=2a-b\)，则得到答案为

\[(b-a)+\lfloor\frac{2}{3}c\rfloor+(c\bmod 3) \]

P2455 [SDOI2006]线性方程组

判无解优先于判无穷解！！！

代码

UVA11082 矩阵解压 Matrix Decompressing

建网络流的时候一定不要吝啬空间，记得精细算点数，边数（开两倍）。

405. 将他们分好队

qwq 被坑惨了。

题意转化为：给一个图，让划分成两个点集 \(S,T\)，使得 \(S,T\) 分别为独立集，\(n\le 100\)。当然希望两个子集大小尽量相同（靠近 \(n/2\)），然后输出方案。

首先跑二分图。然后对于每一个连通块有两部分各自独立的点集。然后相当于分组背包了，最后体积要尽量接近 \(n/2\)。

坑点 1：分组背包中要二选一，不能不选（这个调了一下午qwq）。

坑点 2：多重背包不能滚动，因为要找方案（调了一晚上qwq）。

总计交了 20 遍。