思路 ∣i2−j2∣+∣ai2−aj2∣可以化为四种形式，取绝对值也就两种形式,因此我们只需要对i2−ai2以及i2+ai2排序，然后最大减最小比较即可。|i^2-j^2|+|a_i^2-a_j^2|可以化为四种形式，取绝对值也就两种形式,\\ 因此我们只需要对i^2-a_i^2以及i^2+a_i^2排序，然后最大减最小比较即可。∣i2−j2∣+∣ai2​−aj2​∣可以化为四种形式，取绝对值也就两种形式,因此我们只需要对i2−ai2​以及i2+ai2​排序，然后最大减最小比较即可。 代码 #include<bits/stdc++.h> #define int long long...

思路 看作无向图的时候，它是一个环，因此遍历每个点只有顺时针和逆时针两种。 所以先跑一次无向图的dfs确定顺序，然后在有向边的时候如果方向不对就加上其权值，得 到修改代价，答案取一个min就可以了。 代码 #include<bits/stdc++.h> using namespace std; const int N=105; int n,u,v,w,mp[N][N],vis[N],dfn[N],idx=0; vector<int>G[N]; void dfs(int x){ vis[x]=1; dfn[++idx]=x; for(auto to:G[x])...

思路 第一时间注意到了组合数，发现能过样例，然后就交了，果不其然wa了。 看这个数据也不像，于是还是考虑DP思路。（爆搜也不像，得20左右） 对于一个子树来说，它的构造方案数实际上就是左子树构造数×右子树构造上， 并且对于二叉树来说，左子树的节点数表示出来了，右子树也知道了，所以我们写出dp转移式 dp[i][j]=∑(dp[x][y]∗dp[i−x−1][j−y])%mod其中dp[i][j]表示树有n个结点m个叶子的方案数dp[i][j]=\sum(dp[x][y]*dp[i-x-1][j-y]) \% mod\\ 其中dp[i][j]表示树有n个结点m个叶子的方案数dp[i][j]=∑(...

思路 dfs的数据范围只能出到20左右吧，这道题肯定是要用记忆化思想的。 我们先处理一下每一位数字，将他们都模3，然后我们知道一个数能被3整除，那么每一位加起来就是3的倍数。 因此我们dp[i][j]表示前i位数字%3余数为j的方案数。首先我们子序列不选第i位必有dp[i][j]=dp[i-1][j]， 选了的话就继承dp[i-1][(j-ai+3)%mod]，然后这道题就解决了。 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #inc...

思路 暴力枚举，O(nm) 注意要等长，所以母串最多到n-m 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; //int read(){ int x=0,f=1;cha...

思路 考察容斥定理。质因子最多20个，所以我们可以状压一下，枚举每次选定因子的情况。考虑只有一个因子pri的情况下，1~m个数中总共由m/pri个，那么下一次选定两个因子p1,p2时，就要减去m/(p1*p2)个，加减取决于选定因子的个数。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; int n,m,pri[21],flag,res,ans=0; int gcd(int a,int b){return...

思路 对于每个节点来说，对答案的期望贡献都是其深度的倒数。因此，我们只要将每个点贡献累加就能得到最终期望。 用快速幂求每个贡献(1dep[i]\frac{1}{dep[i]}dep[i]1​)的逆元，再相加就是最终答案。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=998244353; //int read(){ int x=0,f=1;char ch=getchar();w...

思路 小老弟树产生的分数都是互质的，由于题目规定第n行产生的分子分母不超过n,而且经过简单推导可以猜测第n代可以表示出分子分母不超过n的所有互质对，那么我们就可以用欧拉函数来做。直接规定第n代产生的数就是欧拉函数的n行前缀和。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e6+7; const int mod=1e9+7; int pri[N],is_pri[N],phi[N],sum[N],cnt=0; void...

思路 我们普通求阶乘的时候，边乘边除质数，就可以保证不爆范围。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e6+7; //int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10...

思路 对数论初学者来说可能有点困难，但想通了会觉得相当简单。 我们考虑每个数是多少个数的约数，然后贡献到答案中即可， 那么对于n个数，数字p是n/p个数的约数，答案直接加上即可。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e8+7; const int mod=1e9+7; signed main(){ int n,ans=0; cin>>n; for(int i=1;i<=n;i++){...

思路 就是树链剖分+线段树的板子，但是因为眼疾看少了”多组数据“导致一直WA（哭了 不会的可以看一下我的这篇博客：https://editor.csdn.net/md/?articleId=121182009 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=6e4+7; //int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(c...

思路 数论分块模板，式子res=(res+n/i)的i枚举时会超时，注意到n/i的结果会有连续的一段相等，我们使用数论分块，直接返回每一段的答案。 对于常数n，使得式子[ni]=[nj][\frac{n}{i}]=[\frac{n}{j}][in​]=[jn​]成立的最大的满足的i≤j≤n的j的值为[n[ni]]i\le j\le n的j的值为[\frac{n}{[\frac{n}{i}]}]i≤j≤n的j的值为[[in​]n​],即[ni][\frac{n}{i}][in​]所在的块的右端点为[n[ni]][\frac{n}{[\frac{n}{i}]}][[in​]n​] 代码 #incl...

首先感谢TheOnlyMan为我们带来主席树的精彩讲解， 但说到底不管在不在线，本题只用普通的线段树就够了。 时间空间都更优秀。AC结果：287ms 42300KB 思路 先跑一个dfs（因为最近写惯了所以树链剖分没改回来），然后把树拍平去建线段树。 我们知道以x为根的子树表示的范围就是[dfn[x]+1,dfn[x]+sz[x]-1]，+1是因为不需要考虑根节点， 那么我们判断这个范围里面有多少个dis[p]-dis[x]>=k的点，然后把这个dis[p]累加起来即可， 如果有n个合适的点，那么我们就要减去n个dis[x]，因此，我们需要维护的信息为每个节点的距离和、距离最大值和距离最...

思路 01分数规划模板题。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f //#define int long long using namespace std; const int N=1007; const int mod=1e9+7; int n,k; double a[N],b[N],c[N]; bool check(double ans){ for(int i=1;i<=n;i++){ c[i]=a[i]-b[i]*ans; } sort(c+1,c+1+n); double res=0; fo...