上面的公式可以直接高斯消元。

题目链接：题目大意：这题是Light Oj 1027的加强版,1027那道是无记忆的：https://blog.csdn.net/qq_21433411/article/details/89842819。题意： 有n扇门，每次你可以选择其中一扇。xi为负值的门带你abs(xi)后又回到原点。xi为正值的门则带你离开迷宫，并且你会记住你前面选择的K道门，在下次选择的时候不会选择这些门。选择每扇门的概率相等。求走出迷宫的时间期望值。 思路：如果k=0就是上面那道题。如果k！=0，我们知道前面k道门一定是xi<0的。那么我们可选择的门和k相关。 #include<bits/stdc++...

题目链接：https://vjudge.net/contest/76505#problem/Q题目大意：有1个球，进球的概率为p，连续不进k1个球或者连续进k2个球游戏结束。问投球的期望次数。ps:上面写的应该是ans=p * f[1]+q * g[1]+1 #include<bits/stdc++.h> #define LL long long #define DB double using namespace std; int main(){ int T, cas=1; scanf("%d", &T); while(T--){ ...

题目链接：https://vjudge.net/contest/76505#problem/M题目大意：给定一张无向图，每条边都有一个通过的概率 ，如果无法通过，那么就要回到起点重新出发从起点到终点的时间固定为K，如果成功到达，又需要额外花费K的时间，问走S次的最小期望时间思路：我们知道s次是独立的。并且每次如果成功到达用时是2k。如果成功到达的概率为p。那么期望就是s2*k/p。我们只要知道从1-n的最大概率。类型最短路。floyd()把松弛条件改一下就可以了。 #include<bits/stdc++.h> #define ll long long using namespac...

题目链接：题目大意：有n个城市，编号为0~n-1，有m条有权无向边，有个小偷从编号为0的城市出发，他不会走已经走过的城市，他有2种决策：①停留在这个城市5分钟；②如果城市i与现在所在城市相邻，且能在走到i后还能把剩下的城市遍历，则称i为EJ。在当前城市如果有cnt个EJ，那么他选择走向每个EJ的概率和停留在该城市的概率均为1/(cnt+1)求小偷遍历完城市所需时间的期望值(1 ≤ n ≤ 15)思路：我们预处理cnt[s][u]：访问的城市状态为s，如果去城市u能不能访问完所有剩余的城市。然后记忆化状压DP就可以了。预处理cnt[s][u]也需要记忆化。 #include<bits/st...

题目链接：https://vjudge.net/contest/76505#problem/I题目大意：一个答案文件有n行输出，每行是YES或NO，现在给出文件的总字节数s，YES占3字节，NO占2字节。要求你输出1个文件，且第一行一定是YES，接下来第i行的内容是答案文件第i-1行的内容，问输出正确行数的期望。 思路：因为第一个一定是YES正着不好DP。我们用f[i][j][k]:前i个还有j个YES没有出现，并且i+1的猜的是k的方案数。 #include<bits/stdc++.h> #define ll long long using namespace std; dou...

题目链接：https://vjudge.net/contest/76505#problem/G题目大意：给一个质地均匀的n的骰子， 求投掷出所有点数至少一次的期望次数。思路1：DP思路2 几何分布+全期望公式： #include<bits/stdc++.h> #define ll long long using namespace std; double f[100005]; int main(){ int t, cas=1; scanf("%d", &t); while(t--){ int n; scanf(&qu...

题目链接：https://www.luogu.com.cn/problem/P2048题目大意：思路：我们考虑把所有满足条件的区间加入优先队列。显然是不可行的。我们定义：MAX(o, l, r): max{(sum[t]-sum[o-1]), l<=t<=r}即以o为左端点，右端点范围是 [l, r]的最大子段,因为o是确定的，那么sum[o-1]也是确定的，所以求sum[t]（l<=t<=r）就可以了。这里用rmq就可以了。 我们处理出1<=o<=n的MAX(o, l, r)并且加入优先队列。那么满足条件的区间最大值一定在优先队列中，那我们ans+q.to...

题目链接：https://ac.nowcoder.com/acm/contest/6112/E?&headNav=acm题目大意： #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> #define LL long long #define mid (l+r>>1) using namespace std; const int N=1e6+7; LL INF=0; inline int read(){ int x=0,f=1; ...

题目链接：https://codeforces.com/contest/1373/problem/F题目大意：有n个环形城市。每个城市对网络的需求数是a[i]。每个城市都可以修建网络塔。提供b[i]个网络。在b[i]修建的网络塔只能供a[i], a[i+1]使用。现在问是否通过合理的分配可以满足所有城市的网络需求。思路：我们假设b[n]给a[1]分配了x个。如果x小了。导致[1, n-1]中间发现不够用. 如果x大了。发现在b[n]处不够用。那么就可以对x进行二分了。 #include<bits/stdc++.h> #define LL long long using namesp...

题目链接：https://ac.nowcoder.com/acm/problem/14699题目大意：思路：一眼题直接背包：f[i][j][k][w]:前i个单位选择j个人，k件装备，cont==w的最大ATK。 #include <bits/stdc++.h> #define ll long long using namespace std; int a[1005], C[1005], f[605][7][7][205]; int main(){ int n, m, d; scanf("%d%d%d", &n, &m, &d)...

题目链接：https://ac.nowcoder.com/acm/problem/111125题目大意：有一个地图有1，2，3个阵营。现在要修建路让1，2，3可以连接起来。如果地图是'1','2','3'这个单元格不用花费。'#'：不可以修建， '.'：费用为1.现在问最小费用是多少？ 思路：我们知道一定是在地图上一个格子上汇合。枚举这个格子。dis1+dis2+dis3。如果这个格子是'.'有两个阵营在这个单元多修建了需要-2。 dis：用01bfs就可以了。 #include<bits/stdc++.h> using namespace std; char s[1005][1...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4687题目大意：有n个女孩。有m个候选组合。每个组合只有2个人。一个女孩可能属于零个或多个候选组合，但一个人只能注册为一个正式组合的成员。主办方希望今年能有尽可能多的正式组合参加。在这些限制下，某些候选组合实际上是多余的，因为只要必须最大化形式组合的数量，就不可能将其注册为形式组合。（就是就是这个候选组合不可能存在任意一个最大化形式组合方案中）思路：我们先跑个最大匹配ans。然后枚举每条边u-v。如果假设这条边已经匹配。那么所有g[u][i]=g[i][u]=g[v][i]=g[i][v]=0。然后...