这一次的认证较为简单，当时由于还是疫情就没有参加这次认证。
第一题：现值计算
简单的签到题，按照题意直接模拟即可，没有难度
第二题：训练计划
很容易看出跟拓扑排序、关键路径有很大的关系，但是明显出题人降低了难度，训练项目已经按照拓扑序来输入了，不需要拓扑排序了，接着只需要计算最早开始时间和最晚开始时间，不需要计算关键路径了，难度大大降低。因此，计算最早开始时间就是按照拓扑正序递推即可，计算最晚开始时间按照拓扑逆序递推。
最早开始时间：evi=evj+lj,i j是i的前置训练项目，由于一个项目最多只依赖一个项目，因此这里的计算省略了取max的环节。
最晚开始时间：lvi=min(lvj-li,j ) i是j的前置训练项目，这里就需要取min了，因为i可以当多个项目的前置项目。
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 | #include <iostream>#include <cstdio>#include <cmath>using namespace std;const int N = 110;int n, m;int p[N], t[N];int early[N], late[N];bool sucess = true;bool flag[N];int main() { cin >> n >> m; for (int i = 1; i <= m; i++) cin >> p[i]; for (int i = 1; i <= m; i++) cin >> t[i]; // 计算最早开始时间 for (int i = 1; i <= m; i++) { if (p[i] == 0) early[i] = 1; else { early[i] = early[p[i]] + t[p[i]]; } late[i] = 1000; } // 计算最晚开始时间 for (int i = m; i >= 1; i--) { if (flag[i]) continue; if (p[i] == 0) late[i] = n - t[i] + 1; else { late[i] = n - t[i] + 1; int point = p[i], prep = i; while (point) { late[point] = min(late[point], late[prep] - t[point]); if (late[point] < 1) sucess = false; flag[point] = true; prep = point; point = p[point]; } } } for (int i = 1; i <= m; i++) cout << early[i] << " "; cout << endl; if (sucess) for (int i = 1; i <= m; i++) cout << late[i] << " "; return 0;} |
第三题：JPEG解码
感觉是历年来较简单的大模拟题目了，没那么多弯弯绕绕，题目相对较短清晰好懂，直接按流程模拟就行，其中Z字扫描这里硬编码顺序即可，因为只有64个格子，若要写逻辑控制Z字扫描反而麻烦了。
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 | #include <iostream>#include <cstdio>#include <cmath>using namespace std;const int N = 110;const double PI = acos(-1);int q[8][8];double m[8][8];double mp[8][8];int n, t;int data[N];const int ZigZag[64] = { 0, 1, 8, 16, 9, 2, 3, 10, 17, 24, 32, 25, 18, 11, 4, 5, 12, 19, 26, 33, 40, 48, 41, 34, 27, 20, 13, 6, 7, 14, 21, 28, 35, 42, 49, 56, 57, 50, 43, 36, 29, 22, 15, 23, 30, 37, 44, 51, 58, 59, 52, 45, 38, 31, 39, 46, 53, 60, 61, 54, 47, 55, 62, 63};void out() { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) cout << m[i][j] << " "; cout << endl; }}inline double alpha(int u) { return u != 0 ? 1 : sqrt(0.5);}double trans(int x, int y) { double res = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { res += alpha(i) * alpha(j) * m[i][j] * cos(PI / 8 * i * (x + 0.5)) * cos(PI / 8 * j * (y + 0.5)); } } return res / 4;}int main() { for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) cin >> q[i][j]; cin >> n >> t; for (int i = 0; i < n; i++) cin >> data[i]; for (int i = 0; i < 64; i++) { int x = ZigZag[i] / 8, y = ZigZag[i] - x * 8; if (i >= n) m[x][y] = 0; else m[x][y] = data[i]; } if (t >= 1) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { m[i][j] *= q[i][j]; } } } if (t == 2) { for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) mp[i][j] = trans(i, j); for (int i = 0; i < 8; i++) for (int j = 0; j < 8; j++) { m[i][j] = round(mp[i][j] + 128); if (m[i][j] > 255) m[i][j] = 255; else if (m[i][j] < 0) m[i][j] = 0; } } out(); return 0;} |
第四题：聚集方差
即便这题我只会暴力方法，也可以拿到65分，可以说这次认证难度真的下降了。
首先是公司人员的结构可以使用一棵树来存储，树的存储我就采用儿子兄弟表示法，整棵树就使用二叉树的形式存储起来了。然后计算每个节点的聚集方差，就先序遍历相应的子树得到其支配员工的偏好时间集合，按照题目公式计算聚集方差即可。（这不是最佳方法，只能拿到65分）
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 | #include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;typedef long long LL;const int N = 300010;struct Node { int left, right; int a;};int n;int p[N], a[N];Node nodes[N];LL arr[N];void find_child(int no, int &nums) { if (no == 0) return; arr[nums++] = nodes[no].a; if (nodes[no].left) find_child(nodes[no].left, nums); if (nodes[no].right) find_child(nodes[no].right, nums);}LL compute(int nums) { if (nums == 1) return 0; sort(arr, arr + nums); LL res = (arr[0] - arr[1]) * (arr[0] - arr[1]); res += (arr[nums - 2] - arr[nums - 1]) * (arr[nums - 2] - arr[nums - 1]); for (int i = 1; i < nums - 1; i++) { LL t1 = (arr[i] - arr[i - 1]) * (arr[i] - arr[i - 1]); LL t2 = (arr[i] - arr[i + 1]) * (arr[i] - arr[i + 1]); res += (t1 < t2 ? t1 : t2); } return res;}int main() { cin >> n; for (int i = 2; i <= n; i++) cin >> p[i]; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { nodes[i].a = a[i]; if (p[i]) { if (nodes[p[i]].left == 0) nodes[p[i]].left = i; else { int tmp = nodes[p[i]].left; while (nodes[tmp].right) tmp = nodes[tmp].right; nodes[tmp].right = i; } } } for (int i = 1; i <= n; i++) { int nums = 0; arr[nums++] = nodes[i].a; find_child(nodes[i].left, nums); cout << compute(nums) << endl; } return 0;} |
