算法：基环树DP 这道题是我学完基环树后自己做出来的第一道题目hh，虽然调了很久 和这道题目有些类似的题目有IOI2008 Island 这题 https://www.luogu.com.cn/problem/P4381 下面来说这一题的思路： n点n边，任意两点之间都有一条双向边，因此这是一颗基环树，对于基环树DP的题目，我们首先做的应该是找到环并断开 1.找环 void dfs_s(int u,int fa){ st[u] = ins[u] = true; for(int i=h[u];~i;i=ne[i]){ //if(i == (from^1)) c...

Output ``` 74650554378.0 ``` Input ``` 1800 1314 1319 574444787 935 929 125284730 1210 1201 807712963 1 4 604191201 273 275 69920794 1798 1796 15301194 1422 1412 385233438 200 199 316142137 116 110 80383246...

做法1： 1.通过并查集维护连通性找出所有基环树的环的起点终点 2.对于每一个起点终点dfs不选这个点（和没有上司的舞会一摸一样的dfs），取max累加答案 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; //================================ #define debug(a) cout << #a": &q...

Time: O(n) Memory: O(1) int n; double s = 1.0 , p = 0.5; //================================= int main(){ n=read(); rep(i,1,n) s = (s + 1.0) * p + s * (1.0 - p),p = 1.0 * s/(i+2.0); printf("%.7lf",s); return 0; }

期望长度： ki=(ki−1+1)×pi k_i=(k_{i−1}+1)×p_i ki​=(ki−1​+1)×pi​ 期望分数： fi=fi−1×(1−pi)+(fi−1+2×ki−1+1)×pi f_i=f_i−1×(1−p_i)+(f_i−1+2×k_i−1+1)×p_i fi​=fi​−1×(1−pi​)+(fi​−1+2×ki​−1+1)×pi​ 于是可以写出： int n; double p[N],f[N],k[N]; void solve(){ //k[0] = 0; rep(i,1,n) k[i] = (k[i-1] + 1) * p[i]; //f[0] = 0;...

倒着推导 f[i][st]+=((pre[j]&st)==pre[j]?max(f[i+1][st],f[i+1][st∣(1<<j)]+score[j]):f[i+1][st])/k;f[i][st] += ((pre[j] \& st)==pre[j]?max(f[i+1][st],f[i+1][st|(1<<j)]+score[j]):f[i+1][st])/k;f[i][st]+=((pre[j]&st)==pre[j]?max(f[i+1][st],f[i+1][st∣(1<<j)]+score[j]):f[i+1][st]...

(f[st]+1)∗∑p[j]=∑jp[j]∗f[st∣(1<<j)](f[st] + 1) * \sum p[j] = \sum_{j} p[j] * f[st|(1<<j)] (f[st]+1)∗∑p[j]=∑j​p[j]∗f[st∣(1<<j)] 看不懂的话就展开来 #include<bits/stdc++.h> using namespace std; const int N = 21; int n; double f[1<<N],p[N]; //f[st]表示集齐st状态的卡的期望包数 void solve(){ ...

砍m个连接点即砍成m+1块，所以m再输入完后要++...可能是我态弱了，debug了好久...

链接：https://ac.nowcoder.com/acm/problem/111634 来源：牛客网 题目描述 Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score a and Lexa starts with score b. In a single turn, both Memory and Lexa get some integer in the range [ - k;k] (i.e. one inte...