CF
Problem - 839C - Codeforces（DFS）（1500）（期望）
求期望dp
即求1的（所有孩子的期望+1）的和，除以孩子数量
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=1e5+10;
double dp[N];
vector<int> e[N];void dfs(int u,int fa){int cnt = 0;for (int i = 0; i < e[u].size();i++){int v = e[u][i];if(v==fa)continue;dfs(v, u);dp[u] += (dp[v] + 1.0);cnt++;}if(cnt)dp[u] /= (double)cnt;
}int main()
{int n,u,v;cin >> n;for (int i = 1; i < n;i++){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}dfs(1, 0);printf("%.15lf", dp[1]);
}
flag
等字符串专题学完，数论整理好之后，就去学期望dp（kuangbin）！！！
【原创】概率DP总结 by kuangbin - kuangbin - 博客园
Problem - 1789C - Codeforces
这题要求m+1个数组，两两拼接后，不同元素的数量
思路是求出m+1个数组中，每个数字x，cnt[x]的值
然后计算
- 含x的和和不含x的结合
cnt[x]*(m+1-cnt[x]) - 两个都有x的结合
cnt[x]*(cnt[x]-1)/2
对
cnt[x]的计算，用前缀和的思想
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL a[N], cnt[N*2];void solve()
{int n,m,p,v;LL ans = 0;cin >> n >> m;for (int i = 1; i <= n+m;i++){cnt[i] = 0;}for (int i = 1; i <= n; i++){cin >> a[i];cnt[a[i]]++;}for (int i = 1; i <= m;i++){cin >> p >> v;cnt[a[p]] += i - 1;cnt[v] -= i - 1;a[p] = v;}for (int i = 1; i <= n;i++){cnt[a[i]] += m;}for (int i = 1; i <= n + m;i++){ans += cnt[i] * (m + 1 - cnt[i]);ans += cnt[i] * (cnt[i] - 1) / 2;}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 1536C - Codeforces
题意：要求找每个前缀子串的最大可分割组数，使得组数满足D:K与子串比例相等
- cntD与cntK互质，只有一组，它本身
- else 求
tmp=gcd(cntD,cntK),{d,k}出现的数量即可分割的组数
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;
}void solve()
{int n;cin >> n;string s;cin >> s;int cd = 0, ck = 0,d,k;map<pair<int, int>, int> mp;for (int i = 0; i < n;i++){if(s[i]=='D'){cd++;}else{ck++;}int tmp = gcd(cd, ck);d = cd, k = ck;d /= tmp, k /= tmp;mp[{d, k}]++;cout << mp[{d, k}] << " ";}cout << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
Problem - 74B - Codeforces（模拟）（注意输入）
[!warning] getline
cin >> n >> l >> r;读取3 1 2，缓冲区剩余\n（回车符）。getline(cin, s1)读取到\n，将s1设为""（空字符串）。即此时getline没有读入字符串，所以cin和getline最好不要混用
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;int main()
{int n,l,r;int flag;cin >> n >> l >> r;string s1,s;cin >> s1 >> s1;cin >> s;if(s1[0]=='h')flag = -1;elseflag = 1;int ans = 0;for (int i = 0; i < s.size();i++){ans++;if(r==1)flag = 1;if(r==n)flag = -1;if(s[i]=='1')l = r;r += flag;if(l==r)l += flag;if(l==0||l==n+1){cout << "Controller" << " " << ans << endl;return 0;}}cout << "Stowaway\n";
}