杂项与STL代码模板

发表于 更新于 分类于 阅读次数：

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

杂项

常用宏定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//#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
 *
*/

快速读入

1
2
3
4
5
6
7
8
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$次操作：

  1. 在时间$t$时刻插入一个$x$.

  2. 在时间$t$时刻删除一个$x$.

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

思路

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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)$，最大差值即作为斜率上下界，即每多选择一个物品额外产生的收益都是单调递减的。

img

此时我们不知道$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)$的值即为我们所需要的答案。

学习笔记

关于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)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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求得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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：使用结构体排序：不能有重复元素，但速度略快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
1
2
3
4
5
6
7
8
9
10
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内置函数

1
2
3
4
5
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 的情况例外

一些不好分类的算法

判断闰年

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

求日期差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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，要加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

模拟退火

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
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 把输入解释为一个指针（一个地址）
[] 字符集合

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;//返回转换后的字符串
}

对拍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}