-
常错bug部分
i++??????
逻辑错误
分号出现在不该出现的位置
纯粹手打快出错
位置放错
0或1值的处理遗漏，cout对位数的偷工减料
死循环啦
- 并查集中的father[i]=i初始化；
- union中father[t1]=t2;而不是t1=father[t2]
- 设立的标记数组更新还是不需要更新
- 函数中调用全局变量，全局变量已有初值，多加了一次
- isprime里的if（x<=1）return false;忘写了
- isprime里的sqrt(1.0*x)，x写成n了,偷换变量
- in-off型存储，先排序，一个vector两个两个存，两个两个取
- 处理时间的问题，全化到最小（一个标准），大减小
- getline(cin,s)处理含空格的字符串时，如果前面出现换行，要加一个getchar()
- 字符串cin，cout超时问题采用hash或换成scanf("%s",s.c_str)
- 处理字符串时，错误判断数字的位数
- 在处理输出保留几位eg:%05d时，整体全用printf，防止遗漏。
- 分子为0的情况？
- 因为除号取整，先取整后乘还是先乘后取整~~~
- 数据中有出现double，可能另一种没有说明的数据类型也是double
- 数据超过int型用longlong存储
- 开数组时刚好开到边界处会数组越界
- 有些画图题，空的地方必须是空格，否则一直0
-
题目：
搜索
two points
贪心
map映射
图论
树
模拟
排队模拟
二分
其他
-
代码块
gcd
int gcd(int a,int b)
{
return !b ? a:gcd(b,a%b);
}
在一串字符串中提取单词。
//two points,第一个指针找第一个单词，第二个指针找完这个单词
vector<string>vt;
int main()
{
string s;
getline(cin,s);
int t;
for(int i=0;i<s.size();i++)
{
if((s[i]>='A'&&s[i]<='Z')||(s[i]>='a'&&s[i]<='z'))
{
t=i;
string temp="";
while((s[t]>='A'&&s[t]<='Z')||(s[t]>='a'&&s[t]<='z'))
{
temp+=s[t];
t++;
}
vt.push_back(temp);
i=t;
}
}
for(int i=0;i<vt.size();i++)
cout<<vt[i]<<endl;
return 0;
}
STL中非空判断要在前，会出现段错误
1.一定要先检测非空再判断
while(!st.empty()&&st.top()==a[t])
// while(st.top()==a[t]&&!st.empty())
{
st.pop();
t++;
}
有些并查集的题不路径压缩过不了
int findfather(int x)
{
if(x==father[x])
return x;
else
{
int f=findfather(father[x]);
father[x]=f;
return f;
}
}
排队问题的窗口处理
void deal(int pindex,int tindex)
{
if(person[pindex].arrive>=table[tindex].endtime)//来迟了
person[pindex].start=person[pindex].arrive;
else
person[pindex].start=table[tindex].endtime;。//来早了
table[tindex].endtime=person[pindex].start+person[pindex].dotime;//窗口处理完的时间
}
最短路和最短路+dfs
- 点数范围都较少，使用邻接矩阵存储
- 着重点倾向于求最短路径的第二标尺，求==输出路径满足：最小/大点权，边权，平均点权，平均边权==
- 方法 ==只用dijkstra==或==dijkstra+dfs==
1.只用dijkstra
顺便求出第二标尺，第三标尺的模板
//dis[]最短路径
//G[][]边权
//w[]点权和，weight[]点权
//num[]最短路条数
//pt[]到该点的累计顶点数
//pre[]前驱结点
//注意各个数组的初始化
if(book[v]==0)//k未被访问
{
if(dis[v]>dis[u]+G[u][v])
{
dis[v]=dis[u]+G[u][v];
w[v]=w[u]+weight[v];//加上v处的点权
pre[v]=u;
pt[v]=pt[u]+1//s->v的顶点数等于s->u的顶点数+1
num[v]=num[u];//更新到v点的最短路的条数
}
else if(dis[v]==dis[u]+G[u][v])
{
if(w[v]<w[u]+weight[v])
{
w[v]=w[u]+weight[v];
pt[v]=pt[u]+1;
pre[v]=u;
}
else if(w[v]==w[u]+weight[v])
{
........
}
num[k]+=num[u];//最短路的条数
}
}
dfs输出路径
void dfs(int v)
{
if(v==st)
{
printf("%d",v);
return ;
}
dfs(pre[v]);
printf("%d",v);
}
2.dijkstra+dfs
dis[]数组更新时
//
vector<int>pre[MAX];
//
if(dis[v]>dis[u]+G[u][v])
{
dis[v]=dis[u]+G[u][v];
pre[v].clear();//否定比它长的那一条
pre[v].push_back(u);
}
else if(dis[v]==dis[u]+G[u][v])
{
pre[v].push_back(u);
}
dfs模板
//
vector<int>path,temppath;
//
void dfs(int start)
{
if(v==start)
{
temppath.push_back(v);
.....
int value//用于计算临时路径temppath的第二标尺的值
.....
//计算时注意循环从temppath.size()-1开始，倒叙。
.....
if(value 优于 最佳value)
{
最佳value=value;
path=temppath;
}
temppath.pop_back();//回溯
return ;
}
temppath.push_back(v);
for(int i=0;i<pre[v].size();i++)
{
dfs(pre[v][i]);
}
temppath.pop_back();//回溯
}
分块
int SQR=633;//633块，632个
int block[SQR];
int table[MAX];
void fenkuai(int k)
{
int sum=0;
int index=0;
while(sum+block[index]<k)
{
sum+=block[index++];
}
int num=index*632;
while(sum+table[num]<k)
{
sum+=table[num++];
}
cout<<num<<endl;
}
BST
struct node
{
node* lchild;
node* rchild;
int data;
};
node* newnode(int x)
{
node* Node=new node;
Node->data=x;
Node->lchild=Node->rchild=NULL;
return Node;
}
//初始化 node* root=NULL;
//////////////////////////
void Insert(node* &root,int data)
{
if(root==NULL)
{
root=newnode(data);
return ;
}
if(data<root->data)
Insert(root->lchild,data);
else
Insert(root->rchild,data);
}
///////////////////////////////
