简要的证明一下floyd算法的正确性.想必大家都做过旅行商问题(状态压缩).floyd就是暴力枚举了每个点的对整幅图的贡献.然后就是讲下这个题,这个题是个概率dp,因为要求最小.首先得明确dp所表示的含义.我们令f[i][j][0/1]表示我们学到了第i门课,我们用了j次机会,第j次的时候用了/没用的期望最短距离.转移方程就比较容易了.代码如下: #include <bits/stdc++.h> using namespace std; #define f first #define s second const int N=2e3+5; const int M=3e2+5; in...

一个简单的算法,0/1分数规划.具体就是二分. 分子是一些ai的和,分母是一些bi的和.假定我的值是满足要求且要扩大.那我们很容易得出ai-bi*x>=0. 那么就是我们按ai-bi*x排个序,删掉k个小的即可.#include <bits/stdc++.h> using namespace std; const int N=1005; const double eps=1e-5; int n,k; double a[N],b[N],c[N]; bool ck(double x) { for(int i=1;i<=n;i++) { c[i]=a[i]-b[i]*x; }...

水题?不解释.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+5; ll vis[N],d[N],a[N],cnt=0,n,m,ins[100],ans=0; vector<pair<ll,ll>>v[N]; void dfs(ll u,ll fa)//当前位子和它爸爸 { vis[u]=1; for(ll i=0;i<v[u].size();i++) { auto t=v[u][i]; //if(t.first==fa) ...

有些题你写多了或许就不觉得麻烦了,但是这题是我三天前拖欠的,一直不敢写..ε=唉,我对于100+的纯代码都有一种莫名的恐惧感.其实每个题也就那么几个过程.这题是用高斯消元解异或同余方程.并没有重点要讲的地方.代码如下: #include <bits/stdc++.h> using namespace std; const int N=305; const int mod=7; int a[N][N]; string s[7]={"MON","TUE","WED","THU","FRI","SAT","SUN"}; inline int gcd(int a,int b) { retu...

教我***儿子做题.https://www.acwing.com/problem/content/173/ 这个题的思路和这个题目是类似的.我们可以先进行排序,预处理k/2的种类存入一个数组..然后另外一半再进行dfs.这种做法很优但是对于这个题目来说.因为数据水,就不至于,但是还是写下. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=105; const int M=1e6+5; int k,m; int a[10]; int v[10][N]; ll ans=0; ...

这题不难,重要是理解吧..我发现自己越来越菜了.求任意四个gcd为1,并不好求,但是它的对立面就很明显了,就是有相同的约数.那么我们就可以分解每个数的约数,显然这是一个莫比乌斯函数.又或者说莫比乌斯函数和容斥关系很大,对于总的方案数挺显然就是C(n,4).对于每个数,我们先进行质因数分解,然后进行合成因数,对于2,3这样的因数,我们显然是-,而对于6来说,因为我们-了关于2的约数,又-了关于3的约数,我们就要+回来,具体来说就是个莫比乌斯函数.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ...

今天更完这题结束吧,明天多校爆零ε唉.(这题和前面3个题目.然后打多校的时候,每天更一篇就好了...4天结束数论.这题是个概率题,很简单的maybe.题目意思啥的都不解释了.直接上代码: #include <bits/stdc++.h> using namespace std; const int N=205; double dp[N][N][N<<1];//到了第几次,赢了几次,背包容量为多少. double p[N]; int a[N]; int n,l,k;//n次比赛,至少赢l次,初始有k的包包. int f(int x) { x=min(x,n);//节省容量...

不要我为啥更这题,因为这种题,代码简单,思路简单.dp:先讲讲错排公式,D[1]=0,D[2]=1.这个是初始值.下面讲讲转移方程:D[i]=(n-1)*(D[i-1]+D[i-2]).考虑把第n个元素放到任意一个地方,那就有n-1种放法,假定我放的位子为k,那么我k就有两种放法,第一种是放到n的位子,那就是D[i-2],第二种是不放到n的位子,那就相当于i-1的一个错排,D[i-1]. 数学:(容斥原理)总方案数为n!,放对一个位子的方案数是C(n,1)An-1,其中必定包含放对两个的方案数,C(n,2)An-2...容斥下去即可得到通项公式. 反演暂时不熟悉,以后再更~ 代码如下: #in...

今天带大家推一个简单的矩阵快速幂?教大家推比fbi难一点的矩阵...首先看a[i][j]=a[i-1][j]+a[i][j-1].其中n行(n<=10)m列(m<=1e9).我们可以观察到n很小对吧.这个题目是已知矩阵第一行的所有数都长23、233、2333这样.矩阵的第一列已经给出,那么就是看我们如何用第一列推出第m列了?(因为n很大,不可能用n推矩阵.)好了,我们继续观察递推公式,a[i][j]=a[i-1][j]+a[i][j-1].我们很容易知道,a[i][j]=a[i][0]+a[1~i][j-1].如此,我们就很容易推出矩阵了. f[i]={a1,0,a2,0,…,an...

异或线性基是一个集合可以通过异或表示原集合的所有数.线性基的贪心证明正确性(简要),假定1,4,5.我们可以选择插入1,4|1,5,显然插入4,5更优.简单的更下这个题题解.我们知道原nim游戏,假如堆数异或和为0且你现在动,那么你必输.我如何才能使得到这个东西呢?换句话来说,我们制造一个别人通过取或不取一堆得都不能使异或和为0则可以,那么我们只需维护一个最大的线性基即可.从大到小排序,然后套个线性基就好了.至于nim游戏?这就不用讲了吧..以后会做博弈论+dp专题的.maybe退役?代码如下: #include <bits/stdc++.h> using namespace st...

https://blog.csdn.net/fisher_jiang/article/details/986654 https://blog.csdn.net/maxichu/article/details/45458569

今天是个雨天,昨天玩了一天,混过了考试,今天什么都没做,好颓废.缺乏信念的人很能成功吧.今天一个好朋友高考考的挺好,为他开心.我又想到自己的高考,又十分悲哀,自己一定要把握自己的想法,不能太善变.不能改变自己的节奏.划水也得有划水的样子.

水题不解释.https://www.acwing.com/problem/content/99/做法相同不过换成了矩阵. #include <bits/stdc++.h> using namespace std; const int N=35; int n,m; struct vv{ int a[N][N]; }; vv add(vv nt,vv mt) { vv res; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { res.a[i][j]=(nt.a[i][j]+mt.a[i][j])%m; } } return r...

有注释 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll x,y; void exgcd(ll a,ll b) { if(b==0) { x=1,y=0; return; } exgcd(b,a%b); ll cx=x,cy=y; x=cy; y=cx-a/b*cy; } inline ll qp(ll a,ll b,ll mod) { a%=mod; ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1...