一些实用的东西...（亲测
目录
文章目录
废话不多说，直接切入正题
读优
.
:
这大概是我见过的码风最能接受的读优了…
总之好写好用，用就对了
inline int read(){
int re=0;
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){
re=re*10+ch-'0';
ch=getchar();
}
return re;
}
输优
.
:
这个输优不用开数组，而且好写，所以…
当然不需要换行就把\n给干掉…
inline void write(int x){
int y=10,len=1;
while(y<=x){
y*=10;
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
putchar('\n');
}
求lg
换底公式，在无理数后+1/+0.5来减少误差是个好习惯…log2n=log(n)/log(2)+1
求n个数的lg
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==0);
树上前向星
树上的dfs其实可以不用打访问标记，因为只需要不让连的点为父亲就好了
for(int i=head[u];i>-1;i=e[i].next)
if(e[i].v!=fa)
dfs(e[i].v,u);
流同步
关闭：ios::sync_with_stdio(false);
开启：ios::sync_with_stdio(true);
精度误差
产生原因是浮点数存储空间有限，导致无限循环数改变，这时一般需要±esp（esp=1e-8）
至于为什么是1e-8,只能说是出题人默认a>=0–> a>-epsa<=0–> a<eps
还有个类似的操作
利用强制类型转换模拟四舍五入
double a;
printf("%d",a+0.5);
当然也可以用下取整实现~~（然而更啰嗦~~…
#include<cmath>
int a;
double b;
printf("%d",a=floor(b+0.5));
位运算优化
判断整数奇偶： x&1
比较两数是否相等： !x^y
判断两数是否同号： !((x^y)>>31)
交换两个数：a^=b;b^=a;a^=b;
求绝对值：(n^(n>>31))-(n>>31)
双端队列
简单来说就是左端是队列，右端是栈
Floyd求最小环
dis是被k更新过的，map是未更新的，二者刚好构成环
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(j=1;j<=n;j++)
ans=min(ans,map[i][k]+map[k][j]+dis[j][i];
Floyd求最短路的条数
用乘法原理更新最短路条数，分三种情况
1、当有新路径等于最短路，条数+=
2、当有新路径小于最短路，直接更新，条数=
3、新路径大于最短路，直接跳过
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
num[i][j]=num[i][k]*num[k][j];
}
if(dis[i][j]==dis[i][k]+dis[k][j])
num[i][j]+=num[i][k]*num[k][j];
}
伪去重离散化
//unique(u,v)返回去重(伪)后的地址，被删掉的会加到返回值后
//bo==lower_bound(u,v,x)返回最接近x的值的地址
int const maxn=1e5+10;
int a[maxn], t[maxn];
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",a[i]),t[i]=a[i];
sort(t+1,t+n+1);//排序，找相对大小
m=unique(t+1,t+1+n)-t-1;//m为不重复的元素的个数
for(int i=1; i<=n; i++)
a[i]=lower_bound(t+1,t+1+m,a[i])-t;//相对大小的
Cmp函数维护序列的稳定性
inline int cmp(int x,int y)
{
return a[x]>a[y];
}
inline int cmp(int x,int y)
{
return a[x]>=a[y];
}
上述两个cmp函数结果虽然相同
然而当遇到相同的数时
前者是按在原序列中出现的时间先后排序（时间先者先）
后者则是逆在原序列中出现的时间先后排序（时间后者先）
用前缀和维护区间大于k的值的和
for(int i=1;i<=n;i++)
{
if(w[i]>=ans)
prs[i]=prs[i-1]+v[i];
else
prs[i]=prs[i-1];
}
二分的范围
l=minx,r=maxx;
能达到左界，但达不到右界
想达到右界需要r=maxx+1;
多个long long模拟高精
乱搞即可
宏定义
没啥卵用的东西 (快乐就完事了#define int long long
建一个命名空间防止变量重复
namespace Panther
//匿名的namespace可以当static使用
{
//可以存类 变量 函数
int god;
}
int main()
{
Panther::god=true;
//233
return 0;
}
并没有卵用的多变量手写max
int max(int a,int b,int c,int d)
{
return (((((a>b)?a:b)>c)?((a>b)?a:b):c)>d)?((((a>b)?a:b)>c)?((a>b)?a:b):c):d;
}
利用构造函数快速赋值
前向星的毒瘤压行写法
struct E
{
int to,next,w;
E(int to=0,int next=0,int w=0):
to(to),next(next),w(w){}
}e[maxn2<<1];
void add(int u,int v,int w)
{
e[++cnt]=(E){v,head[u],w};
head[u]=cnt;
构造重载运算符
struct node
{
int nd,dis;
bool operator<(const node &b)const
{
return dis>b.dis;
}
node(int nd=0,int dis=0):
nd(nd),dis(dis){}
};
利用前向星记录最短路
用一个下标为终点点号的数组存边号
用前向星记录起点的点号
while(v!=s)
v=e[way[v].from;