求区间图字典序最小的最大点独立集。n<=20W

题目链接

平面上有n[0, 200]个点，每个点的横纵坐标范围为[0, 1000]，问最少5条直线能不能把这些点全部覆盖，时限15000ms。

想法：1.n^2枚举任意两个点构成的直线，在[0, 1000]的范围内枚举是否有其它点在这条线上。问题转化为有m个集合，每个集合有Ki个点，求最少几个集合的并集能成为全集。
2.二分图的最小点覆盖

正解：找出能覆盖5个以上点的直线，如果超过5条，则不可以；否则把这些直线放入解的集合，然后搜索减枝。

一维数轴上有一些线段，每个线段有一个权值和头尾位置，选取一些线段使权值最大，线段不能相交，求得到的最大权值。

开始打算最小费用流套区间线段覆盖的模型，两个线段向切的情况没法处理…

正解DP：dp[0][i]表示选第i个线段，从i到n能得到的总价值，dp[1][i]表示不选第[i]条线段，从i到n能得到的总价值，那么答案就是max(dp[0][1], dp[1][1])

状态转移方程：如果选第i条线段的时候，i的右边还有线段j可选：
dp[0][i] = val[i] + max(dp[0][j], dp[1][j])
否则 dp[0][i] = val[i]
dp[1][i] = max(dp[0][i+1], dp[1][i+1])

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 5;

struct node {
    int s, t, v;
    bool operator < (const node &rhs) const {
        return s < rhs.s;
    }
}p[MAXN];

int x[MAXN];
int dp[3][MAXN];

void solve(int n) {
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &p[i].s, &p[i].t, &p[i].v);
    }
    sort(p, p+n);
    dp[0][n] = dp[1][n] = 0;
    for (int i = 0; i < n; i++) x[i] = p[i].s;
    for (int i = n-1; i >= 0; i--) {
        int j = lower_bound(x, x + n, p[i].t+1) - x;
        if (j < n) {
            dp[0][i] = p[i].v + max(dp[1][j], dp[0][j]);
        } else {
            dp[0][i] = p[i].v;
        }
        dp[1][i] = max(dp[0][i+1], dp[1][i+1]);
    }
    printf("%d\n", max(dp[0][0], dp[1][0]));
}

int main() {
    //freopen("in.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF) {
        solve(n);
    }
    return 0;
}

1564题的矩阵是这样的：

4x4的矩阵             第一层             第二层
----------           ----------        -----
1  2  3  4           1  2  3  4
12 13 14 5           12       5        13 14
11 16 15 6           11       6        16 15
10 9  8  7           10 9  8  7

第一种方法按照右下左上右下左上的顺序构造出整个矩阵，第二种方法能在O(1)时间求出坐标为（i, j)的位置上的数字是多少

算法：
1.根据坐标能算出(x, y)所在的层数k， k = min(n - x + 1, x)
2.根据层数k能算出该层的左上角的元素s(k, k)是什么, 
  s = n * n - (n-(k-1)*2) * (n-(k-1）*2) + 1
  s = 2(k-1)(n-k+1) + 1
3.根据(x, y)和(k, k)的相对位置，
  如果x在第k层，A(x, y) = s + |x - k|
  否则 A(x, y) = s + 2*(n-(k-1)*2) - 1 - |x - k|
  如果y在第k+(n-(k-1）*2)层，A(x, y) += |y - k|
  否则 A(x, y) += 2*(n-(k-1)*2) - 1 - |y - k|

2192的矩阵是从中心开始的，矩阵边长为奇数，所以一定是正方形，现在已知边长n，和数m，求m的坐标

5x5的矩阵            第一层      第二层         第三层
------------------- -----   -----------   ---------------
21  22  23   24  25                        21 22 23 24 25
20   7   8    9  10          7   8   9     20          10
19   6   1    2  11   1      6       2     19          11
18   5   4    3  12          5   4   3     18          12
17  16  15   14  13                        17 16 15 14 13

1.思路也是对矩阵分层，从内向外分层：
  第k层数的范围是[(2k-3)^2+1, (2k-1)^2]
2.nxn的矩阵中，'1'的坐标为((n+1)/2, (n+1)/2),则第k层的
  最大元素(右上角)的坐标为S（（n+1)/2+k-1, (n+1)/2-k+1)
3.从S开始左，下，右，上找m,更新坐标
时间复杂度:O(n)

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20000;
int dep[N + 2];

void init() {
    for (int i = 1; i <= N; i++) {
        dep[i] = (2*i-1) * (2*i-1);
    }
}

void solve(int n, int m) {
    int k = lower_bound(dep + 1, dep + N, m) - dep;
    int sy = (n+1)/2 + k-1;
    int sx = (n+1)/2 - k+1;
    int wid = k * 2 - 1;
    int now = dep[k];
    if (now != m) {
        for (int i = 1; i < wid; i++) {
            sy--;
            now--;
            if (now == m) {
                printf("%d %d\n", sx, sy);
                return;
            }
        }
        for (int i = 1; i < wid; i++) {
            sx++;
            now--;
            if (now == m) {
                printf("%d %d\n", sx, sy);
                return;
            }
        }
        for (int i = 1; i < wid; i++) {
            sy++;
            now--;
            if (now == m) {
                printf("%d %d\n", sx, sy);
                return;
            }
        }
        for (int i = 1; i < wid; i++) {
            sx--;
            now--;
            if (now == m) {
                printf("%d %d\n", sx, sy);
                return;
            }
        }
    } else {
        printf("%d %d\n", sx, sy);
        return;
    }
}

int main() {
    init();
    int t, n, m;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        solve(n, m);
    }
    return 0;
}

和HDU 2835 Operating system很像，都以页面置换算法为背景，HDU的是最佳置换算法，而本题是最近最久未使用置换算法。

用STL::map查找某个结点的时间复杂度为O(logn)
用map找到位置后双链表删除一个元素的时间降为O(1)

时间复杂度O(mlogn)

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;

//可以用hash_map unordered_map 或者map
//#define MAP map
//#define MAP unordered_map
#define MAP hash_map
template <class K, class T>
struct Node{
    K key;
    T data;
    Node *prev, *next;
};

template <class K, class T>
class LRUCache{
public:
    LRUCache(int size){
        entries_ = new Node<K,T>[size];
        for(int i=0; i<size; ++i)
            free_entries_.push_back(entries_+i);
        head_ = new Node<K,T>;
        tail_ = new Node<K,T>;
        head_->prev = NULL;
        head_->next = tail_;
        tail_->prev = head_;
        tail_->next = NULL;
    }

    ~LRUCache(){
        delete head_;
        delete tail_;
        delete[] entries_;
    }
    void Put(K key, T data){
        Node<K,T> *node = hashmap_[key];
        if(node){
            detach(node);
            node->data = data;
            attach(node);
        }
        else{
            if(free_entries_.empty()){
                node = tail_->prev;
                detach(node);
                hashmap_.erase(node->key);
            }
            else{
                node = free_entries_.back();
                free_entries_.pop_back();
            }
            node->key = key;
            node->data = data;
            hashmap_[key] = node;
            attach(node);
        }
    }
    T Get(K key){
        Node<K,T> *node = hashmap_[key];
        if(node){
            detach(node);
            attach(node);
            return node->data;
        }
        else{// 如果cache中没有，返回T的默认值。
            return T();
        }
    }
private:
    // 分离结点
    void detach(Node<K,T>* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    // 将结点插入头部
    void attach(Node<K,T>* node){
        node->prev = head_;
        node->next = head_->next;
        head_->next = node;
        node->next->prev = node;
    }
private:
    MAP<K, Node<K,T>* > hashmap_;
    vector<Node<K,T>* > free_entries_; // 存储可用结点的地址
    Node<K,T> *head_, *tail_;
    Node<K,T> *entries_; // 双向链表中的结点
};

const int MAXN = 10010;

int main(){
    //freopen("in.txt", "r", stdin);
    int n, m;
    int test, cas(1);
    scanf("%d", &test);
    while(test--){
        scanf("%d%d",&n,&m);
        LRUCache<int, int> lru_cache(n);
        int suc_cnt(0);
        for(int i = 0, q;i < m; ++i){
            scanf("%d",&q);
            if (lru_cache.Get(q)) {
                suc_cnt++;
            }
            lru_cache.Put(q, q+1);
        }
        printf("Case %d: %d\n", cas++, suc_cnt);
    }
    return 0;
}

每个数字带权值，求最长上升子序列的同时要求权值和最小

一：O(n^2)求LIS的时候维护一个最小代价

二：O(nlogn)线段树维护一个区间最大值，这个最大值的最高位表示LIS的长度，最低几位表示代价，取个相反数可以保证LIS长度相同时代价越小的值越大，这样线段树维护一下区间最大值就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 100000 + 5;

ll tree[MAXN << 2];

void update(int rt, int l, int r, int p, ll v) {
    if (l == r) {
        tree[rt] = max(tree[rt], v);
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(rt<<1, l, mid, p, v);
    else update(rt<<1|1, mid+1, r, p, v);
    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
}

ll query(int rt, int l, int r, int L, int R) {
    if (L > r || R < l) return 0;
    if (L <= l && r <= R) return tree[rt];
    int mid = (l + r) >> 1;
    return max(query(rt<<1, l, mid, L, R), query(rt<<1|1, mid+1, r, L, R));
}

struct point {
    int x, y; ll v;
    void read() {
        scanf("%d%d%lld", &x, &y, &v);
    }
    bool operator < (const point &rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
} p[MAXN];

const ll wwtf = 1e11;

int main() {
    int t; scanf("%d", &t);
    for (int _ = 1; _ <= t; _++) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) p[i].read();
        sort(p, p + n);
        memset(tree, 0, sizeof(tree));
        for (int i = 0; i < n; i++) {
            ll tep = query(1, 0, MAXN-1, 0, p[i].y) + wwtf + 10000 - p[i].v;
            update(1, 0, MAXN-1, p[i].y, tep);
        }
        ll len = query(1, 0, MAXN-1, 0, MAXN-1);
        ll wtf = len / wwtf;
        printf("Case #%d: %lld %lldn", _, wtf,wtf*10000-(len%wwtf));
    }
    return 0;
}

三：nlogn的二分+贪心的有点问题，贪心的正确性没有了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 5;

struct point {
    int v, x, y;
    void read() {
        scanf("%d%d%d", &x, &y, &v);
    }
    bool operator < (const point &rhs) const {
        return x < rhs.x;
    }
} p[MAXN];

int b[MAXN], val[MAXN];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            p[i].read();
            val[p[i].y] = p[i].v;
        }
        sort(p, p + n);
        b[0] = p[0].y;

        int ans = p[0].v;
        int len = 0;
        for (int i = 1; i < n; i++) {
            if (p[i].y >= b[len]) {
                len++;
                b[len] = p[i].y;
                ans += p[i].v;
            } else {
                int pos = lower_bound(b, b + len, p[i].y) - b;
                ans -= val[b[pos]];
                b[pos] = p[i].y;
                ans += p[i].v;
            }
        }
        printf("%d %dn", len + 1, ans);
    }
    return 0;
}

B【】给出一个图，其中一些边的长度可以为任意值，问从s到t的距离能否恰好是L，如果能，输出每条边的长度。

2016.9.14 Codeforces Round #371 (Div. 1)

2016.9.11 Codeforces Round #370 (Div. 2)

2016.8.29 Codeforces Round #369

C 【DP】dp[i][j][k]表示前I棵树，第j棵的颜色是j，不同的段数为k时的最小代价，则：

2016.8.25 Codeforces AIM Tech Round 3 (Div. 1)

B 【构造】要求构造一个长度不超过1000000的由0，1构成的字符串，使其中长度为2的‘00’，‘01’，‘10’，‘11’的序列个数恰好为A00， A01， A10， A11(A00等为题目中给的已知量)

从1到100000枚举可确定0和1的数量, 由0*1的数量与A01+A10是否相等判断是否存在这样的字符串
之后问题转化为由x个0，y个1，如何构造

2016.4.29 Codeforces Round #349 (Div. 1)

A  给一个字符串，由root和一些suffix组成，suffix的长度为2或3，同一个组成内相连的的suffix不能相同，求suffix有多少种情况，并按字典序输出

【DP】O(len(s))
dp[i][L]表示在i点长为L的字符串是不是suffix，则dp[i][L] |= dp[i+L][L2], 2 <= L2 <= 3,若dp[i][L]为真，则把i点长为L的字符串插入STL::set中

B 给了一个有向图，图中每两点间距离为1，若在图中选4个点，并按这4个点的顺序进行遍历能使路径长度最长，求出这四个点和它们的顺序

【枚举】【图上搜索】O(n^2logn)
设四个点依次为h, i, j, k,想求dis[h][i]+dis[i][j]+dis[j][k]距离最大：n^2logn的时间内预处理图上任意两点的最短距离，n^2的时间预处理距离每个点最远的点依次是哪些，然后枚举i和j为图上任意两点，分别在距离i，j最远的三个点中找满足条件的h，k

2016.3.19

CF 653C Bear and Up-Down 【暴力】规律：偶数位最大，奇数位最小

2015.12.14

LeetCode  Add Digits 【模拟】【按%9是否为0讨论】

2015.12.13

CF 605B     Lazy Student 【构造】贪心构造最小生成树，树边1-2-3…n-1，非树边1-3 1-4 2-4 1-5 2-5 3-5 …

2015.12.6

CF 604B     More Cowbell 【暴力】考虑k=1时有p^p种，k!=1时算i*k%p有多少种
CF 603A     Alternative Thinking 【思考】置反一次最多能把字串长度+2
CF 604B     More Cowbell 【贪心Hack】for (int i = 5; i >= -1000; i–) ans = max(ans, A[i]) 也能被hack
CF 604A     Uncowed Forces 【模拟 约分】

2015.11.25

CF 601A     The Two Routes 【最短路】两次最短路的最大时间

CF 602B     Approximating a Constant Range 【RMQ】O(nlongn + n) 两个指针维护最长长度

CF 602A     Two Bases  【模拟】k进制转10进制用long long …别用pow()

2015.11.22

HDU 1878【欧拉回路】无向图的欧拉回路存在，每点度数为偶数且全图连通

HDU 3018  Ant Trip 【欧拉路径的性质】每个欧拉路径最多两个点度为奇数

HDU 1116 Play on Words【有向图的欧拉通路】 最多一个点入度比出度大1，一个点出度比入度大1

CF 599D Spongebob and Squares 【解方程】假设m为矩形较小的边 (x = sum_{d=0}^{m-1} (n-d)(m-d) )，则 (n = (m^3-m+6x)/(3m(m+1)) )，枚举m

CF 599C Day at the Beach 【贪心】 找到两个相邻的段，使左段的最大值不小于右段的最小值，rmq求每个段的最大最小值

CF 599B Spongebob and Joke 【讨论】Bi在Ai中是否存在以及个数是否大于1

CF 599A Patrick and Shopping 【枚举】枚举四种可能的情况

CF 596C Wilbur and Points 【贪心】 每遇到一个wi，尽量用x排序靠前的满足条件，如果出现曾经与当前y值比配的x比当前的x更大，则不满足

CF 596B Wilbur and Array  【贪心】 每次维护左边的值都会影响右边的值，最好的方法就是从左往右维护数组了

CF 596A Wilbur and Swimming Pool  【脑筋】 能够成唯一矩形的条件是不同的横纵坐标种数有且仅有两种

2015.11.15

CF 595A     Vitaly and Night 【模拟】 按题目说的做就行了

2015.11.8

CF 593A     2Char   【枚举】 枚举26个字母中的两个，维护最大值

CF 593B     Anton and Lines 【排序】 判断是否存在逆序关系

2015.11.1

CF 591B     Rebranding 【字符串模拟】

CF 591A     Wizards’ Duel 【简单数学】

5题能拿金，4题能拿银，能拿铜，也能打铁，我们队就是那个4题打铁的，比铜牌最后一名多了53分钟罚时。

有点不甘心。

开场之前我配vim，崔说我们用Codeblocks吧，争了半天，陈洋说你就让他配吧（之前说好了用vim的，热身赛也用的vim，怎么突然就换了呢？），之后我敲PC^2的账户密码，崔说让我先读题，又争了一会儿。看来每个队还是要有一个队长的，要么大家谁也不服谁，都认为自己做的对，整个队伍就乱了。

之后我读前4道题，崔中间4道，陈洋最后5道。崔发现F题可以做，我听他说了题意，没什么思路，就继续读我的题。过了一会儿，崔有了F的思路，扫一遍，分别查’>’和'<‘的数目是否为n-1个，我想想觉的没问题，他敲完了，测了几组数据，发现没法过5 1 2 3 4这组数据，然后卡住了。这时候我有了F的想法，一共6种情况枚举一下就行了，虽然不优雅，绝对能过。这时候陈洋发现L能做，给崔讲了F，崔赶紧过来敲L，40min1Y。

然后我继续枚举串最开始上升的3种情况，下降的把上升的复制一下就行了，写了好久，队友开始出数据，又改了好久bug，感觉没问题了，交上去T了，写了两重for找转折点，有两个地方没break掉。崔和陈洋又看了一遍，觉得没问题了，交，WA了。这时候崔说换题，我说你们看别的吧，我再想一会儿。然后崔和陈洋还看这题，于是我说你们看这题吧，我去读别的。我开始读题…过了一会崔说你原来的代码是对的，（崔查代码的时候帮我改掉了一处”错误”，我当时觉的他说的对就改了），又过了一会儿，崔说你少了一种情况，他画了个图，我清醒了。我原来写的是情况1，他改成了情况2，所以我觉得两个都对。我说，你在我那代码下面再加一个循环就行了，这时候我应该去抢键盘，毕竟是我写的代码，队友可能没看懂，而不是做在旁边指手画脚。果然队友没改我的代码，崔重写了一份，又过了好久，我去问他卡到哪里了，他不缺定第一种情况的第一个值是多少，默认递减第一个是正无穷啊！然后他继续写，过了一会151min3Y。

之后崔去上厕所，陈洋给我讲了G的题意，并讲了想法：先求凸包，再判角。崔最近在弄计算几何，这道题就给他写了。我说不用判角，凸包只要边都相等就是正多边型了，崔说不对，这时候我想到了菱形，狠狠打了脸。然后崔开始敲他的计算几何模板，敲一会儿看一会儿。我拿出了吉大的模板看了看，很短很简单，看懂每个数组的意思，我和崔说要不要让我来敲，崔说不用。我说你看看吉大这个模板，很短。崔看了看，决定用吉大的。过了一会儿我瞅他还是看一会儿敲一会儿，他说吉大模板有坑，极角排序怎么怎么样的balabala…（这模板里根本没有极角排序）我说我来吧，崔说不用。过了以会儿我感觉J能写出O(n^2)的，想把崔换下去，10min就能写完，正好崔又卡住了，但陈洋想让崔把G写完，最后崔打印debug，我写J。写了5min感觉不对，想错了，把机器让给崔，崔和陈洋让我继续写（我要是能继续写下去能让机器吗…），崔继续写G。过了一会儿，陈洋问我怎么求两条线段的有向夹角，我不会用叉积，但小白书上有个有向面积2倍的求法，用那个就行了，因为边长确定了，面积也相等，夹角一定相等。把白书给了陈洋，崔继续敲。又debug了一会儿，G232min1Y。

这时候都觉的没题可以做了，开始随意看题，这时候我说J试试O(n^3)的暴力吧，我加个fread挂，显然崔和陈洋都不抱希望了，也就同意了，J266min1Y。

也出乎了我的意料。大家很高兴，看了下榜，才发现封榜了。又读读题，比赛就结束了。

132拿铜，我们排140

这场比赛的几个坑点：

开场关于用vim还是codeblocks，先输密码还是先读题，现在感觉有点逗逼。

F：崔敲了一次，我敲了一次，崔又敲了一次。我如果1A就没后面那么多事了。先T一次又WA了一次，贡献了40min的罚时和巨大的编码时间。

G：崔用了79分钟，在处理环形的时候判断的很麻烦。而我的思路很清晰，那27行模板加上判边判角，30分钟我觉对能敲完。

陈洋和崔debug用了大量时间，如果我能加入他们一定能快很多，这个怪我。我很喜欢把他俩仍一起，我陈洋和我一起讨论题我会忍不住发火，事实上已经发火好几次了，感觉她说的那种方法…完全不可能啊，但毕竟是个妹子，忍了。

大部分队伍40分钟2次过F，而我们151分钟加3过的，卡F题卡的太久了，导致没能拿铜。

ACM生涯就这么结束了…

感谢boss唐，如果不是他用心在维持，我校也不会取得这么好的成绩。新增了E1130和E1530这两个大机房，为我们提供了很好的学习环境。

感谢队友，如果没有陈洋和小崔，可能我也不会有打长春站的机会。

刷题的日子还会继续…

12月份的校赛打算自己单挑。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1005;

int lis[N], ln;
bool vis[N], g[N][N];

int n;

int get(int u) {
    for (int i = 1; i <= n; i++) {
        if (!g[u][i] || vis[i]) continue;
        return i;
    }
    return 0;
}

void gao() {
    while (1) {
        while (1) {
            int v = get(lis[ln - 1]);
            if (v == 0) break;
            lis[ln++] = v; vis[v] = true;
        }
        reverse(lis, lis + ln);
        while (1) {
            int v = get(lis[ln - 1]);
            if (v == 0) break;
            lis[ln++] = v; vis[v] = true;
        }
        if (!g[lis[0]][lis[ln - 1]]) {
            for (int i = 1; i <= ln - 2; i++) {
                if (g[lis[i + 1]][lis[0]] && g[lis[i]][lis[ln - 1]]) {
                    reverse(lis + i + 1, lis + ln);
                    break;
                }
            }
        }
        if (ln == n) break;
        for (int i = 0; i < ln; i++) {
            int v = 0;
            for (int j = 1; j <= n; j++) {
                if (!g[lis[i]][j] || vis[j]) continue;
                v = j;
                break;
            }
            if (v) {
                reverse(lis, lis + i);
                reverse(lis + i, lis + ln);
                lis[ln++] = v;
                vis[v] = true;
                break;
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int v; char c;
        while (~scanf("%d%c", &v, &c)) {
            g[i][v] = true;
            if (c == 'n') break;
        }
    }
    lis[ln++] = 1;
    vis[1] = true;
    gao();
    for (int i = 0; i < ln; i++) {
        if (lis[i] == 1) {
            int u = i;
            for (int j = 0; j < ln; j++) {
                printf("%d ", lis[u]);
                u++;
                if (u == ln) u = 0;
            }
            break;
        }
    }
    printf("1n");
    return 0;
}

Linux下的比赛Vimrc的配置

set nu ai ci si mouse=a ts=4 sts=4 sw=4
nmap<F2> : vs %<.in <CR>  " 新建一个读入文件
nmap<F8> : !./%< < %<.in <CR>  "从文件读入并输出运行结果
nmap<F9> : make %< <CR>  " 编译

"可选填的代码比如

nmap<F4> : !gedit % <CR>  "用gedit打开代码
nmap<F5> : !./%< <CR>       " 直接运行
nmap<F10> : !g++ % -o %< -O2 -g -Wall <CR> " -O2优化，-Wall警告

日常的配置

" =============================================================================
"        << 判断操作系统是 Windows 还是 Linux 和判断是终端还是 Gvim >>
" =============================================================================
" -----------------------------------------------------------------------------
"  < 判断操作系统是否是 Windows 还是 Linux >
" -----------------------------------------------------------------------------
:cd /home/gyf/Codes/
let g:iswindows = 0
let g:islinux = 0
if(has("win32") || has("win64") || has("win95") || has("win16"))
    let g:iswindows = 1
else
    let g:islinux = 1
endif

" -----------------------------------------------------------------------------
"  < 判断是终端还是 Gvim >
" -----------------------------------------------------------------------------
if has("gui_running")
    let g:isGUI = 1
else
    let g:isGUI = 0
endif


" =============================================================================
"                          << 以下为软件默认配置 >>
" =============================================================================
" -----------------------------------------------------------------------------
"  < Linux Gvim/Vim 默认配置> 做了一点修改
" -----------------------------------------------------------------------------
if g:islinux
    set hlsearch        "高亮搜索
    set incsearch       "在输入要搜索的文字时，实时匹配

    " Uncomment the following to have Vim jump to the last position when
    " reopening a file
    if has("autocmd")
        au BufReadPost * if line("'"") > 1 && line("'"") <= line("$") | exe "normal! g'"" | endif
    endif

    if g:isGUI
        " Source a global configuration file if available
        if filereadable("/etc/vim/gvimrc.local")
            source /etc/vim/gvimrc.local
        endif
    else
        " This line should not be removed as it ensures that various options are
        " properly set to work with the Vim-related packages available in Debian.
        runtime! debian.vim

        " Vim5 and later versions support syntax highlighting. Uncommenting the next
        " line enables syntax highlighting by default.
        if has("syntax")
            syntax on
        endif

        set mouse=a                    " 在任何模式下启用鼠标
        set t_Co=256                   " 在终端启用256色
        set backspace=2                " 设置退格键可用

        " Source a global configuration file if available
        if filereadable("/etc/vim/vimrc.local")
            source /etc/vim/vimrc.local
        endif
    endif
endif


" =============================================================================
"                          << 以下为用户自定义配置 >>
" =============================================================================

" -----------------------------------------------------------------------------
"  < Vundle 插件管理工具配置 >
" -----------------------------------------------------------------------------
" 用于更方便的管理vim插件，具体用法参考 :h vundle 帮助
" 安装方法为在终端输入如下命令
" git clone https://github.com/gmarik/vundle.git ~/.vim/bundle/vundle
" 如果想在 windows 安装就必需先安装 "git for window"，可查阅网上资料

set nocompatible                                      "禁用 Vi 兼容模式
filetype off                                          "禁用文件类型侦测

if g:islinux
    set rtp+=~/.vim/bundle/vundle/
    call vundle#rc()
else
    set rtp+=$VIM/vimfiles/bundle/vundle/
    call vundle#rc('$VIM/vimfiles/bundle/')
endif

" -----------------------------------------------------------------------------
"  < 编码配置 >
" -----------------------------------------------------------------------------
" 注：使用utf-8格式后，软件与程序源码、文件路径不能有中文，否则报错
set encoding=utf-8                                    "设置gvim内部编码
set fileencoding=utf-8                                "设置当前文件编码
set fileencodings=ucs-bom,utf-8,gbk,cp936,latin-1     "设置支持打开的文件的编码

" 文件格式，默认 ffs=dos,unix
set fileformat=unix                                   "设置新文件的<EOL>格式
set fileformats=unix,dos,mac                          "给出文件的<EOL>格式类型

if (g:iswindows && g:isGUI)
    "解决菜单乱码
    source $VIMRUNTIME/delmenu.vim
    source $VIMRUNTIME/menu.vim

    "解决consle输出乱码
    language messages zh_CN.utf-8
endif

" -----------------------------------------------------------------------------
"  < 编写文件时的配置 >
" -----------------------------------------------------------------------------
filetype on                                           "启用文件类型侦测
filetype plugin on                                    "针对不同的文件类型加载对应的插件
filetype plugin indent on                             "启用缩进
set smartindent                                       "启用智能对齐方式
set expandtab                                         "将Tab键转换为空格
set tabstop=4                                         "设置Tab键的宽度
set shiftwidth=4                                      "换行时自动缩进4个空格
set smarttab                                          "指定按一次backspace就删除shiftwidth宽度的空格
set foldenable                                        "启用折叠
set clipboard=unnamed
" set foldmethod=indent                                 "indent 折叠方式
" set foldmethod=marker                                "marker 折叠方式

" 用空格键来开关折叠
nnoremap <space> @=((foldclosed(line('.')) < 0) ? 'zc' : 'zo')<CR>

" 当文件在外部被修改，自动更新该文件
set autoread

" 常规模式下输入 cS 清除行尾空格
nmap cS :%s/s+$//g<CR>:noh<CR>

" 常规模式下输入 cM 清除行尾 ^M 符号
nmap cM :%s/r$//g<CR>:noh<CR>

set ignorecase                                        "搜索模式里忽略大小写
set smartcase                                         "如果搜索模式包含大写字符，不使用 'ignorecase' 选项，只有在输入搜索模式并且打开 'ignorecase' 选项时才会使用
" set noincsearch                                       "在输入要搜索的文字时，取消实时匹配

" Ctrl + K 插入模式下光标向上移动
imap <c-k> <Up>

" Ctrl + J 插入模式下光标向下移动
imap <c-j> <Down>

" Ctrl + H 插入模式下光标向左移动
imap <c-h> <Left>

" Ctrl + L 插入模式下光标向右移动
imap <c-l> <Right>

" 启用每行超过80列的字符提示（字体变蓝并加下划线），不启用就注释掉
"au BufWinEnter * let w:m2=matchadd('Underlined', '%>' . 80 . 'v.+', -1)

" -----------------------------------------------------------------------------
"  < 界面配置 >
" -----------------------------------------------------------------------------
set number                                            "显示行号
set laststatus=2                                      "启用状态栏信息
set cmdheight=2                                       "设置命令行的高度为2，默认为1
set cursorline                                        "突出显示当前行
" set guifont=YaHei_Consolas_Hybrid:h10                 "设置字体:字号（字体名称空格用下划线代替）
set nowrap                                            "设置不自动换行
set shortmess=atI                                     "去掉欢迎界面

" 设置 gVim 窗口初始位置及大小
if g:isGUI
    " au GUIEnter * simalt ~x                           "窗口启动时自动最大化
    winpos 100 10                                     "指定窗口出现的位置，坐标原点在屏幕左上角
    set lines=38 columns=120                          "指定窗口大小，lines为高度，columns为宽度
endif

" 设置代码配色方案
if g:isGUI
    colorscheme Tomorrow-Night-Eighties               "Gvim配色方案
else
    colorscheme Tomorrow-Night-Eighties               "终端配色方案
endif

" 显示/隐藏菜单栏、工具栏、滚动条，可用 Ctrl + F11 切换
if g:isGUI
    set guioptions-=m
    set guioptions-=T
    set guioptions-=r
    set guioptions-=L
    map <silent> <c-F11> :if &guioptions =~# 'm' <Bar>
        set guioptions-=m <Bar>
        set guioptions-=T <Bar>
        set guioptions-=r <Bar>
        set guioptions-=L <Bar>
    else <Bar>
        set guioptions+=m <Bar>
        set guioptions+=T <Bar>
        set guioptions+=r <Bar>
        set guioptions+=L <Bar>
    endif<CR>
endif

" -----------------------------------------------------------------------------
"  < 单文件编译、连接、运行配置 >
" -----------------------------------------------------------------------------
" 以下只做了 C、C++ 的单文件配置，其它语言可以参考以下配置增加


map <F5> :w<cr>:!python %<cr>


" F9 一键保存、编译、连接存并运行
map <F9> :call Run()<CR>
imap <F9> <ESC>:call Run()<CR>

" Ctrl + F9 一键保存并编译
map <c-F9> :call Compile()<CR>
imap <c-F9> <ESC>:call Compile()<CR>

" Ctrl + F10 一键保存并连接
map <c-F10> :call Link()<CR>
imap <c-F10> <ESC>:call Link()<CR>

let s:LastShellReturn_C = 0
let s:LastShellReturn_L = 0
let s:ShowWarning = 1
let s:Obj_Extension = '.o'
let s:Exe_Extension = '.exe'
let s:Sou_Error = 0

let s:windows_CFlags = 'gcc -fexec-charset=gbk -Wall -g -O0 -c % -o %<.o'
let s:linux_CFlags = 'gcc -Wall -g -O0 -c % -o %<.o'

let s:windows_CPPFlags = 'g++ -fexec-charset=gbk -Wall -g -O0 -c % -o %<.o'
let s:linux_CPPFlags = 'g++ -Wall -g -O0 -c % -o %<.o'

func! Compile()
    exe ":ccl"
    exe ":update"
    let s:Sou_Error = 0
    let s:LastShellReturn_C = 0
    let Sou = expand("%:p")
    let v:statusmsg = ''
    if expand("%:e") == "c" || expand("%:e") == "cpp" || expand("%:e") == "cxx"
        let Obj = expand("%:p:r").s:Obj_Extension
        let Obj_Name = expand("%:p:t:r").s:Obj_Extension
        if !filereadable(Obj) || (filereadable(Obj) && (getftime(Obj) < getftime(Sou)))
            redraw!
            if expand("%:e") == "c"
                if g:iswindows
                    exe ":setlocal makeprg=".s:windows_CFlags
                else
                    exe ":setlocal makeprg=".s:linux_CFlags
                endif
                echohl WarningMsg | echo " compiling..."
                silent make
            elseif expand("%:e") == "cpp" || expand("%:e") == "cxx"
                if g:iswindows
                    exe ":setlocal makeprg=".s:windows_CPPFlags
                else
                    exe ":setlocal makeprg=".s:linux_CPPFlags
                endif
                echohl WarningMsg | echo " compiling..."
                silent make
            endif
            redraw!
            if v:shell_error != 0
                let s:LastShellReturn_C = v:shell_error
            endif
            if g:iswindows
                if s:LastShellReturn_C != 0
                    exe ":bo cope"
                    echohl WarningMsg | echo " compilation failed"
                else
                    if s:ShowWarning
                        exe ":bo cw"
                    endif
                    echohl WarningMsg | echo " compilation successful"
                endif
            else
                if empty(v:statusmsg)
                    echohl WarningMsg | echo " compilation successful"
                else
                    exe ":bo cope"
                endif
            endif
        else
            echohl WarningMsg | echo ""Obj_Name"is up to date"
        endif
    else
        let s:Sou_Error = 1
        echohl WarningMsg | echo " please choose the correct source file"
    endif
    exe ":setlocal makeprg=make"
endfunc

func! Link()
    call Compile()
    if s:Sou_Error || s:LastShellReturn_C != 0
        return
    endif
    if expand("%:e") == "c" || expand("%:e") == "cpp" || expand("%:e") == "cxx"
        let s:LastShellReturn_L = 0
        let Sou = expand("%:p")
        let Obj = expand("%:p:r").s:Obj_Extension
        if g:iswindows
            let Exe = expand("%:p:r").s:Exe_Extension
            let Exe_Name = expand("%:p:t:r").s:Exe_Extension
        else
            let Exe = expand("%:p:r")
            let Exe_Name = expand("%:p:t:r")
        endif
        let v:statusmsg = ''
        if filereadable(Obj) && (getftime(Obj) >= getftime(Sou))
            redraw!
            if !executable(Exe) || (executable(Exe) && getftime(Exe) < getftime(Obj))
                if expand("%:e") == "c"
                    setlocal makeprg=gcc -o %< %<.o
                    echohl WarningMsg | echo " linking..."
                    silent make
                elseif expand("%:e") == "cpp" || expand("%:e") == "cxx"
                    setlocal makeprg=g++ -o %< %<.o
                    echohl WarningMsg | echo " linking..."
                    silent make
                endif
                redraw!
                if v:shell_error != 0
                    let s:LastShellReturn_L = v:shell_error
                endif
                if g:iswindows
                    if s:LastShellReturn_L != 0
                        exe ":bo cope"
                        echohl WarningMsg | echo " linking failed"
                    else
                        if s:ShowWarning
                            exe ":bo cw"
                        endif
                        echohl WarningMsg | echo " linking successful"
                    endif
                else
                    if empty(v:statusmsg)
                        echohl WarningMsg | echo " linking successful"
                    else
                        exe ":bo cope"
                    endif
                endif
            else
                echohl WarningMsg | echo ""Exe_Name"is up to date"
            endif
        endif
        setlocal makeprg=make
    endif
endfunc

func! Run()
    let s:ShowWarning = 0
    call Link()
    let s:ShowWarning = 1
    if s:Sou_Error || s:LastShellReturn_C != 0 || s:LastShellReturn_L != 0
        return
    endif
    let Sou = expand("%:p")
    if expand("%:e") == "c" || expand("%:e") == "cpp" || expand("%:e") == "cxx"
        let Obj = expand("%:p:r").s:Obj_Extension
        if g:iswindows
            let Exe = expand("%:p:r").s:Exe_Extension
        else
            let Exe = expand("%:p:r")
        endif
        if executable(Exe) && getftime(Exe) >= getftime(Obj) && getftime(Obj) >= getftime(Sou)
            redraw!
            echohl WarningMsg | echo " running..."
            if g:iswindows
                exe ":!%<.exe"
            else
                if g:isGUI
                    exe ":!gnome-terminal -x bash -c './%<; echo; echo 请按 Enter 键继续; read'"
                else
                    exe ":!clear; ./%<"
                endif
            endif
            redraw!
            echohl WarningMsg | echo " running finish"
        endif
    endif
endfunc

" -----------------------------------------------------------------------------
"  < 其它配置 >
" -----------------------------------------------------------------------------
set writebackup                             "保存文件前建立备份，保存成功后删除该备份
set nobackup                                "设置无备份文件
" set noswapfile                              "设置无临时文件
"set vb t_vb=                                "关闭提示音