一些好的博客/技巧
学习博客
1.斜率优化 包含斜率优化的两种做法,一些例题。
3.FFT
技巧
1.对于大量字符串输入的办法:stringstream 讲解
2.当一道题的数量超过 __int128
,又不想写高精时,就可以用到 long double
,它的范围在:\(1.2 \times 10^-4932 ~ 1.2 \times 10^4932\),虽然会掉精度,但对于:\(10 ^ {1000}\) 的数据还是绰绰有余。输出时要注意处理,因为如果直接输出 double
类型,就会出现:
//类型一:整数位很多
double x=12345678;
//类型二:小数位很多,有效小数位少
double y=0.00001234;
cout<<x<<endl;
cout<<y<<endl;
输出:
1.23457e+07
1.234e-05
我们要不让他输出科学计数法,可以加上 fixed
语句,然后要让它不保留小数部分,加上 setprecision(0)
。
详见:详解C++中fixed,setprecision(),setw()的用法
例题:P2687 [USACO4.3] 逢低吸纳Buy Low, Buy Lower
4.有关矩阵运算题的处理
- 把矩阵都封装在结构体中
struct matrix{
int a[5][5];
void init()
{
}
void .......
{
}
.......
};
- 初始化都是单位矩阵 \(I\)。
可以封装在结构体中。
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=(i==j);
如可以手写出来可以用 const
直接定义,会快一点。
const matrix I
{{
{1,0,0,0,0},
{0,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,0},
{0,0,0,0,1}
}};
- 矩阵乘法可以用自定义符号方便的求出,这也封装在结构体里。
matrix operator*(const matrix y)const
{
matrix c;
c.init();
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
for(int k=0;k<=4;k++)
c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*y.a[k][j]%mod)%mod;
return c;
}
也可以在外面重载运算符:
matrix operator*(const matrix &a,const matrix &b)const
{
matrix c;
c.init();
for(int i=0;i<=4;i++)
for(int j=0;j<=4;j++)
for(int k=0;k<=4;k++)
c.x[i][j]=(c.x[i][j]+1ll*a.x[i][k]*b.x[k][j]%mod)%mod;
return c;
}
- 关于树的直径的求法
先随便找一个点求每个结点的深度,然后把最深的那个结点作为根,再变量一遍,树的深度为直径。
求直径的路径:只用记录每个点的父亲,然后找到最深的那个结点一直向上找即可(就是一个单向链表)。
void dfs(int *dd ,int u,int fa)
{
from[u]=fa;
dd[u]=dd[fa]+1;
for(int v : g[u])
{
if(v==fa) continue;
dfs(dd,v,u);
}
}
int main()
{
dfs(d,1,0);
for(int i=1;i<=n;i++) if(d[st]<d[i]) st=i;
dfs(d,st,0);
for(int i=1;i<=n;i++) if(d[ans]<d[i]) ans=i;
int len=d[ans];
while(len--) cout<<ans,ans=from[ans];
}
易错点
-
多测不清空,oi 一场空,但清空数组时注意范围,是清空 \(1\) 到 \(n\),还是 \(0\) 到 \(m\)。
-
有些题看似不用卡
long long
,但在某些很小的地方要开。如特判时的语句时:
if(n*m>s) return ;
但 \(n*m\) 爆了,要开 long long
。
if((long long)n*m>(long long)s) return ;
- 莫队中四个 while 循环的顺序
保证正确的原则是 l<=r
(注意\(l,r\)的大小顺序)。
最好记的是先扩大,也就是 --l
, ++r
,然后再缩小l++
,r--
。
while (l > a[i].l) add(c[--l]);
while (r < a[i].r) add(c[++r]);
while (l < a[i].l) del(c[l++]);
while (r > a[i].r) del(c[r--]);
还有其他的一种
oi wiki 。
排序方式
一定要看清楚判断的先后级,是比较块的大小还是本身端点的大小,每个莫队的比较方式不一样。
还有要看清楚结构体的编号。
错误示范(来源)
P1903 [国家集训队] 数颜色 / 维护队列)
bool cmp(node2 a,node2 b)
{
if(be[a.l]!=be[b.l])return be[a.l]<be[b.l];
if(be[a.r]!=be[a.r])return be[a.r]<be[a.r];
//改成 if(be[a.r]!=be[b.r])return be[a.r]<be[b.r];
return a.t<b.t;
}
标签:const,matrix,int,long,--,while,杂项
From: https://www.cnblogs.com/hutongzhou/p/18169029