chentong1023-CSDN博客

原创关于Fibonacci博弈的一些学习

关于Fibonacci博弈的一些学习一道例题问题给定n(n≥2)n(n\ge 2)个石头，游戏双方轮流取至少一个石子，取到最后一个石子的人算赢，但是要满足一下规则：第一次取不能全部取完所有的石子。设前一次取的石子数为mm,这次取的石子的数量不能超过2m2m。问先手是否有必胜策略。分析当时看到这道题（当时看的还是加强版）的时候第一反应是设计DP。计fi

2017-04-25 22:15:51 335

原创 FJWC2017&FJOI2017一试游记

day1 早上是以前泉州七中的杨国烨讲课。（据说当时看新闻说是一对双胞胎一起上thu的其中一个）课题是图论/网络流。下午第一道一开始推出来了一个之和面积有关的式子，然后觉得可以容斥一发，觉得细节太多（要求矩形和矩形的交）就拖到最后再写（结果没rush出来）。第二题看出来是支配树模型，然后觉得支配树写不动于是就写了纯三方的暴力。第三题是一个带区间覆盖字母，区间查长度小于等于k（k很小）的

2017-01-25 18:43:11 1723

原创 NOIP2016滚粗记

Day0翘课在机房敲了一个早上的模板。（结果模板太多没敲完这就很尴尬了）下午做校车去屏东看NOIP考场。我真的好想吐糟：我的那个考室真的好挤啊。空间大概是其他考室的三分之一，过道一次只能走一个人，而且走的时候必然会碰到旁边坐着的人。。。电脑是一排排过去的，机子和机子之间大概只有一个键盘的距离，中间强行用挡板隔着（感觉没卵用）。机子也比较鬼畜。但愿明天能分到一个好一点的机器和座位吧。。。晚上无

2016-11-18 19:21:54 1199

NOIP以前可能会持续更新写在前面NOIP好像马上就要到了，感觉在校内训练里面经常被虐有一种要滚粗的感觉（雾。不管是普及组还是提高组，我都参加了好几年了，结果一个省一都没有，今年如果还没有的话感觉就真的要滚大粗退役回去念书了QAQ。于是有了压力就来刷（水水水）题。感觉校内OJ的题库还挺多的就开始做校内OJ的题。（本校的其他神犇都在其他各种OJ上屠丧题我感觉好虚啊！）于是把这几年NOIP的原题拿出来做

2016-10-29 17:38:18 1114

原创【bzoj4034】[HAOI2015]T2

*题目描述：有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。*输入：第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值

2016-09-21 17:36:35 294

原创【bzoj2763】[JLOI2011]飞行路线

*题目描述： Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少

2016-09-21 17:33:43 289

原创【bzoj1189】[HNOI2007]紧急疏散evacuate

*题目描述：发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是’.’，那么表示这是一块空地；如果是’X’，那么表示这是一面墙，如果是’D’，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地

2016-09-21 17:28:48 232

原创【bzoj1059】[ZJOI2007]矩阵游戏

*题目描述：　　小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N *N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上

2016-09-21 17:23:55 273

原创【bzoj1015】[JSOI2008]星球大战starwar

*题目描述：　　很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始

2016-09-21 16:59:26 286

原创【bzoj4562】[Haoi2016]食物链

*题目描述：如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号 M条能量流动关系形如 a1 b1 a2 b2 a3 b3 …… am-1 bm-1 am bm 其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链*输入：第一行两个整数n和m,接下来m行每行两

2016-09-21 16:50:14 349

原创【bzoj3672&&uoj7】[Noi2014]购票

*题目描述：今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv 以及到父

2016-09-21 16:42:49 320

原创【bzoj1026】[SCOI2009]windy数

*题目描述：　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？*输入：　　包含两个整数，A B。*输出：　　一个整数*样例输出：【输入样例一】 1 10 【输入样例二】 25 50*样例输出：【输出样例一】 9 【输出样例二】 20*提示：【

2016-09-21 14:54:02 243

原创【bzoj4146】[AMPPZ2014]Divisors

*题目描述：给定一个序列a[1],a[2],…,a[n]。求满足i!=j且a[i]|a[j]的二元组(i,j)的个数。*输入：第一行包含一个正整数n(1<=n<=2000000)，表示序列长度。第二行包含n个正整数，依次表示a[1],a[2],…,a[n] (1<=a[i]<=2000000)。*输出：一个整数，即满足条件的二元组的个数。*样例输入： 5 2 4 5 2 6*样例

2016-09-11 17:23:40 238

原创【bzoj1096】[ZJOI2007]仓库建设

*题目描述：　　L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第

2016-09-10 13:45:48 281

原创【bzoj1010】[HNOI2008]玩具装箱toy

*题目描述：　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地

2016-09-10 11:10:41 216

原创【bzoj3566】 [SHOI2014]概率充电器

*题目描述：著名的电子产品品牌 SHOI 刚刚发布了引领世界潮流的下一代电子产品——概率充电器: “采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI 概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧! ” SHOI 概率充电器由 n-1 条导线连通了 n 个充电元件。进行充电时,每条导线是否可以导电以概率决定,每一个充电元件自身是否直接进行充电也由概

2016-09-07 21:05:51 306

原创【bzoj1013】[JSOI2008]球形空间产生器sphere

*题目描述：　　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。 *输入：　　第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

2016-07-29 14:04:01 257

原创【FJ省队训练&&NOIP夏令营】酱油&&滚粗记

FJOI2016省队训练滚粗记2016.07.03~2016.07.06（Day1~5）在学校期末考。因为才省选二试too young too simple爆蛋了所以下半个学期只能滚回去读文化课，省队训练的前5天和期末考冲突，只能去读文化课。。。2016.07.07（Day 6）早上讲莫比乌斯反演，几乎没听懂。。。至少了解了一下概念，大概直到μ这个函数是干嘛的，还有就是第一次学线性筛（以前太弱都是写

2016-07-22 14:58:26 2138

原创【bzoj3676】[Apio2014]回文串

*题目描述：考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最大出现值。 *输入：输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。 *输出：输出一个整数，为逝查回文子串的最大出现值。 *样例输入：【样例输入l】 abacaba 【样例输入2】 www *样例输

2016-06-28 18:21:55 453

原创【bzoj1031】[JSOI2007]字符加密Cipher

*题目描述：　　喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法：把需要加密的信息排成一圈，显然，它们有很多种不同的读法。例如下图，可以读作： JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0把它们按照字符串的大小排序：07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J读

2016-06-21 18:22:07 346

原创【bzoj4566】[Haoi2016]找相同字符

*题目描述：给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。*输入：两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母*输出：输出一个整数表示答案*样例输入： aabb bbaa*样例输出： 10*题解：构造广义后缀自动机，分别统计每个节点

2016-06-20 16:55:15 261

原创【bzoj3277&&3474】串

*题目描述：字符串是oi界常考的问题。现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。*输入：第一行两个整数n，k。接下来n行每行一个字符串。*输出：输出一行n个整数，第i个整数表示第i个字符串的答案。*样例输入： 3 1 abc a ab*样例输出： 6 1 3*提示：对于100%的数据，n,k,l<=1

2016-06-19 17:55:51 582

原创后缀自动机刷题计划

后缀自动机刷题计划codevs3160: 最长公共子串bzoj3998: [TJOI2015]弦论bzoj2946: [Poi2000]公共串bzoj3926: [Zjoi2015]诸神眷顾的幻想乡bzoj2555: SubStringbzoj4566: [Haoi2016]找相同字符bzoj3238: [Ahoi2013]差异bzoj2806: [Ctsc2012]Cheatbz

2016-06-19 10:54:05 351

原创【bzoj3038】上帝造题的七分钟2

*题目描述： XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 “第一分钟，X说，要有数列，于是便给定了一个正整数数列。第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。第三分钟，k说，要能查询，于是便有了求一段数的和的操作。第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

2016-06-17 15:02:15 317

原创【bzoj1398】Vijos1382寻找主人 Necklace

*题目描述：给定两个项链的表示，判断他们是否可能是一条项链。 *输入：输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。 *输出：如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。设L = 项链长度，对于50%的数据L <= 100000；对于100%的数据L <= 1

2016-06-17 13:53:54 260

原创【bzoj2555】SubString

*题目描述：懒得写背景了，给你一个字符串init，要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)你必须在线支持这些操作。*输入：第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init 接下来Q行，每行2个字符串Type,Str Type是ADD的话表示在后面插入字符串。 Type是QUERY的话表

2016-06-17 11:47:06 388

原创【bzoj3926】[Zjoi2015]诸神眷顾的幻想乡

*题目描述：幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的2600岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。这时幽香发现了一件非常有趣的事情，太阳花田有n块空地。在过去，幽香为了方便，在这n块空地之间修建了n-1条边将它们连通起来。也就是说，这n块空地形成了一个树的结构。有n个

2016-06-17 09:46:42 390

原创【bzoj2946】[Poi2000]公共串

*题目描述：给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务： l 读入单词 l 计算最长公共子串的长度 l 输出结果 *输入：文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。 *输出：仅一行，一个整数，最长公共子串的长

2016-06-16 13:41:17 483

原创 Codeforces Round #354 (Div 2)

A题：*题目描述：给你一个1～n的排列，问只交换一次后，1和n距离的最大值。 *题解：贪心。把1或n交换到最旁边肯定是最优的。 *代码：#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#ifdef WIN32 #define LL "%I64d"#else #define

2016-06-14 19:23:02 246

原创【bzoj4320】ShangHai2006 Homework

*题目描述： 1：在人物集合 S 中加入一个新的程序员，其代号为 X,保证 X 在当前集合中不存在。 2：在当前的人物集合中询问程序员的mod Y 最小的值。（为什么统计这个？因为拯救过世界的人太多了，只能取模） *输入：第一行为用空格隔开的一个个正整数 N。接下来有 N 行，若该行第一个字符为“A” ，则表示操作 1；若为“B”，表示操作 2；其中对于 1

2016-06-13 20:53:31 338

原创【bzoj1975】[Sdoi2010]魔法猪学院

*题目描述： iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一

2016-06-12 11:48:51 283

原创【bzoj3162】独钓寒江雪

*题目描述： *题解：树哈希+组合数学。对于树的形态相同的子树就一起考虑。 *代码：#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#ifdef WIN32 #define LL "%I64d"#else #define LL "%lld"#endif#ifde

2016-06-11 16:56:11 338

原创【bzoj1468】Tree

*题目描述：给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K *输入： N（n<=40000）接下来n-1行边描述管道，按照题目中写的输入接下来是k *输出：一行，有多少对点之间的距离小于等于k *样例输入： 7 1 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2 10 *样例输出： 5 *题

2016-06-01 17:04:07 351

原创 Codeforces Round #353(Div 2)

信息课闲着无聊打的一场cf模拟赛。A题：*题目描述：已知一个等差数列的首项和公差，问某个数在不在等差数列内？ *题解：直接模拟，注意零和负数要判，不然直接模会出错。 *代码：#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#ifdef WIN32 #define LL "%I64d

2016-05-27 22:05:18 186

原创【bzoj1123】[POI2008]BLO

*题目描述： Byteotia城市有n个 towns m条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 所有towns连通。 *输入输入n<=100000 m<=500000及m条边 *输出：输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。 *样例输入： 5 5 1 2 2 3 1 3 3 4 4 5 *样例输出：

2016-05-27 16:07:32 335

原创【bzoj2395】[Balkan 2011]Timeismoney

*题目描述：有n个城市(编号从0..n-1)，m条公路(双向的)，从中选择n-1条边，使得任意的两个城市能够连通，一条边需要的c的费用和t的时间，定义一个方案的权值v=n-1条边的费用和*n-1条边的时间和，你的任务是求一个方案使得v最小 *输入：第一行两个整数n,m,接下来每行四个整数a,b,c,t,表示有一条公路从城市a到城市b需要t时间和费用c *输出：【output

2016-05-26 14:34:45 379

原创【bzoj1179】[Apio2009]Atm

*题目描述： *输入：第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编

2016-05-25 20:35:26 305

原创【bzoj4551】[Tjoi2016&Heoi2016]树

*题目描述：在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）你能帮帮他吗? *输入：输入第一行两个正整数N和Q分别

2016-05-25 19:07:31 315

原创【bzoj4554】[Tjoi2016&Heoi2016]游戏

*题目描述：在2016年，佳缘姐姐喜欢上了一款游戏，叫做泡泡堂。简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小H想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。给定一张n*m的网

2016-05-25 18:50:18 433

原创【bzoj3809】Gty的二逼妹子序列

*题目描述： Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便，我们规定妹子们的美丽度全都在[1,n]中。给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl…sr中，

2016-05-23 20:56:14 541

空空如也

空空如也