ACM►图论►差分约束

差分约束系统小结

介绍

首先差分约束系统是求解关于一组变量的特殊不等式组的方法，不等式组通常是以下形式：

$x_1 - x_5 \le -1$

$x_3 - x_4 \ge 3$

$x_2 - x_4 < 3$

$x1 - x2 = 9$

这里我们定义标准型为 $a_i - b_j \le c_k$ 这里 $c_k$ 为一个常量，a 和 b 是要求的变量。

上面的

$x_2 - x_4 < 3 \sim x_2 - x_4 \le 2$

$x1 - x2 = 9 \sim x_1 - x_2 \le 9 \And x_2 - x_1 \le -9$

都可以将上述等式化为标准型。

求解

现在的问题是怎么求解上述的不等式组。

我们首先看一下图论里面的单源最短路，假设 $dist[u]$ 为 u 到源点的距离。

那么如果有边$(u,v, w)$，从 u 到 v 并且距离为 w，那么我们可以把这条边当做一个约束条件，即对于最终答案的 $dist$ 数组，显然有 $dist[v] - dist[u] \le w$，然后我们将所有的边都转化为约束条件，那么最短路问题就可以转化为上面的差分约束系统，同样的差分约束系统系统也可以通过最短路来求解。

对于所有的 $a_i - b_j \le c_k$ 从 $b_j$ 向 $a_i$ 建一条费用为 $c_k$ 的边，然后跑最短路就是满足约束的答案了，如果有负环的话代表无解。

这里为了保证图连通，有时候需要建一个超级源点向所有点连一条费用为 0 的边。

需要注意的一点是，根据原题目写出约束条件的时候一定要保证不缺不漏，并且有的条件需要特判。

题集

相信大家都做过 POJ 的奶牛的那个经典差分约束系统的题，这里只推荐两个题目（都有坑点）：

http://acm.hdu.edu.cn/showproblem.php?pid=6252

https://vjudge.net/problem/UVALive-4885

ACM►数学►高斯消元

高斯消元小结

介绍

高斯消元是一种解线性方程组的 $O(N ^ 3)$ 的方法。其实也就是线性代数中说的将一个矩阵化为上三角矩阵的的过程，最后再求解每个未知量的值。

类比下，高斯消元的在解方程组的作用，和最短路在查分约束中的作用、网络流在网络流的图论模型中的作用差不多。都只是一个计算的工具，题目考察的核心点并不在高斯消元上而是在如何列出对应的线性方程组。

另外要说的高斯消元大致有三种写法，第一种是简单的，矩阵的值只有 0 和 1，这里高斯消元中只用异或运算就可以了，其实就是求解线性基的过程；第二种是解一些模线性方程组，答案需要整数解，这里消元的时候需要取下最小公倍数；最后一种是没有特殊要求，直接上 Double 类型的，解决概率期望的问题会用到。

消元过程

01矩阵

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
int solve() {
    //rst 代表确定的未知量个数，也就是矩阵的秩、最大无关组
    //r 代表当前进行到了第几行，之前的行都化为了阶梯型
    int rst = 0, r = 0;
    memset(lib, 0, sizeof(lib));
    //代表当前进行到了第几列
    for (int i = 0; i < n; i++) {
        //枚举这一列的所有行，将一个 i 列不为 0 的行换到第 r 行
        for (int j = r; j < n; j++) {
            if (!data[j][i]) continue;
            for (int k = i; k <= n; k++) {
                swap(data[j][k], data[r][k]);
            }
            break;
        }
        //如果当前行的第 i 列全都为 0 那么就跳过这一列
        if (!data[r][i]) continue;
        rst++;
        //用第 r 行去消去其他行，如果其他行第 i 列是 1 的话
        for (int j = 0; j < n; j++) {
            if (j == r || !data[j][i]) continue;
            for (int k = i; k <= n; k++) data[j][k] ^= data[r][k];
        }
        lib[i] = true, r++;
    }
}

模线性方程组

前面的部分都一样，只是进行消元的地方修改一下，求个最小公倍数。

1
2
3
4
5
6
7
8
9
for (int j = 0; j < n; j++) {
    if (j == r || !data[j][i]) continue;
    int t = lcm(data[r][i], data[j][i]);
    int t1 = t / data[r][i];
    int t2 = t / data[j][i];
    for (int k = 0; k <= n; k++) {
        data[j][k] = ((data[j][k] * t2 - data[r][k] * t1) % MOD + MOD) % MOD;
    }
}

浮点数矩阵

消元的地方直接求个浮点数的倍数就可以。

1
2
3
4
5
6
7
for (int j = 0; j < n; j++) {
    if (j == r || eq(data[j][i], 0)) continue;
    double temp = data[j][i] / data[r][i];
    for (int k = i; k <= n; k++) {
        data[j][k] -= data[r][k] * temp;
    }
}

处理答案

高斯消元算法执行结束后，会得到如下信息：自由未知量的个数，那些列是自由未知量，方程的一个解。

01矩阵处理答案的过程是这样的，这里默认让所有自由未知量为 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 0; i < n; i++) {
    //如果第 n 列不为 0，其他列全为 0，说明增广矩阵的秩大于原矩阵，方程无解
    if (data[i][n]) {
        bool flag = false;
        for (int j = 0; j < n; j++) {
            if (data[i][j]) flag = true;
        }
        if (!flag) return -1;
    }
    //如果有自由未知量直接跳过
    if (!l[i]) continue;
    //否则这个变量的值就等于第 n 列的值，因为当前这一列除了自由未知量的列，其他列全为 0
    for (int j = 0; j < n; j++) {
        if (data[j][i]) ans[i] = data[j][n];
    }
}
return n - rst;

01矩阵有时候需要的一种做法是枚举所有的自由未知量，求取 1 的变量最少的解。

一般是直接用二进制去枚举。

1
2
3
4
5
6
7
8
9
10
11
12
int anss = INF;
for (int k = 0; k < 16; k++) {
    int cnt1 = 0, cnt2 = 0;
    int num = (k & 1) + (k >> 1 & 1) + (k >> 2 & 1) + (k >> 3 & 1);
    for (int i = 0; i < 12; i++) {
        int t = 0;
        for (int j = 0; j < 4; j++) if (data[i][12 + j]) t ^= ((k >> j) & 1);
        if (t != data[i][n]) cnt1++;
        if (t != data[i][n + 1]) cnt2++;
    }
    anss = min(min(cnt1, cnt2) + num, anss);
}

推荐题集

https://vjudge.net/contest/207993

起始也就是 kuangbin 的题集。

ACM►数学

CF895 - String Mark（组合数学）

题目链接：

题目链接

题目大意：

给出两个字符串 A 和 B，问将第一个字符串的所有排列中，大于字典序大于 A 并且 小于 B 的排列有多少个。

字符串只包含小写字母，长度小于 $10^6$ 。

题目分析：

首先将问题简化，我们定义函数 $F(S, D)$ 为 S 字典序小于 D 的排列的数量，那么答案就是 $F(S, S) - F(S, D) - 1$

那么问题转化为求解这个函数，我们这里去枚举小于 D 的排列的前缀。

假设 D 为 “bcd”，如果前缀长度为 1，那么保证前缀为 “a”，剩下的进行任意排列即可；

如果前缀长度为 2，那么保证前缀为 “ba”，”bb” 对剩下的进行任意排列即可。

注意这里对于长度为 i 的前缀，它们和 D 拥有长度为 i - 1 的公共前缀。

不难想到这样就可以计算出所有字典序小于 D 的排列。

注意这里要用到多重集的排列公式：$\frac{n!}{n_1!n_2!\cdots n_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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int MAX = 1123456;

string str1, str2;

ll pow_mod(ll a, ll k) {
    ll rst = 1;
    while (k) {
        if (k & 1) rst = rst * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return rst;
}

ll rev[MAX], fac[MAX];
void init() {
    //初始化逆元
    for (int i = 1; i < MAX; i++) {
        rev[i] = pow_mod(i, MOD - 2);
    }
    fac[1] = 1;
    //初始化阶乘
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
}

//求阶乘的逆元
ll rev_fac(ll n) {
    ll rst = 1;
    for (int i = 1; i <= n; i++) {
        rst = rst * rev[i] % MOD;
    }
    return rst;
}

ll cnt[MAX];

ll solve(string &str, string &cmp) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < str.size(); i++) {
        cnt[str[i] - 'a']++;
    }

    ll rst = 0, now = fac[str.size()];
    for (int i = 0; i < 26; i++) {
        if (!cnt[i]) continue;
        now = now * rev_fac(cnt[i]) % MOD;
    }

    for (int i = 0; i < str.size(); i++) {
        //now用来维护去掉当前某个字母后剩下的排列数量
        now = now * rev[str.size() - i] % MOD;
        for (int j = 0; j < cmp[i] - 'a'; j++) {
            if (!cnt[j]) continue;
            rst = (rst + now * cnt[j] % MOD) % MOD;
        }
        if (cnt[cmp[i] - 'a'] == 0) break;
        else {
            now = now * cnt[cmp[i] - 'a'] % MOD;
            cnt[cmp[i] - 'a']--;
        }
    }
    return rst;
}

int main() {
    init();
    cin >> str1 >> str2;
    ll rst1 = solve(str1, str1);
    ll rst2 = solve(str1, str2);
    printf("%lld\n", (rst2 - rst1 - 1 + MOD) % MOD);
}

解题过程：

完全没想到用排列计算，反而去想怎么构造了emmm

ACM►DP

CF383D - Antimatter（DP）

题目链接：

题目链接

题目大意：

给出 N 给数，每个数可以取正或者取负，选取一个连续的区间，并设置好每个数的正负。问有多少种方式可以使得选取的数的和为 0 。

$1 \le N \le 1000$，所有数的和不会超过 10000。

题目分析：

定义 $dp[i][j]$ 的含义为前 i 个数进行选取，和为 j 的取法数量。

设 $a[i]$ 为第 i 个数的值，任意看出状态转移方程为：

$dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j + a[i]]$

如果我们只是设边界 $dp[0][0] = 1$ 的话，那么 $dp[i][0]$ 是第一个数为起始以第 i 个为为结尾的答案。

这里我们初始化所有的 $dp[i][0] = 1$，然后统计答案的时候减去初始化的 1 ，这样就代表以所有的位置为起点了。

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

const int MAX = 1000 + 10;
const int MOD = 1000000007;
const int INF = 30000;
const int S = INF / 2;

typedef long long ll;

int data[MAX];
ll dp[MAX][INF];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", data + i);
    }
    for (int i = 0; i <= n; i++) dp[i][S] = 1;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < INF; j++) {
            if (j > data[i]) dp[i][j] = (dp[i][j] + dp[i - 1][j - data[i]]) % MOD;
            if (j + data[i] < INF) dp[i][j] = (dp[i][j] + dp[i - 1][j + data[i]]) % MOD;
        }
        ans = (ans + dp[i][S] - 1) % MOD;
    }
    printf("%lld\n", ans);
}

解题过程：

想错了状态，然后只能思路整体就不对了emmmmm

以后长时间卡题考虑换个状态试试？

ACM►图论►差分约束

UVA4885 - Task（差分约束）

题目链接：

题目链接

题目大意：

给出 N 个任务，M 个约束条件，条件有两种类型。

A 任务要在 B 之后至少 C 分钟后执行。

A 任务要在 B 之后至多 C 分钟内执行。

满足约束条件即可，不用不同任务可以在同一分钟执行。

$1 \le N \le 100$

题目分析：

假设 $F(A)$ 为 A 任务执行的时间，那么对于上面两个条件可以化为：

$F(A) - F(B) \ge C$

$F(A) - F(B) \le C$

$F(A) \ge F(B) $

注意这里对第二个约束条件，要转化为两个不等式，如果只有一个等式的话，不能保证
A 任务的执行在 B 任务之后。

由于题目要求执行的时间不能超过 $10^6$，那么这里对没一个对所有的 i j 加一个条件:

$F(i) - F(j) \le 10^6 - 1$ ，这样同时使得图连通。

最后将上述条件转化为对应的边跑最短路或者最长路即可。

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

using namespace std;

const int MAX = 200000;
const int INF = 0x3f3f3f3f;

char op[MAX];

struct {
    int v, w, nxt;
} edge[MAX];

int head[MAX], etot;

void add_edge(int u, int v, int w) {
    edge[etot].v = v;
    edge[etot].w = w;
    edge[etot].nxt = head[u];
    head[u] = etot++;
}

int dist[MAX], num[MAX];
bool vis[MAX];
int n, m;

bool spfa() {
    memset(dist, INF, sizeof(dist));
    memset(num, 0, sizeof(num));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(1);
    vis[1] = true;
    dist[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            int w = edge[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    num[v]++;
                    if (num[v] > n + 10) return false;
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    while (~scanf("%d", &n) && n) {
        scanf("%d", &m);
        etot = 0;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            scanf("%*s %d %*s %s", &u, op);
            if (op[0] == 'a') {
                scanf("%*s %d %*s %*s %*s %*s %d", &w, &v);
                add_edge(u, v, -w);
            } else {
                scanf("%d %*s %*s %*s %*s %*s %*s %*s %d", &w, &v);
                add_edge(v, u, w);
                add_edge(u, v, 0);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                add_edge(j, i, 1000000 - 2);
            }
        }
        if (!spfa()) puts("Impossible.");
        else {
            int minn = INF;
            for (int i = 1; i <= n; i++) {
                minn = min(minn, dist[i]);
            }
            for (int i = 1; i <= n; i++) {
                printf("%d%c", dist[i] - minn + 1, i == n ? '\n' : ' ');
            }
        }
    }
}

解题过程：

漏掉了第二个约束条件要转化为两个不等式，ORZ

命题

SDUTACM分组测试赛题解

A - China Final

简单的模拟计算 ACM-ICPC 的排名。

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        printf("%d %d %d\n",n/10,n/10*3,n/10*6);
    }
    return 0;
}

B - 为了相同的前缀-跳楼梯

判断一下是否有两个或多个相邻的台阶同时脏了，或者第 100 个台阶是否脏了即可。

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
#include <stdio.h>

#define MAX 200
int data[MAX];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int flag = 1;

        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
            if (data[i] == 100) flag = 0;
        }

        for (int i = 1; i <= n - 1; i++) {
            for (int j = 1; j < n - i + 1; j++) {
                if (data[j] > data[j + 1]) {
                    int t = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = t;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (data[i] > 100) break;
            if (data[i] - data[i - 1] == 1) flag = 0;
        }

        if (flag) printf("Orz\n");
        else printf("Why are you so ben?\n");
    }
}

C - 完美区间

写好判断素数的函数，然后跑一个 for 循环即可，注意 0 和 1 不是素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

int is_prime(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int l, r;
    while (~scanf("%d %d", &l, &r)) {
        int cnt = 0;
        for (int i = l; i <= r; i++) {
            if (is_prime(i)) cnt++;
        }
        if (is_prime(cnt)) printf("Yes\n");
        else printf("No\n");
    }
}

D - 2017 666!

直接当做字符串读入即可，然后 if 判断有几个 2017 。

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
#include <stdio.h>
#include <string.h>

#define MAX 10

char data[MAX];

int main() {
    int l, r;
    while (~scanf("%s", data)) {
        int len = strlen(data);
        int ans = 0;
        for (int i = 0; i + 3 < len; i++) {
            if (data[i] == '2' &&
                data[i + 1] == '0' &&
                data[i + 2] == '1' &&
                data[i + 3] == '7')
                ans++;
        }
        while (ans--) {
            printf("666");
        }
        printf("\n");
    }
}

E - 场地安排

可以先把数组初始化为 -1，并且最小的下标从 (1, 1) 开始，那么就不需要特判边界了。

对于每个位置的相邻位置可以把增量算出来存到数组里面，比如当前位置是第 i 行第 j 列，那么这个的左上角就是 (i - 1, j - 1)，记录增量 (-1, -1)。

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
#include <stdio.h>
#include <string.h>

#define MAX 112

int data[MAX][MAX];
int dirc[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        memset(data, -1, sizeof(data));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &data[i][j]);
            }
        }
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = 0; k < 8; k++) {
                    int tx = i + dirc[k][0];
                    int ty = j + dirc[k][1];
                    if (data[tx][ty] == data[i][j]) flag = 0;
                }
            }
        }
        if (flag) printf("\\(^o^)/~\n");
        else printf("Oh~no!!!\n");
    }
}

F - 及格名单

将名字和成绩用数组存起来，最后输入及格线，然后在 for 循环一遍数组，如果及格就输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

char name[101][20];
int score[101];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            int t;
            scanf("%s %d", name[i], score + i);
        }
        int bound;
        scanf("%d", &bound);
        for (int i = 1; i <= n; i++) {
            if (score[i] >= bound) printf("%s %d\n", name[i], score[i]);
        }
    }
}

G - 小鑫与斐波那契（二）

有个定理$(a + b) \mod p = (a \mod p + b \mod p) \mod p$。

然后计算过程中可能会有的项超出 long long 的范围。根据上面的定理显然可以知道总结取膜对结果无影响，然后 for 循环计算即可。

注意直接用函数递归一定会超时，因为计算量几乎是按指数递增的，可以简单的画图看一下，有很多项被重复计算了多次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

#define MAX 1000123
#define MOD 1000000007

long long fib[MAX];

int main() {
    int n;
    fib[0] = 0, fib[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }
    while (~scanf("%d", &n)) {
        printf("%lld\n", fib[n]);
    }
}

H - 今年暑假不AC

贪心的经典例题，按每个时间段的右边界排序，然后贪心的尽可能的选就可以了。

（如果不会的话可以等到贪心的专题，肯定会有学长 or 老师讲这道题）

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
#include <stdio.h>

#define MAX 112

struct {
    int l, r;
} data[MAX], t;

int main() {
    int n;
    while (scanf("%d", &n) && n) {
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &data[i].l, &data[i].r);
        }
        for (int i = 1; i <= n - 1; i++) {
            for (int j = 1; j < n - i + 1; j++) {
                if (data[j].r > data[j + 1].r) {
                    t = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = t;
                }
            }
        }
        int pos = 0, cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (pos <= data[i].l) pos = data[i].r, cnt++;
        }
        printf("%d\n", cnt);
    }
}

I - 数字矩阵

设 $dp[i][j]$ 为走到 $dp[i][j]$ 的最大累加和，$data[i][j]$ 为 i 行 j 列的值，那么从左上到右下有：

$$dp[i][j] = \max(dp[i - 1][j], dp[i][j -1]) + data[i]$$

对于右上到左下有：

$$dp[i][j] = \max(dp[i - 1][j], dp[i][j + 1]) + data[i]$$

这里虽然有四个起始位置，但是有两个是重复的只是起点和终点交换了，跑两次 DP 即可。

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
#include <stdio.h>
#include <string.h>

#define MAX 200

int max(int a, int b) {
    return a > b ? a : b;
}

int a[MAX][MAX], b[MAX][MAX], c[MAX][MAX];

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m)) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[i][j] = a[i][j] + max(b[i - 1][j], b[i][j - 1]);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                c[i][j] = a[i][j] + max(c[i - 1][j], c[i][j + 1]);
            }
        }
        printf("%d\n", max(b[n][m], c[n][1]));
    }
    return 0;
}
ACM►命题

2017级《程序设计基础(B)I》期末上机考试 题解（Fish出题部分）

喵帕斯之喵帕斯！

简单的输入输出。

1
2
3
4
5
6
7
8
#include <stdio.h>

int main() {
int n;
    scanf("%d", &n);
    if (n == 1) printf("ohayou");
    else printf("nyanpasu");
}

喵帕斯之副食店

计算所有硬币的面额和然后除以P即可，如果大于K的话输出K。

$\min((\sum_{i = 1}^n a[i] \cdot b[i])/P, K)$就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

int main() {
    int n, k, p;
    while (~scanf("%d %d %d", &n, &k, &p)) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
            sum += a * b;
        }
        int ans = sum / p;
        if (ans > k) ans = k;
        printf("%d\n", ans);
    }
}

喵帕斯之天才算数少女

考察函数的递归应用，根据题意写出代码即可。

（其实这个函数是理论计算机科学里非常重要的一个函数，阿克曼函数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>

int fun(int m, int n) {
    if (m == 0) return n + 1;
    else if (m > 0 && n == 0) return fun(m - 1, 1);
    else return fun(m - 1, fun(m, n - 1));
}

int main() {
    int m, n;
    while (~scanf("%d %d", &m, &n)) {
        printf("%d\n", fun(m, n));
    }
}

喵帕斯之传说中的神剑

其实喵帕斯参加过圣杯战争！（雾

这个题就是一个简单的打印图形，没什么难点，对比打印金字塔和菱形简单多了。注意点格式不要PE就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

int main() {
    int a, b;
    while (~scanf("%d %d", &a, &b)) {
        for (int i = 1; i <= a; i++) {
            if (i == a / 3 * 2) {
                for (int i = 1; i <= b; i++) {
                    printf("#");
                }
            } else {
                for (int i = 1; i <= b / 2; i++) {
                    printf(" ");
                }
                printf("#");
            }
            putchar('\n');
        }
        putchar('\n');
    }
}

喵帕斯之数学难题

考察拆分整数和素数判断，其实直接读字符串也可以。推荐写个判断是否伟素数的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int is_prime(int n) {
    if (n == 1) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        if (is_prime(sum)) printf("YES\n");
        else printf("NO\n");
    }
}

喵帕斯之平地摔

简单的一位数组，判断下是否大于相邻的两个位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

#define MAX 233

int data[MAX];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
        }
        int ans = 0;
        for (int i = 2; i <= n - 1; i++) {
            if (data[i] > data[i - 1] && data[i] > data[i + 1]) ans++;
        }
        printf("%d\n", ans);
    }
}

喵帕斯之短笛

考察字符串比较，注意最后一个数后面没有空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>

char str[][3] = {"do", "re", "mi", "fa", "so", "la", "xi"};

char data[3];

int find() {
    int pos = 0;
    while (strcmp(data, str[pos]) != 0) pos++;
    return pos + 1;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            scanf("%s", data);
            printf("%d%c", find(), i == n ? '\n' : ' ');
        }
    }
}

喵帕斯之矩阵

算是最难的题了，考察排序和二维数组，排序的时候需要找一下下标之间的关系。

这道题可以有多个做法，这里推荐一下郑康的做法。

让每个位置的数和他右下角的去比较，因为最长的对角线最长为 N，跑 N - 1 趟就OK。

大家可以类比下冒泡去理解一下。

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
#include <stdio.h>
#define MAX 112

int data[MAX][MAX];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &data[i][j]);
            }
        }
        for (int k = 1; k < n; k++) {
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if (data[i][j] > data[i + 1][j + 1]) {
                        int t = data[i][j];
                        data[i][j] = data[i + 1][j + 1];
                        data[i + 1][j + 1] = t;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                printf("%d%c", data[i][j], j == n ? '\n' : ' ');
            }
        }
    }
}

SDUT第七届ACM趣味循环赛题解（Fish出题部分）

yxc 的日常

非常简单的一道题。输入 N 个数，求和判断是否大于等于 25 即可。由于题意，数据的和保证不会超过 24，所以对每一组数据直接输出 NO 也可以 AC。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main()
{
    int i,n,a,r=0;
    while(scanf("%d",&n)!=EOF)
    {
        r=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a);
            r+=a;
        }
        if(r>=25)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

金泽的地图

这个题数据量非常大，有两种操作，一种 L 到 R 区间每个位置加 V，一种是询问 L 到 R 的和，操作次数不会超过 $10^5$，保证全部增加完再询问。

$1 \le L \le R \le 10^5$，对于每个增加或询问操作直接 for 循环去跑肯定会 TLE，由之前绿博的帽子那个题可以知道对于询问我们可以用前缀和去预处理一下，然后每次询问都直接计算出来。

但是对于增加操作，我们也需要进行优化，我们这样处理：

首先定义一个初始值为 0 的数组 data

对于每一个 L 到 R 区间增加 V 的操作，让 data[L] += v，data[R + 1] -= v。

然后定义函数 $F(i) = \sum_1^idata[i]$，可以证明$F[i]$的值就是第 i 个位置进行所有增加的操作后最终的数值。

证明如下：

如果一次操作是 [L, R] 区间每个位置增加 V，那么我们实际进行的是 data[L] += v，data[R + 1] -= v。

对于位置 i，如果一次操作的区间 $L \le R < i$ 的话，即修改的区间的右端点小于 i 位置没有交集，那么 $\sum_1^i data[i]$ 中肯定同时包含了 data[L] 和 data[R + 1] 这两个值，然后对于这一次操作对$F(i)$的贡献为 $-v + v = 0$，是对$F(i)$的值无影响的。

如果一次操作的区间 $i < L \le R$ 的话，$\sum_1^idata[i]$，肯定不包含 data[L] 和data[R + 1] 这两个值，所以这次修改操作对$F(i)$的值无影响。

最后对于 $L \le i \le R$ 的区间，即 i 含于区间内，$\sum_1^i$ 肯定包含了 data[L] 但不包含 data[R + 1]，假设这次是增加 V，那么我们让data[L] += v，data[R + 1] -= v就让$F(i)$的值增加了 V，这正符合这个函数的定义。

最后我们对于每一个 L 到 R 区间增加 V 的操作，让 data[L] += v，data[R + 1] -= v。

定义 $F(i) = \sum_1^idata[i]$，$G(i) = \sum_1^iF(i)$

最后对于每次询问 L 到 R 的和，$G(R) - G(L - 1)$ 就是答案。

代码

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
#include<iostream>
#include<cstring>

#define LL long long
using namespace std;
int n, m, i, r, l, x;
LL s[200000];

int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(s, 0, sizeof(s));
        for (i = 1; i <= n; i++) {
            scanf("%d%d%d", &l, &r, &x);
            s[l] += x;
            s[r + 1] += (-x);
        }
        for (i = 1; i <= 100000; i++) s[i] += s[i - 1];
        for (i = 1; i <= 100000; i++) s[i] += s[i - 1];
        for (i = 1; i <= m; i++) {
            scanf("%d%d", &l, &r);
            printf("%lld\n", s[r] - s[l - 1]);
        }
    }
    return 0;
}

lxw AK

这题没什么难点，为了让大家了解一下 ACM-ICPC 比赛的罚时机制，按题意模拟即可。

关键是理解题意，AC 一道题后不增加罚时，一道题没有 AC 不计算罚时等。

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
#include <stdio.h>
#include <string.h>

#define MAX 100

int AC[MAX];
int num[MAX];

char pid, rst[20];
int t;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        memset(AC, 0, sizeof(AC));
        memset(num, 0, sizeof(num));
        scanf("%d %d", &n, &m);
        int sum = 0;
        for (int i = 1; i <= m; i++) {
            scanf(" %c %s %d", &pid, rst, &t);
            pid -= 'A';
            if (!AC[pid]) {
                if (rst[0] == 'A') {
                    sum += t + num[pid] * 20;
                    AC[pid] = 1;
                } else {
                    num[pid]++;
                }
            }
        }
        printf("%d\n", sum);
    }
}

怪盗的谜题

这个题主要考察下将数字转化为字符串，并且判断字符串的回文。最后答案要预处理一下前缀和。

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
#include <stdio.h>

#define MAX 100000 + 100

int data[MAX];
int num[100];

int get(int x) {
    int top = 0;
    while (x) {
        num[top++] = x % 10;
        x /= 10;
    }
    int l = 0, r = top - 1;
    int flag = 1;
    while (l <= r) {
        if (num[l] != num[r]) flag = 0;
        l++, r--;
    }
    int rst1 = 0, rst2 = 1;
    for (int i = 0; i < top; i++) {
        rst1 += num[i];
        rst2 *= num[i];
    }
    return flag ? rst2 : rst1;
}

int main() {
    for (int i = 1; i < MAX; i++) {
        data[i] += data[i - 1] + get(i);
    }
    int QAQ;
    scanf("%d", &QAQ);
    while (QAQ--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", data[r] - data[l - 1]);
    }
}
历程

2017赛季小结

前言

今年的区域赛算是完全结束了，作为第一次参加区域赛，感觉难度比预期的简单一些，当然是暑假的时候的预期。老师也算是给了我们很多的机会，总共参加了五场区域赛，包括 CCPC 秦皇岛站，哈尔滨站，ICPC 青岛站，加上 CCPC Final 和 ECL final。这么多场比赛下来也算是意识到了自己有多菜，一直以为自己有个弱银的水平，结果打了四块铜，唯一一块银还多亏了青岛的 doc 老师出题。

比赛经历

第一场去的是哈尔滨，住了三晚上体验还行，热身赛随便打打的，只切了几个水题，然后热身赛状态算是最爆炸的一次，三个小时才出两个题，本来已经有打铁的打算了，封榜前铜牌倒数第五名。结果比赛完根本没滚榜，然后排名只下滑到了倒数第三，感觉就非常开心了。也算是人生第一块区域赛的牌子吧，不过这次比赛打的是真的惨。

然后第二场紧接着去的秦皇岛，坐的火车居然和去哈尔滨的一样。感受就是这是去过最好吃的食堂，又便宜又好吃。热身赛没有什么印象了。然后正式赛的体验就是感觉在打一场 5 小时的 CF，几乎用不到数据结构。算是非常接近银的一次了，最后 A 题卡住了，没有 A 出了，明明思路和做法都有了，不知道哪里错误…比赛后也是感觉非常可惜，最后算是铜首吧。

第三次青岛站，感觉正式赛的题还没有热身赛有意思，热身赛遇到了一个字典树上维护信息，当时想到了可以这样做，复杂度什么的都证明的很正确，感觉挺爽的，虽然没敲出来，比赛回来就找了一个类似的题补掉了。热身赛算是毫无比赛体验了，前期两个水题，然后一个本来是字符串 Hash 的中档题大家都水了过去，最后三题凭罚时银了…

第四场，CCPC Final，可以说是体验最好的一次了，在哈尔滨待了四天，逛了中央大街松花江教堂。热身赛差点爆零，当时就感觉这场比赛难度好恐怖了。正式赛体验还行，前期水题卡的时间有点长，不过后面中档题出的还算比较快，甚至还冲到了银牌区，不过还没居然卡在了我最喜欢的图论上…查分约束之前都没怎么刷过，感觉很可惜。如果能切掉这个题的话，可能也有银牌了。可以说是打的比较好的一次比赛了，中间和 dalao 们的排名差距很小。

最后是 ECL Final，食堂特别难吃！又贵又难吃，还一点肉都没有！热身赛这次爆零了，体验不是很好。正式赛前期简直爆炸，最简单的水题错了 3 发才过。到比赛中期感觉才上来，连过了几题才到了 100 多名。感觉会做的都做出来了，后面的题是真的心有余而力不足了。这次比赛感觉前面题的代码量太少，只靠思维猜结论…最后也是稳铜了。

总结

总的来说还是先提升自身能力吧，接下来也没有组队的比赛了，补一下自己不擅长的数学几何之类的。然后比赛下来发现卡的并不是知识点，而是 CF 的那种题，明年之前打上紫名？另外队伍配合的并不好，比赛的时候一种感觉是在两个人打比赛…

ACM►DP

URAL1523 - K-inversions（树状数组+DP）

题目链接：

http://acm.timus.ru/problem.aspx?space=1&num=1523

题目大意：

给出 N 个数，求有多少个长度为 K 的严格递减子序列。

$1 \le N \le 20000$，$2 \le k \le 10$

题目分析：

首先为了方便处理，我们翻转一下数组，这样答案变成了求递增。

定义状态 $dp[i][j]$的含义为以 i 结尾的长度为 j 的递增子序列个数。

那么可以这样转移 :

$$dp[i][j] = \sum^{i - 1}_{k = 1} dp[k][j - 1] (\text {where $a_k < a_i$} )$$

这里我们依次计算长度$1 - k$的递增子序列，这样对长度为 j 的子序列就可以从左到右遍历数组，用树状数组统计长度为 j - 1 的子序列贡献。

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

const int MAX = 21234;
const int MOD = 1e9;

int data[MAX], tree[MAX], dp[MAX][20];

inline int low_bit(int x) {
    return x&(-x);
}

int n, k;

//给 x 这个位置增加 v
void add(int x, int v) {
    while (x <= n) {
        tree[x] = (tree[x] + v) % MOD;
        x += low_bit(x);
    }
}

//求 1 ～ x 的和
int query(int x) {
    int rst = 0;
    while (x) {
        rst = (rst + tree[x]) % MOD;
        x -= low_bit(x);
    }
    return rst;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = n; i >= 1; i--) {
        scanf("%d", data + i);
        dp[i][1] = 1;
    }
    for (int i = 2; i <= k; i++) {
        memset(tree, 0, sizeof(tree));
        for (int j = 1; j <= n; j++) {
            dp[j][i] = query(data[j]);
            add(data[j], dp[j][i - 1]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + dp[i][k]) % MOD;
    printf("%d\n", ans);
}

解题过程：

树状数组还是挺好用的，这种问题写线段树还是太麻烦了…