T1 技能 sol1 预处理每一个起点到每一个终点的距离，暴力枚举哪一个起点到哪一个终点。 时间复杂度 。 能拿 分。 正解 显然，从贪心角度考虑，对于每一棵子树，肯定是子树内的起点和终点优先匹配，匹配不了的再到子树外去匹配。 可以证明，子树内匹配肯定比子树内外匹配更优。 那么我们就可以直接得出，对于每一条边，它被账号便利的次数肯定是子树内起点与终点数量之差。 直接对于每一条边，统计答案就可以。 因为 最大到 ，所以我们需要写一个高精。 只需要高精乘低精和高精度加法，直接数组模拟就可以了。 时间复杂度是 。 ...

T1 隔离 要么只隔离一次，要么一直来回，不被隔离。如果去一趟 B 地把所有事情办完也是回来隔离，办一部分回来也是隔离，那肯定选择一次办完。 分类讨论这两种情况哪一种耗时多就可以了。 #include <iostream> #include <algorithm> using namespace std; int n, a[100005]; long long ans; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; int s = ...

T1 学习除法 本题等价于判断质数，若原数字为质数，则输出 0，否则输出 1 因为对于每 #include <iostream> using namespace std; int main(){ long long n; cin >> n; for(int i = 2; i <= n / i; i++){ if(n % i == 0){ cout << 1 << endl; return 0; } } cout << 0 << endl; } 一个大于等于 ...

T1 光 20pt 枚举每一盏灯的耗电量，然后按照公式计算每一个格子的亮度是否符合要求。 70pt 枚举三盏灯的耗电量，计算出此时每个格子的亮度，算出每个格子当前亮度与需求亮度的差值，这个差值由第四盏灯来填补。即枚举好三盏灯之后，我们可以 O(1) 算出第四盏灯的最低耗电量。 100pt 本题显然具有二分性，考虑二分答案。假设总共有 的耗电量可以分配给四盏灯，我们考虑如何分配： 枚举对角线的两盏灯的耗电量，假设枚举的是左上角 和右下角 。那么我们可以发现，右上角这个格子当前亮度为 ，左下角的格子的亮度也一样。我们可以算出这两个格子的亮度与...

A. 跳跃 从第二个数字开始，判断每一个数字是否至少是前一个数字的 倍，或者前一个数字是否至少是当前数字的 倍。要注意问题的转换，如果使用 int 读入，则尽量不要使用除法（因为除法默认整除，会向下取整，使得本题细节更多） #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; int a[maxn]; int main(){ int n, sum = 0, k; cin >> n >> k; for(int i = 1; i <= n;...

普及组题解 T1 反码 使用字符串进行读入，按照题意模拟即可 T2 异或 我们发现在循环移位的时候，结果的改变只与个别位置有关。例如数组长度为 3，则刚开始时数组的价值为 ^ + ^ ，向右循环一次之后变为 ^ + ^ ，其中只少了一个 ^ 的值，多了一个 ^ 的值，其余部分是不变的。（对于更长的数组也可以用类似的方法进行推演） 得到此结论之后，我们只需要关注在循环移动的同时，哪一对异或值消失了，哪一对异或值增加了，就可以得到答案。 #include <iostream> using namespace std; const int maxn = 1e5 + ...

T1 变换 易知，连续变换两个位置是不明智的选择。所以我们可以设计 dp[i][j][0/1] 的状态，其中第三维表示上一个位置是否被改变过，i 表示当前位置，j 表示之前已经变换过 j 次（要保证 j 时刻小于等于 k）。如果当前位置的 a[i] 已经是山谷点，则无需变换，否则可以考虑变换的转移方程，在 dp 过程中一直记录最大值即可。 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48938305 T2 交替 打表找规律题。易知最终的答案是由原来的数组乘以每一位对应的系数求和得到的，所以我们打表找规律，来看...

A 井字棋 总的情况数是 C(n,3)，n 是空位置的数量我们只需要统计 n，然后再枚举一下有多少种情况连成 3，就可以得到答案了。https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45914277 B 字符串魔法(easy) 答案会是形如 AAAA...AAAABBBB...BBBBAAAAA...AAAABBB...BBB 这样一段序列。此时我们将中间的 BBB...BBBAAA...AAA 使用魔法翻转，即可得到一段字典序不下降的序列。所以我们需要统计每一段 AA...AA 或者 BB..BB 的长度。最后枚...

总结 T2 初始题意有点问题，但是一开始就看到很多选手 AC，所以我就以为这个题没锅。后来仔细读了一下才发现会有一些奇怪的情况，这才改了题面，消除误解。赛前以为只是个简单签到，就没有多想这个题，实在抱歉。 T3 一些人没有拿满分，是忽略了 m<2 的情况，这时候还没有开除绩效拿 C 的人，最终答案要加上这些人。 A 面试 按题意模拟即可 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263530 B 纸牌游戏 如果当前有 Q 个人，且每个人的 都大于等于 Q-1，那么他们每个人都可以从其他所有人手中...

before the contest 我是本次比赛出题人鸡尾酒，由于水平比四糸智乃姐姐菜很多，所以出的题也会比她友好一些。在大学中打比赛的时候经常被打星的中学生吊打，深知中学生的强大，给中学生们出题确实是一件体力活，对于题目的不严谨指出还希望大家多多包涵。 ps：T3 是请四糸智乃姐姐帮忙出的，如果觉得毒瘤，请大家一起攻击她。 T1 GCD 20pt 直接根据题意算即可 40pt 我们发现，将 x 进行素因子分解，如果只能分解出一个素数 y，那么 f(x) = y。否则 f(x) = 1。 所以我们可以枚举每个素数，然后枚举它的次方，复杂度约为 O(nlogn) 100pt 我们还可以通过修改...