临行前最后的准备。
UVA11021 Tribles
题目大意
一开始有$k$个生物，这种生物只能活1天，死的时候有$p_i$的概率产生$i$只这种生物（也只能活一天），询问$m$天内所有生物都死的概率（包括$m$天前死亡的情况）
输入格式
第一行输入一个整数TT，表示数据总数
每一组先输入三个整数$n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)$
然后输入n个整数，分别为$p0$到$p{n-1}$
输出格式
对于每一组数据，先输出”Case #x: “ 再输出答案，精度要求在1e-6以内
感谢@xMinh 提供翻译
题解
期望dp的简单题。
期望dp好像大部分都采用倒推的形式，我也不知道为什么不过这样确实好设计状态就是了。
首先我们发现由概率的独立，只需要算出一种生物$m$天后死亡的概率然后$k$次幂就是所有都死亡的概率。
那么如何求一只的呢？
我们设$fi$表示第$i$天死亡的概率。
那么$O(n)$枚举它每天产生的生物的个数，我们有
$f_i = \sum{k=0}^{n-1}f{i-1}^kp_k$
是这样的，如果第$i$天产生了$j$只，那么这$i$只暴毙的概率就是$f{i-1}^k$
然后这道题就做完了。
P1171 售货员的难题
题目描述
某乡有nn个村庄(1<n \le 201<n≤20)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)s(0<s<1000)是已知的，且AA村到BB村与BB村到AA村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为11，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入输出格式
输入格式：
村庄数nn和各村之间的路程(均是整数)。
输出格式：
最短的路程。
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 3 |
说明
输入解释
33 {村庄数}
0 2 1021 {村庄11到各村的路程}
1 0 2102 {村庄22到各村的路程}
2 1 0210 {村庄33到各村的路程}
题解
经典状态压缩dp
我们的状态需要有最后到达的点以及已经到达的点集，最后加上到1的距离即可。
转移枚举状态和下一个点即可。
时间复杂度$O(n^22^n)$
Code：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// luogu-judger-enable-o2
int f[maxn][1<<maxn] , n , dis[maxn][maxn];
int main()
{
scanf("%d",&n);
for(int i = 0 ; i < n ; ++i)
for(int j = 0 ; j < n ; ++j)
scanf("%d",&dis[i][j]);
std::memset(f,0x7f,sizeof(f));
f[0][1] = 0;
int S = 1 << n;
for(int i = 1 ; i < S ; ++i)
{
for(int j = 0 ; j < n ; ++j)
{
if((1 << j) & i)
for(int k = 0 ; k < n ; ++k)
{
if((1 << k) & i) continue;
f[k][i | (1 << k)] = std::min(f[k][i | (1 << k)] , f[j][i] + dis[j][k]);
}
}
}
int ans = 0x7fffffff;
for(int i = 0 ; i < n ; ++i)
ans = std::min(ans , f[i][S - 1] + dis[i][0]);
printf("%d",ans);
}
P1654 OSU!
题目背景
原 《产品排序》 参见P2577
题目描述
osu 是一款群众喜闻乐见的休闲软件。
我们可以把osu的规则简化与改编成以下的样子:
一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 XX 个 11 可以贡献 X^3X3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）
现在给出n，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留1位小数。
输入输出格式
输入格式：
第一行有一个正整数n,表示操作个数。接下去n行每行有一个[0,1]之间的实数，表示每个操作的成功率。
输出格式：
只有一个实数，表示答案。答案四舍五入后保留1位小数。
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 6.0 |
说明
【样例说明】
000分数为0，001分数为1，010分数为1，100分数为1，101分数为2，110分数为8，011分数为8，111分数为27，总和为48，期望为48/8=6.0
N<=100000
题解
一道很不错的期望dp入门题。
我们分别维护连续个数的期望，平方的期望，立方的期望（就是答案了），然后就很好用初中数学知识转移了（这么简单的题甚至懒得打LaTeX qwq）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double p[maxn] , exp , f[maxn] , g[maxn] , h[maxn];
int n;
int main()
{
scanf("%d",&n);
for(int i = 1 ; i <= n ; ++i)
scanf("%lf",&p[i]);
for(int i = 1 ; i <= n ; ++i)
{
g[i] = (g[i-1] + 1) * p[i];
h[i] = (h[i-1] + 2 * g[i-1] + 1) * p[i];
f[i] = f[i-1] + (3 * h[i-1] + 3 * g[i-1] + 1) * p[i];
}
printf("%.1lf\n",f[n]);
}
是不是很有趣？
P4550 收集邮票
题目描述
有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
输入输出格式
输入格式：
一行,一个数字N
N<=10000
输出格式：
要付出多少钱.
保留二位小数
输入输出样例
输入样例#1：
1 | 3 |
输出样例#1：
1 | 21.25 |
题解
我居然没有做出来qwq
其实感觉我那种方法应该是某一个小地方错了，和答案差别很小….
还是用倒推的方法。
设$f_i$为已经有了$i$种邮票，买到$n$种需要支付的期望价格，$g_i$为经有了$i$种邮票，买到$n$种需要的期望次数。然后接下来的推导就很毒瘤了
最主要的思想就是根据定义的量用方程来表达。
$g_i$凭感觉都能推导出来。
$gi = \frac{i}{n}g_i + \frac {n-i}{n}g{i+1}+1$
解出
$gi = g{i+1} + \frac{n}{n-i}$
$f_i$也不难，略有麻烦。用到了费用提前计算的方法，那个1表示当前买的价格，并且在以后还会不断上涨最终以次数为价格。
$fi = \frac{i}{n}(f_i+g_i+1) + \frac{n-i}{n}(f{i+1}+g_{i+1}+1)$
然后这道题就做完了。。。
不过我还是感觉这道题推的思路好怪啊。
1 | // luogu-judger-enable-o2 |
积累经验吧，确实没想到这题的做法。
[HEOI2016/TJOI2016]树
题目描述
在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：
- 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
- 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）
你能帮帮他吗?
输入输出格式
输入格式：
输入第一行两个正整数N和Q分别表示节点个数和操作次数
接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边
接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。
输出格式：
输出一个正整数，表示结果
输入输出样例
输入样例#1：
1 | 5 5 |
输出样例#1：
1 | 1 |
说明
30%的数据，1 ≤ N, Q ≤ 1000
70%的数据，1 ≤ N, Q ≤ 10000
100%的数据，1 ≤ N, Q ≤ 100000
题解
想到一个很简单的做法。
直接HPD维护每条重链上标记个数，查询的点跳到一条有它的重链就可以在上面二分，二分的越靠右越好(我一开始sb的找成越靠左越好。。。显然是深度越大离他越近)
这种sb题一定要争取一遍切。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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114// luogu-judger-enable-o2
std::vector<int> g[maxn];
int n;
int dep[maxn] , hs[maxn] , id[maxn] , idx ,rev[maxn] , tp[maxn] , sz[maxn] , f[maxn] , seg[maxn<<2];
void dfs1(int x , int fx)
{
sz[x] = 1;
dep[x] = dep[fx] + 1;
f[x] = fx;
for(int i = 0 ; i < (int)g[x].size() ; ++i)
{
int vr = g[x][i];
if(vr == fx) continue;
dfs1(vr , x) ,sz[x] += sz[vr];
if(sz[vr] > sz[hs[x]]) hs[x] = vr;
}
}
void dfs2(int x , int topv)
{
tp[x] = topv;
id[x] = ++idx;
rev[id[x]] = x;
if(!hs[x]) return ;
dfs2(hs[x] , topv);
for(int i = 0 ; i < (int)g[x].size() ; ++i)
{
int v = g[x][i];
if(v == f[x] || v == hs[x]) continue;
dfs2(v , v);
}
}
inline void pushup(int x){
seg[x] = seg[x<<1] + seg[x<<1|1];
}
int query(int p , int l , int r , int L , int R)
{
if(L <= l && r <= R) return seg[p];
int mid = l + r >> 1 , ans = 0;
if(L <= mid) ans += query(p << 1 , l , mid , L , R);
if(R > mid) ans += query(p << 1 | 1 , mid + 1 , r , L , R);
return ans;
}
void update(int p , int pos , int l , int r)
{
if(l == r) {
seg[p] = 1;
return;
}
int mid = l + r >> 1;
if(pos <= mid) update(p << 1 , pos , l , mid);
else update(p << 1 | 1 , pos , mid + 1 , r);
pushup(p);
}
int solve(int l , int r)
{
int ans = 0;
while(l <= r)
{
int mid = l + r >> 1;
if(query(1 , 1 , n , mid , r) > 0) ans = mid , l = mid + 1;
else r = mid - 1;
}
return rev[ans];
}
int calc(int x)
{
int k = 0;
for( ; x ; x = f[tp[x]])
{
if((k = query(1 , 1 , n , id[tp[x]] , id[x])))
{
return solve(id[tp[x]] , id[x]);
}
}
return 0;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
int q;
scanf("%d%d",&n,&q);
for(int i = 1 ; i <= n-1 ; ++i)
{
int x, y;
scanf("%d%d",&x,&y);
g[x].push_back(y) , g[y].push_back(x);
}
dfs1(1,1);
dfs2(1,1);
update(1 , id[1] , 1 , n);
for(int i = 1 ; i <= q ; ++i)
{
char ch;
int qr;
std::cin>>ch;
scanf("%d",&qr);
if(ch == 'Q')
printf("%d\n",calc(qr));
else update(1 , id[qr] , 1 , n);
}
}
CF888E Maximum Subsequence
题意翻译
给一个数列和m，在数列任选若干个数，使得他们的和对m取模后最大
Translated by @xzyxzy
输入输出样例
输入样例#1：
1 | 4 4 |
输出样例#1：
1 | 3 |
输入样例#2：
1 | 3 20 |
输出样例#2：
1 | 19 |
说明
题解
meet in the middle暴力。
看到数据范围很好猜算法，接下来我们只需要考虑如何求左右两边合并的最大值。
首先我们发现相加值最大不超过$2m$，这意味着我们只需要分别找出小于$m$的最大值和小于$2m$的最大值。
小于$2m$的最大值就是左右两边最大值相加再减模数。
对于小于$m$的最大值，很显然这是一个经典的双指针。
但是一定要注意只选左边或者只选右边都是合法的！！所以两个指针为0时均可。
时间复杂度$O(2^{\frac{n}{2}}logn)$
1 |
|
P5104 红包发红包
题目背景
红包(redbag)发明了一个抢红包的系统。
题目描述
这个抢红包系统是这样的：假如现在有w元，那么你抢红包能抢到的钱就是[0,w][0,w]等概率均匀随机出的一个数x。
现在红包发了一个ww元的红包，有nn个人来抢。那么请问第kk个人期望抢到多少钱？
输出\bmod (10^9+7)mod(109+7)。
输入输出格式
输入格式：
w,n,k
输出格式
第kk个人期望抢到的钱数\bmod(10^9+7)mod(109+7)
补充：期望可能是分数，关于分数取模，可以问度娘
输入输出样例
输入样例#1：
1 | 2 1 1 |
输出样例#1：
1 | 1 |
说明
注意红包发明的抢红包系统和微信的抢红包系统不一样，红包发明的抢红包系统中的钱不一定是整数分。
0\lt w\lt (10^9+7),n\le 10^{18},k\le n0<w<(109+7),n≤1018,k≤n
特别的，对于30\%30%的数据，k=1k=1
对于另30\%30% 的数据，答案为整数，k\le 10k≤10。
题解
首先只要你凭感觉得出对于第一个人是$\frac{w}{2}那么这道题求的就是\frac{w}{2^k}
没错$n$没有用233.一种更方便的逆元写法见代码。
1 | // luogu-judger-enable-o2 |
累了累了，溜了。
明天准备出发，今晚上写错线段树。。。。
AT1504 ドキドキデート大作戦高橋君
题意
给定$m$条线段（值域在$300000$以内），问有多少能被其他线段完全覆盖的线段。
题解
由于太过弱智没有想到正确的贪心，就写了线段树，结果线段树写错了呜呜呜。
修改的时候一定要$pushdown$，具体还是不大清楚。。。
然后我们只需要给每条线段覆盖+1,然后查询每天线段的最小值是否大于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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
int n , m , l[maxn] , r[maxn] , seg[maxn<<2] , mk[maxn<<2];
inline void pushup(int x){
seg[x] = std::min(seg[x<<1] , seg[x<<1|1]);
}
inline void pushdown(int p)
{
if(mk[p])
{
mk[p<<1] += mk[p] , mk[p<<1|1] += mk[p];
seg[p<<1] += mk[p] , seg[p<<1|1] += mk[p];
mk[p] = 0;
}
}
void update(int p , int l , int r , int L , int R , int v)
{
if(L <= l && r <= R){
seg[p] += v;
mk[p] += v;
return ;
}
int mid = l + r >> 1;
pushdown(p);
if(L <= mid) update(p << 1 , l , mid , L , R , v);
if(R > mid) update(p << 1 | 1 , mid + 1 , r , L , R , v);
pushup(p);
}
int query(int p , int l , int r , int L , int R)
{
if(L <= l && r <= R) return seg[p];
int mid = l + r >> 1 , ans = 0x7ffffff;
pushdown(p);
if(L <= mid) ans = std::min(ans , query(p << 1 , l , mid , L , R));
if(R > mid ) ans = std::min(ans , query(p << 1 | 1 , mid + 1 , r , L , R));
// pushup(p);
return ans;
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= m ; ++i)
scanf("%d%d",&l[i],&r[i]) , update(1 , 1 , n , l[i] , r[i] , 1);
std::vector<int> ans;
for(int i = 1 ; i <= m ; ++i)
{
if(query(1 , 1 , n , l[i] , r[i]) > 1)
ans.push_back(i);
}
printf("%d\n",(int)ans.size());
for(int i = 0 ; i < (int)ans.size() ; ++i)
printf("%d\n",ans[i]);
}
晚上再问问shzr老师是怎么回事，感觉还是没有想出原因qwq。
我想我想明白了，update不及时下传会导致更新一个错误值233.