NOI2018准备Day3
noip2016成绩出来了，199,268名noip2017需要考过6个女生才能进省队，不包括明年会突然跳出来的大神。。。。。。今天晚上玩了一晚上，做了2道题。这事儿只干今晚一次
NOI2017蔬菜(贪心)
小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。 在蔬菜仓库中，共存放有 n 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各 方面因素，设计合理的销售方案，以获得最多的收益。 在计算销售蔬菜的收益时，每销售一个单位第 i 种蔬菜，就可以获得 ai 的收益。 特别地，由于政策鼓励商家进行多样化...
luogu P4008 [NOI2003]文本编辑器 splay 块状链表
LINK：文本编辑器这个东西感觉块状链表写细节挺多 (块状链表本来就难写解释一下块状链表的做法：其实是一个个数组块 然后利用链表给链接起来 每个块的大小为sqrt(n).这样插入删除的时候直接暴力插入删除即可 复杂度都是根号的。插入的时候当前的块过大的时候就要分裂 查询时对于大小为0的块记得及时删除...
【BZOJ4944】【NOI2017】泳池 概率DP 常系数线性递推 特征多项式 多项式取模
题目大意有一个\(1001\times n\)的的网格，每个格子有\(q\)的概率是安全的，\(1-q\)的概率是危险的。定义一个矩形是合法的当且仅当：这个矩形中每个格子都是安全的必须紧贴网格的下边界问你最大的合法子矩形大小为\(k\)的概率是多少。\(n\leq {10}^9,k\leq 1000...
【BZOJ】【2879】【NOI2012】美食节
网络流/费用流跟 BZOJ 1070 修车 几乎是一道题，只是这题“要修的车”（即菜）多了很多……几乎是从$n$变成了$n^2$，所以建图的时候就得动态加点……也就是说，当一个厨师已经确定了他的后k道菜的时候，再加入表示倒数第k+1道菜的节点。我个xx一开始写成了每次加一层……不 T 才怪……加点过...
【bzoj1565】[NOI2009]植物大战僵尸 拓扑排序+最大权闭合图
原文地址：http://www.cnblogs.com/GXZlegend/p/6808268.html题目描述输入输出仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。样例输入3 210 020 0-10 0-5 1 0 0100 1 2 1100 0...
【bzoj1565】 NOI2009—植物大战僵尸
http://www.lydsy.com/JudgeOnline/problem.php?id=1565 (题目链接)题意给出$n*m$的棋盘，僵尸攻击每个格子可以获得$v$的分数，每个格子又会保护一些别的格子，想攻击被保护的格子必须先攻击没被保护的格子。问获得的最大分数。Solution建图，被保...
noi 7219:复杂的整数划分问题
7219:复杂的整数划分问题查看提交统计提问总时间限制: 200ms内存限制: 65536kB描述将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。输入标准的输入...
noi 求分数序列和 x
求分数序列和总时间限制: 1000ms内存限制: 65536kB描述有一个分数序列 q1/p1,q2/p2,q3/p3,q4/p4,q5/p5,.... ,其中qi+1= qi+ pi, pi+1=qi, p1= 1, q1= 2。比如这个序列前6项分别是2/1,3/2,5/3,8/5,13/8,2...
BZOJ4650: [Noi2016]优秀的拆分
考场上没秒的话多拿5分并不划算的样子。思想其实很简单嘛。要统计答案，求以每个位置开始和结束的AA串数量就好了。那么枚举AA中A的长度L，每L个字符设一个关键点，这样AA一定经过相邻的两个关键点。计算出相邻关键点的最长公共前后缀，把对应的位置区间加一下。求lcp和lcs可以用后缀数组，也可以用hash...
NOI 国家集训队论文集
鉴于大家都在找这些神牛的论文。我就转载了这篇论文合集国家集训队论文分类组合数学计数与统计2001 - 符文杰：《Pólya原理及其应用》2003 - 许智磊：《浅谈补集转化思想在统计问题中的应用》2007 - 周冬：《生成树的计数及其应用》2008 - 陈瑜希《Pólya计数法的应用》数位问题200...
P2704 [NOI2001]炮兵阵地
题目描述司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：...
[洛谷P2704] [NOI2001]炮兵阵地
洛谷题目链接:[NOI2001]炮兵阵地题目描述司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在...
P2704 [NOI2001]炮兵阵地 (状压DP)
题目：P2704 [NOI2001]炮兵阵地解析：和互不侵犯一样就是多了一格用\(f[i][j][k]\)表示第i行，上一行状态为\(j\)，上上行状态为\(k\)的最多的可以放的炮兵发现\(100\times 1024\times 1024\)开不下还是通过简单的搜索发现就算\(m==10\)时合...
洛谷P4774 BZOJ5418 LOJ2721 [NOI2018]屠龙勇士（扩展中国剩余定理）
题目链接：洛谷BZOJLOJ题目大意：这么长的题面，就饶了我吧emmm这题第一眼看上去没法列出同余方程组。为什么？好像不知道用哪把剑杀哪条龙……仔细一看，要按顺序杀龙，所以获得的剑出现的顺序也是固定的。那么如果能把所有龙杀死，就能模拟出哪把剑杀那条龙了。（以下设所有除 $n,m$ 外的数的最大值为 ...
luogu P4774 [NOI2018]屠龙勇士
传送门这题真的是送温暖啊qwq,而且最重要的是yyb巨佬在Day2前几天正好学了crt,还写了博客 然而我都没仔细看,结果我就同步赛打铁了QAQ我们可以先根据题意,使用set维护,求出每次的攻击力然后对于一条龙,要使得砍到生命值能加到0,那么 攻击力\(a_i\) * 次数\(x\) 要和 血量\(...
[NOI2005]维护数列——平衡树观止
本题题解并不详细，不推荐大家看这一篇。可以看这篇题目描述请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）100%的数据中，任何时刻数列中最多含有 500 000 个数。100%的数据中，任何时刻数列中任何一个数字均在[-1 000...
洛谷2114 bzoj3668[NOI2014]起床困难综合症
题目描述21世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因： 在深邃的太平洋海底中，出现了一条名为drd的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。 ...
bzoj 1493: [NOI2007]项链工厂（线段树）
1493: [NOI2007]项链工厂Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 1256 Solved: 545[Submit][Status][Discuss]DescriptionInput输入文件第一行包含两个整数N, c，分别表示项链包含...
bzoj 2875: [Noi2012]随机数生成器
#include<cstdio> #include<iostream> #include<cstring> #define ll long long using namespace std; ll x[][],y[][],m,a,c,x0,n,g; ll che...