共 6 篇文章
传送门 这是我做过最简单的 。 先考虑非法的情况。显然，如果n个缺失的骰子全置为6都不能使骰子值之和满足题设条件，这组数据就找不到合法答案。同理可得，n个缺失骰子全为1都不满足题设也是一种镜像情况。这样我们就得到了这道题的边界条件。 接着考虑合法解法。我们可以根据rolls数组之和与mean值计算出n个缺失数据的平均值，将这个值向下取整，就是每个缺失骰子的“最低值”。再依次给n个骰子分配点数，直到分完为止。这样就能依次得出合法的答案序列。 class Solution { public: vector<int> missingRolls(vector<int>& rolls, int mean, int n) { int m = rolls.size(); int tot = 0; for (auto roll : rolls) tot += roll; int idealSum = (n + m) * mean; if (idealSum - tot > n …
传送门 对于任意一个数，×10就能使它尾部多一个0。分析一下样例，n=5时n!=12345=120，其实就是134(25) = 12 * 10。即，产生一个末尾0的原因是累乘的数里能凑一个“10”出来。那么我们只需要统计相乘的n个数有能凑几个10就行。更进一步简化， 由于10=2*5，且固定的范围内，因子5总是比因子2要少。所以，可以直接统计所有累乘的因子里5的数量。 class Solution { public: int trailingZeroes(int n) { if (n == 0) return 0; /* * 对于任意一个数，×10就能使它尾部多一个0 * 分析一下样例，n=5时n!=1*2*3*4*5=120，其实就是1*3*4*(2*5) = 12 * 10 * 即，产生一个末尾0的原因是累乘的数里能凑一个“10”出来 * 那么我们只需要统计相乘的n个数有能凑几个10就行 * 更进一步简化， 由于10=2*5，且固定的范围内，因子5总是比因子2要少 * 所以，可以直接统计所有累乘的因子里5的数量。 */ int cnt = 0; for (int i …
传送门 思路 往位运算想就是想复杂了。根据题目意思，perm[i]的范围是[1,n]，且每个perm[i]不重复。这就意味着perm[0]^perm[1]^...^perm[n]是已知的。 假设： perm=[a,b,c,d,e]，encoded=[f,g,h,i]; 显然有： f = a^b; g = b^c; h = c^d; i = d^e; 我们再设已知的perm[0]^perm[1]^...^perm[n]=k，根据异或的性质：一个数异或自己得到0，任意一个数异或0等于它自己。所以我们可以用k去异或g = b^c与i = d^e来让k==a，这样我们就算出了perm[0]。再根据递推关系perm[i+1] = perm[i]^encoded[i]就可以算出整个perm。 代码 class Solution { public: vector<int> decode(vector<int>& encoded) { vector<int> perm; int a = 0; const …
传送门 题目大意 给定n,k，构造一个1-n的排列P，满足对于1-n中的每个i，P都存在一个长为i的子序列，并且每个子序列的和模n都余k。有解则输出任意P，无解输出-1。 思路 首先考虑判断解存在的问题。根据题意，因为P也是自己的子集，所以一定也应该满足“所有元素的和模n余k”的题设，也就是sum(1~n)%n==k，如果不满足，那自然无解。 假设k满足上述条件，接下来的命题就是判断k了。 这种看似要进行复杂的动态处理的问题大多都有规律，这题也不例外。多写两行数据会发现，当n为奇数时，sum(1~n)一定是n的整数倍，即k==0；n为偶数时，k==n/2。 根据这个写代码就好了。 ```cpp #include using namespace std; int n, k; int main() { scanf( "%d%d", &n;, &k; ); if ( n % 2 ) { if ( !k ) { for ( int i = 1; …
传送门 题目大意 有一个n 维向量空间，从这里面拿出n个01向量，设fn为选出的这n个01向量相互线性独立的概率，求 f1^ f2^...^ fn 的值。 思路 有n个向量，它们都线性无关，所以它们的空间秩也是n。每次随机的向量都会加入之前的向量空间，那么每一个向量都一定不属于之前的空间，则一共有2n个向量。 观察规律不难得到对于每个i，都有2i个向量线性相关，那么反之则有2n-2i个向量线性无关。那么有： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/image-1.png 递推计算出每个f就行了。 ```cpp #include using namespace std; typedef long long ll; const int N = 2e7 + 10; const ll MOD = 1e9 + 7; const ll INF = 500000004; …
传送门 题目大意 游戏地图可以解释为一个无穷大的矩形网格。在每个格子里，你可以安放一台金矿，或者是一部圣水采集器，又或者是大本营。你也可以把一些格子留成绿色，充满生机。然而，存在一个限制：一个大本营必须紧挨着至少一个金矿和至少一个圣水采集器。请让你地图中的大本营数量尽可能地多，并输出它在地图中的占比。 思路 赛时这题卡了很久，最后队友的答案因为精度问题就差了0.000001，属实倒霉。 情况其实挺好想的。让金矿与圣水采集器相间排布，任意的一台金矿与一部圣水采集器都不相邻，大本营插在它们之间。 ```cpp #include using namespace std; int main() { printf("%.6f", 2.0 / 3); return 0; } ```