由于重装系统比较频繁，每次都使用安装包安装 MySQL 的话比较麻烦，看到 MySQL 官网提供了 MySQL 的 ZIP Archive，查了下官方文档，这里记录一下使用 ZIP 包安装 MySQL 的方法。

将本地项目添加 Github repo 后可以方便的在其它设备继续进行项目的开发，也可以方便的与其他人分享自己的项目，我这里记录一下给本地项目添加 Github repo 的方法。

分享在 Ubuntu 18.04 VPS 上搭建 Shadowsocks Server 的方法。

将 Blog 成功搭到 Github 后就要考虑一些配置问题了，需要更加美观的主题，换了电脑或者重装系统后还需要快速的从以前的配置恢复，下面就解决这些问题。

此博客是由 Github Pages 和 Hexo 搭建的，分享以下我的使用实践。

一. 安装 Hexo

1. 安装 Node.js 和 Git

必须安装了 Node.js 和 Git 才能安装使用 Hexo，按照 Hexo 官方提供的教程安装即可，Windows 用户推荐使用安装包安装，安装过程勾选添加到 PATH。

Github 提供了 GitHub pages 绑定到域名的方法，刚好之前申请了一个 freenom 的免费域名，用自己的域名有时候会方便一些，下面是方法。

1. Ping

ping 你的 Github Pages 对应的服务器 IP

1

ping csJd.github.io

听说最近出了个 Magisk 框架，可以在不修改 /system 下实现 root 和 xposed ，这样理论上装了 xposed 框架还能 OTA ，听起来真不错。就拿出了我的 2s 折腾了下，发现真的可以，这里分享一下过程。
我是卡刷官方倒数第二个稳定版（V8.1.2.0.LXACNDI），清空全部数据再进行以下操作的，不保证其他情况不会出现问题，请自行尝试。

题意 给你一个环形串 输出其最小表示法的首字母位置 最大表示法的首字母位置 以及和对应位置等价位置的个数

最小表示法指一个循环串以某一位开始时对应的串的字典序最小 这个串就是该循环串的最小表示法

先看一下求字符串最小表示法的过程 可以看2003年国家集训队论文集中周源的论文

令 p 表示字符串 s 的最小表示法的下标, l = strlen(s) s = s + s

当i <= p && j <= p && i ！= j时 令 k (0 <= k < l) 为最小使得 s[i + k] != s[j + k] 的整数

k 存在时 若 s[i + k] > s[j + k]

那么对于任意的**x (i <= x <= i + k)**都是不可能等于p的因为对于这些 x 都有对应的 y (j <= y <= j + k) 使得**s[x, i + k) == s[y, j + k) && s[i + k] > s[j + k]**那么以 y 为起始位置的串肯定是小于以 x 为起始位置的串的 那么就可以令 i = i + k + 1继续这个过程了 s[i + k] < s[j + k] 时同理可令 j = j + k + 1 注意若前进后i == j 需要令 j = j + 1 因为要保证i != j

重复上面的过程直到 i >= l || j >= l || k不存在 此时 i, j 中小的那个数就是答案了 因为小的那个数前后所有都已经被确定不可能为 p

开始时不妨令i = 0, j = 1 p > 0 时是符合上面的条件的 p == 0 时可以发现 i 会保持0不变 j 一直前进直到 j > l 或 k 不存在

那么令 i = 0, j = 1 然后通过上面的过程就能得到最小表示法对应的位置了 同理也可以得到最大表示法对应的位置

至于求等价位置的个数 只要知道这个串是某个串循环了多少次就行了 通过kmp的l - next[l]表示最小循环节的长度就可以求出来

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

#include <bits/stdc++.h>
using namespace std;
const int N = 2000005;
int nex[N], l;
char s[N];

void getNext()
{
    int i = 0, j = nex[0] = -1;
    while(i < l)
    {
        if(j == -1 || s[i] == s[j])
            nex[++i] = ++j;
        else j = nex[j];
    }
}

int getPos(bool op) //op = 0最小表示法  op = 1 最大表示法
{
    strncpy(s + l, s, l);
    int i = 0, j = 1;
    while(i < l && j < l)
    {
        int k = 0;
        while(k < l && s[i + k] == s[j + k]) ++k;
        if(k >= l) break;
        if((s[i + k] > s[j + k]) ^ op) i += k + 1;
        else j += k + 1;
        if(i == j) ++j;  //保证i != j
    }
    return i < j ? i : j;
}

int main()
{
    while(~scanf("%s", s))
    {
        l = strlen(s);
        getNext();
        int rl = l - nex[l], t = l % rl ? 1 : l / rl;
        int p0 = getPos(0) + 1, p1 = getPos(1) + 1;
        printf("%d %d %d %d\n", p0, t, p1, t);
    }
    return 0;
}
//Last modified :  2015-10-06 09:30 CST

String Problem

Problem Description

Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings:
String Rank
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7
and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once.
Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Input

Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.
Output

Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.
Sample Input

abcder aaaaaa ababab
Sample Output

1 1 6 1 1 6 1 6 1 3 2 3
Author

WhereIsHeroFrom

题意 输出n个串的字典序最小的最长公共子串

可以枚举第一个串的所有子串 然后对每个串kmp匹配 比较复杂 而且慢 发现和HDU2846（求模式串在n个串中出现的次数）有类似之处 都可以用Trie来处理 一个串的子串肯定是其某个后缀的前缀 我们把第一个串的所有后缀都插入到Trie中 最长公共子串肯定是在这个Trie里面的 因为它肯定是第一个串的子串 在插入后面的串的后缀时 可以发现

1. 对于在第一个串中没有的节点是可以直接break的 在第一个串中都没有怎么会是公共的呢

2. 当前前缀在前面i个串中出现的次数小于i 那么也可以break了 因为肯定有某些串已经不包含这个前缀了

所以我们后面的插入只用基于第一次插入的Trie就行了 插入最后一个串的后缀时取插入长度最长的串就是答案了

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

#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int trie[N][26], cnt[N], L;
char s[N];

void initTrie()
{
    L = 1;
    memset(cnt, 0, sizeof(cnt));
    memset(trie, 0, sizeof(trie));
}

int insertTrie(char s[], int id)
{
    int r = 0, i = 0, len = 0, j;
    while(s[i])
    {
        j = s[i++] - 'a';
        if(!trie[r][j])
        {
            if(id == 1) trie[r][j] = L++;
            else break;  //在第一个串中都没有的就不用管了
        }

        r = trie[r][j];
        if(cnt[r] + 1 >= id) cnt[r] = id;
        else break;  //当前前缀出现过的次数小于id说明该前缀不是前面某些串的子串 不用再往前看
        ++len;   //当前前缀的长度
    }
    return len;
}

int main()
{
    int n;
    while(scanf("%d", &n), n)
    {
        initTrie(); //初始化Trie
        int len = 0;
        char ans[N] = "IDENTITY LOST", t[N];

        for(int i = 1; i <= n; ++i)
        {
            scanf("%s", s);
            for(int j = 0; s[j]; ++j)
            {
                int k = insertTrie(s + j, i);
                if(!k || i < n) continue; //插入最后一一个串时才需要处理

                strncpy(t, s + j, k), t[k] = 0;
                if(k > len || (k == len && strcmp(ans, t) > 0))
                    strcpy(ans, t), len = k;
            }
        }

        puts(ans);
    }
    return 0;
}
//Last modified :  2015-10-05 15:50 CST

Corporate Identity

Problem Description

Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Building Masters (IBM), which has recently asked ACM for a help with their new identity. IBM do not want to change their existing logos and trademarks completely, because their customers are used to the old ones. Therefore, ACM will only change existing trademarks instead of creating new ones.
After several other proposals, it was decided to take all existing trademarks and find the longest common sequence of letters that is contained in all of them. This sequence will be graphically emphasized to form a new logo. Then, the old trademarks may still be used while showing the new identity.
Your task is to find such a sequence.
Input

The input contains several tasks. Each task begins with a line containing a positive integer N, the number of trademarks (2 ≤ N ≤ 4000). The number is followed by N lines, each containing one trademark. Trademarks will be composed only from lowercase letters, the length of each trademark will be at least 1 and at most 200 characters.
After the last trademark, the next task begins. The last task is followed by a line containing zero.
Output

For each task, output a single line containing the longest string contained as a substring in all trademarks. If there are several strings of the same length, print the one that is lexicographically smallest. If there is no such non-empty string, output the words “IDENTITY LOST” instead.
Sample Input

3 aabbaabb abbababb bbbbbabb 2 xyz abc 0
Sample Output

abb IDENTITY LOST

题意 有n个作业要做 给你每个作业的最后期限 和做完这个作业需要的时间 作业每超过最后期限一天就会扣一分 只能把一个作业做完了再做另一个作业 问做完所有作业至少扣多少分

作业最多只有15个 看到这个数字容易想到是状态压缩 dp[i]表示i对应状态的最小扣分 i转换为二进制后为1的位表明该位对应的作业已经做了 为0的位没做 那么dp[i] = min{dp[k] + cost |k为将某一位变成1后等于 i 的状态}

由于要打印路径 所有还需要记录每个状态的上一个状态pre

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

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 16, M = 1 << N;
int d[N], c[N], n;
int dp[M], pre[M], t[M];
char s[N][105];

void print(int k)
{
    if(k == 0) return;
    print(pre[k]);
    k -= pre[k];
    for(int i = 0; i < n; ++i)
        if(k & 1 << i) puts(s[i]);
}

int main()
{
    int T, m, cost;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%s%d%d", s[i], &d[i], &c[i]);
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = t[0] = 0;  //边界 所有作业都没做的扣分为0
        m = 1 << n;

        for(int i = 1; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if((i & 1 << j) == 0) continue;
                int k = i - (1 << j);
                t[i] = t[k] + c[j];
                cost = t[i] > d[j] ? t[i] - d[j] : 0;
                if(dp[k] + cost <= dp[i])  //'='保证字典序最小
                {
                    dp[i] = dp[k] + cost;
                    pre[i] =  k;  //记录路径
                }
            }
        }
        printf("%d\n", dp[m - 1]);
        print(m - 1);  //打印路径
    }
    return 0;
}

Doing Homework

Problem Description

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test, 1 day for 1 point. And as you know, doing homework always takes a long time. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.
Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case start with a positive integer N(1<=N<=15) which indicate the number of homework. Then N lines follow. Each line contains a string S(the subject’s name, each string will at most has 100 characters) and two integers D(the deadline of the subject), C(how many days will it take Ignatius to finish this subject’s homework).
Note: All the subject names are given in the alphabet increasing order. So you may process the problem much easier.
Output

For each test case, you should output the smallest total reduced score, then give out the order of the subjects, one subject in a line. If there are more than one orders, you should output the alphabet smallest one.
Sample Input

2 3 Computer 3 3 English 20 1 Math 3 2 3 Computer 3 3 English 6 3 Math 6 3
Sample Output

2 Computer Math English 3 Computer English Math

Hint In the second test case, both Computer->English->Math and Computer->Math->English leads to reduce 3 points, but the word “English” appears earlier than the word “Math”, so we choose the first order. That is so-called alphabet order.