第三次CCF计算机软件能力认证

第一题：门禁系统

涛涛最近要负责图书馆的管理工作，需要记录下每天读者的到访情况。

每位读者有一个编号，每条记录用读者的编号来表示。

给出读者的来访记录，请问每一条记录中的读者是第几次出现。

输入格式

输入的第一行包含一个整数 n，表示涛涛的记录条数。

第二行包含 n 个整数，依次表示涛涛的记录中每位读者的编号。

输出格式

输出一行，包含 n 个整数，由空格分隔，依次表示每条记录中的读者编号是第几次出现。

数据范围

1≤n≤1000，
读者的编号为不超过 n 的正整数。

输入样例：

5
1 2 1 1 3

输出样例：

1 1 2 3 1

 解题思路：直接使用哈希表，检查每一个元素是否需要我们的输出

以下是代码：

c++

#include<iostream>using namespace std;const int N = 1010;
int a[N];
int n;int main()
{cin >> n;for(int i = 0;i < n;i ++){int x;cin >> x;a[x] ++;cout << a[x] << " ";}return 0;
}

Python

n = int(input())
l = list(map(int , input().split()))
d = {}
for i in l:d[i] = 1 if i not in d else d[i] + 1print(d[i] , end = ' ')

第二题：门禁系统

在图像编码的算法中，需要将一个给定的方形矩阵进行 Z 字形扫描(Zigzag Scan)。

给定一个 n×n 的矩阵，Z 字形扫描的过程如下图所示：

对于下面的 4×4 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行 Z 字形扫描后得到长度为 16 的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个 Z 字形扫描的程序，给定一个 n×n 的矩阵，输出对这个矩阵进行 Z 字形扫描的结果。

输入格式

输入的第一行包含一个整数 n，表示矩阵的大小。

输入的第二行到第 n+1 行每行包含 n 个正整数，由空格分隔，表示给定的矩阵。

输出格式

输出一行，包含 n×n 个整数，由空格分隔，表示输入的矩阵经过 Z 字形扫描后的结果。

数据范围

1≤n≤500，
矩阵元素为不超过 1000 的正整数。

输入样例：

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

  解题思路：模拟，观察图片可以发现一共有四个方向

这四个方向可以使用偏移量数组进行模拟

当然，这里来一种不一样的方法，我们发现可以只是用一个flag标记即可解决问题。

使用一个flag标记控制前两种方向移动，因为有-1 +1，所以是有可能跃出边界的，因此我们在这个坐标跃出边界时，判断，然后将溢出的坐标置0，并且将flag置反（通过测试可以发现每一次需要转弯的时候往往就是某一个坐标溢出的时候）

以下是代码：

c++

#include<iostream>using namespace std;const int N = 510;
int n;
int a[N][N];int main()
{cin >> n;for(int i = 0;i < n;i ++)for(int j = 0;j < n;j ++)cin >> a[i][j];int x = 0 , y = 0;// 方向一：ture就x--，y++。方向二：false就x++，y--。bool f = true;while(x != n || y != n){if(x < n && y < n) cout << a[x][y] << " ";if(f) x -- , y ++;else x ++ , y --;if(x < 0) x = 0 , f = !f;if(y < 0) y = 0 , f = !f;}return 0;
}

第三题：集合竞价

某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。

该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：

1. buy p s 表示一个购买股票的买单，每手出价为 p，购买股数为 s。
2. sell p s 表示一个出售股票的卖单，每手出价为 p，出售股数为 s。
3. cancel i 表示撤销第 i 行的记录。被撤销的记录一定是前两种。

如果开盘价为 p0，则系统可以将所有出价至少为 p0 的买单和所有出价至多为 p0 的卖单进行匹配。

因此，此时的开盘成交量为出价至少为 p0 的买单的总股数和所有出价至多为 p0 的卖单的总股数之间的较小值。

你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。

如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。

输入格式

输入数据有任意多行，每一行是一条记录。

保证输入合法。股数为不超过 1e8 的正整数，出价为精确到恰好小数点后两位的正实数，且不超过 10000.00。

输出格式

你需要输出一行，包含两个数，以一个空格分隔。

第一个数是开盘价，第二个是此开盘价下的成交量。

开盘价需要精确到小数点后恰好两位。

数据范围

对于 100% 的数据，输入的行数不超过 5000。
0<p≤1e4
1≤s≤1e8
数据保证一定存在某个开盘价使得成交量不为 0。
保证输入合法。数据保证 cancel 指令只会取消 buy 和 sell 记录。

输入样例：

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

输出样例：

9.00 450

 解题思路：首先使用结构体记录每一条信息，注意cancel信息使用 ***** 进行标记，剩下两个参数记为-1即可。

由于数据量很小因此可以在的复杂度完成。

直接根据题目进行模拟即可。

以下是代码：

c++

#include<iostream>using namespace std;const int N = 5010;
typedef long long ll;
struct record
{// cancel 状态为"*****"string st;double p;ll money;
}r[N];int idx = 1;int main()
{string s1;double p;ll mon;while(cin >> s1 >> p){if(s1 == "cancel") r[(int)p].st = "*****" , r[idx ++] = {s1 , -1 , -1};else{cin >> mon;r[idx ++] = {s1 , p , mon};}}p = -1;// 开盘价ll res = -1;// 交易量 for(int i = 1;i < idx;i ++){if(r[i].st == "*****") continue;ll buy = 0 , sell = 0;double p0 = r[i].p;for(int j = 1;j < idx;j ++){// 出价至少为 p0 的买单if(r[j].st == "buy" && r[j].p >= p0) buy += r[j].money;// 出价至多为 p0 的卖单if(r[j].st == "sell" && r[j].p <= p0) sell += r[j].money;}// cout << p0 << " " << buy << " " << sell << endl;ll x = min(buy , sell);if(res < x) res = x , p = p0;else if(res == x) {if(p < p0) p = p0; }}printf("%.2lf %lld" , p , res);return 0;
}

第四题：最优灌溉

雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。

为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。

现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

输入的第一行包含两个正整数 n,m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用 1,2,3,…… 依次标号。

接下来 m 行，每行包含三个整数 ai,bi,ci，表示第 ai 片麦田与第 bi 片麦田之间可以建立一条水渠，所需要的费用为 ci。

输出格式

输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。

数据范围

前 20% 的评测用例满足：n≤5。
前 40% 的评测用例满足：n≤20。
前 60% 的评测用例满足：n≤100。
所有评测用例都满足：1≤n≤1000，1≤m≤100,000，0≤ci≤10,000
保证一定可以灌溉到所有麦田，并且无重边和自环（补充这个条件是为了和官方数据保持一致）。
注意，关于 ci 的取值范围，官网标注的是 ci≥1，但是经过实际测试，官方数据中包含 ci=0 的数据，因此在这里予以修正，并添加相应数据。

输入样例：

4 4
1 2 1
2 3 4
2 4 2
3 4 3

输出样例：

6

样例解释

建立以下三条水渠：麦田 1 与麦田 2、麦田 2 与麦田 4、麦田 4 与麦田 3。

 解题思路：经典的最小生成树算法，可以使用Kruskal算法或是prim算法，这里直接是Kruskal算法，注意数据可能很大，开longlong就行

以下是代码：

c++

// Kruskal算法
#include<iostream>
#include<algorithm>using namespace std;const int N = 1010 , M = 1e5 + 10;int p[N];
int n , m;
struct nodes
{int a , b;long long c;
}node[M];
int idx = 0;void init()
{for(int i = 1;i <= n;i ++)p[i] = i;
}int find(int x)
{if(x != p[x]) p[x] = find(p[x]);return p[x];
}bool cmp(nodes x , nodes y)
{return x.c < y.c;
}int main()
{cin >> n >> m;init();while(m --){int a , b , c;cin >> a >> b >> c;node[idx ++] = {a , b , c};}// 根据权值进行排序sort(node , node + idx , cmp);int cnt = 0;long long res = 0;for(int i = 0;i < idx;i ++){// cout << node[i].a << " " << node[i].b << " " << node[i].c << endl;int fa = find(node[i].a) , fb = find(node[i].b);if(fa != fb) {p[fa] = fb;cnt += 1;res += node[i].c;}if(cnt == n - 1) break;}cout << res << endl;return 0;
}

第五题：货物调度

某公司要处理一个周期性的物流问题。

有 n 个城市，第 i 个城市在每周的第 j(1≤j≤7) 天会生产 aij 吨某种货物，同时需要消耗 bij 吨该种货物。

已知每周的产量等于消耗量（即 aij 之和等于 bij 之和）。

城市之间有 m 条道路，第 k 条道路连接了城市 sk 和 tk。

一条道路上运输 1 吨货物有一个固定的成本 ck。

道路都可以双向使用。

每天运输的货物量没有限制。

城市之间的距离并不远，货物可以从任意一个城市运输到任意另一个城市并且在当天到达。

货物如果在当天没有被消耗掉，就需要存放在仓库里过夜。

第 i 个城市的仓库容量为 vi，存放 11 吨货物过一夜所需的成本是 wi。

请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话，该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。

输入格式

输入的第一行有两个正整数 n 和 m，即城市的个数和道路的条数。

接下来有 n 行，每行包含 16 个整数，用以描述第 i 个城市的相关数据。其中第 i 行包含的数为 ai1,ai2,ai3,ai4,ai5,ai6,ai7,bi1,bi2,bi3,bi4,bi5,bi6,bi7,vi,wi

接下来有 m 行，每行包含 3 个整数，用以描述一条道路的相关数据。其中第 k 行包含的数为 sk,tk 和 ck。

输入数据中城市的编号均为 1 到 n 之间。

输入数据的每行的行首行尾均保证没有空格，两个数之间恰好被一个空格隔开。

输出格式

你只需要输出一个数，即最优方案下每周的支出。

数据范围

对于 100% 的数据，1≤n≤100，1≤m≤500，0≤aij,bij,vi≤1000≤，1≤wi,ck≤100。
数据保证仓库够用。
数据保证无重边和自环。（补充这个条件是为了和官方数据保持一致）

输入样例：

3 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4
0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1
0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5
1 2 1
1 3 5
2 3 1

输出样例：

67

样例解释

城市 1 每周五生产 5 吨货物，把其中 2 吨运到存储费用低廉的城市 2 存储，把 1 吨运到城市 3 存储，剩下的 2 吨留在城市 1。

在次周一的时候城市 2 会消耗掉存放在那里的 2 吨货物。

为了节约存储成本，将囤放在城市 1 的货物运到城市 2 存放。

周三再将所有货物运到城市 3 以满足该城市的需求。

在此方案下，每周的运输成本为 8，每周的存储成本为 59，因此每周的总支出为 67。

 解题思路：网络流的经典问题 （但是我不会）

学习学习

以下是代码：

c++

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 710, M = (N * 3 + 500 * 7 * 2) * 2 + 10, INF = 0x3f3f3f3f;int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];int get(int a, int b)
{if (b == 8) b = 1;return (a - 1) * 7 + b;
}void add(int a, int b, int c, int d)
{e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}bool spfa()
{int hh = 0, tt = 1;memset(d, 0x3f, sizeof d);memset(incf, 0, sizeof incf);q[0] = S, d[S] = 0, incf[S] = INF;while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = false;for (int i = h[t]; ~i; i = ne[i]){int ver = e[i];if (f[i] && d[ver] > d[t] + w[i]){d[ver] = d[t] + w[i];pre[ver] = i;incf[ver] = min(incf[t], f[i]);if (!st[ver]){q[tt ++ ] = ver;if (tt == N) tt = 0;st[ver] = true;}}}}return incf[T] > 0;
}void EK(int& flow, int& cost)
{flow = cost = 0;while (spfa()){int t = incf[T];flow += t, cost += t * d[T];for (int i = T; i != S; i = e[pre[i] ^ 1]){f[pre[i]] -= t;f[pre[i] ^ 1] += t;}}
}int main()
{cin >> n >> m;S = 0, T = n * 7 + 1;memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++ ){int c, d;for (int j = 1; j <= 7; j ++ ){cin >> c;add(S, get(i, j), c, 0);}for (int j = 1; j <= 7; j ++ ){cin >> c;add(get(i, j), T, c, 0);}cin >> c >> d;for (int j = 1; j <= 7; j ++ )add(get(i, j), get(i, j + 1), c, d);}while (m -- ){int a, b, c;cin >> a >> b >> c;for (int i = 1; i <= 7; i ++ ){add(get(a, i), get(b, i), INF, c);add(get(b, i), get(a, i), INF, c);}}int flow, cost;EK(flow, cost);cout << cost << endl;return 0;
}

这两篇可以学习记录一下 

最大流 - OI Wiki (oi-wiki.org)

网络流简介 - OI Wiki (oi-wiki.org)