test – Tgotp-Blog

最短路(route)

先套路的正反求两次最短路,然后容易发现如果反向能更新最短路直接输出1

然后如果不变或者如果这条边压根不在最短路上则输出0,

如果均不是,接下来就是判断这条路是否在最短路上必须经过.

(评讲的时候大佬们给了很多做法,[......]

Read more

sqr

set4

其实三道题都是水题,t1计算几何一个经典题,自行百度,t2单调栈。

这里讲一下第三题。

评讲的时候有人给出了扫描线线段树的做法。。。

然后我觉得有点麻烦,这里给出我的做法。。。

容易想到共同的一步,先旋转坐标系45°,但是这一步我们考虑到会出现小数,

但[......]

Read more

2144: 跳跳棋

求lca神题。

手推一下会发现,对于一个点,有三种跳法:

即中间点向两边跳,两边点向中间跳。

设三元组(u,v,w)(u < v < w).

设a  = v - u,b = u - v.

不难发现,若 a < b ,则只能u向后跳,反之w向前跳。[......]

Read more

1592: [Usaco2008 Feb]Making the Grade 路面修整

按排序后的数组来搞一搞就好了。

枚举上一次选某种情况下的最小话费,同时可以加个优化,

即f[i][j]表示在第i个点,在b中选>=j 的编号的点的最小话费。

g[i][j]表示在第i个点,在b中选<=j 的编号的点的最小话费。

1:c++代码如下:
[crayo[......]

Read more

T15832 有趣的拖拉机

题目背景

回忆当年lyc,与xd,cyh,zjc三巨牛玩拖拉机的场景还历历在目。其中有一局 zjc和我打A,摸牌时都没人亮牌。刚摸完牌时,zjc突然说:“我手上有个A”。此时cyh开始嘀咕了,可能zjc不止有一个A吧。可是仍然没有人亮牌。就在要翻底牌的时候,zjc将手中的黑桃A亮了出来,此时xd大[......]

Read more

T15683 切

题目背景

2017/11/01 T1

题目描述

给出一棵有n个结点的树,将其中的一些边切掉,使得每个节点至少有k个结点与之相连(包括自己),求方案数对786433取模的结果。

输入输出格式

输入格式:

输入第一行,包含两个正整数n,k。

接下来的 n-1 行,每行包含两个正整数[......]

Read more

T15463 人心丑恶的妹子们[来自光棍的呐喊]

题目背景

Rikka 喜欢将他的妹纸们排成一队。

题目描述

假设他拥有 N 只妹纸,编号为 1 至 N。Ls 让他们

站成一行,等待自己来派送营养餐。这些妹纸按照编号大小排列,并且由于它们都很想

4 早点吃饭,于是就很可能出现多只妹纸挤在同一位置的情况(也就是说,如果我们认为[......]

Read more

T14967 交通

题目背景

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区(由桥连接岛的西部)到东岸的工业区(由桥连接岛的东部)。

题目描述

黄金大神国的首都位于 oier 河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西

岸的住宅区[......]

Read more

Distance

题目链接:https://www.nowcoder.com/acm/contest/16/B

TGSteven大佬说是智障题,所以我成了智障了。。。

整场比赛就写了1,2题,而且这题还是最后做出来的。

如果没有绝对值,无疑是大水题。

然后有绝对值的话,只用分类讨论即可。[......]

Read more