Luogu – 第2页 – Tgotp-Blog

P3938 斐波那契

死于没开long long

打表观察发现 除了一号兔子以外,以后每月产生的兔子为斐波那契数列的个数。

所以前60项左右就会兔子总数就会达到1e12,然后其父亲为该id – 此时的sum[fi],所以跑一跑就好了。

c++代码如下:
[crayon-5a64f87452977287[……]

Read more

1192: [HNOI2006]鬼谷子的钱袋&&P2320 [HNOI2006]鬼谷子的钱袋

似乎洛谷的要难点,洛谷还要输出方案数。

跟以前我见过的某道题比较像,一个思想是,令f[i]为组合i的最少话费,那么下一次只用取的时候袋子就只用是i +1个,然后这题要袋子数量尽量少,那么只用倒序搞一搞就好了

c++代码如下:

Read more

T11839 s3

观察n的范围,爆搜,加个剩余价值的估价优化

c++代码如下:

 

P2016 战略游戏

MDZZ,竟然是有向图,

很简单的树形dp,

令f[i][0]表示i点不放士兵,f[i][1]表示i点放士兵。

然后

f[x][1] += min(f[to[i]][0],f[to[i]][1]);

f[x][0] += f[to[i]][1];

搞定

c+[……]

Read more

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd;

记住:大胆假设,不用证明

先存图,观察数据范围n <= 50 ,直接用floyd求出最短路。

继续二分最大长度 c ,对于每个已有城堡的城市,直接去标记其能到达的城市,然后对于不能到达的,

我们将其距离不超过枚举的c的点期望[……]

Read more

P2111 考场奇遇

概率dp

这一次对的某种情况为上一次少一的概率*成功的概率 + 一样*不成功的概率

c++代码如下:

 

NOIP2011 P1311 选择客栈

直接dp搞搞,似乎做的麻烦了一点。。

c++代码如下:

更新后的代码如下:

如果符合要求的酒吧位置 >= last[x] ,就可以更新新的值

不然的话对于某个颜色就一直加上之前他有多少个酒店。
[cray[……]

Read more

2017年9月21日 0 / /
Tag:  No Tags

P2264 情书

来个比较好理解的,直接套上trie

然后对于前n个建trie,然后对于文本直接在trie上跑跑。

对于 . 看成一句话的理解,可以是如果你在当前的话里面有使用  . ,就把此时的val初始为cnt,如果val[x]  != cnt,才进行更新。

搞定。

c++代码如下:
[[……]

Read more

P1345 [USACO5.4]奶牛的电信Telecowmunication

对于这道题,

很容易看出是网络流,

然后怎么建图呢。

发现此题不是删边,而是删点,理所当然一个点只能删一次,如何保证呢?

把点删一次看作容量为1的边,然后把i 与i+n连起来,对于任何与i相连接的点,把i+n与之连接起来。

跑一边dinic,搞定。

c++代码如下[……]

Read more

NOIP2012 开车旅行

好难呀。。。

花了一早上来肝这道题,我认为真心不好做。

首先思路是倍增:

令F[I][J]表示以I出发2^J个点所到达的点

令A[I][J]表示以I出发2^J个点a所行驶的距离

令B[I][J]表示以I出发2^J个点b所行驶的距离

首先,你需要找到n个点距离他最近的点与次近的点。

显而[……]

Read more