树的直径 题解  树的直径 树的直径的定义:图中两个叶子节点的最长距离 定义d1[i]d1[i]d1[i]表示以iii为根节点到叶子节点的最长距离 定义d2[i]d2[i]d2[i]表示以iii为根节点到叶子节点的次最长距离 定义mp[i][j]mp[i][j]mp[i][j]表示从iii到jjj的距离 若ververver为fafafa的子节点，动态转换方程可以写成： d1[fa]<d1[ver]+mp[fa][ver]：d2[fa]=d1[ver],d1[fa]=d1[ver]+mp[fa][ver]d1[fa]<d1[ver]+mp[fa][ver]：d2[fa]=d1[ve...

结论：从高位计算，第一个不相同的之后全部为111 假设lll,rrr在第iii位开始不相同，iii位之前的异或之后全为000，之后的我们可以保证凑成不一样的，异或之后全部位111。这样我们的结果就是从iii开始往后全为111的二进制，将二进制转换位十进制输出即可。 AC代码 #include <bits/stdc++.h> using namespace std; void dilingtian() { long long l, r; cin >> l >> r; int i; for (i = 63; i >= 0; i--) if ((l >...

玄学做法： 打表找规律：    名称 缩写     a0a_0a0​ 1   a1a_1a1​ 3   a2a_2a2​ 8   a3a_3a3​ 20   a4a_4a4​ 48   ... ...   ana_nan​ 2∗an−1+2n−12*a_{n-1}+2^{n-1}2∗an−1​+2n−1     根据递推公式：an=2∗an−1+2n−1a_n=2*a_{n-1}+2^{n-1}an​=2∗an−1​+2n−1 可以得到：an=n∗2n−1+2na_n=n*2^{n-1}+2^{n}an​=n∗2n−1+2n 逻辑做法: 注：10n2{10_n}_210n​2​表示二进制写法，...

错误版本 本题可以理解为矩阵上的单源最短路径，因为数据不是很大，我们可以使用BFS进行搜索PLMM和猫到达图中所有点的最短路径。但是题目加上了附属条件，PLMM走的步数是有限的，而且猫的嗅觉也是有限的。所以我们可以求完最短路径之后，找到一个可以同时满足两个要求的点，如果可以找到，则更新答案。不能则输出-1。 bug样例： 5 3 1 2 P.. .*. *.. M.. ... (感谢大佬补充数据） #include <bits/stdc++.h> using namespace std; int n, m; int r, l; bool vis[2000][2000]; int a...

异或规则：只有同时出现1才结果为1，其他的全为0。 即：1&1=1 1&0=0 0&0=0 ∏i=1n∏j=1nAi\prod_{i=1}^n\prod_{j=1}^nA_i∏i=1n​∏j=1n​Ai​&AjA_jAj​ 式中AiA_iAi​&AjA_jAj​的结果是Amin(i,j)A_{min(i,j)}Amin(i,j)​ 所以我们根据二进制的规则进行暴力乘法即可 AC代码 #include <bits/stdc++.h> using namespace std; const long long mod = 998244353; in...

三的倍数判断条件：数位相加的和是否为三的倍数 证明： abcabcabc =a∗100+b∗10+c=a*100+b*10+c=a∗100+b∗10+c =a∗99+b∗9+a+b+c=a*99+b*9+a+b+c=a∗99+b∗9+a+b+c 显然，a∗99+b∗9a*99+b*9a∗99+b∗9是3的倍数，那么只需要判断a+b+ca+b+ca+b+c是否是3的倍数即可 即：∑i=1n10i−1∗xi≡∑i=1nxi(mod\sum_{i = 1}^n{10^{i-1}*x_i}≡\sum_{i=1}^n{x_i}(mod∑i=1n​10i−1∗xi​≡∑i=1n​xi​(mod 3)3)3...

贪心： 假设如果有两头牛，往返的时间分别是tit_iti​，每分钟摧毁的花是did_idi​。 那么我们可以得出： 1.先牵第一头牛，消耗的总数为t1∗d2t_1*d_2t1​∗d2​ 2.先牵第二头牛，消耗的总数为t2∗d1t_2*d_1t2​∗d1​ 我们使第一种情况消耗总数最小，可以列出t1∗d2<t2∗d1t_1*d_2<t_2*d_1t1​∗d2​<t2​∗d1​。 我们根据这个条件排序，再从头模拟就可以得出答案。 如果只考虑ddd，那么我们可以根据上面的假设判断出，这是错误的想法。 如果t1=2,t2=3,d1=1,d2=2t_1=2,t_2=3,d_1=1,d_...

本题是找一个最大面积的矩形，图形是不能变换的，所以我们只需要先确定左右区间，再得到本区间的最小高度便可得到面积。我们可以通过栈的特点，确定第i个位置上的左端点和右端点，高度为h[i]。h[i]。h[i]。 当我们遍历到第i个位置时，我们以h[i]h[i]h[i]为矩形高度，对于左右端点而言，增加高度大于等于h[i]h[i]h[i]的小矩形只会增大面积,而两端小的矩形在之前已经计算完毕，所以不需要更改高度思考要不要加入。记录好左右两端的端点后，计算面积，更新最大值即可。 #include <bits/stdc++.h> using namespace std; using ll = ...

这是一个计算概率的问题，最直接的做法是将满足条件的情况数算出，除以所有情况。观察到本题的数据nnn只有30，所以所有情况最多只有4304^{30}430种，即260<2642^{60}<2^{64}260<264。 方法一：时间复杂度（N5N^5N5） 题意中说只有四种牌，我们进行四层遍历，每层遍历代表每种牌的个数，当这些牌的总数为nnn时，我们对其进行排列组合，如果这些牌的价值大于成本，我们就计入分子中，不论分子是否增加，本次排列组合必须加入分母中。 AC代码 #include <bits/stdc++.h> using namespace std; using...

本题不可以采用dfs爆搜，极其容易TLE，因为时间复杂度大致为:4M4^M4M,而M的大小为120，即使在运算过程中达不到4M4^M4M，但是也远远大于10710^7107，所以我们应该使用动态规划。题目中说只有四种牌，这个是可以利用的条件。我们dp的状态表示每张牌已经使用了多少张，我们根据使用的牌数算出向前移动了多少格，再将上一个状态加入，便可算出最大答案。 #include <bits/stdc++.h> using namespace std; using ll = long long int; using ull = unsigned long long int; usin...

欧拉筛 题解  欧拉筛 欧拉筛法可以在线性的时间复杂度里筛出N以内的所有质数 vector<long long> oula(long long n) { vector<long long> prime; vector<bool> vis(n + 1); for (int i = 2; i <= n; i++) { if (!vis[i]) prime.emplace_back(i); for (int j = 0; j < prime.size(); j++) { if (prime[j] * i > n) break; vis[prime...

有 n 件货物， 第i件重wiw_iwi​吨，另有 x 个集装箱，每个集装箱可以装重量不超过 W 吨的货物。 货物不能分拆，请判断这 x 个集装箱能否装下所有货物。 n的数据很小，所以可以考虑爆搜 AC代码 #include <bits/stdc++.h> using namespace std; using ll = long long int; using ull = unsigned long long int; using pll = pair<ll, ll>; const ll mod = 1e9 + 7; long long n, x, W, w[25], ...

求解:∑l=1n∑r=lnwr−l+1∗∑i=lrai\sum_{l=1} ^n \sum_{r=l} ^n w_{r-l+1}*\sum_{i=l} ^ra_i∑l=1n​∑r=ln​wr−l+1​∗∑i=lr​ai​ 定义：si=∑j=1iaj,sumi=∑j=1isjs_i=\sum_{j=1} ^i a_j ,sum_i=\sum_{j=1} ^i s_jsi​=∑j=1i​aj​,sumi​=∑j=1i​sj​ ⟹\Longrightarrow⟹ ∑l=1n∑r=lnwr−l+1∗(sr−sl−1)\sum_{l=1} ^n \sum_{r=l} ^n w_{r-l+1}*(s_r-...

快速幂 排列组合 容斥原理及二项式反演 题解  快速幂 对于一个数的次幂，如:2102^{10}210。最常规的计算方法是将2乘以10次，时间复杂度为：O(NNN)。 如果我们将它写成二进制:2101022^{{1010}_2}210102​，很自然的可以分解成2100022^{{1000}_2}210002​与21022^{{10}_2}2102​两个数相乘，即：28∗222^{8}*2^{2}28∗22。这样，我们可以在计算282^828时使用已经计算完毕的242^424，所以我们只需要将底数不断的平方就可以计算出答案，时间复杂度:O(log2Nlog_2Nlog2​N)。 long lo...