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

第一题：小明上学

小明是汉东省政法大学附属中学的一名学生，他每天都要骑自行车往返于家和学校。

为了能尽可能充足地睡眠，他希望能够预计自己上学所需要的时间。

他上学需要经过数段道路，相邻两段道路之间设有至多一盏红绿灯。

京州市的红绿灯是这样工作的：每盏红绿灯有红、黄、绿三盏灯和一个能够显示倒计时的显示牌。

假设红绿灯被设定为红灯 r 秒，黄灯 y 秒，绿灯 g 秒，那么从 0 时刻起，[0,r) 秒内亮红灯，车辆不许通过；[r,r+g) 秒内亮绿灯，车辆允许通过；[r+g,r+g+y) 秒内亮黄灯，车辆不许通过，然后依次循环。

倒计时的显示牌上显示的数字 l（l>0） 是指距离下一次信号灯变化的秒数。

一次上学的路上，小明记录下了经过每段路的时间，和各个红绿灯在小明到达路口时的颜色和倒计时秒数。

希望你帮忙计算此次小明上学所用的时间。

输入格式

第一行包含空格分隔的三个正整数 r、y、g，表示红绿灯的设置。

第二行包含一个正整数 n，表示小明总共经过的道路段数和看到的红绿灯数目。

接下来的 n 行，每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路，耗时 t 秒，此处 t 不超过 1e6；k=1、2、3 时，分别表示看到了一个红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。

输出格式

输出一个数字，表示此次小明上学所用的时间。

数据范围

1≤n≤100,
1≤r,y,g≤1e6,
测试点 1,2 中不存在任何信号灯。
测试点 3,4 中所有的信号灯在被观察时均为绿灯。
测试点 5,6 中所有的信号灯在被观察时均为红灯。
测试点 7,8 中所有的信号灯在被观察时均为黄灯。
测试点 9,10 中将出现各种可能的情况。

输入样例：

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

输出样例：

70

样例解释

小明先经过第一段道路，用时 10 秒，然后等待 5 秒的红灯，再经过第二段道路，用时 11 秒，然后等待 2 秒的黄灯和 30 秒的红灯，再经过第三段、第四段道路，分别用时 6、3 秒，然后通过绿灯，再经过最后一段道路，用时 3 秒。

共计 10+5+11+2+30+6+3+3=70 秒。

#include<iostream>using namespace std;int r , y , g;
int n;int main()
{cin >> r >> y >> g;cin >> n;long long res = 0;while(n --){int a , b;cin >> a >> b;if(a == 0) res += b;else{if(a == 1) res += b;else if(a == 2) res += b + r;}}cout << res << endl;return 0;
}

 第二题：小明放学

解题思路：

灯时的总循环时间是r+y+g

#include<iostream>using namespace std;typedef long long ll;ll r , y , g , n;
ll res = 0;int main()
{cin >> r >> y >> g;cin >> n;while(n --){ll a , b;cin >> a >> b;if(!a) res += b;else{/*灯时的总循环时r + y + g使用数轴求解*/// 红灯if(a == 1) b = r - b;// 黄灯else if(a == 2) b = r + y + g - b;// 绿灯else b = r + g - b;b += res;b = b % (r + g + y);if(b < r) res += r - b;else if(b >= r + g) res += r + g + y - b + r;}}cout << res << endl;return 0;
}

第三题：CIDR合并

纯计算机网络的知识（应该是网络层的知识）

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int n;
struct IP
{string v;int k;bool operator< (const IP& t) const{if (v != t.v) return v < t.v;return k < t.k;}bool is_substr(IP& t){if (t.k < k) return false;if (v.substr(0, k) != t.v.substr(0, k)) return false;return true;}int get_number(string str){int res = 0;for (int i = 0; i < 8; i ++ )res = res * 2 + str[i] - '0';return res;}void print(){for (int i = 0; i < 32; i += 8){if (i) printf(".");printf("%d", get_number(v.substr(i, 8)));}printf("/%d\n", k);}
}ip[N];IP merge(IP& a, IP& b)
{IP res;res.k = -1;if (a.k != b.k) return res;if (a.v.substr(0, a.k - 1) != b.v.substr(0, b.k - 1)) return res;res.k = a.k - 1;res.v = a.v.substr(0, a.k - 1);while (res.v.size() <= 32) res.v += '0';return res;
}int main()
{scanf("%d", &n);char str[20];int d[4];for (int i = 0; i < n; i ++ ){scanf("%s", str);memset(d, 0, sizeof d);int cnt = 0;ip[i].k = -1;for (int j = 0; str[j]; j ++ ){if (str[j] == '/'){ip[i].k = atoi(str + j + 1);break;}if (str[j] == '.') continue;while (str[j] && str[j] != '.' && str[j] != '/')d[cnt] = d[cnt] * 10 + str[j ++ ] - '0';j -- ;cnt ++ ;}for (int j = 0; j < 4; j ++ )for (int k = 7; k >= 0; k -- )if (d[j] >> k & 1)ip[i].v += '1';elseip[i].v += '0';if (ip[i].k == -1) ip[i].k = cnt * 8;}sort(ip, ip + n);int k = 1;for (int i = 1; i < n; i ++ )if (!ip[k - 1].is_substr(ip[i]))ip[k ++ ] = ip[i];n = k;k = 1;for (int i = 1; i < n; i ++ ){ip[k ++ ] = ip[i];while (k >= 2){auto t = merge(ip[k - 2], ip[k - 1]);if (t.k != -1){k -= 2;ip[k ++ ] = t;}else break;}}n = k;for (int i = 0; i < n; i ++ )ip[i].print();return 0;
}

 第四题：数据中心

经典克鲁斯卡尔算法

#include<iostream>
#include<algorithm>
#include<vector>using namespace std;const int N = 1e6 + 10;
int n , m , root;
int p[N];struct node
{int a , b , c;
};bool cmp(node a , node b)
{return a.c < b.c;
}vector<node>edge;int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m >> root;for(int i = 1;i <= n;i ++)p[i] = i;while(m --){int a , b , c;cin >> a >> b >> c;edge.push_back({a , b , c});}sort(edge.begin() , edge.end() , cmp);int res = 0;for(int i = 0;i < edge.size();i ++){int pa = find(edge[i].a) , pb = find(edge[i].b);if(pa != pb){p[pa] = pb;res = edge[i].c;}}cout << res << endl;return 0;
}

 第五题：管道清洁

网络流问题

 

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 210, M = (500 + N) * 2 + 10, INF = 1e6;int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], dist[N], pre[N], incf[N];
bool st[N];
int din[N], dout[N];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(dist, 0x3f, sizeof dist);memset(incf, 0, sizeof incf);q[0] = S, dist[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 j = e[i];if (f[i] && dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];pre[j] = i;incf[j] = min(f[i], incf[t]);if (!st[j]){q[tt ++ ] = j;if (tt == N) tt = 0;st[j] = true;}}}}return incf[T] > 0;
}int EK(int tot)
{int flow = 0, cost = 0;while (spfa()){int t = incf[T];flow += t, cost += t * dist[T];for (int i = T; i != S; i = e[pre[i] ^ 1]){f[pre[i]] -= t;f[pre[i] ^ 1] += t;}}if (flow != tot) return -1;return cost;
}int main()
{int C, E;scanf("%d%*d%d", &C, &E);while (C -- ){memset(h, -1, sizeof h);idx = 0;memset(din, 0, sizeof din);memset(dout, 0, sizeof dout);scanf("%d%d", &n, &m);S = 0, T = n + 1;int down_cost = 0;while (m -- ){int a, b;char c;scanf("%d %d %c", &a, &b, &c);int down, up;if (c == 'A') down = 1, up = INF, down_cost += E;else if (c == 'B') down = up = 1, down_cost += E;else if (c == 'C') down = 0, up = INF;else down = 0, up = 1;add(a, b, up - down, E);din[b] += down, dout[a] += down;}int tot = 0;for (int i = 1; i <= n; i ++ )if (din[i] > dout[i]){add(S, i, din[i] - dout[i], 0);tot += din[i] - dout[i];}else add(i, T, dout[i] - din[i], 0);int c = EK(tot);if (c != -1) c += down_cost;printf("%d\n", c);}return 0;
}