NC 13885. Music Problem
发表于
分类于
解题报告
POJ 3273. Monthly Expense
发表于
分类于
解题报告
NC 13250. 景区路线规划
发表于
分类于
解题报告
链接
https://ac.nowcoder.com/acm/problem/13250
题意
对于一个景区道路网，求出游客的满意度的期望值。基于用户的喜好差异，需要对男性游客和女性游客的满意度分别计算。
景区被描述成一张 $n$ 个点、$m$ 条边的无向图（无重边，无自环）。每个点代表一个景点，第 $i$ 个景点游览需要耗费$c_i$ 分钟，会让男性游客和女性游客的满意度分别增加 $h1$ 和 $h2$（满意度初始值都为 $0$）。每条边代表一条路，第 $i$ 条边连接编号为 $x_i,y_i$ 的两个景点，从景点 $x_i$ 走到 $y_i$和从 $y_i$走到$x_i$ 的时间都是 $t_i$ 分钟
每个游客在景区中最长可以游览 $k$ 分钟，最开始会随机的通过不同大门进入到一个景点开始游览，每游览完一个项目，游客会等概率随机选择一个可以从当前景点直达且来得及游览的景点作为下一个游览目标（已经游览过的景点也会被作为目标）。如果游览完一个景点后，周围没有来得及游览的景点，本次游玩就结束了
分别计算男性和女性在游玩结束后开心度的期望。
NC 13249. 黑白树
发表于
分类于
解题报告
链接
https://ac.nowcoder.com/acm/problem/13249
题意
有一颗树，开始时每个节点都是白色，每个节点 $i$ 可以将 $i$ 到根的链上（包括 $i$ 与根）所有与 $i$ 距离小于 $k[i]$ 的点变黑，问最少操作几次能把整棵树变黑
牛客练习赛 1 B. 树
发表于
分类于
解题报告
题目链接
https://ac.nowcoder.com/acm/contest/2/B
题意
有一颗树，有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对 $(x,y)$，$x$ 到 $y$ 的路径上的所有点的颜色都要与 $x$ 和 $y$ 相同,请统计方案数
POJ 3784. Running Median
发表于
分类于
解题报告
2020牛客暑期多校训练营（第二场）A. All with Pairs
链接
https://ac.nowcoder.com/acm/contest/5667/A
题意
有 $n$ 个字符串
定义 $f(s,t)$ 为最大的 $i$ 满足 $s_{1…i}=t_{|t|-i+1…|t|}$
求 $\sum_{i=1}^n\sum_{j=1}^n{f(s_i,s_j)^2}\pmod{998244353}$