0.（森森美图）判断一个点x3，y3在一条直线（由x1，y1和x2，y2组成）的哪一边
若(y2-y3)/(x2-x3) - (y1-y3)/(x1-x3)>0 逆时针方向
否则顺时针方向
1.vector
vector<node>ve;//定义
ve.insert(ve.begin()+i,k);//中间插入
ve.insert(ve.begin()+i,num,key);
ve.erase(ve.begin()+i);//删除
ve.erase(ve.begin()+i,ve.end());
reverse(ve.begin(),ve.end());//翻转
ve.erase(unique(ve.begin(),ve.end()),ve.end());//去重
ve.pop_back();//pop掉最后一个
int x=lower_bound(ve.begin(),ve.end(),1)-ve.begin();//二分查找维护一个有序的vector
vector<int>::iterator it;
it=lower_bound(ve.begin(),ve.end(),20);//不减首地址 就返回迭代器 找>=
ve.insert(it,20);//it作为地址练习：http://acm.hdu.edu.cn/showproblem.php?pid=4841 （圆桌问题）
题意：给你2n，循环从左到右数，1-m，1-m这样数，数到m的人为坏人，数到的人出局（好人：坏人=1：1）
求好人坏人结果序列
思路：因为要出局，所以vector动态更新，数到的人就erase。
#include<bits/stdc++.h>
using namespace std;
vector<int>ve;
set<int>se;
int main()
{
int i,j,n,m,f=0;
while(cin>>n>>m){
ve.clear();se.clear();
for(i=1;i<=2*n;i++){
ve.push_back(i);
}
int pos=0;
// if(f)cout<<endl;
while(ve.size()>n){
pos=(pos+m-1+ve.size())%ve.size();
ve.erase(ve.begin()+pos);
}
for(i=0;i<ve.size();i++){
se.insert(ve[i]);
}
for(i=1;i<=2*n;i++){
if(se.count(i))cout<<"G";
else cout<<"B";
if(i%50==0)cout<<endl;
}
i--;
if(i%50!=0)cout<<endl;
f=1;
cout<<endl;
}
return 0;
}View Code
2.队列
q.back() // 返回队尾元素
3.优先队列
priority_queue<int> qu;默认从大到小
priority_queue<int,voctor<int>,greater<int> > qu;从小到大
struct node{
int data;
friend bool operator <(node a,node b)
{
return a.data<b.data;
}
};
priority_queue<node>qu;4.链表（插入删除都是O(n),而vector查询是O(n);两个刚好互补
list<int>li;
for(i=1;i<=n;i++)li.push_back(i);//插入
list<int>::iterator it;
for(it=li.begin();it!=li.end();it++){
if(num%k==0)it=li.erase(it),it--;//删除，返回迭代器
num++;
}练习：http://acm.hdu.edu.cn/showproblem.php?pid=1276 （士兵人数训练问题）
题意：n个人，1-n编号。1212报数，报到2的出局，剩下的123123报数，报到3的出局，往复循环，剩下人数<=3结束。
求剩下人的编号
思路：因为反复删除，vector受不了，要用链表list来每次删除，修改指针。
注意：链表的erase操作在执行完的时候iterator也被销毁了，这样的话关于iterator的操作就会报错
迭代器遍历时erase操作就要注意这种情况
#include<bits/stdc++.h>
using namespace std;
list<int>li;
int main()
{
int i,j,n,m,f=0;
cin>>m;
while(m--){
cin>>n;
li.clear();
for(i=1;i<=n;i++){
li.push_back(i);
}
list<int>::iterator it;
int num=2;
while(li.size()>3){
int sum=0;
for(it=li.begin();it!=li.end();){
sum++;
if(sum%num==0)it=li.erase(it);
else it++;
}
num==2?num++:num--;
}
for(it=li.begin();it!=li.end();it++){
if(it!=li.begin())cout<<' ';
cout<<*it;
}
cout<<endl;
}
return 0;
}View Code
for(it=li.begin();it!=li.end();){
sum++;
if(sum%num==0)it=li.erase(it);
else it++;
}
5.set
se.insert(se.begin(),9);//插入
se.erase(se.begin());//删除
se.erase(9);//可以直接写数字
set<int>::iterator it=se.lower_bound(1);//返回迭代器
set<int>::iterator it2=se.find(1);
se.count(23)//判断set容器里是否有该数6.全排列
do{
for(i=0;i<3;i++)cout<<a[i]<<' ';
}while(next_permutation(a,a+3));
7.反向迭代器（reverse只有vector能用--而反向迭代器都可用）
vector<int>::reverse_iterator it;
for(it=ve.rbegin(); it!=ve.rend(); it++)
{
cout<<*it<<endl;
}8.isalpha（）判断是否是字母 isdigit（）判断是否是数字
9.char字符串常用函数
char *strstr(const char *string, const char *strSearch); //查找函数；下面有写
strcpy(demo,s+2);//从s+2的地址开始赋值给demo
int strcmp(const char *string1, const char *string2); //比较函数其中strstr函数比string中的find要快
char s[20]="abababaaa";
char demo[20]="abagaaa";
char *t;
t=strstr(s,demo);
if(t==NULL)cout<<"NULL";//为空
else cout<<t<<endl;//输出指针指向的第一个字符串10.string字符串常用库函数
s.replace(0,2,"23U");//下标0开始的 2两个字符串 替换为23U
string ss=s.substr(1,4);//截取，从1开始，后面一个数字不填则取到结尾
findd=s.find("11");11.从s+1字符串开始取->作为数字
char s[10];
scanf("%s",s);
int x;
if(s[0]=='-')sscanf(s+1,"%d",&x);
else sscanf(s,"%d",&x);12.堆排序（大顶堆 小顶堆就是堆排序的结果）
堆排序思路：以大根堆为例：
第一步：从最后一个父节点开始；往上走。如果孩子节点>父节点则调换位置，然后往下更新孩子节点，因为小的换下来了，所以要更新。
第二步：把第一个节点和最后一个节点换位置，这样最后一个节点就是最大值。然后就是第一步，不过这次直接更新父节点即可，不用从最后一个父亲节点开始到根节点。
因为只有根节点换到了小的值。
动画演示：(知乎https://zhuanlan.zhihu.com/p/124885051
for(i=0;i<n;i++)cin>>a[i],make_heap(a,a+i+1,greater<int>());
//按输入序建立小顶堆：（父节点的值要比孩子节点的都要小）void update(int start,int maxxn)
{
int dad=start;
int son=dad*2+1;//这里注意先给初值，在while里再更新
while(son<maxxn){
if(son+1<maxxn&&pre2[son+1]>pre2[son])son++;
if(pre2[son]<pre2[dad])break;
swap(pre2[son],pre2[dad]);
dad=son;
son=dad*2+1;
}
}
void solve(int maxxn)
{
for(int i=maxx;i>=0;i--){
update(i,n);//init 每个父节点都更新
}
for(int i=n-1;i>=0;i--){
swap(pre2[i],pre2[0]);//取得最大值
update(0,i);//再去0节点往下更新
}
}13.两个队模拟栈，两个栈模拟队列
了解大致思想即可
14.ALV 平衡二叉树（空树 or 左右子树深度差不超过1 的 二叉搜索树）
二叉搜索树：左子树比它小，右子树比他大
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct node{
int data,height;
struct node *l,*r;
};
int deep(node *p)
{
if(p==NULL)return 0;//這個 return 0而不是1
return max(deep(p->l),deep(p->r))+1;
}
node *ll_change(node *y)
{
node *x=y->l;
y->l=x->r;
x->r=y;
return x;//這裏return錯了 是x而不是y！！
}
node *rr_change(node *y)
{
node *x=y->r;
y->r=x->l;
x->l=y;
return x;//這裏return錯了 是x而不是y！！
}
node *lr_change(node *y)
{
y->l=rr_change(y->l);
return ll_change(y);
}
node *rl_change(node *y)
{
y->r=ll_change(y->r);
return rr_change(y);
}
node * build(node *root,int x)
{
if(root==NULL){
node *p=new node;
p->l=p->r=NULL;
p->data=x;
p->height=1;
return p;
}
if(x<root->data)root->l=build(root->l,x);
else root->r=build(root->r,x);
root->height=deep(root);
int balance=deep(root->l)-deep(root->r);
if (balance > 1 && x < root->l->data) //LL型
return ll_change(root);
if (balance < -1 && x >root->r->data) //RR型
return rr_change(root);
if (balance>1 && x > root->l->data) //LR型
return lr_change(root);
if (balance < -1 && x <root->r->data) //RL型
return rl_change(root);
return root;
}
int main()
{
int i,j,n,m;
node *root =new node;
root=NULL;//這裏要初始化為NULL，不然build函數的if判斷不了
cin>>n;
for(i=0;i<n;i++){
int x;cin>>x;
root=build(root,x);
}
cout<<root->data;
return 0;
}
15.大数加减
c++
const int N=1e3+5;
int na[N],nb[N];
string add(string a,string b)
{
string ans;
int i;
int la=a.size(),lb=b.size();
memset(na,0,sizeof na);
memset(nb,0,sizeof nb);
for(i=0;i<la;i++){
na[la-i-1]=a[i]-'0';
}
for(i=0;i<lb;i++){
nb[lb-i-1]=b[i]-'0';
}
int maxl=max(la,lb);
for(i=0;i<maxl;i++){
na[i]+=nb[i];
na[i+1]+=na[i]/10;
na[i]%=10;
}
if(na[maxl]==0)maxl--;//去前置零
for(i=maxl;i>=0;i--)ans+=na[i]+'0';
return ans;
}java
public class Main {
public static void main(String[] args) {
BigInteger n,m;//定义
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){//多个输入
n=scanner.nextBigInteger();//输入
m=scanner.nextBigInteger();
n=n.add(m);
System.out.println(n);
}
}
}16.最短路
dij：
typedef pair<int,int>pai;
vector<pai>vec[1005];
int dis[1005];
void dij(int u)
{
int i;
for(i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[u]=0;
queue<int>qu;
qu.push(u);
while(!qu.empty())
{
int t=qu.front();
qu.pop();
for(i=0;i<vec[t].size();i++)
{
if(dis[vec[t][i].first]>dis[t]+vec[t][i].second)
{
dis[vec[t][i].first]=dis[t]+vec[t][i].second;
qu.push(vec[t][i].first);
}
}
}
}堆优化 就改成优先队列 再加个visit数组 表示是否进过队列即可
ll dist[N],x;
bool vis[N];
struct qnode
{
int v;ll c;
qnode(int _v=0,ll _c=0):v(_v),c(_c) {}
bool operator <(const qnode &r)const
{
return c>r.c;
}
};
struct Edge
{
int v;ll cost;
Edge(int _v=0,ll _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[N];
void add(int u,int v,ll w)
{
E[u].push_back(Edge(v,w));
E[v].push_back(Edge(u,w));
}
ll Dijkstra()
{
for(int i=0; i<=2*n+1; i++)dist[i]=1e15,vis[i]=false;
priority_queue<qnode>que;
while(!que.empty())que.pop();
dist[s]=0;
que.push(qnode(s,0));
qnode tmp;
while(!que.empty())
{
tmp=que.top();
que.pop();
int u=tmp.v;
if(vis[u])continue;
vis[u]=true;
for(int i=0; i<E[u].size(); i++)
{
int v=E[tmp.v][i].v;
ll cost=E[u][i].cost;
if(!vis[v]&&dist[v]>dist[u]+cost)
{
dist[v]=dist[u]+cost;
que.push(qnode(v,dist[v]));
}
}
}
return dist[t];
}
堆优化View Code
floyd：
for(i=0;i<n;i++){
for(j=0;j<n;j++){
mp[i][j]=INF;
}
mp[i][i]=0;
}
//输入语句
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(mp[i][k]+mp[k][j]<mp[i][j])
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}spfa:
typedef pair<int,int>pai;
vector<pai>vec[1005];
const int INF=1e9;
int d[1005],inq[1005];//d数组 离源点距离；inq数组检查是否在队列里面
int cnt[1005];//入队次数
void spfa(int u)
{
int i;
memset(d,INF,sizeof d);
memset(inq,0,sizeof inq);
d[u]=0;
queue<int>qu;
qu.push(u);
inq[u]=1;
while(!qu.empty())
{
int t=qu.front();
qu.pop();
// cnt[t]++;
// if(cnt[t]==n+1){
// printf("有环\n");
// return;
// }
inq[t]=0;
for(i=0;i<vec[t].size();i++)
{
if(d[vec[t][i].first]>d[t]+vec[t][i].second)
{
d[vec[t][i].first]=d[t]+vec[t][i].second;
if(inq[vec[t][i].first]==1)continue;//先更新 再判断是否入队
qu.push(vec[t][i].first);
inq[vec[t][i].first]=1;
}
}
}
}
spfa(p);
cout<<d[q]<<endl;
17.结构体构造函数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pai;
const int INF=1e9;
const int N=1e6+5;
struct node{
int a,b;
node(){}
node(int x,int y){//构造函数
a=x,b=y;
}
};
int main()
{
int i,j,n,m,k;
queue<node>qu;
node no;//法一
no.a=3,no.b=4;
qu.push(no);
qu.push(node(3,4));//法二
return 0;
}18.已知三点求三角形面积：|(x2-x1)(y3-y1)-(x3-x1)(y2-y1) | / 2
已知三边求三角形面积：（海伦公式）P=(a+b+c)/2 S=sqrt(P(P-a)(P-b)(P-c))
19.欧拉回路/欧拉路
无向图：欧拉回路-所有点都是偶点。欧拉路-只有两个积点，一个奇点是起点，另一个是终点，其他都是偶点（偶点表示偶数条边的点）
有向图：欧拉回路-所有点度数为0。欧拉路-只有一个点度数=1，另一个点度数=-1，其他=0（入度+1，出度-1，度数表示该点度数之和）
20.gcd可以--gcd(x,y)
也可以：
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}lcm则是x*y/gcd---防止爆精度，先除再乘
21.读懂题意很重要
https://pintia.cn/problem-sets/1320987234661515264/problems/1320988224353681413
所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。意思是：选中的垃圾点要求 到所有居民点的min距离要最大，同时max距离也要小于规定范围
https://pintia.cn/problem-sets/1320987234661515264/problems/1320988224366264321
二叉搜索树的最近公共祖先。给你先序，让你求任意两点的最近公共祖先思路：我一开始建树，没必要，这样的话只能知道层序，不能知道父子关系，除非存一个父节点指针
后来 还是dfs 求下标，再直接判断
https://pintia.cn/problem-sets/1320987234661515264/problems/1320987934195933188
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑
在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个
任务之间的关系，请你计算出这个项目的最早完工时间。看到任务想到拓扑，既然是拓扑，那么完成该节点的话就需要完成先该节点依赖的所有节点。
然后算出该节点完成的最短时间，也就是max时间，最后所有节点里求个max就是最早完工时间
22.零多项式含义：
零次多项式f（x）=a（a！=0）
零多项式即f（x）=0
零多项式和零次多项式都是常数多项式
findd=s.find("11");