排列组合
排列组合就是计算题啊。。
A. Game on Tree
期望可加性
需要知道一个定理:E s u m = ∑ E i E_{sum}=\sum E_i E s u m = ∑ E i ,可以把整个树上的期望变为单点的期望值之和。
要求删除整个树的操作数的期望值,我们就转化为求每个点的操作数期望值。
单点期望值=∑ \sum ∑ 各种情况出现的概率*各种情况下的对该点的 操作数。
首先我们考虑在哪些情况下该点会被删除
对于第一种情况,我们对该点并无操作,操作数=0;对于第二种情况,操作数=1。
**再来看两种情况概率,由于只有上述两种情况会删除该点,所以对其子节点的操作不应该考虑。**因此总的情况数应等于该点的所有祖宗节点+自身。设祖宗节点+1=k,则第一种情况概率为(k-1)/k;第二种情况概率为1/k.
前面说了子节点不应该考虑,通过观察根节点可以更能理解,若考虑所有子节点,则根节点自身被删除的概率为1/n,n为总节点数,所以根节点操作数的期望值应该是1/n,这就说明我们可能不通过直接删除根节点自身而去除根节点,然而由于根节点无父节点,所以这是不可能的,这就说明我们不应考虑子节点,因为子节点并未达到删除当前节点的目的。
再考虑实现方法,k为当前点的深度,每个点的期望值=1/深度。所以我们只要把深度求出来。
求深度dfs一下就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std;#define ll long long const int maxn = 1e5 + 5 ;int n;vector<int >G[maxn]; int par[maxn];int dep[maxn];void add_edge (int u, int v) { G[u].push_back (v); G[v].push_back (u); } void dfs (int x,int d) { dep[x] = d; for (int i = 0 ; i < G[x].size (); i++) { if (G[x][i] != par[x]) { par[G[x][i]] = x; dfs (G[x][i], d + 1 ); } } } int main () { cin.sync_with_stdio (false ); cin >> n; for (int i = 0 ; i < n - 1 ; i++) { int u, v; cin >> u >> v; add_edge (u, v); } dfs (1 ,1 ); double ans = 0 ; for (int i = 1 ; i <= n; i++) { ans += (1.0 / dep[i]); } printf ("%.12f" , ans); return 0 ; }
B. Bad Luck Island
概率dp
有趣的题目,石头剪刀布三个种族,求最终存活的概率。
dp[i] [j] [k]表示石头剩余i个,剪刀剩余j个,布剩余k个,这种情况出现过的概率。
初始dp[r] [s] [p]=1,因为r,s,p的情况已知出现过了,概率为1.
最终情况,rsp中某两个为0,这种情况一旦出现就不会再变化,所以它出现过 就表示它是最终结果,我们可以放心的把它加到答案中去。
状态转移:
若i>0,则说明i还可以减少,此时可以推出i-1的概率,即i的概率*石头遇上布的概率。
jk同理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <string> using namespace std;#define ll long long int r, s, p;double dp[105 ][105 ][105 ];int main () { cin >> r >> s >> p; dp[r][s][p] = 1 ; for (int i = r; i >= 0 ; i--) { for (int j = s; j >= 0 ; j--) { for (int k = p; k >= 0 ; k--) { int kind = 0 ; if (i > 0 )kind++; if (j > 0 )kind++; if (k > 0 )kind++; if (kind <= 1 )continue ; int sum = i * j + i * k + j * k; if (i > 0 ) { dp[i - 1 ][j][k] += dp[i][j][k] * i*k / sum; } if (j > 0 ) { dp[i][j - 1 ][k] += dp[i][j][k] * i*j / sum; } if (k > 0 ) { dp[i][j][k - 1 ] += dp[i][j][k] * j*k / sum; } } } } double a1 = 0 , a2 = 0 , a3 = 0 ; for (int i = 1 ; i <= r; i++) { a1 += dp[i][0 ][0 ]; } for (int i = 1 ; i <= s; i++) { a2 += dp[0 ][i][0 ]; } for (int i = 1 ; i <= p; i++) { a3 += dp[0 ][0 ][i]; } printf ("%.12f %.12f %.12f" , a1, a2, a3); return 0 ; }
C. Basketball Team
纯概率计算题
考虑反面,要求有队友的概率,可能有1个,2个等等,比较麻烦,我们考虑没有队友的概率。
接着分类讨论,主要注意点是要把公式化简,不能硬用组合数莽,否则会爆。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <algorithm> #include <cmath> #include <map> using namespace std;#define ll long long int n, m, k;int a[1005 ];int sum;int main () { cin >> n >> m >> k; for (int i = 1 ; i <= m; i++) { cin >> a[i]; sum += a[i]; } if (sum < n) { cout << -1 ; } else if (sum == n) { if (a[k] > 1 ) { cout << 1 ; } else cout << 0 ; } else { if (a[k] == 1 ) cout << 0 ; else { double p = 1 ; int u = sum - a[k]; int v = sum - 1 ; for (int i = 0 ; i < n - 1 ; i++) { p *= (1.0 *u) / v; u--; v--; } cout << 1 - p; } } return 0 ; }
D. Intercity Travelling
找规律
每个点有01两种情况,考虑a 1 , a 2 , a 3 , ⋯ a_1,a_2,a_3,\cdots a 1 , a 2 , a 3 , ⋯ ,什么时候出现。
起初都是a 1 a_1 a 1 ,接着有一半的加油站,表示出现了一半的a 2 a_2 a 2 ,这一半的a 2 a_2 a 2 ,在下一波又有一半变成a 3 a_3 a 3 ,以此类推。
注意第一次有一半a 1 a_1 a 1 变为a 2 a_2 a 2 ,还剩下一半a 1 a_1 a 1 ,它们又会变成a 2 , a 3 , ⋯ a_2,a_3,\cdots a 2 , a 3 , ⋯ ,不能忘了这一支。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream> #include <algorithm> #include <cmath> #include <map> using namespace std;const int maxn = 1e6 + 5 ;#define ll long long ll n, a[maxn]; const int mod = 998244353 ;ll ans; ll p[maxn]; int main () { p[0 ] = 1 ; cin >> n; for (int i = 1 ; i <= n; i++) { cin >> a[i]; } for (int i = 1 ; i <= n; i++) { p[i] = p[i - 1 ] * 2 % mod; } for (int i = 1 ; i <= n; i++) { ans = (ans +a[i]*(p[n-i]+(n-i+mod)%mod*p[n-i-1 ]%mod)%mod) % mod; } cout << ans; return 0 ; }
E. Little Pony and Expected Maximum
计算题
期望值=该数数值*该数为最大值的概率
一个数成为最大的数,当且仅当比该数大的数都不出现,并且该数出现了。
接下来求出各个数出现或不出现的概率,乘起来就好了。
注意公式化简和精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> #include <algorithm> #include <cmath> #include <map> using namespace std;const int maxn = 1e5 + 5 ;#define ll long long double ans;int n, m;double p[maxn];double q[maxn];int main () { cin >> n >> m; for (int i = 1 ; i <= n; i++) { p[i] = 1.0 *i/n; } for (int i = 1 ; i <= n;i++) { ans += i*pow (p[i], m)*(1 - pow (1.0 *(i - 1 ) / i, m)); } printf ("%.12f" , ans); return 0 ; }
G. Bus Number
枚举+组合数公式
回忆到的每个数至少会出现一次且有次数上限,而没回忆到的数都不会出现。
所以我们可以枚举每种数出现的次数组合。
对于每种情况,先考虑无限制的排列数,再减去有前导零的排列数。
假设共有sum位,则无限制的排列数要首先去重,即P = P s u m s u m P a 0 P a 1 ⋯ P a n P=\frac{P_{sum}^{sum}}{P_{a_0}P_{a_1}\cdots P_{a_n}} P = P a 0 P a 1 ⋯ P a n P s u m s u m ,其中a 0 a_0 a 0 表示0的个数;有前导零的情况,就是先确定第一位为0,接下来sum-1位按上面的公式排列去重。最终两者相减。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> using namespace std;#define ll long long ll ans; int ct[10 ];int tmp[10 ];ll P[20 ]; void init () { P[0 ] = 1 ; for (int i = 1 ; i < 20 ; i++) { P[i] = i * P[i - 1 ]; } } void dfs (int x) { if (x == 10 ) { int sum = 0 ; for (int i = 0 ; i <= 9 ; i++) { sum += tmp[i]; } ll a = P[sum]; for (int i = 0 ; i <= 9 ; i++) { a /= P[tmp[i]]; } a -= (a*tmp[0 ] / sum); ans += a; return ; } if (ct[x] == 0 )dfs (x + 1 ); else { for (int i = 1 ; i <= ct[x]; i++) { tmp[x] = i; dfs (x + 1 ); } } } int main () { init (); string s; cin >> s; for (int i = 0 ; i < s.length (); i++) { ct[s[i] - '0' ]++; } dfs (0 ); cout << ans; return 0 ; }
H. Malek Dance Club
递推
要找两个数,满足a>b,且(a^n) < (b^n)。我刚开始考虑异或的单调性,但是发现它并不单调且没有规律。
考虑递推,看能否把位数减小,归并到1位的情况。
分两种情况,最高位为0或1.
最高位为0,现在假设我们已知 位数-1的情况,只要考虑最高位对答案的影响。最高位为0,则表示无影响,则我们在已知的 位数-1 的配对上都加上最高为1,或者0,他们仍然是满足条件的。
即f ( 0 x ) = 2 f ( x ) f(0x)=2f(x) f ( 0 x ) = 2 f ( x )
最高位为1,首先,我们在位数-1的配对上都加上最高位0或者1,由于两个数a,b最高位都被异或了,所以相当于没有最高位,仍然是满足条件的。其次,抛开位数-1,我们创造出两个数,一个数a最高位是0,另一个b最高位是1.两者必然是a<b,然而异或了1,之后,a最高位变1,b最高位变0.则是(a^n) > (b^n)。满足条件。从开头为0的数中选择a,有 2 n − 1 2^{n-1} 2 n − 1 种选择,从开头为1的数中选择b,同样有2 n − 1 2^{n-1} 2 n − 1 种选择,则共有4 n − 1 4^{n-1} 4 n − 1 种配对。同时,由于两个数一个最高位0,另一个1,所以不会与前面的情况重复,可以放心加上。
即f ( 1 x ) = 2 f ( x ) + 4 n − 1 f(1x)=2f(x)+4^{n-1} f ( 1 x ) = 2 f ( x ) + 4 n − 1
只有一位的情况:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <string> using namespace std;#define ll long long const int mod = 1000000007 ;string s; ll ans; ll p[105 ]; void init () { p[0 ] = 1 ; for (int i = 1 ; i < 105 ; i++) { p[i] = p[i - 1 ] * 4 % mod; } } ll solve (int x) { if (x == 0 ) { if (s[0 ] == '1' ) return 1 ; else return 0 ; } if (s[x] == '0' ) { return 2 * solve (x - 1 ) % mod; } else { return (2 * solve (x - 1 ) % mod + p[x]) % mod; } } int main () { init (); cin >> s; reverse (s.begin (), s.end ()); cout<< solve (s.length ()-1 ); return 0 ; }
I. Inna and Nine
找规律,分类讨论
把相邻的能合成9的数合成9,要求9最多的方案数。
如果奇数个能合成9,例如363,则有两种方案,合成39或93,ans*2;若偶数个,如3636,则必须全部合成9,只有1种.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <iostream> #include <algorithm> #include <cstring> #include <string> using namespace std;#define ll long long int main () { string s; cin >> s; ll cnt = 1 ; ll ans = 1 ; for (int i = 1 ; i <= s.length (); i++) { if (i == s.length () || (s[i] + s[i - 1 ] - 2 * '0' != 9 )) { if (cnt > 1 && (cnt & 1 )) { ans *= (cnt + 1 )/2 ; } cnt = 1 ; } else { cnt++; } } cout << ans; return 0 ; }
J. Monotonic Renumeration
区间合并
相同的两个数之间也必定是相同的。
所以问题变为有几段不相同的数,即把相同数作为区间端点,求有几个区间。
这里看到一个较巧妙地方法。
把一个数字最后出现的位置 记录下来。
新建一个指针从最左端起移动,若指针所指位置不是当前数字最后位置,则指针移动到当前数字最后位置,相当于把中间都略过了。
若指针与i相等,说明扫完了一个区间,即将开始新的一个区间。这时计数器+1.
i到达最后结束。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <algorithm> #include <map> using namespace std;typedef long long ll;const int maxn = 2e5 + 5 ;const int mod = 998244353 ;map<ll, int > mp; ll a[maxn]; ll ans = 1 ; int n;int main () { cin >> n; for (int i = 1 ; i <= n; i++) { cin >> a[i]; mp[a[i]] = i; } int r = 1 ; for (int i = 1 ; i <= n; i++) { if (r >= i) r = max (r, mp[a[i]]); else { ans = ans * 2 % mod; r = mp[a[i]]; } } cout << ans; return 0 ; }