2 Fatalzyc

尚未进行身份认证

我要认证

一身入此门,再无回头言

等级
TA的排名 30w+

P3708 koishi的数学题

2018-10-22 20:51:56

P3092 [USACO13NOV]没有找零No Change

题目描述Farmer John is at the market to purchase supplies for his farm. He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000. FJ would like to make a sequence o...

2018-07-14 16:30:14

P3478 [POI2008]STA-Station

考虑直接对于每个点计算一次 时间复杂度O(n2)显然无法接受 所以,考虑只进行一次DFS在通过递推求解 如果已经知道根节点的答案的话 那么,他的儿子节点很容易的可以递推出来: Ans[son]=Ans[father]+n−2∗size[son] 有点利用树链剖分的思想,其实就是dfs1// luogu-judger-enable-o2#include <cstdio&g...

2018-07-10 15:12:09

斐波那契数列定理们

斐波那契数列定理1gcd(f[i],f[i+1])=1gcd(f[i],f[i+1])=1 利用辗转相减法 证明: gcd(f[i],f[i+1])gcd(f[i],f[i+1]) =gcd(f[i+1]−f[i],f[i])=gcd(f[i+1]−f[i],f[i]) =gcd(f[i−1],f[i])=gcd(f[i−1],f[i]) =….=…. =gcd(f[1],f[2...

2018-07-08 21:56:18

NOIP 2016 换教室 DP

DP 很好想: 首先,考虑对于所有的教室与道路,地图本身是存在最短路的,我们先用floyd求出任意两点之间的最短距离。其次,针对所有事件可能发生的情况:1.当前的课不换的情况:(1)上一节课也没换;(2)上一节课换了—-成功or不成功;2.当前的课换的情况:(1)当前课成功换了:a.上一节课换了—-上一节课成功or不成功b.上一节课没换;(2)当前的课换了失败...

2018-07-08 19:05:11

2017 NOIP 子串

定义状态 f[i][j][k][0/1] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符用了 k 个子串,第四维为 1 表示 A 字符串的第 i 个字符必须被选出,为 0 表示 A 字符串的第 i 个字符不能被选出。那么很容易得出转移:1、对于任意一个 0<=i<=n,f[i][0][0][0]=1 。2、f[i][j][k][0]=f[i−1][j][k]...

2018-07-08 08:02:28

bzoj 绝世好题

Description给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。 Input输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数,第i个整数表示ai。 Output输出文件共一行。 包括一个整数,表示子序列bi的最长长度。 Sample Input31 2 3 Sample...

2018-05-21 18:50:19

P1533 可怜的狗狗 平衡树

题目背景 小卡由于公务需要出差,将新家中的狗狗们托付给朋友嘉嘉,但是嘉嘉是一个很懒的人,他才没那么多时间帮小卡喂狗狗。题目描述 小卡家有N只狗,由于品种、年龄不同,每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比(漂亮值越低越漂亮),吃饭时,狗狗们会按顺序站成一排等着主人给食物。可是嘉嘉真的很懒,他才不肯喂这么多狗呢,这多浪费时间啊,于是他每次就只给第i只到第j只狗中第k漂亮的狗...

2018-05-17 20:48:20

树链剖分笔记(一)-------初识树链剖分

写在前面首先,在学树链剖分之前最好先把 LCA、树形DP、DFS序 这三个知识点学了emm还有必备的 链式前向星、线段树 也要先学了。如果这三个知识点没掌握好的话,树链剖分难以理解也是当然的。树链剖分树链剖分 就是对一棵树分成几条链,把树形变为线性,减少处理难度需要处理的问题:将树从x到y结点最短路径上所有节点的值都加上z求树从x到y结点最短路径上所有节点的值之和将以x为根节点的子树内所有节点值都...

2018-05-16 20:28:08

[TJOI2007]线段

转载:https://www.cnblogs.com/qdscwyy/p/7953758.html(主要是偷懒)题目描述在一个 n*n 的平面上,在每一行中有一条线段,第 i 行的线段的左端点是(i, L(i)),右端点是(i, R(i)),其中 1 ≤ L(i) ≤ R(i) ≤ n。你从(1, 1)点出发,要求沿途走过所有的线段,最终到达(n, n)点,且所走的路程长度要尽量短。更具体一些说,...

2018-05-16 16:11:04

P3871 [TJOI2010]中位数

最近在学splay,一看要求中位数,就上一个单点修改splay吧 顺便安利一发splay写的极好(还行)的博客https://blog.csdn.net/zj_js_zxb/article/details/80258824#include <cstdio>#include <iostream>#include <cmath>using namespace ...

2018-05-16 16:00:40

bzoj 2208

暴力+BFS 水过#include<iostream>#include<cstdio>#include<cstring>const int N=2000+5;inline int read(){ int f=1,x=0; char c=getchar(); while (c<'0'||c>'9'){if (c=='-') f=-1;c=...

2018-05-15 11:24:43

NOIP2017模拟赛10.02

A. 「NOIP2017模拟赛10.02」电阻 个人认为是思维题。第一题其实很简单,而且很有意思。 对于每个电阻我们不是串联进去,就是并联进去。 如果a>ba>b,那么我们肯定是串联进去比较好,所需达到的阻值abab变成了a−bba−bb,如果发现a<ba<b,那么我们只能选择并联,我们知道1R=1R1+1R2+1R3+...+1Rk1R=1R1+1R2+1R3+...+1...

2018-05-11 19:41:47

HNOI2008 GT考试 BZOJ1009 洛谷P3193

此题主要思路是dp,但dp有多种写法。我们用f[i][j]表示现在已经有i个数字了,而且最后j个数字是不幸数字前j个数字。(保证不包含不吉利序列) 为了防止dp的意义出现歧义,我们让对于同一个状态j要竟可能大; 比如 1212是不幸数字,那么551212是f[6][4]; 这样的话我们可以发现f[0][0]=1; ans=f[n][k] ,k∈[0,m-1] ∪Z(若k=m,那么已经形成一个不吉利...

2018-05-09 21:51:23

BZOJ P1899 [ZJOI2005]午餐DP+贪心

看到有两队人马在吃饭,再看看数据范围,题目应该属于贪心+DP.贪心:以吃饭时间,从大到小排序,为什么是正确的呢?我们可以假设只有一个队时只有两个人甲乙;         打饭时间      吃饭时间   甲     X                 Y   乙     Z                 Y+k(k>0)如果甲先打,哪么tot(总时间)=X+Z+Y+k(因为Y+k>k...

2018-05-08 20:38:40
勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!