ACM►搜索

UVA140 - Bandwidth （暴力dfs+排列+剪枝）

题目链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=76

题目大意

有一个图，有n个节点 (n < 8) ，讲这些节点排成一列。定义节点i的带宽为与相邻节点在排列中的最远距离，所有节点的带宽最大值为图的带宽。求将这些节点排列后，带宽最小的一种排列方式。

解题过程：

这个题写了两遍，之前一次，写了差不多一半了，不在状态，感觉又很烦，于是直接不想写了。今天网上状态很好，正好切换下了命名规范，以后还是以下划线分割好了，普通变量名和函数小写，类首字母大写。

这里把这道题放上来，是因为 get 了新知识，解答树的剪枝，当一种情况已经预知到不符合条件的时候，就不需要继续 dfs 下去了，直接舍弃，相当于剪掉了解答树的一条分支。

题目分析：

  • 先处理输入数据，这里自己写了两个辅助函数，用来处理输入数据和初始化一些变量。
  • 这里选择用矩阵储存图，之前用邻接表感觉太麻烦了，因为直接添加的话，可能有重边。
  • 然后是类似紫书上面全排列示例程序那样写的 dfs 函数，需要注意的是剪枝，和标记。
    • 当一个节点还有m个相邻的节点未分配时，如果 m >= k (当前取得的最小带宽) 时就舍弃掉这种情况，因为就算后面 m 个节点和当前节点紧挨着，那么最小带宽也是 m ，题目要求是最小字典序的所以等于 k 的情况也舍掉。
    • 另外如果一个节点的相邻节点已经分配了，如果这两个节点的距离大于等于 k 也舍弃掉，理由同上。
    • 每次尝试后，都需要把标记撤回。

      AC代码：

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
#include<bits/stdc++.h>
using namespace std;

const int MAX = 30;
bool edges[MAX][MAX];
char raw_data[1123];
int node_num, book_num[MAX];
int pos[MAX], ans[MAX], k;

void put()
{
    char result[112];

    for (int i = 0; i < MAX; i++)
    {
        if (ans[i] != -1)
            result[ans[i]] = 'A'+i;
    }

    for (int i = 0; i < node_num; i++)
        printf("%c ", result[i]);
    printf("-> %d\n", k);
}


void add_edge(int l, int r)
{
    int u = raw_data[l] - 'A';

    for (int i = l+2; i <= r; i++)
    {
        int v = raw_data[i] - 'A';
        edges[u][v] = 1;
        edges[v][u] = 1;
    }
}

void analysis()
{
    node_num = 0, k = 9999;
    memset(pos, -1, sizeof(pos));
    memset(edges, 0, sizeof(edges));
    memset(book_num, 0, sizeof(book_num));

    int len = strlen(raw_data);

    int head = 0;
    for (int i = 0; i < len; i++)
    {
        if (isalpha(raw_data[i]) && book_num[raw_data[i]-'A'] == 0)
        {
            book_num[raw_data[i]-'A'] = 1;
            node_num++;
        }
        if (i == len-1 || raw_data[i+1] == ';')
        {
            add_edge(head, i);
            head = i+2;
        }
    }
}

void solve(int cur, int cnt)
{
    if (cur == node_num)
    {
        if (cnt < k)
        {
            for (int i = 0 ; i < MAX; i++)
                ans[i] = pos[i];
            k = cnt;
            return;
        }
    }
    else
    {
        for (int i = 0; i < MAX; i++)
        {
            if (!book_num[i] || pos[i] != -1)
                continue;

            pos[i] = cur;

            int dis = 0, flag = 1;
            for (int j = 0; j < MAX; j++)
            {
                if (edges[i][j])
                {
                    if (pos[j] == -1)
                        dis++;
                    else if (cur - pos[j] >= k)
                    {
                        flag = 0;
                        break;
                    }
                    else
                        cnt = max(cnt, cur - pos[j]);
                }
            }

            if (dis >= k)
                flag = 0;

            if (flag)
                solve(cur+1, cnt);

            pos[i] = -1;
        }
    }
}



int main()
{
    while (cin >> raw_data && raw_data[0] != '#')
    {
        analysis();
        solve(0, 0);
        put();
    }
}

小结：

感觉有时候状态真的挺重要的，没状态的时候，写的很长，而且很乱。有状态的时候，写的很长，但是写的很爽，各种函数，功能分离开来，单独调试。这题看着很麻烦，写起来也很麻烦，但是这次状态很好，然后写起来顺心的话，细节也不容易出bug，写出来过了样例就一次AC了。感觉好玄学的样子。

ACM►DP

CF 766C - Mahmoud and a Message （DP+字符串）

题目链接：

http://codeforces.com/problemset/problem/766/C

题目描述：

有一个只含小写字母的字符串，输入一个26个整数，用来限制每个字母所在字符串的最大长度，在保证符合限制的前提下。

  • 输出分割字符串的方案数。
  • 输出所有方案中，最少的分割次数。
  • 输出所有方案中，最大的子串长度。

    结题过程：

一开始打算放弃掉的，英文题，题目很长，看起来又比较麻烦。
然后学长来讲了一下，感觉毕竟讲都讲了，不做下挺可惜的，倒是个好题。

刚开始示例一直过不了，第二层循环字符串长度的时候出了问题，我用j表示到那一个字符了，后来发现用j代表分隔符的位置更好。

题目分析：

  • 首先确定状态，很明显字符串处理经常用长度做状态，无后效性。

  • 接下来是确定状态转移方程：

    • 先说下第二层循环，这里j代表分隔符的所在位置，位于第j个字符的前方。
      用一个变量用来标记当前最小的长度限制，如果 i - j + 1 > limit 就跳出循环。
      最后虽然 j = -1 的时候退出循环，但是要给方案数加一，整个字符串可以不用分割。

    • 方案次数：dpNum[i] += dpNum[j-1] , 0 < j <= i.

    • 最少子串数：dpMinNum[i] = min(dpMinNum[j-1]+1, dpMinNum[i]).

    • 最长子串数，只需一直用 j 来更新最大长度 ansLen 就好了。

  • 最后注意一下初始化。

AC代码：

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
#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9+7;

int main()
{
    int n;
    scanf("%d", &n);
    char data[1123];
    int maxLen[30];
    scanf("%s", data);
    long long dpNum[1123], dpMinNum[1123], ansLen = 1;
    for (int i = 0; i < 26; i++)
        scanf("%d", maxLen+i);

    dpMinNum[0] = 1;
    dpNum[0] = 1;

    for (int i = 1; i < n; i++)
    {
        dpMinNum[i] = n;
        dpNum[i] = 0;
        int limit = n;
        int j;
        for (j = i; j >= 0; j--)
        {
            limit = min(maxLen[data[j]-'a'], limit);
            if (i-j+1 > limit)
                break;

            if (!i)
                continue;

            dpMinNum[i] =  min(dpMinNum[j-1]+1, dpMinNum[i]);
            ansLen = max(ansLen, (long long)i-j+1);
            dpNum[i] = (dpNum[i]%MOD + dpNum[j-1]%MOD)%MOD;
        }
        if (j == -1)
            dpNum[i]+=1;
    }
    printf("%lld\n%lld\n%lld\n", dpNum[n-1], ansLen, dpMinNum[n-1]);
}
ACM►数据结构►线段树

POJ 3468 - A Simple Problem with Integers（线段树区间更新+模板）

题目链接：

http://poj.org/problem?id=3468

题目描述：

给n个整数，进行m次查询或更新，查询指区间[l ,r]整数的和，更新指区间[l ,r]的整数全部增加z。

解题过程

题目不难，妥妥的模板题，卡在 pushDown 函数上两次，还不够细心。

首先是lazy标记没处理好，这个提应该是让 lazy += z， 我第一次写成了 lazy = z，导致标记直接被替换掉了，之前的更新没加上。

第二次卡在了long long上面， 全部检查了一遍， 感觉应该都用 long long 了， 最后又仔细看了一遍， 发现 pushDown 函数里面的 lazy 是和用来标记左右区间的 l, r 一起定义的，改了之后就AC了。

讲道理，这个lazy还真是有点懒，更新的时候，能不更新下一步就坚决不更新下一步，然后所有事都拖到必须要干的时候才干23333。

题目分析：

  • 首先由于线段树是完全二叉树，建树使用数组就可以。
  • 要写一个pushDown函数， 用来把lazy标记传给他的两个儿子。
  • query 和 upDate 函数，每次如果向下递归的时候，都要首先检查下当前节点是不是有lazy标记，如果有的话就传给下一级。
  • 最后有点要注意的是，本题的更新是数字的值增加，不是直接替换，同理添加或传递lazy标记的时候也要以 += 的形式， 不能直接替换掉原来的。

AC代码：

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
#include<cstdio>
using namespace std;

struct node
{
    long long lazy;
    long long value;
    int l, r;
};

node store[100000*100];
long long data[100000*100];

void build(int l, int r, int root)
{
    store[root].l = l, store[root].r = r;
    store[root].lazy = 0;

    if (l == r)
    {
        store[root].value = data[l];
        return;
    }

    int m = (l + r) / 2;

    build(l, m, root*2+1);
    build(m+1, r, root*2+2);

    store[root].value = store[root*2+1].value + store[root*2+2].value;
    return;
}

void pushDown(int root)
{
    if (store[root].lazy != 0)
    {
        long long l, r;
        long long z;
        z = store[root].lazy;

        store[root*2+1].lazy += z;
        l = store[root*2+1].l, r = store[root*2+1].r;
        store[root*2+1].value += (r - l + 1) * z;

        store[root*2+2].lazy += z;
        l = store[root*2+2].l, r = store[root*2+2].r;
        store[root*2+2].value += (r - l + 1) * z;

        store[root].lazy = 0;
    }
    return;
}

void upDate(int l, int r, int root, long long z)
{
    int nl = store[root].l, nr = store[root].r;

    if (l <= nl && r >= nr)
    {
        store[root].lazy += z;
        store[root].value += (nr - nl + 1) * z;
        return;
    }

    pushDown(root);

    int m = (nl + nr) / 2;

    if (l <= m)
        upDate(l, r, root*2+1, z);
    if (r > m)
        upDate(l, r, root*2+2, z);

    store[root].value = store[root*2+1].value + store[root*2+2].value;
    return;
}

long long query(int l, int r, int root)
{
    int nl = store[root].l, nr = store[root].r;

    if (l <= nl && r >= nr)
        return store[root].value;

    pushDown(root);
    int m = (nl + nr) / 2;

    long long sum = 0;
    if (l <= m)
        sum += query(l, r, root*2+1);
    if (r > m)
        sum += query(l, r, root*2+2);

    return sum;
}

int main()
{
//    freopen("in", "r", stdin);
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++)
        scanf("%lld", data+i);

    build(0, n-1, 0);

    char mode[11];
    int l, r;
    long long z;
    while (q--)
    {
        scanf("%s %d %d", mode, &l, &r);
        if (mode[0] == 'Q')
            printf("%lld\n", query(l-1, r-1, 0));
        else if (mode[0] == 'C')
        {
            scanf("%lld", &z);
            upDate(l-1, r-1, 0, z);
        }
    }
}
ACM►数据结构

Uva 806 - Spatial Structures（四分树+模板）

题目链接：

https://vjudge.net/problem/24840/origin

题目描述：

黑白图像有好几种表示方式，可以用点阵或者路径，路径需要把图像转化成四叉树。
题目要求就是实现两种表示方式的转换。

解题过程：

题目不难，注意细节就好，直接的judge函数错了好几次，以后写的严谨点，不拿两个相邻的方块比较了，立一个flag再和flag比较。
没注意输出格式，pe了好几次，12个数字为一行。

题目分析：

  • 转化为路径，首先以递归的方式建树，每次搜索范围缩小为原来的1/4。
    找到黑块的时候，把搜索时记录下来的路径转化成十进制，储存。
    最后排序输出，12个为一行。
  • 转化为图像，首先把十进制转化为路径，然后递归式的把图像画出来就好了。

AC代码：

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
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

struct node
{
    int status;
    node *one, *two, *three, *four;
    node():status(-1),one(NULL),two(NULL),three(NULL),four(NULL){}
};

vector<int> ans;
int num;
string drawPath;
char data[112][112];

bool judge(int l, int r, int u, int d)
{
    int flag = data[u][l];
    for (int i = u; i < d; i++)
        for (int j = l; j < r; j++)
            if (data[i][j] != flag)
                return false;
    return true;
}

void trns(int num)
{
    drawPath = "";
    if (num == 0)
    {
        drawPath += '0';
        return;
    }

    while (num)
    {
        string temp = "";
        temp += (char) (num%5 + '0');
        drawPath = temp + drawPath;
        num /= 5;
    }

//    cout << drawPath << endl;
}

void add(string path)
{
    int len = path.size(), num = 0;
    for (int i = 0; i < len; i++)
        num += (path[i] - '0') * pow(5, i);

    ans.push_back(num);
}

void solve(int l, int r, int u, int d, string path)
{

    if (judge(l, r, u, d))
    {
        if (data[u][l] == '1')
        {
            add(path);
            num++;
        }
        return;
    }

    solve(l, (l+r)/2, u, (u+d)/2, path+'1');
    solve((l+r)/2, r, u, (u+d)/2, path+'2');
    solve(l, (l+r)/2, (u+d)/2, d, path+'3');
    solve((l+r)/2, r, (u+d)/2, d, path+'4');
}

void draw(int l, int r, int u, int d, int p)
{
    if (p == -1 || drawPath[p] == '0')
    {
        for (int i = u; i < d; i++)
            for (int j = l; j < r; j++)
                data[i][j] = '*';
        return;
    }
//    printf("%c\n", drawPath[p]);
    if (drawPath[p] == '1')
        draw(l, (l+r)/2, u, (u+d)/2, p-1);
    if (drawPath[p] == '2')
        draw((l+r)/2, r, u, (u+d)/2, p-1);
    if (drawPath[p] == '3')
        draw(l, (l+r)/2, (u+d)/2, d, p-1);
    if (drawPath[p] == '4')
        draw((l+r)/2, r, (u+d)/2, d, p-1);
}

int main()
{
//    freopen("in", "r", stdin);
//    freopen("out", "w", stdout);
    int n, testCase = 0;
    while (~scanf("%d", &n) && n)
    {
        if (testCase)
            putchar('\n');
        printf("Image %d\n", ++testCase);
        num = 0;
        if (n > 0)
        {
            ans.clear();
            for (int i = 0; i < n; i++)
                scanf("%s", data+i);
            solve(0, n, 0, n, "");
            sort(ans.begin(), ans.end());
            for (int i = 0; i < ans.size(); i++)
            {
                printf("%d", ans[i]);
                if ((i+1) % 12 == 0)
                    printf("\n");
                else if (i != ans.size()-1)
                    putchar(' ');
            }

            if (num && ans.size()%12 != 0)
                putchar('\n');
            printf("Total number of black nodes = %d\n", num);
        }
        else
        {
            memset(data, '.', sizeof(data));
            n *= -1;
            int t;
            while (cin >> t && t != -1)
            {
                trns(t);
                draw(0, n, 0, n, drawPath.size()-1);
            }


            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    putchar(data[i][j]);
                putchar('\n');
            }
        }
    }
}
ACM►数据结构

UVa 12166 - Equilibrium Mobile（二叉树+递归处理括号匹配+模板）

题目链接

题目

Mark下大神的博客：http://morris821028.github.io/
简直太强了。
题解链接：http://morris821028.github.io/2014/10/03/oj/uva/uva-12166/#Problem

题目大意：

給一個天平表達式，請問至少要調整幾個權重才能使之平衡。（直接复制来的）

解题过程：

自己大概废了一个小时想一个特麻烦的解法，首先想的是自顶向下的平衡，然后dfs下去还是从必须从叶节点开始平衡。

于是想自底向上平衡，每次把可以平衡成的质量和调整的次数传给上一层，比如调整[1,2]，给上一层传递三个状态：调整2到1，质量变为1，调整1次；调整1变为2，质量变为2，调整一次；两个都一起调整到一个任意的数，调整两次。
显然这样需要给每个节点开辟一个空间储存状态，妥妥爆内存。

想了一个小时只是这个结果，于是去百度了下，看到：
那麼可以得知道假使一個權重不改，最後的天平重量為何。
假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。

于是想到建树，统计下叶子节点所在的层数，然后拿每个叶子节点跑一边，结果是O(n^2)。

后来看到这个博客确实是惊艳到了……

题目分析：

这里分析下下面的代码好了。

这里map的使用和遍历可以做模板了，要是我的话，就桶排然后遍历一遍了…

这个递归写的真是太强了！！

然后就是sscanf的用法，可以拿来做模板，要我的话，专门写一个字符串转整数的函数了，麻烦的要死。

AC代码：

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
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;

char exp[1123456];
map<long long, int> R;

void dfs(int l, int r, int dep)
{
    if (exp[l] == '[')
    {
        int p = 0;
        for (int i = l + 1; i <= r - 1; i++)
        {
            if (exp[i] == '[')
                p++;
            if (exp[i] == ']')
                p--;
            if (p == 0 && exp[i] == ',')
            {
                dfs(l+1, i-1, dep+1);
                dfs(i+1, r-1, dep+1);
            }
        }
    }
    else
    {
        int w;
        exp[r+1] = '\0';
        sscanf(exp+l, "%d", &w);
        R[(long long)w<<dep]++;
    }
}

int main()
{
    int testcase;
    scanf("%d", &testcase);
    while (testcase--)
    {
        scanf("%s", exp);
        R.clear();
        dfs(0,strlen(exp) - 1, 0);
        int sum = 0, mx = 0;
        for (map<long long, int>::iterator it = R.begin(); it != R.end(); it++)
            sum += it->second, mx = max(mx, it->second);
        printf("%d\n", sum - mx);
    }
    return 0;
}
ACM►模拟

UVA506 System Dependencies（模拟）

题目链接：

https://vjudge.net/problem/31990/origin

题目大意：

模拟安装软件，分显式好隐式安装两种情况。安装一个软件的时候，指明安装的就是显式安装。
比如：

INSTALL A

这里A是显示安装，如果A必须要B和C软件的支持的话，顺便安装上B和C，这里B和C就是隐式安装上的。

然后是删除软件，删除的时候以递归的形式删除，先删除指明安装的软件，然后删除这个软件的支持软件，但是如果支持软件是显式安装上的话，就不删除了。

INSTALL B
INSTALL A
REMOVE A

这里的B就不会被删除，安装A时同时安装的C会被删除掉。此外如果A的支持软件是另一个软件的支持软件的话，也不会被删除掉。

解题过程：

题目本身不难，有是一个复杂的模拟题，书上给了些提示和代码，对比着，写出来不难。
需要映射下软件的名字，这里用到了之前 UVA-12096 里面的映射方法。

题目分析：

先把字符串名称用MAP映射成整数，容易处理些。
安装和删除的函数，注意递归处理。
把depend的输入分离的时候使用stringstream处理。

题目不难，不过用到了好多有用的方法，这里Mark下。

AC代码：

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
#include<bits/stdc++.h>
using namespace std;

const int MAX = 112345;

map<string, int> nameList;
vector<string> getName, nameTable;
string str;
vector<int> depend1[MAX], depend2[MAX];
int status[MAX];
string blank = "   ";

int ID(string name)
{
    if (nameList.count(name))
        return nameList[name];

    getName.push_back(name);
    return nameList[name] = getName.size()-1;
}

void depend()
{
    stringstream ss;
    string item_name;
    int item1, item2;
    ss << str;
    ss >> item_name;

    ss >> item_name;
    item1 = ID(item_name);

    while (ss >> item_name)
    {
        item2 = ID(item_name);
        depend1[item1].push_back(item2);
        depend2[item2].push_back(item1);
    }
}

void install(int item, bool topLevel)
{
    if (!status[item])
    {
        for (int i = 0; i < depend1[item].size(); i++)
            install(depend1[item][i], false);

        string item_name = getName[item];
        cout << blank << "Installing " << item_name << endl;
        nameTable.push_back(item_name);
        status[item] = topLevel? 1:2;
    }
    else if (topLevel)
        cout << blank << getName[item] << " is already installed." << endl;
}

void list_()
{
    for (int i = 0; i < nameTable.size(); i++)
        cout << blank << nameTable[i] << endl;
}

bool needed(int item)
{
    for (int i = 0; i < depend2[item].size(); i++)
        if (status[depend2[item][i]])
            return true;
    return false;
}

void remove_(int item, bool topLevel)
{
    string item_name = getName[item];
    if (status[item] == 0 && topLevel)
    {
        cout << blank << item_name << " is not installed." << endl;
        return;
    }

    if (!needed(item) && (status[item] == 2 || topLevel))
    {
        status[item] = 0;
        for (int i = 0; i < nameTable.size(); i++)
        {
            if (nameTable[i] == item_name)
            {
                nameTable.erase(nameTable.begin()+i);
                break;
            }
        }
        cout << blank << "Removing " << item_name << endl;

        for (int i = 0; i < depend1[item].size(); i++)
            remove_(depend1[item][i], false);
    }
    else if (topLevel)
        cout << blank << item_name << " is still needed." << endl;
}

int main()
{
//    freopen("in","r",stdin);
    while(getline(cin, str))
    {
        cout << str << endl;
        if (str[0] == 'D')
        {
            depend();
        }

        if (str[0] == 'I')
        {
            stringstream ss;
            ss << str;
            string item_name;
            ss >> item_name;
            ss >> item_name;

            int item = ID(item_name);

            install(item, true);
        }

        if (str[0] == 'E')
        {
            break;
        }

        if (str[0] == 'R')
        {
            stringstream ss;
            ss << str;
            string item_name;
            ss >> item_name;
            ss >> item_name;

            int item = ID(item_name);

            remove_(item, true);
        }

        if (str[0] == 'L')
        {
            list_();
        }
    }
}

ShadowSocks配置（Linux）

参考教程：

强烈推荐教程教程！！！

服务端配置：

Linux 直接 ssh 服务器：

ssh [ 用户名]@[IP]

*例如：

1
ssh root@45.76.206.109

安装ShadowSocks：
使用Python原版，Ubuntu下直接输入：

1
2
apt install python-setuptools && easy_install pip
pip install shadowsocks

用来安装Python的组件和shadowsocks。

ShadowSocks的配置：
创建配置文件：

1
vim /etc/shadowsocks.json
1
2
3
4
5
6
7
8
9
10
{
    "server":"your_server_ip",
    "server_port":8388,
    "local_address": "127.0.0.1",
    "local_port":1080,
    "password":"auooo.com",
    "timeout":300,
    "method":"aes-256-cfb",
    "fast_open": false
}

参数说明：

名称 说明
server 填入你的服务器 IP ，即当前操作的 VPS 的 IP 地址，必须修改
server_port 服务器端口，可以根据实际需要修改，或者保持默认
local_address 本地监听地址，建议保持默认
local_port 本地端口，这个参数一般保持默认即可
password 用来加密的密码，可以根据实际需要修改
timeout 单位秒，一般保持默认即可
method 默认的是”aes-256-cfb”，一般保持默认即可
fast_open 使用TCP_FASTOPEN, 参数选项true / false，一般保持默认即可
workers worker的数量, 在 Unix/Linux 上有效，一般不用加此项

启动SS服务：

1
nohup ssserver -c shadowsocks.json start &

#客户端配置：
使用ShadowSocks-qt：
官网下载&Wiki

配置客户端：
按照服务器的配置文件配置即可。

爬虫&数据处理

Python爬取SDUTOJ比赛提交代码及批量提交（爬虫（伪)）

需求：

  • 把自己之前在contest里面的代码提取出来。
  • 实现批量提交contest和problem里面的题目。

过程：

总共大概花了4个小时，一晚上，一个类一个文件的方法写起来真的爽，一晚上没停住手。
自己首先写的是下载器，首先明确需求。

  • 可以模拟登陆。
  • 可以post请求。
  • 可以下载网页。
  • 为了省事，把提交题目的功能也整合里面了。

代码如下，实现起来没啥困难，毕竟已经是轻车熟路了。

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
# coding:utf8
import  urllib2
import cookielib
import urllib

class Down(object):

    def __init__(self):
        #初始化常用网址
        self.login_url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Login/login'
        self.home_url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home'
        self.submit_url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/1110.html'

        #安装cookie处理
        cj = cookielib.CookieJar()
        cookie_support = urllib2.HTTPCookieProcessor(cj)
        opener = urllib2.build_opener(cookie_support)
        urllib2.install_opener(opener)

        #初始化cookie
        home_temp = urllib2.urlopen(self.home_url)

        self.headers = {
            'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/54.0.2840.71 Safari/537.36',
            'Referer': 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Login/login',
            'Host': 'acm.sdut.edu.cn'}

        self.login()

    def post(self, url, post_data = None):
        #下载网页和POST请求
        if post_data is None:
            request = urllib2.Request(url, headers = self.headers)
            response = urllib2.urlopen(request)
            return response.read()
        else:
            post_data = urllib.urlencode(post_data)
            request = urllib2.Request(url, post_data, self.headers)
            response = urllib2.urlopen(request)
            return  response

    def login(self, user = 'Fish', password = '123456'):
        #登陆信息
        post_data = {'user_name': user, 'password':password }
        self.post(self.login_url, post_data)

    def submit(self, pid, code, language = 'g++', cid = None):
        if cid == None:
            post_data = {'pid': pid, 'code': code, 'lang' : language}
            self.post(self.submit_url, post_data)


if __name__ == '__main__':
    test = Down()
    print test.post('http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/1110.html')

然后是网页分析器，这里我由内到外的写的，首先需求是给定一个贴着代码的网页，把代码爬下来。
下一步需求是给定一个status，把AC的代码记录的链接爬下来发给上一步的爬取代码的函数。
最后是给定一个比赛的cid，找到ranklist链接并且找到自己的status页面发给上一步实现的处理。

这样做的好处就是每一步都可以单独调试，每一个函数写起来，它需要调用的函数已经写完调试好了。

这里麻烦点的就是status页面的处理，最后返回数据的时候我按（代码，题号）的二元组构成的列表返回的。

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
# coding:utf8
from bs4 import BeautifulSoup
import html5lib
import Down
import time

class ReadCode(object):

    def __init__(self):
        self.data = []
        self.downer = Down.Down()

    def read_code(self, html):
        soup = BeautifulSoup(html, "html5lib")
        time.sleep(0.01)
        return soup.find('pre').text

    def read_status(self, html):
        soup = BeautifulSoup(html, "html5lib")
        table = soup.find_all('tr')

        tdata = []

        #读取每一个提交信息
        for tr in table:
            try:
                tr = tr.find_all('td')
                if tr[3].text == "Accepted" and (tr[6].text == "g++" or tr[6].text == "gcc"):
                    temp =  'http://acm.sdut.edu.cn/' + tr[6].a['href'], tr[2].a['href'][-9:-5]
                    print temp[1]
                    tdata.append(temp)
            except:
                pass

        #读取代码
        for temp in tdata:
            html = self.downer.post(temp[0])
            ans = self.read_code(html)
            self.data.append((ans,temp[1]))

        #读取下一页
        try:
            url = 'http://acm.sdut.edu.cn/' + soup.find(class_ = 'next')['href']
            html = self.downer.post(url)
            self.read_status(html)
        except:
            pass

    def read_rank(self, cid):
        html = self.downer.post('http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestranklist/cid/'+str(cid))
        soup = BeautifulSoup(html, "html5lib")

        #找到个人的status页面并读取
        try:
            print cid
            url = 'http://acm.sdut.edu.cn' + soup.find(text = "jk160801李东庆").parent.parent.find_all('td')[2].a['href']
            html = self.downer.post(url)
            self.read_status(html)
        except:
            pass

if __name__ == '__main__':
    test = ReadCode()
    print test.data

最后是一个Main调度一下，顺便实现了读写到文件的功能。
（这里有个玄学的小细节，代码中也备注了）

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
# coding:utf8
import Down
import ReadCode
import  urllib2
import cookielib
import urllib

#改下输出流的编码？玄学
import sys
reload(sys)
sys.setdefaultencoding( "utf-8" )

class Main(object):

    def __init__(self):
        self.data = []
        self.reader = ReadCode.ReadCode()
        self.cid = 0

    def read_contest(self, cid):
        self.cid = cid
        self.reader.read_rank(cid)
        self.data += self.reader.data
        self.reader.data = []

    def output(self):
        for temp in self.data:
            f = open('code/'+temp[1], 'w')
            f.write(temp[0])
            print self.cid, temp[1]
        self.data = []

if __name__ == '__main__':
    oj = Main()
    for cid in range (1828, 1976):
        oj.read_contest(cid)
        oj.output()

最后实现批量提交的时候自己又写了一下提交的函数，之前下载器里面的太弱了，当然这里也调用了下载器，比赛提交的代码的时候是暴力了点…
（当然这个提交器是利用了之前爬下来的代码）

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
# coding:utf8
import Down
import time

class Submit(object):
    def __init__(self):
        self.downer = Down.Down()

    def submit_problem(self, pid ,url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/1000.html', cid = 233):
        try:
            f = open('code/'+str(pid), "r")
            code = f.read()
            post_data = {'pid':pid, 'lang':'g++', 'code':code}
            self.downer.post(url, post_data)
            post_data = {'pid': pid, 'lang': 'g++', 'code': code, 'cid':cid}
            self.downer.post(url, post_data)

            print cid,pid
            time.sleep(0.01)
        except:
            pass

    def submit_contest(self, cid):
        url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/' + str(cid) + '/pid/'
        for pid in range(1000, 3764):
            try:
                self.submit_problem(pid, url+ str(pid) + '.html', cid = cid)
            except:
                pass

if __name__ == '__main__':
    submiter = Submit()
    for cid in range(1875, 1881):
        submiter.submit_contest(cid)

#效果：
这里写图片描述这里写图片描述

大概就是爬下来了200+个自己的代码，然后给小号刷了一下，一键AC（笑

爬虫&数据处理

Python爬虫基础细节（urllib+cookielib+BeautifulSoup）

内容大概：

  • 简单介绍python如何下载网页
  • 发送post请求
  • urllib/2模块的方法应用
  • 分析网页的post请求
  • cookie处理
  • 利用BS分析网页

（由于并没有系统的学过http之类的，可能会有错误，希望大家可以指出）

urllib&cookielib：

urllib模块只用到了urlencode方法，目的是将原来的字典post数据转化成特定的字符串格式，只用到了下面的一行代码。

1
post_data = urllib.urlencode(post_data)

urllib2用到的就多了，首先模拟登陆的话需要用到cookie处理。
主要用到以下代码，固定格式，拿来用就好了。

1
2
3
4
5
#安装cookie处理
cj = cookielib.CookieJar()
cookie_support = urllib2.HTTPCookieProcessor(cj)
opener = urllib2.build_opener(cookie_support)
urllib2.install_opener(opener)

然后设置一下自己的hears，目的是把自己伪装成一个浏览器。
导入这里的各种参数可以设置成别的，这里只是例子，具体改成什么可以打开浏览器的开发者模式看一下。

1
2
3
4
self.headers = {
            'User-Agent': 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/54.0.2840.71 Safari/537.36',
            'Referer': 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Login/login',
            'Host': 'acm.sdut.edu.cn'}

这里写图片描述

然后设置打开网页时需要的request，需要用到url，post请求的数据，headers，当然这一步也可以跳过，单纯下载网页的话只用url就可以了。

1
request = urllib2.Request(url, post_data, headers)

接下来就是重要的打开网页，用到了urllib2的urlopen方法，参数可以是只是网页，也可以是一个之前说到的request。

1
2
3
#以下两种都可以
response = urllib2.urlopen(request)
response = urllib2.urlopen(url)

最后一点是response对象使用read方法就可以得到下载的html文本了。

1
response.read()

post请求的分析：

这里拿登陆OJ来做下示范。
首先打开登陆页面自己打开F12登陆一次。
然后注意箭头上指的两处，点下login后，右边的Request URL就是接下来将要用python访问的页面。
这里写图片描述

然后继续往下滑，下面箭头的部分就是自己提交的数据，也是接下来post_data里要放的内容。
这里写图片描述

于是登陆的过程我就可以这样写了（假设安装了cookie处理，定义了headers）

1
2
3
4
url = 'http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Login/login'
post_data = {'user_name': user, 'password':password }
request = urllib2.Request(url, post_data, headers)
response = urllib2.urlopen(request)

BeautifulSoup：

强烈推荐官方文档，有中文！有中文！！有中文！！！
https://www.crummy.com/software/BeautifulSoup/bs4/doc/index.zh.html

首先明确一点，BS就是分析html的文本，按照一种树形的结构，每一个节点都可以拿来当一个bs对象使用。
首先创建一个bs对象先。
（这里用了html5lib解析器，具体可以百度去下载安装，另外python装好pip的话安装第三方库很方便的。当然这里也可以不要第二个参数，这样的话就会默认使用python自带的）

1
soup = BeautifulSoup(html, "html5lib")

然后是bs对象的find_all和find方法，find方法返回的是第一个匹配到的节点（bs对象），find_all则是返回一个列表（包含bs对象的列表），里面包含所有匹配的节点，如果没用匹配的节点的话，分别是None和[]（空列表）。
他们都有name, class_, text参数（其实还有很多，这里我只用了这些基本的）
分别代表是节点名字，节点的class内容，和节点的文本。
下面只是一个示例，当然可以多个参数放在一起。

1
2
3
soup.find(class_ = 'next')
soup.find_all('tr')
soup.find(text = "Fish")

bs对象还可以直接访问他的节点的属性，父节点和子节点，当前这个节点的文本。
(假设a是他的子节点的话)

1
2
3
4
soup['href']
soup.parent
soup.a
soup.text

介绍了这些，然后以下就是一些综合应用的示例了，总之BS是非常好用，刚开始我以为得用到正则表达式…

1
2
3
4
5
6
7
8
#从ranklist找到自己的status
url = 'http://acm.sdut.edu.cn' + soup.find(text = "Fish").parent.parent.find_all('td')[2].a['href']
#找到页面的下一页的超链接
url = 'http://acm.sdut.edu.cn/' + soup.find(class_ = 'next')['href']
#找到每一个AC记录的代码链接
tr = tr.find_all('td')
                if tr[3].text == "Accepted" and (tr[6].text == "g++" or tr[6].text == "gcc"):
                    temp =  'http://acm.sdut.edu.cn/' + tr[6].a['href'], tr[2].a['href'][-9:-5]
ACM►搜索

SDUT Problem_5 二哥的狗（水题）

题目链接：

二哥的狗
（在重现比赛里，可能随时消失，题目也找不到，这里把题目描述发一下好了）

第一学期已经接近尾声了，通往寒假的大门由八位Exam把守。
作为Exam大家族里的二哥，当然要比之前那些Exam们要凶恶的多。
二哥养了一群恶犬，如果你能战胜他们，二哥就放你过去。
当然不是让你赤手空搏，二哥也给你准备了同样数目的几只恶犬。
已知你的每只恶犬只能攻击二哥对应位置的恶犬，
当你的某只恶犬进行攻击时，会同时遭受敌方和其左右两只恶犬的攻击，如果某侧没有恶犬或者已被消灭，则该侧不会对你的恶犬造成伤害。
已知每只斗犬的攻击力，如果你的当前进行攻击的恶犬攻击力大于等于对方及左右两侧恶犬造成的总攻击力，就可以消灭掉敌方对应的那一只恶犬，否则不能消灭对方。

题目大意：

就是输入来个等长的数组，然后把两个数组相同位置的数比较，假设输入a, b两个数组，如果b[i] >= a[i-1]+a[i]+a[i+1]，那么第一个数组的a[i]就会被攻击掉，不再提供战斗力了。

解题过程：

  • 做这个题的曲线也是比较曲折的，花了将近半小时，如果考试的时候就GG了。
  • 刚开始一个思路时，从两部逐渐比较，比如定义head=0，tail定义尾部，然后先比较head，然后head++，再比较tail，tail–。
  • 这么想也是因为边界只有两条恶犬，赢得概率大点23333.
  • 然后WA了。
  • 这里写图片描述
  • 显然是不对的，随便可以出一组数据就GG了，比如
    • 1 2 1
    • 1 4 1
  • 如果这样先从两边往中间凑的话，两边都无法操纵就GG了，当初是为了O(n)的结果来的。
  • 然后就开始暴力两个for遍历就好了，显然是可以的，不过不知道我那里写错了，最后TLE，不过这样不太优雅~正好突然想起来一个思路，就是接下来题目分析上说的了，虽然TLE了一次，是因为已经攻击的狗又攻击了一次，处理一下就AC了。

题目分析：

  • 首先一个循环把每个恶犬都遍历一遍。
  • 每条狗都尝试去进攻一下。
    • 如果攻击成功的话就去让这条狗的左右两条狗去攻击下，因为一条狗攻击成功的话，那么它左右两条狗攻击成功所需要的攻击力就会刷新（减少）了。
    • 如果不成功的话继续尝试下一条狗。
  • 最后结束上面的尝试后，再来一个for检查下二哥的狗是不是全部被咬死了就可以了。
  • 这样虽然最差的情况是O（n^2+n），但是感觉平均起来要好不少。

AC代码：

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
#include<iostream>
#include<cstring>
using namespace std;

int n;
int data1[11234], data2[11234];

void attack(int i)
{
    if (data1[i] == 0)
        return;

    int temp = data1[i]+data1[i+1]+data1[i-1];
    if (data2[i] >= temp && temp)
    {
        data1[i] = 0;
        if (i-1 >= 1)
            attack(i-1);
        if (i+1 <= n)
            attack(i+1);
    }
}

int judge()
{
    for (int i = 1; i <= n; i++)
        attack(i);

    for (int i = 0; i <= n; i++)
        if (data1[i])
            return 0;

    return 1;
}

int main()
{
    while (cin >> n)
    {
        memset(data1,0,sizeof(data1));
        memset(data2,0,sizeof(data2));

        for (int i = 1; i <= n; i++)
            cin >> data1[i];
        for (int i = 1; i <= n; i++)
            cin >> data2[i];

        if (judge())
            cout << "Fighting!!!" << endl;
        else
            cout << "QAQ!!!" << endl;
    }
}