题目链接：https://ac.nowcoder.com/acm/contest/5672/A题目描述：求在一个半径r的圆内整点上放置n个人，使得两两距离和最大。(n<=8 r<=30)解题思路：考虑dp打表，状态dp[i][j][k]为放置i个点，横坐标和为j，纵坐标和为k的每个点和圆心的的距离的平方和的最大值。为什么这样dp?把题目中的公式先写出来：由于减法不好维护，我们尝试转化为加法：我们可以单独来看前面的xi^2+xj^2+yi^2+yj^2，它们可以写为(xi^2+yi^2)+(xj^2+yj^2)这个累加也就是在求所有的两两组合，每个出现n-1次，比如a、b、c，它们的...

链接：https://www.luogu.com.cn/problem/P1337模拟退火算法学习参考：https://www.cnblogs.com/flashhu/p/8884132.htmlhttps://99nl.blog.luogu.org/guan-yu-mu-ni-tui-huo-di-xue-xi-bi-ji思路：模拟退火适用的问题通常是一些求最优解的问题比如把问题抽象地看成一个长得毫无规律的函数，而最优解就是函数的最低点。  模拟退火过程简要概述：我们给一个初始解x，并让它不断变动。要模拟变动的大小随温度的降低而降低，我们每次的delta x应该在一个大小与T成正比的范围内随...

Blow up the Enemy题意：爸爸和儿子玩游戏，每个人只能从n个武器中选择一种战斗，每种武器还有两个属性，一个是伤害A，另一个是两次使用的时间间隔D，爸爸的武器随机选择，儿子想赢得比赛，替他选一种武器，求最大的获胜率。思路这题很简单，在时间相同的情况下打出的伤害最先到达100就是最好的武器，爸爸能赢就只能选择最好的武器中一把，能赢的概率再乘上50%，主要值得注意的是怎么算伤害达到100所花费的时间：((100+a-1)/a-1)*t这里需要学的小技巧是小数取整的时候如何进1加上a-1是为了如果还有剩余不到a的生命值，最后小数取整需要进1，如果刚好打完了生命值，加a-1也不会对答案有影...

链接：https://ac.nowcoder.com/acm/contest/5672/B题意：n * m个口罩，装最少的箱，使得在个数平均的情况下，既能分箱分给n个医院，也能分给m个医院。思路：我们当然要从n，m中最小的那个考虑，所以考虑装口罩最多的盒子，显然不能超过n，不然人数在m的时候这盒子分不出去了。不妨设(n<m)继续考虑字典序最大，医院数量为n的时候需要给每个医院安排m个口罩，贪心的思考，我们可以先给前n个医院各n个口罩，然后还剩nm-nn个，剩余的这些既要能组成(m-n)个n，也要能组成n个(m-n)，那么问题就变为了有nm-nn个口罩，如何分使得既能分箱给m-n个‘医院’...

链接：https://ac.nowcoder.com/acm/contest/5672/H题意：正整数二元组Legend Tuple(n,k)是这样定义的 (1,k)总是Legend Tuple 若(n,k)是Legend Tuple，那么(n+k,k)也是 若(n,k)是Legend Tuple, 那么(nk, k)也是统计有多少个Legend Tuple(n,k)满足1<=n<=N, 1<=k<=K, 其中N，K是不超过1e12的整数思路：看也看不出来什么，这种题就是写写找找规律。能看出只有ak和ak+1满足题意(a是任意整数)，当k=1的时候会有重复以外，ak和a...

题目链接：https://ac.nowcoder.com/acm/contest/6488/B题目大意：给一个数判断是否个完全平方数对1000取模得到的。解题思路：若x是由(kk)%1000得到的即x=(k%1000 * k%1000) % 1000只要取遍0-999的全部数就可知道可以所有取到的x值了。*代码：** class Solution { public: /** * * @param x int整型 * @return bool布尔型 */ bool solve(int x) { for(int i = 0; i <= 999; i++) { if(i * i % 1000 ...

题目链接：https://ac.nowcoder.com/acm/contest/5670/D题目大意：Miyako想通过Drop-2和Invert两种操作把一个给定的排列变成1，2，...，n，连续做任何次数的Drop-2是一个multi-drop，求需要多少次multi-drop Drop-2操作可以把p-1位放到首位Invert操作可以把第一位放到最后 解题思路：每次操作还是通过环来想。两种操作就是整体在转圈圈和前n-1项在转圈圈我们思考一下操作的意义，Invert操作不必多说，Drop-2操作让前n-1项转圈相当于在调整pn和其他的相对位置关系。我们只需要相对位置是1，2，...，n就...

题目链接：https://ac.nowcoder.com/acm/contest/5670/E题目大意：求可以通过这个函数排好序的排列个数。这个的shuffle实现的功能就是让a[i] = b[p[i]],把原来p[i]位置的a放到i位置。我们画个图来看看。我们可以把这个环想象为一个在转圈圈的传送带，1，2，3...,n通过这个环的转动来生成的排列都可以再通过环的转动来转回1，2，3...n，也就是说我们要去求这些置换的循环节。每次转的时候是所有环一起转，因此转lcm次才能转回最开始的样子。这题在代码实现上：1.需要考虑怎么去考虑这个环。2.因为很多个数的lcm最后可能很大，因此还需考虑如何求...

题目描述：在保证所有叶子节点都挂礼物(礼物总数为L)且二叉树的高度不超过H的情况下，二叉树最多能有几个结点？解题思路：这道题从叶子结点的个数来入手，因为最后我们的二叉树显然是H的高度，我们不妨一层一层的来看，如果当前层的叶子结点小于等于礼物数量的话，就加上这一层，如果当前层的叶子结点数目大于礼物数量的话，这一层只能由L个，后面的(H-i)层也只能由L个。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll T, H, L, cnt = 0; cin >&gt...

题目描述：从(x,0)开始，每次的操作就是都把多的那个复制一下加给少的那个，做了N次操作后，会产生bug，即多的那个会+y，后面不会再出现bug，问M次后，两个数的gcd是多少。解题思路：这种叠加的题目首先考虑一下斐波那契数列。这道题写写样例就知道确实是关于斐波那契数列的。加了y以后，关于y的系数也是斐波那契数列。但是n和m的范围都特别大，会爆longlong。于是你想用个大数模板，结果居然超了内存。最终，你不得不向打表势力低头，于是你发现i>=n的所有gcd都相同。代码： #include<bits/stdc++.h> using namespace std; typede...

题目链接：https://ac.nowcoder.com/acm/contest/5670/I题目大意：大本营(H)必须与一个gold miner(G)和一个elixir collector(E)相邻，f(n,m)表示在nm的方格中能最多放多少个H。问n->∞， m-> ∞时，f(n,m)/nm 的值是多少。解题思路：一开始尝试了打表找规律，wa了一发。后来从无穷入手考虑了几何意义。反正我们要求无限大的一个平面的这个值，考虑时候能找到一种单位块来填充整个平面。这样我们只需让单位块的值越大越好，也就是考虑这样一个式子：H/(H+G+E)，从贡献的角度来考虑，一个G对上下左右都有贡献，...

题目连接：https://ac.nowcoder.com/acm/contest/5670/F题目大意：i号玩家对敌人的伤害是di,跟据公式来模拟图表。解题思路：水题，模拟。代码： #include<bits/stdc++.h> using namespace std; int d[110]; map<int, int> memo; int main() { int n, maxd = 0; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d",&d...

题目链接：https://ac.nowcoder.com/acm/contest/5671/K题目大意：一个由一些1-n的排列组成的数列称为k-bag。比如1，2，3，2，1，3，3，2，1就是一个k-bag。部分k-bag是k-bag的一个子串，现在给一个长度为n的数列，判断是否是一个部分k-bag。解题思路：参考sunsetcolors的解法：https://blog.nowcoder.net/n/1cf39334dfea43339767441bc1e836b6跟据题意能想到，满足条件的序列，我们不管头和尾，中间一定要是几个k排列摆放的过程。但是我们并不清楚，头和尾在什么位置结束。因此我们...

题目链接：https://ac.nowcoder.com/acm/contest/5671/B题目大意:随机生成n个n维{0,1}组成的向量，它们线性无关的概率记为f(n)求解f(1)⊕f(2)⊕....⊕f(N)解题思路：由于这N个向量线性无关，则这N个N维向量组的秩为N，考虑每次将随机生成的向量加入之前向量组中，那么最后N个向量线性无关当且仅当每次加入的向量都不属于之前的空间。那么每次可以将随机生成的向量加入之前的向量组中的概率是(2^N-2^i)/2^N, 分子可以这样理解：2^N是所有的情况，2^i是所有在之前的向量组(空间)的情况。从而推出f(N)的公式。但N是2e7啊，会超时。虽然...