杂项与STL代码模板

发表于 2021-06-24 更新于 2023-01-27 分类于算法模板阅读次数：

这里记录了平时个人常用的一些不好分类的代码模板。

杂项

常用宏定义

#pragma GCC optimize(2)
#pragma G++ optimize("O2") //O2优化
#pragma comment(linker, "/STACK:102400000,102400000") //手动扩栈
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<iomanip>//控制输出,<<setiosflags(ios::fixed)<<setprecision(9)
#include<string>
//#define lowbit(x) ((x) & -(x))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=200005;
#define PI 3.14159265358979323846
#define e  2.7182818284590452354
#define ln_2 0.69314718055994530942
#define ln_10 2.30258509299404568402
//#define DEBUG
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
    //	freopen("output.txt", "w", stdout);
    #endif

    return 0;
}

cb

//#pragma comment(linker, "/STACK:102400000,102400000") 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10|,inf=0x3f3f3f3f,mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9;
//#define DEBUG//#define lowbit(x) ((x) & -(x))//<<setiosflags(ios::fixed)<<setprecision(9)
void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif
    
    return 0;
}
/*
 * $NOW_L
 * $ACTIVE_EDITOR_FILENAME
 *
*/

快速读入

void read(){}
template<typename T,typename... T2>inline void read(T &x,T2 &... oth) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
    read(oth...);
}

CDQ分治

使用分治+双指针，用于处理偏序计数问题。

CF641E Little Artem and Time Machine

你有一个初始为空的可重集，按给定顺序进行如下$q$次操作：

在时间$t$时刻插入一个$x$.
在时间$t$时刻删除一个$x$.
询问在$t$时刻有多少个$x$（只考虑本次操作之前操作所造成的影响）.

思路

操作本身有偏序关系，此前的操作的各个时间点$t$也有偏序关系。

cdq分治下去，将操作分为左右两块，分别按时间点$t$来排序，用双指针分别指向左区间和右区间，来统计左区间的操作对于右区间所有点的影响。

struct opt
{
    int id,op,t,x;
    opt(int a=0,int b=0,int c=0,int d=0):
        id(a),op(b),t(c),x(d){}
    bool operator < (const opt &y)const{
        return t>y.t;
    }
} a[maxn];
vector<bool>ok;
vector<int>ans,mp,v1;
void cdq(int l,int r)
{
    if(l==r)
        return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(a+l,a+mid+1);//区间内按t排序
    sort(a+mid+1,a+r+1);//[l,mid]操作早于[mid+1,r]
    int i=mid+1,j=l;
    for(;i<=r;i++)
    {//在这前面的操作,且时间点t也在前面,则j对i有影响
        for(;a[j].t<=a[i].t&&j<=mid;j++)//双指针维护t这一维
        {
            if(a[j].op==1)
                mp[a[j].x]++;
            else if(a[j].op==2)
                mp[a[j].x]--;
        }
        if(a[i].op==3)//影响累计,左对右
            ans[a[i].id]+=mp[a[i].x];
    }
    for(j--;j>=l;j--)//j前面的才做出了有效贡献的
        if(a[j].op!=3)//桶清空
            mp[a[j].x]+=(a[j].op==1?-1:1);
}
signed main(signed argc, char const *argv[])
{
    int q,op,t,x;
    cin>>q;
    ans.resize(q+1,0);
    mp.resize(q+1,0);
    ok.resize(q+1,0);//标记哪些是询问
    for(int i=1;i<=q;i++)
    {
        cin>>op>>t>>x;
        a[i]=opt(i,op,t,x);//操作顺序,操作类型,时间点t,数值x
        if(op==3)
            ok[i]=1;
        v1.push_back(x);//离散化要用
    }
    sort(v1.begin(),v1.end());
    v1.erase(unique(v1.begin(),v1.end()),v1.end());
    for(auto &i:a)//离散化,map也行
        i.x=lower_bound(v1.begin(),v1.end(),i.x)-v1.begin()+1;
    cdq(1,q);
    for(int i=1;i<=q;i++)
        if(ok[i])//第i是询问
            cout<<ans[i]<<endl;
    return 0;
}

整体二分

整体二分算法完整总结

WQS二分

模型

题型1：在物品集合中恰好选取$m$个物品，不同组合情况有不同的价值，要求最大/最小化总价值。

设选取$x$个物品时的最大价值为$g(x)$，以$x$为横坐标，$g(x)$为纵坐标，那么会在坐标系上呈现出一个上凸包的形状（斜率单调递减），即满足$g(i)-g(i-1)\ge g(i+1)-g(i)$，最大差值即作为斜率上下界，即每多选择一个物品额外产生的收益都是单调递减的。

此时我们不知道$g(x)$的值是多少，使用直线$g(x)=kx+b$来切这个凸包（相当于对每个物品附加了权值$-k$），通过$O(n)$的方法来找到最大的$b$，同时我们也得到了此时的$x$，通过$x$与$m$的关系来调整斜率$k$继续二分使得$x$接近$m$，二分的方向与上凸包还是下凸包有关。

最终$ans=b-mk$，注意当有多个点权值相同时（既有连续几个点的斜率相同，截距相同），要使用$ans=b-mk$而不是$ans=b-xk$，来得到正确答案，注意二分的方向和斜率上限的估计。

扩展：求限制数量不超过m的最优解

题型2：在所给物品中选取数量没有限制，求出达到最大的收益需要选择的物品数量以及最大收益。

此类题型可以视为无限制问题+wqs二分的一个组合。

我们知道，对于无限制问题可以通过$O(n)$的手段解决，那么如果函数图形是一个上凸包的话，最大值可以轻松得出，如果这个最大值$g(x)$对应的$x\le m$的话，那么就是我们所需要的答案；否则若$x$超出了$m$的限制，那么我们可以将$[1,m]$视为上凸包的左半部分，函数单调递增，斜率单调递减，可以通过$wqs$二分来确定$g(m)$的值即为我们所需要的答案。

P1484 种树

学习笔记

关于WQS二分算法以及其一个细节证明

WQS二分，可以视为下凸壳的左半部分

习题

P4767 [IOI2000]邮局

坐标轴上有$n$个村庄，要选择$m$个村庄建造邮局，不方便值为每个村庄与其最近的邮局之间的距离总和，你要使其最小。

设$g(x)$为修建邮局的最小不方便值，因为造的地铁站越多$g(x)$越小，所以本题是一个下凸包的左半部分。

使用wqs二分来将问题转化为建造一个邮局花费$-k$代价，使不方便值$-k\times $邮局数最小。

可以发现邮局建立在中点总是最优的，令$mid=\dfrac{l+r}{2}$，这里建造一个邮局控制$[l,r]$区间的贡献为$\sum\limits_{i=l}^{mid}(p_{mid}-p_i)+\sum\limits_{i=mid+1}^{r}(p_{i}-p_{mid})$.

整体复杂度$O(n^2logV)$，单调栈+二分优化dp过程似乎可以$O(nlognlogV)$。

int p[maxn],sum[maxn],dp[maxn],cnt[maxn];
pii check(int n,int k)
{//建造一个邮局的额外开销-k
    auto w = [](int l,int r)
    {//a[mid]处花费最小,左面贡献=,右面
        int mid=(l+r)>>1;
        return sum[r]+sum[l-1]-2*sum[mid]+(2*mid-l-r+1)*p[mid];
    };
    for(int i=1;i<=n;i++) {//前i个村庄安放邮局后的最小代价
        for(int j=1;j<=i;j++) {//在[j,i]村庄安放一个邮局
            if(dp[j-1]+w(j,i)-k<dp[i]) {
                dp[i]=dp[j-1]+w(j,i)-k;
                cnt[i]=cnt[j-1]+1;
            }
        }
    }
    return make_pair(dp[n],cnt[n]);
}
signed main(signed argc, char const *argv[])
{
    int n,m;
    read(n,m);
    for(int i=1;i<=n;i++)
    {
        read(p[i]);//邮局的位置
        sum[i]=sum[i-1]+p[i];
    }
    int l=-m*p[n]-10,r=10,ans=INF;
    while(l<=r)
    {
        int k=(l+r)>>1;
        for(int i=1;i<=n;i++)
            dp[i]=inf,cnt[i]=0;
        pii now=check(n,k);
        if(now.ss<=m)
            ans=now.ff+m*k,l=k+1;
        else
            r=k-1;
    }
    printf("%d\n",ans);
    return 0;
}

P2619 [国家集训队]Tree I

本题是一个下凸包（凹函数），每一个状态的最优解可以通过kruskal求得。

struct edge
{
    int u,v,w,c;
    edge(){}
    edge(int u,int v,int w,int c):
        u(u),v(v),w(w),c(c){}
    bool operator <(const edge &y)
    {
        if(w!=y.w)
            return w<y.w;
        return c<y.c;//白边优先
    }
};
vector<edge>B,W;
int fa[maxn],cnt=0;
int findfa(int x)
{
    if(fa[x]!=x)
        fa[x]=findfa(fa[x]);
    return fa[x];
}
bool Merge(int x,int y)
{
    int a=findfa(x),b=findfa(y);
    if(a==b)
        return 0;
    if(a<b)
        fa[b]=a;
    else
        fa[a]=b;
    return 1;
}
int kruskal(int n,int k)
{//斜率k,每个白边附加权值为-k
    for(int i=1;i<=n;i++)
        fa[i]=i;//b=g(x)-kx
    int ans=0;
    vector<edge>E;
    E.insert(E.end(),W.begin(),W.end());
    for(auto &x:E)
        x.w-=k;
    E.insert(E.end(),B.begin(),B.end());
    sort(E.begin(),E.end());
    for(auto &e:E)
    {
        if(Merge(e.u,e.v))
        {
            ans+=e.w;
            n--;
            if(e.c==0)
                cnt++;
            if(n==1)
                return ans;
        }
    }
    return ans;
}
signed main(signed argc, char const *argv[])
{
    int n,m,need,u,v,c,w;
    cin>>n>>m>>need;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w>>c;
        u++,v++;
        if(c==0)
            W.push_back(edge(u,v,w,c));
        else
            B.push_back(edge(u,v,w,c));
    }
    sort(W.begin(),W.end());
    sort(B.begin(),B.end());
    int l=-105,r=105,ans=-1,b,k;
    while(l<=r)
    {
        k=(l+r)>>1;//二分斜率
        cnt=0;
        b=kruskal(n,k);//白边附加值为mid时选择白边的数量
        if(cnt<need)//g(x)=b+kx//b随着x增加单调递减
            l=k+1;//增大斜率,使白边权变得更小
        else{
            r=k-1;
            ans=b+k*need;//让b相同时仍能取到正确答案
        }
    }
    cout<<ans<<endl;
    return 0;
}

离散化

法1：使用结构体排序：不能有重复元素，但速度略快

struct node
{
    int v,id;//v即为原先的数值
    bool operator < (const node a)const{
        return v<a.v;
    }
} a[maxn];
void discretization(int n)
{
    for(int i=1;i<=n;i++)
        a[i].id=i;//a[i]的顺序
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        rak[a[i].id]=i;//rak[i]即为原来a[i]相对顺序
}

法2：排序后unique去重确定范围，再用lower_bound

ll a[maxn],t[maxn];
void discretization(int n)
{
    for(int i=1;i<=n;i++)
        t[i]=a[i];
    sort(t+1,t+n+1);
    int m=unique(t+1,t+n+1)-t-1;//m为离散化后范围
     for(int i=1;i<=n;i++)
        a[i]=lower_bound(t+1,t+m+1,a[i])-t;//a[i]即为离散化后的a[i]相对大小
}

曼哈顿距离与切比雪夫距离

切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。

将原坐标系每个点的坐标$(x,y)$变为$(x+y,x−y)$，则原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。

反过来，将原坐标系每个点的坐标$(x,y)$变为$(\frac{x+y}{2},\frac{x-y}{2})$，则原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。

位运算

GCC内置函数

int __builtin_popcount(unsigned int x) ：返回x的二进制中1的个数。
int __builtin_ffs(int x) ：返回x的二进制末尾最后一个1的位置，位置的编号从1开始（最低位编号为1）。当x为0时返回0。
int __builtin_clz(unsigned int x) ：返回x的二进制的前导0的个数。当x为0时，结果未定义。
int __builtin_ctz(unsigned int x) ：返回x的二进制末尾连续0的个数。当x为0时，结果未定义。
//都可以在函数名末尾添加ll（如 __builtin_popcountll ）

判断是否为2的幂

1	bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }

判断两个数符号位是否相同

1	bool isSameSign(int x, int y) { return (x ^ y) >= 0; } //有 0 的情况例外

一些不好分类的算法

判断闰年

bool Isleap(int year)           
{
    if(year%400==0||year%100&&year%4==0)
        return true;
    return false;
}

求日期差

int leap(int y)           
{
    if(!y)
        return 0;
    return y/4-y/100+y/400;
}
int  calc(int day,int mon,int year)       
{
    int res=(year-1)*day+leap(year-1);
    int s[12]={31,28,31,30,31,30,31,31,30,31,30,31};
    for(int i=1;i<mon;i++)
        res+=s[i];
    if(Isleap(year)&&mon>2)
        res++;
    res+=day;
    return res;
} 
ll count_day(int da,int ma,int ya,int db,int mb,int yb)  
{
    int resa=calc(da,ma,ya);
    int resb=calc(db,mb,yb);
    return abs(resa-resb); 
}

蔡勒公式

给定日期求星期几，返回0~6，要加一。

int whatday(int day,int mon,int year)   
{
    int ans;
    if(mon==1||mon==2)
    {
        mon+=12;
        year--;
    }
    if((year<1752)||(year==1752&&mon<9)||(year==1752&&mon==9&&day<3))   //当日期在1752年9月3日之前
      ans=(day+2*mon+3*(mon+1)/5+year+year/4+5)%7;
    else  
      ans=(day+2*mon+3*(mon+1)/5+year+year/4-year/100+year/400)%7;
    return ans;
}

模拟退火

#include<bits/stdc++.h>
using namespace std;
const double delta=0.996;
int n;
double sx,sy;
double ansx,ansy;//最优解坐标
double ans=1e18+10,temper;//全局最优解、温度
struct node
{
    double x,y,w;
} a[1005];
int read()//快读挂
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
}
inline double evaluate(const double &x,const double &y)//评价函数
{
    double ret=0;
    for(register int i=1;i<=n;i++)
    {
        double dx=x-a[i].x,dy=y-a[i].y;
        ret+=(double)sqrt(dx*dx+dy*dy)*a[i].w;//使各方向力矩平衡
    }
    return ret;//一定不为负
}
void simulateAnneal()//模拟退火主过程
{
    double nowx=ansx,nowy=ansy;
    ans=evaluate(nowx,nowy);//f(x)
    for(temper=2e3+50;temper>1e-14;temper*=delta)//目标小一点就过了
    {//为什么不除以RAND_MAX?
        double nexx=nowx+temper*(((rand()<<1)-RAND_MAX));
        double nexy=nowy+temper*(((rand()<<1)-RAND_MAX));
        double now=evaluate(nexx,nexy);
        double diss=now-ans;//函数变动值delta
        if(diss<=0)//成功降低系统能量
        {
            nowx=nexx,nowy=nexy;
            ansx=nowx,ansy=nowy;
            ans=now;
        }
        else if(exp(-diss/temper)*RAND_MAX>rand())//概率接受,跳出局部
        {
            nowx=nexx,nowy=nexy;
        }
    }
}
void ac(int ca)
{
    for(int i=1;i<=n;i++)
        sx+=a[i].x,sy+=a[i].y;
    ansx=sx/n,ansy=sy/n;
    for(register int i=1;i<=ca;i++)
    {
        srand(rand());
        simulateAnneal();
    }
}
int main()
{
    srand(time(0));
    srand(rand());
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].w);
    }//输出平衡时绳结的位置
    ac(15);
    printf("%.3lf %.3lf\n",ansx,ansy);
    return 0;
}

CB简易使用手册

操作	快捷键
显示信息栏	F2
显示管理栏	Shift + F2
跳转指定行	Ctrl + G
跳转至下一未保存修改行	Ctrl + F3 / Ctrl + Shift + F3
开启自动换行	Settings->Editor->Other Options->Word warp
开启自动完成	Settings->Editors->Code completion
重复上一次操作	Ctrl + Shift + Z
与上一行调换	Ctrl + T
添加书签	Ctrl + B
跳转书签	Alt + PgUp / PgDown
跳转上下函数	Ctrl + PgUp / PgDown
呼出最近打开的文件	Ctrl + Tab
向上/下滚动	Ctrl + Up / Down
跳转一个单词	Ctrl + Left / Right

豆沙绿配色

Settings>Editor>Syntax Highlighting调整背景色

在Settings->Editor->左侧General settings，修改字体为Consolas，字号选择11号，同时把下面的show line numbers选中调整字体

色调：85。饱和度：123。亮度：205.

鹅黄：241，229，201.

如何调试

新建项目：File -> New -> Project... -> Console application -> Go -> 填写项目名和路径 -> 选择默认编译器 -> 在main中编写C++

启动调试器：View -> Toolbars -> Debugger 呼出调试栏，以Debug模式启动，点击按钮debug，打开调试窗口Watches可以显示变量值。点击 Next line 执行下一个语句，右边的Step into为执行内部语句，最右侧的红色按钮Stop debugger为结束调试；当执行到函数调用时，可以使用next line直接执行函数，或step into跳转到函数内部执行语句，希望停止调试则点击stop debugger。

Function	Shortcut Key
Debug	F8
Continue debugging	Ctrl + F7
跳过代码块	F7
单步执行代码块	Shift + F7
跳出代码块	Ctrl + Shift + F7
切换断点	F5
运行到光标	F4
Previous error	Alt + F1
Next error	Alt + F2

gvim简易手册

_vimrc

set nocompatible
source $VIMRUNTIME/vimrc_example.vim
source $VIMRUNTIME/mswin.vim
behave mswin

set encoding=utf-8 fileencodings=utf-8 termencoding=utf-8 "自动识别utf8
source $VIMRUNTIME/delmenu.vim "解决右键乱码
source $VIMRUNTIME/menu.vim
"解决consle输出乱码
language messages zh_CN.utf-8

"设置默认保存位置
exec 'cd ' . fnameescape("C:\\Users\\dell\\Desktop")  
set autochdir "自动识别当前打开文件路径
set pythonthreedll="C:\Program Files\Python38\python38.dll "改成自己的版本
"set pythonthreehome="C:\Program Files\Python38"

set diffexpr=MyDiff()
function MyDiff()
  let opt = '-a --binary '
  if &diffopt =~ 'icase' | let opt = opt . '-i ' | endif
  if &diffopt =~ 'iwhite' | let opt = opt . '-b ' | endif
  let arg1 = v:fname_in
  if arg1 =~ ' ' | let arg1 = '"' . arg1 . '"' | endif
  let arg2 = v:fname_new
  if arg2 =~ ' ' | let arg2 = '"' . arg2 . '"' | endif
  let arg3 = v:fname_out
  if arg3 =~ ' ' | let arg3 = '"' . arg3 . '"' | endif
  let eq = ''
  if $VIMRUNTIME =~ ' '
    if &sh =~ '\<cmd'
      let cmd = '""' . $VIMRUNTIME . '\diff"'
      let eq = '"'
    else
      let cmd = substitute($VIMRUNTIME, ' ', '" ', '') . '\diff"'
    endif
  else
    let cmd = $VIMRUNTIME . '\diff'
  endif
  silent execute '!' . cmd . ' ' . opt . arg1 . ' ' . arg2 . ' > ' . arg3 . eq
endfunction


filetype on
syntax on " 高亮
set cindent " C代码里需要的缩排
set smartindent
set autoindent " 自动缩进
set tabstop=4 " 修改 tab 字符的显示宽度
set shiftwidth=4 " 自动缩进所使用的空白长度
set softtabstop=4
"set ts=4
"set sw=4
"set sts=4
"缩进
if $OS == 'Windows_NT'
    set mouse=a
else
    set mouse-=a " Linux鼠标使用
endif
color molokai
"colo desert
"主题
set number " 行号
set guifont=Consolas:h15
"Linux: set guifont=Consolas\ h16
set backspace=2
set ruler " 显示标尺
"set bs=2
set clipboard=unnamed " 共享剪切板
set go= " 不要图形按钮
set nobackup
set undofile " 保留历史撤销记录

" 括号补全
inoremap ( ()<esc>i
inoremap [ []<esc>i
inoremap { {}<esc>i
inoremap ' ''<esc>i
inoremap " ""<esc>i

function! Compile()
    exec "w"
    if &filetype == 'python'
        exec "!python %"
    elseif &filetype == 'cpp'
        exec "!g++ % -o %< -std=c++11 -static-libgcc -Wall -g3"
        "exec "!g++ % -o %< -std=c++17 -static-libgcc -Wall -g3 -fexec-charset=GBK -finput-charset=UTF-8"
    elseif &filetype == 'c'
        exec "!g++ % -o %<"
    elseif &filetype == 'kotlin'
        exec "!kotlinc -d . %"
    elseif &filetype == 'java'
        exec "!javac %"
    else
        exec "!start %"
    endif
endfunction

function! Run()
    if &filetype == 'kotlin'
        exec "!kotlin %<Kt"
    elseif &filetype == 'java'
        exec "!java %<"
    elseif &filetype == 'go'
        exec "!go run %"
    else
        exec "!start %<"
    endif
endfunction

function! Open()
    exec "vsp %<.out"
    exec "sp %<.in"
endfunction

":call libcallnr("vimtweak64.dll", "SetAlpha", 200)
au GUIEnter * call libcallnr("vimtweak64.dll", "SetAlpha", 210)   "自动透明

syntax enable  
   
   
map<F4> <Esc>:call Open() <CR>
imap<F4> <Esc>:call Open() <CR>
map<F9> <Esc>:call Compile() <CR>
imap<F9> <Esc>:call Compile() <CR>
map<F10> <Esc>:call Run() <CR>
imap<F10> <Esc>:call Run() <CR>
map<F11> <F9> <CR> <F10> <CR>
imap<F11> <F9> <CR> <F10> <CR>


" <CTRL>-w m : mark first window
" <CTRL>-w m : swap with that window
let s:markedWinNum = -1
 
function! MarkWindowSwap()
    let s:markedWinNum = winnr()
endfunction
 
function! DoWindowSwap()
    "Mark destination
    let curNum = winnr()
    let curBuf = bufnr( "%" )
    exe s:markedWinNum . "wincmd w"
    "Switch to source and shuffle dest->source
    let markedBuf = bufnr( "%" )
    "Hide and open so that we aren't prompted and keep history
    exe 'hide buf' curBuf
    "Switch to dest and shuffle source->dest
    exe curNum . "wincmd w"
    "Hide and open so that we aren't prompted and keep history
    exe 'hide buf' markedBuf
endfunction
function! WindowSwapping()
    if s:markedWinNum == -1
        call MarkWindowSwap()
    else
        call DoWindowSwap()
        let s:markedWinNum = -1
    endif
endfunction
nnoremap <C-w>m :call WindowSwapping()<CR>

vim的四种模式

模式	说明
正常模式	默认，按 esc 进入，可复制粘贴、撤销重做
命令模式	正常模式下输入:或/进入，可进行保存、退出、搜索、运行
插入模式	按 i 进入，可进行输入编辑
可视模式	选中一块区域进行操作，按 v 进入

文件操作

命令	效果
:wq	保存并退出
:w 文件名	在当前路径下保存为指定文件
:q	退出
:q!	强制退出

移动

命令	效果
xw	光标向下移动x个单词
xb	光标向上移动x个单词
0	移动到行首

文本删除

命令（普通模式）	效果
dd	删除一行
de	从光标开始删除一个单词
dw	从光标开始删除一个单词（包括末尾空白）
dxw	删除x个单词
d$	删除到行末
dxd	删除x行

复制粘贴

按v进入可视模式，通过hjkl选择区域后，按下:y即可复制，在普通模式按p即可粘贴。

跳转

命令	效果
gg	跳转到第一行
G	跳转到最后一行
xG	跳转到第x行
[[	跳转到上一函数
%	跳转到匹配括号
`/word\>`	查找文本内所有word
`:%s/foo/bar/g`	全局替换foo为bar
`:%s/foo/bar/gc`	全局替换foo为bar并需要确认

编译

命令	效果
cpp test.cpp > test.i	将编译预处理结果（文本替换、宏展开以及删除注释）输入到test.i文件
g++ % -e %	同上
g++ -S %	使用指令编译成汇编代码
g++ tmp.cpp -o tmp -std=c++14 -static-libgcc -Wall -g3	编译
:10,20s#^#//#g	在 10 - 20 行添加 // 注释
:10,20s#^//##g	在 10 - 20 行删除 // 注释

STL

vector

vec.size();//获取vector里的元素个数
vector<int>(n); //构造大小为n的容器，没有初始化里面的元素
vec.empty();    //判断是否为空，为空返回true,否则返回false;
vec.capacity(); //获取容器分配的存储空间，区别于vec,size()
vec.resize(n+m); //调整vec的大小变为n+m
sort(vec.begin(),vec.end(),cmp);//排序
reverse(vec.begin(), vec.end());//反转,要加algorithm

list

c.size()    返回容器的大小
c.empty()    判断容器是否为空,等价于size()==0,但可能更快
c.max_size()    返回容器最大的可以存储的元素
reserve()    如果容量不足，扩大之
c.front()    返回第一个元素，不检查元素存在与否
c.back()    返回最后一个元素，不检查元素存在与否
c.begin() 返回一个逆向迭代器，指向逆向迭代的第一个元素
c.end()    返回一个逆向迭代器， 指向逆向迭代的最后一个元素的下一个位置 
c.insert(pos, elem)    在迭代器pos所指位置上(前面)安插一个elem副本，并返回新元素的位置
c.insert(pos,n,elem)    在pos位置上插入n个elem副本，无返回值
c.push_back(elem)    在尾部添加一个elem副本
c.pop_back()    移除最后一个元素，无返回值
c.push_front()    在头部添加一个elem副本
c.pop_front()    移除第一个元素，但不返回
c.remove(val)    移除所有其值为val的元素
c.erase(pos)    移除pos位置上的元素，返回下一个元素的位置
c.unique()    如果存在若干相邻而数值相等的元素，就移除重复元素，只留下一个
c.sort(op)    以op()为准则，对所有元素排序
c1.merge(c2，op)    假设c1和c2容器都包含op()原则下的已序(相同的排序方式)元素，将c2的全部元素转移到c1，并保证合并后的list在op（）原则仍是已序。
c.reverse()    将所有元素反序

set

multiset可重集，都为红黑树实现
begin()  返回set容器的第一个迭代器，不检查set是否为空
end()  返回set容器的最后一个迭代器，不检查set是否为空
clear() 删除set容器中的所有的元素
empty()  判断set容器是否为空，复杂度O(1)
max_size()  返回set容器可能包含的元素最大个数
size()  返回当前set容器中的元素个数，复杂度O(1)
set.count(x)  返回set或multiset中值为x的元素个数，复杂度O(log n)
set.insert(x) 插入元素，返回插入地址的迭代器和是否插入成功的bool并成的pair，复杂度O(log n)
erase(参数) 删除，参数可以是元素或者迭代器，返回下一个元素的迭代器，复杂度O(log n)
set.find(x) 在set中查找值为x的元素，并返回指向该元素的迭代器，若不存在，返回set.end()，复杂度O(log n)
lower_bound(x) 返回第一个大于等于x的定位器
upper_bound(x) 返回最后一个大于等于x的定位器

函数

max_element与min_element

template< class ForwardIt >//都返回一个迭代器,复杂度O(n)
ForwardIt max_element(ForwardIt first, ForwardIt last );
template< class ForwardIt, class Compare >
ForwardIt max_element(ForwardIt first, ForwardIt last, Compare comp );
nth_element(first,nth,last,cmp)//无返回值,但第k大位置确定(快速排序)

scanf格式化输入

转换说明符	意义
%d，%i	把输入解释为一个有符号十进制整数
%o	把输入解释为一个有符号八进制整数
%x,%X	把输入解释为一个无符号十六进制整数
%p	把输入解释为一个指针（一个地址）
[]	字符集合

[]里面填写需要捕获的字符集合

char buf[20];
scanf("%[abc]", buf);　　//输入abcdabcd123, buf内容为abc
scanf函数匹配[]中的所有字符，直到找到一个非[]中的字符

[]中也可以填写字符范围，例如
[a-z] //捕获包括字符从a到z的所有字符，直到找到一个非a-z的字符
[a-zA-Z] //捕获所有字母
[0-9] //捕获所有数字
[a-zA-Z0-9]捕获所有字母和数字
[a-zA-Z0-9!]捕获所有字母和数字并且捕获!(感叹号)

[]中如果第一字符为^符号则表示出现[]中的内容则停止捕获,并且仍然留在缓冲区,例如
[^a-zA-Z]捕获非字母
[^0-9]捕获非数字
scanf(" %[^\n]",s);//即可读入一整行到s字符数组

十进制转任意进制itoa

char* itoa(int num,char* str,int radix)
{
    char index[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";//索引表
    unsigned unum;//存放要转换的整数的绝对值,转换的整数可能是负数
    int i=0,j,k;//i用来指示设置字符串相应位，转换之后i其实就是字符串的长度；转换后顺序是逆序的，有正负的情况，k用来指示调整顺序的开始位置;j用来指示调整顺序时的交换。
    //获取要转换的整数的绝对值
    if(radix==10&&num<0)//要转换成十进制数并且是负数
    {
        unum=(unsigned)-num;//将num的绝对值赋给unum
        str[i++]='-';//在字符串最前面设置为'-'号，并且索引加1
    }
    else unum=(unsigned)num;//若是num为正，直接赋值给unum
    //转换部分，注意转换后是逆序的
    do{
        str[i++]=index[unum%(unsigned)radix];//取unum的最后一位，并设置为str对应位，指示索引加1
        unum/=radix;//unum去掉最后一位
    }while(unum);//直至unum为0退出循环
    str[i]='\0';//在字符串最后添加'\0'字符，c语言字符串以'\0'结束。
    //将顺序调整过来
    if(str[0]=='-') k=1;//如果是负数，符号不用调整，从符号后面开始调整
    else k=0;//不是负数，全部都要调整
    char temp;//临时变量，交换两个值时用到
    for(j=k;j<=(i-1)/2;j++)//头尾一一对称交换，i其实就是字符串的长度，索引最大值比长度少1
    {
        temp=str[j];//头部赋值给临时变量
        str[j]=str[i-1+k-j];//尾部赋值给头部
        str[i-1+k-j]=temp;//将临时变量的值(其实就是之前的头部值)赋给尾部
    }
    return str;//返回转换后的字符串
}

对拍

int main()
{
    int i;
    for (i=1;i<=1000;i++)
        {
            system("./make");//随机生成数据的程序
            system("./ab1");//暴力保证的正确程序,用freopen打开数据
            system("./ab2");//待验证的程序,用freopen打开数据
            printf("%d : ",i);
            if (system("diff ab1.out ab2.out"))
            {//两个都用freopen("ab1.out","w",stdout);输出到文件
                printf("WA\n");
                return 0;
            }
            else printf("AC\n");
        }
    return 0;
}