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

第一题：灰度直方图

解题思路：

哈希表即可

#include<iostream>
#include<cstring>using namespace std;const int N = 610;
int a[N];
int n , m , l;int main()
{memset(a , 0 , sizeof a);cin >> n >> m >> l;for(int i = 0;i < n;i ++)for(int j = 0;j < m;j ++){int x;cin >> x;a[x] ++;}for(int i = 0;i < l;i ++)cout << a[i] << " ";return 0;
}

第二题：邻域均值 

解题思路：

二维前缀和

#include<iostream>
#include<cstring>using namespace std;const int N = 610;
int s[N][N];
int n , l , r , t;int main()
{memset(s , 0 , sizeof s);cin >> n >> l >> r >> t;for(int i = 1;i <= n;i ++)for(int j = 1;j <= n;j ++){int x;cin >> x;s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + x;}int res = 0;for(int i = 1;i <= n;i ++)for(int j = 1;j <= n;j ++){int x1 = max(1 , i - r) , y1 = max(1 , j - r);int x2 = min(n , i + r) , y2 = min(n , j + r);int sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];int cnt = (x2 - x1 + 1) * (y2 - y1 + 1);if(sum <= t * cnt) res ++;}cout << res << endl;return 0;
}

第三题：DHCP服务器

解题思路：

认真读题，题目描述的非常清楚更具题目进行求解即可，

#include<iostream>
#include<algorithm>using namespace std;const int N = 1e5 + 10;int n , tdef , tmax , tmin;
string h; // 本机名称struct IP
{int st; // 0表示未分配、1表示待分配、2表示占用、3表示过期string owner; // 未分配状态没有占用者int t; // 待分配和占用状态拥有一个大于零的过期时刻
}ip[N];int get_ip_d(string c)
{for(int i = 1;i <= n;i ++)if(ip[i].owner == c) return i;return 0;
}int get_ip(int state)
{/*若没有，则选取最小的状态为未分配的 IP 地址若没有，则选取最小的状态为过期的 IP 地址*/for(int i = 1;i <= n;i ++)if(ip[i].st == state) return i;return 0;
}void update(string send)
{/*若不是，则找到占用者为发送主机的所有 IP 地址，对于其中状态为待分配的，将其状态设置为未分配，并清空其占用者，清零其过期时刻，处理结束*/for(int i = 1;i <= n;i ++)if(ip[i].owner == send) {if(ip[i].st == 1){ip[i].st = 0;ip[i].owner = "";ip[i].t = 0;}}
}void change(int tc)
{/*在到达该过期时刻时，若该地址的状态是待分配，则该地址的状态会自动变为未分配，且占用者清空，过期时刻清零；否则该地址的状态会由占用自动变为过期，且过期时刻清零。*/for(int i = 1;i <= n;i ++)if(ip[i].t && ip[i].t <= tc){if (ip[i].st == 1){ip[i].st = 0;ip[i].owner = "";ip[i].t = 0;}else{ip[i].st = 3;ip[i].t = 0;}}
}int main()
{cin >> n >> tdef >> tmax >> tmin >> h;int q;cin >> q;while(q --){// <发送主机> <接收主机> <报文类型> <IP 地址> <过期时刻>string send , get , type;int x , tc , te;cin >> tc >> send >> get >> type >> x >> te;if(get != h && get != "*") {// 判断接收主机是否为本机，或者为 *，若不是，则判断类型是否为 Request，若不是，则不处理；if(type != "REQ") continue; }// 若类型不是 Discover、Request 之一，则不处理if(type != "REQ" && type != "DIS") continue;// 若接收主机为 *，但类型不是 Discover，或接收主机是本机，但类型是 Discover，则不处理。if(get == "*" && type != "DIS" || get == h && type == "DIS") continue;change(tc);// discover 报文if(type == "DIS"){int k = get_ip_d(send);if(!k) k = get_ip(0);if(!k) k = get_ip(3);if(!k) continue;// 将该 IP 地址状态设置为待分配，占用者设置为发送主机ip[k].st = 1 , ip[k].owner = send;// 若报文中过期时刻为 0 ，则设置过期时刻为 t+tdefif(!te) ip[k].t = tc + tdef;else{int w = te - tc;w = min(w , tmax) , w = max(w , tmin);ip[k].t = w + tc;}cout << h << " " << send << " OFR " << k << " " << ip[k].t << endl;}else{if(get != h) {update(send);continue;}if(!(x <= n && x >= 1 && ip[x].owner == send)){cout << h << " " << send << " NAK " << x << " " << 0 << endl;continue;}// 无论该 IP 地址的状态为何，将该 IP 地址的状态设置为占用ip[x].st = 2;if (!te) ip[x].t = tc + tdef;else{int w = te - tc;w = max(w , tmin), w = min(w, tmax);ip[x].t = tc + w;}cout << h << " " << send << " ACK " << x << " " << ip[x].t << endl;}}return 0;
}

第四题：校门外的树

解题思路：

dp问题

设 f[i] 为用了前 i 个障碍点的所有方案

f[i]=(f[0]∗cnt1+f[1]∗cnt2+…+f[j]∗cnt3+…+f[i−1]∗cnt(i−1))

f[i] 在循环的时候已经计算出结果，计算cnt值为重中之重

cnt值，也就是两个位置之间可以整除的结果个数，也就是约数个数。

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<vector>using namespace std;const int N = 1010 , M = 1e5 + 10 , mod = 1e9 + 7;
int n;
int a[N] , f[N];
unordered_map<int , vector<int>>mp;
bool st[M];int main()
{for(int i = 1;i < M;i ++)for(int j = i * 2;j < M;j += i)mp[j].push_back(i); // 枚举因数cin >> n;for(int i = 0;i < n;i ++) cin >> a[i];f[0] = 1;for(int i = 1;i < n;i ++){memset(st , 0 , sizeof st);for(int j = i - 1;j >= 0;j --){int d = a[i] - a[j] , cnt = 0;for(int k : mp[d])if(!st[k]){cnt ++;st[k] = true;}st[d] = true;f[i] = (f[i] + (long long)f[j] * cnt) % mod;}}cout << f[n - 1] << endl;return 0;
}

第五题：疫苗运输

迪杰斯特拉+扩展欧几里得算法（不会）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>#define x first
#define y secondusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 510;
const LL INF = 0x3f3f3f3f3f3f3f3fll;int n, m;
int len[N];
struct Node
{int cid, sum, pid;
};
vector<Node> ps[N];
vector<PII> line[N];  // x表示节点编号；y表示到下一个点的距离
LL dist[N], ans[N];
int pid[N];
bool st[N];LL exgcd(LL a, LL b, LL &x, LL &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b)
{if (!b){x = 1; y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= (a / b) * x;return d;
}void dijkstra()
{memset(dist, 0x3f, sizeof dist);for (int i = 0; i < m; i ++ ){int d = 0;for (int j = 0; j < line[i].size(); j ++ ){if (line[i][j].x == 1){dist[i] = d;pid[i] = j;break;}d += line[i][j].y;}}for (int i = 0; i < m; i ++ ){int t = -1;for (int j = 0; j < m; j ++ )if (!st[j] && (t == -1 || dist[j] < dist[t]))t = j;st[t] = true;auto& l = line[t];auto d = dist[t];for (int j = pid[t], k = 0; k < l.size(); j = (j + 1) % l.size(), k ++ ){for (auto& c: ps[l[j].x]){if (st[c.cid]) continue;  // 优化很重要LL a = d, b = len[t];LL x = c.sum, y = len[c.cid];LL X, Y;LL D = exgcd(b, y, X, Y);if ((x - a) % D) continue;X = (x - a) / D * X;y /= D;X = (X % y + y) % y;if (dist[c.cid] > a + b * X){dist[c.cid] = a + b * X;pid[c.cid] = c.pid;}}d += l[j].y;}}
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < m; i ++ ){int cnt, sum = 0;scanf("%d", &cnt);for (int j = 0; j < cnt; j ++ ){int ver, t;scanf("%d%d", &ver, &t);ps[ver].push_back({i, sum, j});line[i].push_back({ver, t});sum += t;}len[i] = sum;}dijkstra();memset(ans, 0x3f, sizeof ans);for (int i = 0; i < m; i ++ ){if (dist[i] == INF) continue;LL d = dist[i];for (int j = pid[i], k = 0; k < line[i].size(); j = (j + 1) % line[i].size(), k ++ ){int ver = line[i][j].x;ans[ver] = min(ans[ver], d);d += line[i][j].y;}}for (int i = 2; i <= n; i ++ )if (ans[i] == INF) puts("inf");else printf("%lld\n", ans[i]);return 0;
}