A十七边形   答案一定是r * r * ???的形式根据样例可以算出来答案是r * r * 3.07055416259080当然也可以用三角函数算。大概就是相似图形，或者是物理中的量纲分析。可以推断出面积和半径平方成正比。类比圆和正方形。     B首都   首先考虑一维的情况非常简单，答案就是中位数，然后如果n是偶数，那么中间的2个数字之间的数字都可以。对于二维的情况，如果是曼哈顿距离|x1 x2| + |y1 - y2|那么可以两个方向分别考虑。而这个是切比雪夫距离max(|x1 - x2|, |y1 - y2|)可以通过(x , y) -> (x + y, x - y)的方式，转...

A染色   我们把染色操作倒过来考虑，染色的定义就变成了：如果当前格子未被染色，就染上对应的颜色，否则不进行操作。下面W表示白，R(l,r)表示把l到r的格子染成红，B类似。 比如：我们进行了操作R(3,4),B(1,5),R(2,4)，最终的格子是BRRRB。倒过来考虑也就是：先进行操作R(2,4)得到WRRRW，然后进行操作B(1,5)，我们发现中间三个格子已经被染色，于是我们只改变第一个和最后一个格子得到BRRRB。最后进行操作R(3,4)发现已经全部被染色，于是我们什么都不做。 这里，由于操作序列里的操作可以不选择任何格子，我们可以认为被染过色的格子左右两个格子是相邻的，并把被染过色的...

A回文串   按照长度的奇偶性，回文串有两种类型： 长度为偶数的回文串 所有字母出现次数都为偶数 长度为奇数的回文串 除了最中间的字母出现次数为奇数 其他都是偶数  我们枚举最后得到的回文串的长度的奇偶性。如果是奇数，还需要枚举最中间的字母是什么。总共27种情况。 对于每种情况，由于最终每个字母的出现次数的奇偶性确定了，所以插入哪些字母也就确定了。 除了最中间的位置，将字符串左半边按照字母从小到大的顺序排序，右半边由左半边对称得来。       B闹钟   首先只有当N为奇数且K=0时无解，否则一定有解。 考虑对于每个学号的人，如何判断学号为x的人有没有可能成为单身狗： 设cntl=x-1为学...

A中国式家长2   题目大意   模拟一个挖脑洞游戏，判断行动过程是否合法，如果合法输出最终游戏结果   模拟   直接按题意模拟即可 在格子挖取后把周围的格子标记为开启，把当前格子标记为已挖取 注意一下行动力和悟性的计算方式 细心一点就可以满分了          B随机生成树 题目大意   有N个点从1到N编号，每个点有一个颜色 生成一棵树，每个点的父亲编号都是它的约数， 求树上最多有多少个同色联通块   题意转换   考虑题目中联通块的定义：联通块中任意两点间都有一条同色的路径 因此如果一条边的两端点颜色不同，那么这条边是不能经过的 因此我们可以考虑断开两端颜色不同的边，联通块数等于剩下...

A循环   题目大意   给一个循环语句 for (i = a; i op b; i += c) op为<=, >=或!= 求i += c执行的次数 或 判断死循环   做法   分类讨论 1、判断掉死循环的情况（既一开始条件为假，之后也不会为真） 2、判断掉一开始就为真的情况 3、除法计算答案 这题很简单，主要是要细心        B供给和需求   题目大意   给定若干个供给关系: 供给 = 价格 * c[i]        若干个需求关系: 需求 = max(0, a[i] – 价格 * b[i]) 价格是整数，求最小的 |总供给 – 总需求|    做法   1、常见的错...

A同余方程   首先可以把区间变成前缀，只需要考虑问题 和 的情况就可以了 如果 ，，不妨设 ，那么结果一定在区间 中，而 且每一个值出现了 次 对于更一般的情况，可以把 和 给表示成 log 段高位确定，低位随便放 的区间，然后两两之间统计答案       B旅游   相当于对每一条边设定一个 a[i] 表示通过次数，那么一个方案合法当且仅当 所有的 a[i] 都大于 0 切每一个点相邻的边的 a[i] 的和都是偶数 结论：只有最小生成树上的边的 a[i] 会 >1 证明：使用最小生成树上两点之间的路径一定是图中经过边权最大值最小的 路径可以直接得到 因此只需要求出最小生成树，然后在最...

A体积数   因为要求 b ≥ 2，所以 a 一定小于等于 n0.5，所以可以枚举 a 注意两点： 运算过程可能会爆 int 要去重（开个数组就可以了）       B故事王   大模拟题 每一个评委的给分有 n! 种，因此局面总数只有 (n!)m  枚举所有的情况然后统计就可以了 next_permutation 注意会爆 int      C二叉树  两个点 u 和 v 在先序遍历中的顺序只和 lca 有关：   1. 如果 u 是 v 的祖先，那么 u 一定在 v 前面（反过来同理）    2. 如果最近公共祖先 f ≠u,v，那么哪个在左子树哪个就先 因此随机交换中，对于第一种情况，不...

A中位数  • 对于第一档数据，可以枚举选取的合法的子区间，再重新排序， 直接得到中位数。时 间复杂度O(n^3)。 • 对于第二档数据，可以枚举子区间的左端点，依次往右增加新的数，现在要做的就是 往一个有序列表里加数，然后查询第k小的值。这个可以用平衡树维护。总复杂度就是 O(n^2logn)。 • 对于第三档数据，直接枚举最终可能的答案x。把数字>x的记为1，<=x的记为-1。检 验是否存在和>=0的区间。可以维护一个前缀和的前缀最大值。时间复杂度O(Mn)， M为不同的数的个数。   • 正解：发现第三档数据中的x其实是可以二分的。那么二分答案x，用上面的方法检验。 时...

A方差   题目大意    对一个长度为 𝑚 的序列，定义方差：  给定长度为 N 的序列 𝑎𝑖 ，对每个位置，求出删掉这个位置后，剩下元素的方差乘以 的值      解法  考虑：       由此易见，只需维护序列元素的和、平方和即可快速计算方差。 对一个序列，询问删掉每个元素之后剩下序列的元素和、平方和是容易完成的。     B分糖果  题目大意  N 个小朋友围成一圈，要给他们分一些糖果。 第 i 个小朋友最少拿到 1 个、最多拿到 a[i] 个。 问有多少种方案使得任意两个相邻的小朋友拿到的糖果数不同。 部分分做法  考虑 N 和 a[i] 均不是很大的情形，此时我们可以DP ...

A你好 a+b    输入2个整数a和b 保证输入的a和b在long long范围之内，即满足 -9223372036854775808 <= a, b <= 9223372036854775807 计算a+b的值，即这两个数字的和。 如果a+b在long long范围之内，即满足 -9223372036854775808 <= a + b <= 9223372036854775807 那么输出一行一个整数表示a+b的结果。  如果a+b不在long long范围之内，即越界了，那么输出"hello, %lld\n"，包含引号。      做法 编程...

A最长路   先考虑所有字符都相等的情况，相当于只用求以每个点为起点的最长路的长度。   对反向图进行拓扑排序，所有在环中的点最长路都是无限长，对于其他点dp，f_x表示以x为起点的最长路的边数，则   。特别的，若x没有出边，则f_x=0。      下面考虑所有字符互不相等的情况。  多记一个g_x，表示以x为起点的最长路的哈希值   则   其中y是所有满足f_x可以从f_y转移过来的y中 w_{x,y} 最小的那个。特别的，若x没有出边，则g_x=0。  下面考虑一般的情况。  我们需要快速比较两个方案的字典序大小。  注意到，处理到x时，前面的点的转移边都确定了，所以可以使用倍增+哈...

A金币 首先把[l,r]转化成[1,r]-[1,l-1] 从小到大枚举金币数i，记录当前剩余天数leave 当leave>=i^2时，将i^3加入答案，leave-=i^2； 否则将leave*i加入答案，并输出答案。 时间复杂度O(n^(1/3)) B网格 首先模拟求出s，然后枚举|s|次，每次把s最右的字符移到最左边，然后暴力比较和答案的字典序大小。 时间复杂度O(q*min(n,m)^2)C疏远度 先考虑给你一个集合，如何求。 然后把max的和通过暴力枚举每一个max的取值换成和的max：这里的w是一个k维向量，每一维都是-1或者1。 然后交换枚举顺序： 然后将x，y的贡献分开计算...

A. 动态点分治  • 求出现在 𝑙,𝑟 内的形如 的数 • 模拟题意就好了，注意一下 𝑘 = 1 或 𝑘 = 0 的边界 • 吗？ • 坑点：有可能 ，但是 𝑘𝑥 溢出了，溢出之后刚好又在 𝑙,𝑟 甚至 𝑥,𝑟 之间    • 应对措施：如果 ，则 break       B. 区间  • 找一个最长的区间，使得区间里存在一个数是区间里每个数的因数 • 三方四方暴力不讲了    • 平方暴力：枚举 𝑖，往两边扩展到不能扩展为止（60pts） • 注意到：如果 𝑖 的区间扩展到了 𝑗，那么 𝑗 的区间一定是 𝑖 的区间的子区间（因为 𝑗 是 𝑖 的一个倍数），...

比赛地址：https://www.nowcoder.com/acm/contest/167#question       A新个税   直接if判断就好，注意不要对负数收税。   事实上网上有很多计算新个税的工具，可以用来验算。        B二分之一   非常简单的高精度   或者   printf(“%.*f”, n, pow(0.5, n));   cout << fixed << setprecision(n) << pow(0.5, n) << endl;              C部分和     裸FWT，   for (int ...