链接：https://vjudge.net/contest/401586#problem/B辗转相减法：https://www.cnblogs.com/HuangWj/p/11261870.html这样去想：假设最后答案为T，也就是所有数都为T。那么一开始任何一个数X都可以写成TTTT...的形式，跟据辗转相减法我们知道这样减完的T就是最大公约数。因此答案也就是求所有数的最大公约数。代码不放了

链接：https://vjudge.net/contest/400607#problem/I思路：思路还是很简单的，要么把所有的防卫都打掉，要么留下所有的防卫。剩下就是些细节问题啦代码： #include<bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5+7; inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} ...

链接：https://vjudge.net/contest/400848#problem/D注：a/2向上取整就是(a+1)/2代码： #include<bits/stdc++.h> using namespace std; const int maxn = 2e5+7; char s[maxn]; int a[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n)...

思路：这道题首先是求关于路径的情况，我们需要直到用题目中已知所有的WL，为了求出最终的期望，我们应该求出每一个L的概率Pl,这是对某个路径长度的全部情况在树上求解，显然是用点分治处理。用母函数的角度来考虑f(x)=a0x^0+a1x^1+a2x^2+...+an-1x^n-1，a是概率以u为当前根结点，f(x)中x^i是经过当前u且到u距离为i(i > 0)的点分布在子树中的概率，f(x)*f(x)可以得到经过u的两条长度为j，k，(j+k==i)的线路合并为长度为i的，也就是一条距离为i的路径在子树中的概率。按照点分治的思路，当前u为根结点，只算经过u的路径，所以去掉两端点在同一颗子树...

链接：https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_d思路：分为x轴和y轴来进行组合考虑1.如果x轴A,B不相交，y轴随便的话假设A在左，B在右，我们考虑AB在x轴上有哪些情况，怎么算呢？b现在在最右边，a向右移动有n-a-b+1种方式，b向左移动一个，a向右移动有n-a-b种方式，...,直到a向右移动只有一种方式。这是一个等差数列，跟据求和公式，答案为(n-a-b+1+1)(n-a-b+1)/2那么A如果在右，B在左，也是同样，故答案要乘2。考虑y轴，A有(n-a+1)种放法，B有(n-b+1)种放法，那么总共有(n-a+1)(n-...

链接：https://vjudge.net/contest/400607#problem/D突然想起来概率里面还有一个概率dp，这个之前确实学的不扎实，通过这道题回顾一下。题意：打一局游戏的胜率是p，初始开箱爆率是q=2%，每打一局游戏如果赢了，可以开箱，如果没开中，开箱爆率会加2%（最大为100%）。如果游戏输了，开箱爆率为加1.5%，求开中箱需要玩多少局游戏的期望。解法：这是一道期望dp，期望dp一般来讲是逆推设dp[p][q]为胜率为p，开箱率为q的局数的期望。注：因为dp的下标都是整数，会出现1.5这种的话，我们让q为1000考虑一下状态转移方程：dp[p][q] = 1.0 + dp...

思路：先复习一下三角形全等条件，SSS,SAS,AAS,ASA分析题目，可以分为一下几个情况1.3条边2.3个角3.1个边2个角4.一个角2个边1只有1种，2有无穷种，3有AAS和ASA都只有一种，4有SAS和SSA两种，特判一下SSA的情况就行。然后再考虑一下构不成三角形的情况。 #include<bits/stdc++.h> #define eps 1e-8 using namespace std; const double pi = acos(-1.0); int g[5], s[5]; bool SAS() { int sum = 0; for(int...

思路：fx表示1-x的排列对于前(pi<x)的限制都满足，但是不满足x的限制条件的个数。fx初始为n！现在要去掉不合法的，为了避免重复计算,应该减去所有pi的贡献，即fpi(n-pi)!。*代码：** #include<bits/stdc++.h> #define int long long using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); const int mod = 20000311; int n, m; cin >&...

链接：https://vjudge.net/contest/399982#problem/D思路：其实就是个枚举，想明白的话就很简单，想不明白就会绕进去。题目其实很简单，就是考虑怎么通过向右向上走能出去，且走的次数最小。参考题解的枚举方式：在有效的监控中枚举，考虑横坐标差为x的监控向上走y步能够逃离。然后再来枚举向右走1e6-0步，能走出去的向上+向右走的最小值为多少。向右走的步数从大到小枚举过程中，比如向右走了x步，那么小于x的都会通过向右移动来出去，而大于x的则还需要结合向上才能移出去，用mx来维护后面向上移动的最大值即可。 代码： #include<bits/stdc++.h&gt...

快速傅里叶变换(FFT) 作用：加速多项式乘法 朴素高精度乘法时间O(n^2),但FFT能O(nlog2n)的时间解决 前置知识： 1.点值表示法： f(x)={( x0,f(x0) ),( x1,f(x1) ) ,( x2, f(x2) ), ( x3, f(x3) ), ( x4, f(x4) ), ... , (xn-1, f(xn-1) )} g(x)={( x0,g(x0) ),( x1,g(x1) ) ,( x2, g(x2) ), ( x3, g(x3) ), ( x4, g(x4) ), ... , (xn-1, g(xn-1) )} 设它们乘积为h(x)，那么 h(x)={(...

链接：https://ac.nowcoder.com/acm/contest/7817/H原字符串与新字符串的字符构成一对，那么如果A-A这种就不需要换，若形如A-B就和B-A交换，但如果没有B-A呢？系统的归一下类：A-A 0次A-B B-A 1次A-B B-C C-A 2次A-B B-C C-D D-A 3次for循环搞定，暴力，没做出来实在反思自己，太愚蠢了！。代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define mk make_pair const int maxn = ...

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6155思路：考虑构造dpdp[i][j]表示前i个，以j为结尾的不同子序列有多少个。如果第i个是1，那么dp[i][1]=dp[i-1][1]+dp[i-1][0]+1,dp[i][0]=dp[i-1][0]如果第i个是0，那么dp[i][1]=dp[i-1][1]dp[i][0]=dp[i-1][1]+dp[i-1][0]怎么去想？第i个为1，就把前面i-1个得到的序列都在末尾加上s[i]，那么会导致，没有1这个单独的序列了，(原来的1变为了1,1)那么+1即补上。这是一个递推式子，那么我们自然可以写...