夏荷浅梦

分类

未归档(117) 读书笔记(1) 题解(6)

/ 注册

全部文章（共6篇）

SP14932 LCA - Lowest Common Ancestor

Description: 一棵树是一个简单无向图，图中任意两个节点仅被一条边连接，所有连通无环无向图都是一棵树。\(-Wikipedia\) 最近公共祖先（\(LCA\)）是……（此处省去对\(LCA\)的描述），你的任务是对一棵给定的树\(T\)以及上面的两个节点\(u,v\)求出他们的\(L...

LCA 倍增 SPOJ

2018-12-21

0 401

SP1716 GSS3

题意翻译 \(n\) 个数，\(q\) 次操作操作\(0\) \(x\) \(y\)把\(A_x\) 修改为\(y\) 操作\(1\) \(l\) \(r\)询问区间\([l, r]\)的最大子段和输入输出格式输入格式： The first line of input contai...

线段树 SPOJ

2018-12-31

0 427

SP1043 GSS1

题目描述给出了序列\(A[1]，A[2]，…，A[N]。 (a[i]≤15007，1≤N≤50000)\)。查询定义如下：查询\((x，y)=max{a[i]+a[i+1]+...+a[j]；x≤i≤j≤y}\)。给定\(M\)个查询，程序必须输出这些查询的结果。输入输出格式输入格式...

线段树 SPOJ

2018-12-31

0 450

SP375 QTREE - Query on a tree

题意大意给定\(n\)个点的树，边按输入顺序编号为\(1,2,...n-1\)，要求作以下操作： CHANGE \(i\) \(t_i\) 将第\(i\)条边权值改为\(t_i\)，QUERY \(a\) \(b\) 询问从\(a\)点到\(b\)点路径上的最大边权有多组测试数据，每组数据以...

线段树树链剖分 SPOJ

2019-01-05

0 501

SP2713 GSS4 - Can you answer these queries IV

题目大意 \(n\) 个数，和在\(10^{18}\)范围内。也就是\(\sum~a_i~\leq~10^{18}\) 现在有两种操作 0 x y 把区间[x,y]内的每个数开方，下取整 1 x y 询问区间[x,y]的每个数的和格式：有多组数据，数据以EOF结束，对于每组数据，输...

线段树 SPOJ

2019-01-06

0 490

SP1026 FAVDICE - Favorite Dice

题目描述一个\(n(n \leq 1000)\)面的骰子，求期望掷几次能使得每一面都被掷到。输入输出样例输入样例#1： 2 1 12 输出样例#1： 1.00 37.24 思路：期望\(dp\)中典型的赠券收集问题，用f[i]表示还剩i个面没有掷到，那么掷到之前没有掷到过的面的概...

期望期望DP DP SPOJ

2019-05-03

0 540