2018.09.09模拟总结

昨天学姐又说Day2难度是Day1两倍,反正我都无所畏惧了……

 

T1 forging

Day2果然毒瘤啊,T1就出一道期望dp,然后我期望基本忘得差不多了……

不过这道题其实不难。先考虑这个问题:抛一枚硬币,如果为反面就接着抛,求抛到正面的概率。设抛到正面的期望为x,首先要抛一次,然后有1/2的概率抛到反面,1/2的概率抛到正面,根据本题期望的定义,期望=概率 * 次数,那么就有 x = 1 + 1/2 * x + 1/2 * 0,即x  =1/2 * x + 1,得x = 2。还有另一种更好理解的方法:x = 1/2 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 + ……+ 1/2n * n。这个不难解,2 * x - x = 1 + 1/2 + 1/4 + 1/8 + …… + 1/2n,根据等比数列求和公式可知1/2 + 1/4 +1/8 + …… + 1/2n = 1,于是x = 2.

那么回到此题:令 k 表示锻造成功的概率,则k = min(ci-1, bi-2) / ci-1.于是fi + fi-1 = k * fi+1 + (k - 1) * fi-1.整理一下,然后退一位得fi = 1/k * fi-1 + fi-2

用线性求逆元预处理ci,然后递推求解。

2018.09.09模拟总结2018.09.09模拟总结
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<cctype>
 8 #include<vector>
 9 #include<stack>
10 #include<queue>
11 using namespace std;
12 #define enter puts("") 
13 #define space putchar(' ')
14 #define Mem(a) memset(a, 0, sizeof(a))
15 #define rg register
16 typedef long long ll;
17 typedef double db;
18 const int INF = 0x3f3f3f3f;
19 const db eps = 1e-8;
20 const int mod = 998244353;
21 const int maxn = 1e7 + 5;
22 inline ll read()
23 {
24     ll ans = 0;
25     char ch = getchar(), last = ' ';
26     while(!isdigit(ch)) {last = ch; ch = getchar();}
27     while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
28     if(last == '-') ans = -ans;
29     return ans;
30 }
31 inline void write(ll x)
32 {
33     if(x < 0) x = -x, putchar('-');
34     if(x >= 10) write(x / 10);
35     putchar(x % 10 + '0');
36 }
37 
38 int n, a;
39 int b[maxn], c[maxn], inv[maxn];
40 int dp[maxn];
41 
42 int main()
43 {
44     freopen("forging.in", "r", stdin);
45     freopen("forging.out", "w", stdout);
46     n = read(); dp[0] = read();
47     
48     int bx = read(), by = read(), cx = read(), cy = read(), p = read();
49     b[0]=by+1;c[0]=cy+1;
50     for(rg int i=1;i<n;i++)
51     {
52         b[i]=((long long)b[i-1]*bx+by)%p+1;
53         c[i]=((long long)c[i-1]*cx+cy)%p+1;
54     }
55     
56     inv[1] = 1;
57     for(rg int i = 2; i < maxn; ++i) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
58     dp[1] = ((ll)c[0] * inv[min(c[0], b[0])] % mod + 1) * dp[0] % mod;        //f[0]最好单独写一下 
59     for(rg int i = 2; i <= n; ++i)
60         dp[i] = ((ll)c[i - 1] * inv[min(c[i - 1], b[i - 2])] % mod * dp[i - 1] + dp[i - 2]) % mod;
61     write(dp[n]); enter;
62     return 0;
63 }
View Code

 

T2 division

这题尽管学姐说就是CRT板子,然而我不得不说是真心不会,讲完后还是不太懂……溜了……

 

T3 money

嗯……维护动态树上链的最小值,知道干啥,然后就是不会写,于是只能暴力水一发。

方法1:LCT……呵呵,等考完NOIP再说吧

方法2:兔哥自创妙法:虽然听懂了,然而就是不会写。首先我们想,如果树是静态的,那么自然可以用树剖(考试的时候我就想这么做,然而40分钟我觉得敲不完)或倍增解决。那么动态的怎么办:启发式合并。就是两棵树,然后把结点少的树往大树合并。这样的话,这些树必须改成无向的,要不然每一次合并还要想办法再找根节点或是干脆无法合并。既然无向的,那么自然要开一个数组记录每一链的方向,dir[i][j] = 1代表结点 i 像上跳2j步这个区间的这条链都是借别人钱的,2代表都是被借钱的,3代表这两种情况都有。因此合并的时候只要或起来就行了(很方便)。为此,还要有一个数组记录往上跳2j步是哪一个结点,因为合并的时候祖先会改变。当然还有最重要的记录最小值以及维护结点深度的数组了。

复杂度:启发式合并最坏复杂度为O(nlogn),加上查询O(mlogn),总时间复杂度O(nlogn + mlogn)。

思路就是这样,然而就是不会写……

方法3:是一个特别强的验题人想出来的,他叫wys。方法2我都不会,更别说这个了。什么用vector储存同一深度的结点,然后用链表串起来……弃疗了。

上一篇:Linux 环境变量


下一篇:Linux学习之/etc/init.d/functions详解