NOIP模拟（20171031）T2 朋友（BZOJ2143 飞飞侠）
题目链接 BZOJ2143 orz题解 我们引入云端的概念 建立一个包含 n∗m∗(n+m−2) 个点的分层图 G[1⋯n][1⋯m][1⋯n+m−2] 其中 G[n][m][0] 表示街区， G[n][m][h](h>0) ...
BZOJ4719 [Noip2016]天天爱跑步
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。 本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！ Description小c同学认为跑步非常有趣,于是决...
【bzoj 十连测】[noip2016十连测第八场]Problem B: 降雷皇（最长上升子序列+线段树|next数组）
Problem B: [noip2016十连测第八场]降雷皇 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 39 Solved: 20 [ Submit][ Status][ Web Board] Description...
【bzoj 十连测】[noip2016十连测第五场]Problem A: simple（bfs）
【题解】【BFS】【T1一眼exgcd。。。吓哭了】【还好，其实只是一个模拟】【BFS搜[1,q]中所有能到达的高度，但由于q范围过大，O（n）就爆炸了。有一个很良心的性质：若ax+by=c成立，那么ax+by=2*c也能成立。所以，在[0,n]的范围内搜索f[i]，f[i]表示%n等于i的最小...
【bzoj 十连测】[noip2016十连测第二场]Problem B. Market（dp:01背包）
【题解】【背包dp】 【由于n很小，m很大，所以一般的暴力背包dp一定会超时】 【所以我们把物品和预算都按时间排序，按每一时间戳dp一遍，并二分求出此时满足条件的最大价值】 #include<cstdio>#include<cstring>#include<alg...
【bzoj 十连测】[noip2016十连测第九场]Problem C: 小P的生成树（kruskal+数学知识）
【题解】【kruskal】 【因为要使生成树的边长和模长最大，那么只需每个复数在其方向向量的投影最大。so，可以把投影作为权值来做最大生成树。】 【kruskal的理论告诉我们：生成树的大小只与各边的相对边长有关，也就是说，只需考虑各边的大小关系尽量选权值大的边建生成树就行】 【考虑两边权值： ...
【bzoj 十连测】[noip2016十连测第八场]Problem C: 幻魔皇（递推）
Problem C: [noip2016十连测第八场]幻魔皇 Time Limit: 10 Sec Memory Limit: 512 MB Submit: 16 Solved: 10 [ Submit][ Status][ Web Board] Descript...
【bzoj 十连测】[noip2016第一场]Problem C. Walk（dfs）
在 【题解】【dfs】【这道题的瓶颈主要在于建图，因为点实在是太太太多了！这样就导致需要枚举的边特别多。如果直接建图跑，果断TLE】【所以考虑调整一下，使在BFS时需要枚举的边的数量减少一些。类似于以前一个代换的思路】【类似拆点，将每个点转变为2^20+i并与当前点的权连边，并把2^20内的每个值...
【bzoj 十连测】[noip2016十连测第二场]Problem C. Dash Speed（树链剖分+并查集）
【题解】【树链剖分+并查集+二分】 【线段树维护边的信息，类似next数组的存储。并查集维护父子信息和每个区间的起点终点。考虑每次限定一个速度范围，速度在这个范围内的边都可以操作。分治，每次做完一个区间再把当前不符合的递归到下一区间处理，由于存在回溯和分治两侧，所以这里并查集不能进行路径压缩。...
[BZOJ 3629][ JLOI2014 ]聪明的燕姿
这道题考试选择打表，完美爆零。。算数基本定理：任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=P₁^a₁ P₂^a₂…Pn^an，这里P₁<P₂<…<Pn均为质数，其诸指数ai是正整数。这样的分解称为N的标准分解式。约数和定理：对于任意一个大于1的正整数N可以分解正整...
BZOJ_5118_Fib数列2_矩阵乘法+欧拉定理
BZOJ_5118_Fib数列2_矩阵乘法+欧拉定理DescriptionFib定义为Fib(0)=0,Fib(1)=1,对于n≥2,Fib(n)=Fib(n-1)+Fib(n-2)现给出N，求Fib(2^n).Input本题有多组数据。第一行一个整数T，表示数据组数。接下来T行每行一个整数N，含义...
BZOJ 1355 & KMP
BZOJ放这种丝帛我也是醉了...不过来填一下求最小循环节的坑...以这道题为例,相同文本串粘起来的串中取一小节,可以把任意一个字符看做文本串头.那么我们一次KMP求出next函数然后显见,最后一个字符它会与上一个循环串的尾匹配,所以减一减就好啦.../*======================...
NOI模拟（5.11） BJOID2T3 治疗之雨 （bzoj5292）
治疗之雨 题目背景： 5.11 模拟 BJOI2018D2T3 分析：期望DP + 高斯消元优化 我对这道题真的是有一千句喵喵喵，因为一句特判没写，100变10分，内心崩溃。直接说正解吧，定义dp[i]表示还剩i点血的期望步数，f[i]表示在k次攻击中被打中i次的概率。显然： 显然，对于每一...
BZOJ4195 程序自动分析
Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束 条件，请判定是否可以分别为每一个变量赋予恰当的值，使得...
bzoj1196: [HNOI2006]公路修建问题（最小生成树+模板题）
bzoj题目链接 luogu题目连接 题目大意： 1、n个点，m-1条边，每条边有两个权值，权1表示用高价修路，权2表示用低价修路。 2、求：选k条高价路的情况下，最小生成树的边权最大值是多少？ 解题思路： 1、题目框架和昨天做的2654tree似乎一样，都是双色道路，其中一...
【BZOJ 4011】[HNOI2015]落忆枫音
题目描述 给出一个 n 个节点 m 条边的有向无环图，外加一条有向边 (x,y) ，求以 1 为根的生成树数量。（保证原 m 条边中不指向 1 号节点） 题目解析 GG，考试时看了一眼第一发现没有思路，于是果断暴力，开...
【BZOJ】T3240 矩阵游戏
题目描述 F[1][1]=1 F[i,j]=a*F[i][j-1]+b (j!=1) F[i,1]=c*F[i-1][m]+d (i!=1) 求F[n,m]%1000000007的值 NOI2013 单纯的前50分，可以作为矩阵乘法的模板题，根据二维递推式构造矩阵，快速幂加速递推即可...
NOIP2014 D2T3 解方程 BZOJ3751 UOJ20 数论 秦九韶算法 玄学
大家都很强， 可与之共勉 。 话说这是一道简单爆了的难题。 【NOIP2014】解方程 已知多项式方程： a0+a1x+a2x2+...+anxn=0 求这个方程在 [1,m] ...
【BZOJ 1565】 [NOI2009]植物大战僵尸
1565: [NOI2009]植物大战僵尸 Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1488 Solved: 707 [ Submit][ Status][ Discuss] Description Inp...
[Noi2016]区间 BZOJ4653 洛谷P1712 Loj#2086
额... 首先，看到这道题，第一想法就是二分答案+线段树... 兴高采烈的认为我一定能AC，之后发现n是500000... nlog^2=80%，亲测可过... 由于答案是求满足题意的最大长度-最小长度最小，那么我们可以考虑将区间按长度排序 之后，因为我们是需要最大最小，所以，我们必定选择在排完序的...