inklutcuah-CSDN博客

原创【jzoj5405】【NOIP2017提高A组模拟10.10】【Permutation】

2017-10-15 15:05:26 651 1

原创【jzoj5389】【NOIP2017提高A组模拟9.26】【解梦】

descriptionDYY 很善于解梦，昨晚，他梦见自己来到了一个高度发达的国度。众所周知，我们现在有极为常用的三级运算，+、、^。其中，a*b=a+a+a+…+a(b 个a)，a^b=a*a*a…*a(b 个a)。但是，在这个国家，还有第四级运算——♂，a♂b=a^a^a^…^a(b 个a，从左往右计算)。同时，由于这个国家的历史背景，他们非常反感高精度，所以a♂b 的结果是经过1e9+7 取模

2017-09-28 19:11:19 576

原创【jzoj5368】【NOIP2017提高A组模拟9.16】【为逝去的公主献上的七重樱】【单调队列】

descriptionsolution可以发现答案可能出现在两个部分，没有加入过的最小的数，出去了的最小数。对于前一个部分可以用桶记录，对于一部分我们构出一个队列，如果一个数在另一个数加入前加入且比那个数大，那它一定不可能出现在答案中，用单调队列维护即可。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm

2017-09-17 07:35:37 575

原创【jzoj5358】【NOIP2017提高A组模拟9.12】【BBQ】

descriptionsolution可以发现组合数的意义就是在二维平面上一个点只能往上往右走走到另一个点的方案数，这个问题可以用递推来解决，相当于在(-a[i],-b[i])上都加一，求f(a[i],b[i])的和，减去i，j相等的情况再除以二即可。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>

2017-09-16 11:07:31 386

原创【jzoj5359】【NOIP2017提高A组模拟9.12】【Arrays and Palindrome】

descriptionsolution发现A只会有两个奇数或者没有奇数，发现a一定将两个奇数放在头尾（如果有的话），剩下的第一个数加一，最后一个数建议，中间不变即为b（注意1的情况）。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL long

2017-09-13 22:22:52 465

原创【jzoj5360】【NOIP2017提高A组模拟9.12】【Shorten Diameter】

description给定一棵有n 个点的树，现要求不断删点直到树的直径<=K，求最少需要删除的点数。一个点可以被删掉当且仅当该点的度数为1。保证树的形态为随机生成（请勿过度解读）。solution由于树的形态是随机的，可以考虑当k为偶数时，枚举一个点往外扩展k/2层，当k为奇数时，枚举一条边从两个点往外扩展k/2层，统计最大值即可。code#include<cstdio>#include<cma

2017-09-13 22:19:22 485

原创【jzoj4726】【NOIP2016提高A组模拟8.22】【种花】【可撤销贪心】

description经过三十多个小时的长途跋涉，小Z和小D终于到了NOI现场——南山南中学。一进校园，小D就被花所吸引了（不要问我为什么），遍和一旁的种花园丁交（J）流（L）了起来。他发现花的摆放竟有如此奥秘：圆形广场共有 N 个种花的位置，顺时针编号1到N。并且每个位置都有一个美观度ai ，如果在这里种花就可以得到这ai 的美观度。但由于地处南山土壤肥力欠佳，两株花不能种在相邻的位置（1号和N号

2017-09-10 10:18:51 623

原创【jzoj5350】【NOIP2017提高A组模拟9.7】【陶陶摘苹果】【动态规划】

descriptionsolution题目的意思是板凳不可重叠，数据不能直接摘苹果。对苹果排序，对凳子按r从小到大排序。设f[i][j]表示前i个凳子，选了j个，最后一个选了i的最大贡献，枚举由那个f[k][j-1]转移过来，能贡献多少就在苹果序上二分再max一下i左端点k右端点+1即可。code#include<cstdio>#include<cmath>#include<cstring>#

2017-09-08 22:17:28 762

原创【jzoj5347】【NOIP2017提高A组模拟9.5】【遥远的金字塔】【斜率优化动态规划】

descriptionsolution考虑动态规划，设f[i][j]表示前i个，用了j个矩阵的最大答案。f[i][j]=maxk<=if[k][j−1]+a[i]∗(i−k)f[i][j]=\max_{k<=i}f[k][j-1]+a[i]*(i-k)，其中a[i]表示第i段的长度。可以发现对于i的两个决策点x,y（x<y）x,y（x<y），当(f[y]−f[x])/(y−x)<a[i](f[y]-

2017-09-08 22:12:22 460

原创【jzoj5346】【NOIP2017提高A组模拟9.5】【NYG的背包】【贪心】

descriptionsolution考虑贡献为正的，显然花费a最少先做，考虑贡献为负的，可以将ab调转过来，那显然花费最少的先做，也就是b最小的先做。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL long long#define ULL

2017-09-06 22:15:53 470

原创【jzoj5343】【NOIP2017模拟9.3A组】【健美猫】

descriptionsolution可以把点投射到以i坐标为x坐标，以a[i]为y坐标的二维平面，考虑维护两条斜率为1直线，点到直线竖直距离和即为答案，分别为维护多少个点在直线上，用两个桶维护即可，坐标分别为到y=x竖直距离和到(n,0)曼哈顿距离。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>

2017-09-03 16:30:43 661

原创【jzoj5344】【NOIP2017模拟9.3A组】【摘果子】【树型依赖背包】

descriptionsolution直接树型依赖背包没什么好说的。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL long long#define ULL unsigned int#define fo(i,j,k) for(int i=

2017-09-03 11:34:36 501

原创【jzoj5341】【NOIP2017模拟9.2A组】【密州盛宴】

descriptionsolution可以发现如果把1看做1，把0看做-1，做后缀和如果小于-1表示东坡不能吃够n天，否则就一定合法。可以发现如果要移动就一定将后面的0移到最前面，移动x个就是前面的数往后移x位，往后移一位相当于把后缀和+1，可以发现最小后缀和是-x，那至少要往前移x-1个0。code#include<cstdio>#include<cmath>#include<cstring>

2017-09-02 16:28:25 481

原创【jzoj5340】【NOIP2017模拟9.2A组】【春思】

descriptionsolution分解质因数然后等比数列求和。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL long long#define ULL unsigned int#define fo(i,j,k) for(LL i=j;

2017-09-02 11:49:20 535

原创【jzoj3418】【NOIP动态规划专题】【选课】【树型依赖动态规划】

description大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课，并通过考核就能获得相应的学分。学生最后的学分是他各门课学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。例如，《剥皮术》就必须在选修了《屠龙术》后才能选修。我们称《屠龙术》是《剥皮术》的先修课。每门课的直接先修课最多之有一门。两

2017-09-01 22:02:23 841

原创【jzoj5337】【NOIP2017提高A组模拟8.25】【夜莺与玫瑰】【莫比乌斯反演】

descriptionsolution我们可以发现一个性质ans=n+m+∑n−1i=1∑j=1m−1([(i,j)==1](n−i)(m−j)−[(i,j)==2](n−i)(m−j))ans=n+m+\sum_{i=1}^{n-1}\sum{j=1}^{m-1}([(i,j)==1](n-i)(m-j)-[(i,j)==2](n-i)(m-j))考虑两条重合的直线（以两个端点确定一条直线的线段）

2017-08-25 15:45:56 486

原创【jzoj5338】【NOIP2017提高A组模拟8.25】【影子】【点分治】

descriptionsolution直接点分治，维护点权最小值和边权和，按点权最小值排序，两个指针维护一下最大值即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for(int i=j;i

2017-08-25 11:51:13 420

原创【jzoj5334】【NOIP2017提高A组模拟8.24】【空】【扫描线】【set】

descriptionsolution考虑用扫描线，可以发现有相交和内含两种情况，相交就是l+r的差，内含就是r-l的差，可以分别两次用set维护。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k)

2017-08-24 12:00:17 344

原创【jzoj5335】【NOIP2017提高A组模拟8.24】【早苗】【矩阵乘法快速幂】

descriptionsolution设f[i][j]表示到第i天，往前j天不同的方案数，可以转移到f[i+1][k]，当k<=j时系数是1，当k==j+1时系数是m-j，当然要保证j!=m，可以发现这时可以用矩阵乘法快速幂解决的。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorit

2017-08-24 11:39:23 416

原创【jzoj3327】【陶陶的难题】【类欧几里得】

description陶陶给Crash出了一个大难题，他要求Crash计算出下面式子的值：其中A,B,C,L,R均为给定正整数。由于答案可能会很大，你只需要输出答案mod 1,000,000,007后的值。solution可以发现这就是裸的类欧，求出g即可。类欧几里得问题推导code#include<cstdio>#include<cmath>#include<cstring>#include

2017-08-23 21:56:44 406

原创【类欧几里得学习小记】

类欧几里得算法因为形式上像欧几里得算法而得名，其时间复杂度也和欧几里得算法一致，类欧几里得算法有很多应用，下面只举部分例子。目标求出以下三个函数值f(a,b,c,d)=∑ni=0⌊ai+bc⌋f(a,b,c,d)=\sum_{i=0}^n\lfloor{ai+b\over c}\rfloorg(a,b,c,d)=∑ni=0i⌊ai+bc⌋g(a,b,c,d)=\sum_{i=0}^ni\lfloor

2017-08-23 21:54:05 320

原创【jzoj5333】【NOIP2017提高A组模拟8.23】【大新闻】【可持久化线段树】

descriptionsolution可以发现把序列倒过来就是在队末加或删数维护前缀权值线段树即可，这不就是主席树，直接做就可以了。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for(in

2017-08-23 14:15:46 271

原创【jzoj5332】【NOIP2017提高A组模拟8.23】【密码】【ac自动机】【动态规划】

descriptionsolution先把秘钥建ac自动机，设f[i][j][k][l]表示现在填到第i位，对应ac自动机上j结点，包含k个秘钥，有没有顶上界，枚举下一个填什么转移即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long lon

2017-08-23 14:09:51 311

原创【jzoj5328】【NOIP2017提高A组模拟8.22】【世界线】【bitset】

descriptionsolution这题显然要求一个点能通过边到达多少个点，这样我们可以用bitset来做，然而直接做会爆空间，可以考虑做两次，分别考虑和一半点的连通性。code#include<bitset>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#d

2017-08-22 15:22:00 358

原创【jzoj5329】【NOIP2017提高A组模拟8.22】【时间机器】【数据结构】【扫描线】

descriptionsolution把机器和电阻按l排序，l相等时电阻排前面，扫描线从左往右扫，遇到电阻把右端点放入set，遇到机器lowerbound找到最小的r比机器的r大匹配即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long lo

2017-08-22 12:28:56 314

原创【jzoj5322】【GDOI2017模拟8.21】【小朋友】【状态压缩动态规划】

descriptionsolution可以发现三人桌不会超过3个，设f[i][j][s]表示到第i个人，用了j个3人桌，往前k+1个人选取状态为s。每个状态最前的位为1就一定要安排一桌，暴力枚举即可，到了最后i要枚举到n+k+1，n以后的不算贡献，但是要保证n-k到n的人都被选完。code#include<cstdio>#include<cmath>#include<cstring>#incl

2017-08-21 14:21:21 259

原创【jzoj5315】【NOIP2017提高A组模拟8.19】【小串串】【sam 】

descriptionsolution构出sam，求出fail树子树大小，贡献为size[x]^2*(mx[fa[x]]-mx[x])。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define ULL unsigned lo

2017-08-19 17:24:17 328

原创【jzoj5306】【NOIP2017提高A组模拟8.18】【棋盘游戏】

description这个游戏上在一个无限大的棋盘上，棋盘上只有一颗棋子在位置（x,y）(x,y>=0)棋盘的左下角是（0，0）Amphetamine每次都是第一个移动棋子，然后Amphetamine与Alphago轮流移动。每一轮可以做以下三种中的一种操作：1）在同一行，将棋子从当前位置向左移动任意格；2）在同一列，将棋子从当前位置向下移动任意格；3）将棋子从当前位置向下移动k格再向左移动k格（

2017-08-18 20:25:51 494

原创【jzoj5305】【NOIP2017提高A组模拟8.18】【C】

descriptionsolutiontarjan缩环，一个环贡献2^1，跑lca即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for(int i=j;i<=k;i++)#define

2017-08-18 11:40:28 315

原创【jzoj5290】【NOIP2017提高组A组模拟8.17】【行程的交集】

Description豪哥生活在一个n个点的树形城市里面，每一天都要走来走去。虽然走的是比较的多，但是豪哥在这个城市里面的朋友并不是很多。当某一天，猴哥给他展现了一下大佬风范之后，豪哥决定要获得一些交往机会来提升交往能力。豪哥现在已经物色上了一条友，打算和它（豪哥并不让吃瓜群众知道性别）交往。豪哥现在spy了一下这个人的所有行程起点和终点，豪哥打算从终点开始走到起点与其相遇。但是豪哥是想找话题的，他

2017-08-17 22:10:50 352

原创【jzoj5289】【NOIP2017提高组A组模拟8.17】【偷笑】【数据结构】

Descriptionberber走进机房，边敲门边喊：“我是哔哔”CRAZY转过头：“我警告你，哔哔刚刚来过！”“呵呵呵呵……”这时，哔哔站了起来，环顾四周：“你们笑什么？……”巧了，发出笑声的人都排成了一排，每个人刚开始发出的笑声值为a[i]的笑声。但是有些笑声哔哔是听不出来的，他只听得出笑声值只包含2和3的数字，比如说什么2333。但是同学们还是很会秀操作的。对于操作add l r x表示l

2017-08-17 16:10:42 687

原创【jzoj5288】【NOIP2017提高组A组模拟8.17】【球场大佬】

Description每天下午，古猴都会去打羽毛球。但是古猴实在是太强了，他必须要到一些比较强的场去打。但是每个羽毛球场都有许多的人排着队，每次都只能上四个人，每个人都有自己的能力值，然而这四个人的总能力的高低与否才是古猴是否决定参加这个场的关键。每四个人的总能力值的定义是：任意选两个与另两个PK，能力值的贡献是较高的一组减去较低的一组。比如能力值为5和7的去PK 6和10的差值，那么用较高的减去较

2017-08-17 11:35:45 432

原创【jzoj5286】【NOIP2017提高A组模拟8.16】【花花的森林】【时间倒流】

题目大意解题思路离线时间倒流，逐渐加边，用并查集维护连通块直径，可以发现两个连通块合并新直径，一定是原来直径四个点组合之一，倍增算一下即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for

2017-08-16 12:32:32 275

原创【jzoj5285】【NOIP提高组模拟赛A组8.16】【排序】

题目大意解题思路用栈模拟，如果后面没有比栈顶大的数就弹出栈即可。code#include<set>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for(int i=j;i<=k;i++)#define fd(i,j,k) f

2017-08-16 11:45:14 246

原创【jzoj5281】【NOIP提高组模拟A组8.15】【钦点】

题目大意解题思路用链表维护每个格子往右往下到那个格子，交换时更改边界连接即可，在原本的行和列之间加入空白列可以简化操作。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LL long long#define fo(i,j,k) for(int i=j;i<=k;i++)#defi

2017-08-15 21:29:00 295

原创【jzoj3771】【NOI2015模拟8.15】【小 Z 的烦恼】

题目大意小 Z 最近遇上了大麻烦，他的数学分析挂科了。于是他只好找数分老师求情。善良的数分老师答应不挂他，但是要求小 Z 帮助他一起解决一个难题问题是这样的，现在有 n 个标号为 1～n 的球和 m 个盒子，每个球都可以放进且只能放进一个盒子里面，但是要满足如下的规则：1. 若把标号为 i 的球放进了第 j 个盒子，那么标号为 2*i 的球一定要在第 j+1 个盒子里面(若 j2. 若把标号为

2017-08-14 19:35:57 320

原创【jzoj5251】【GDOI2018模拟8.11】【决战】【状态压缩动态规划】

题目大意解题思路设f[i][j][s]表示第i行放了j个哲学家01状态是s，预处理转移方法，计算j的上下界优化常数即可以通过。实在不行就手动开o2。code#pragma GCC optimize(2)#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL

2017-08-13 09:03:28 327

原创【jzoj5250】【GDOI2018模拟8.11】【质数】

题目大意解题思路ans=∑ni=1∑d|i[(d,i/d)==1]ans=\sum_{i=1}^n\sum_{d|i}[(d,i/d)==1]因为2f(i)2^{f(i)}相当于从i的质因子中考虑选不选进一个数里，要么选要么不选，等同于拆成两个互质的数。ans=∑ni=1∑d|i∑p|d&&p|(i/d)[(d,i/d)==1]ans=\sum_{i=1}^n\sum_{d|i}\sum_{p|d\

2017-08-12 20:28:09 352

原创【jzoj1617】【SCOI2005】【互不侵犯】【状态压缩动态规划】

题目大意在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。解题思路设f[i][j][k][s]表示到i，j这个格子，之前放了了k个国王，最后n+1个格子的状态为s，方案数是多少，转移就很简单了，只需滚动一下数组卡空间即可。code#include<cstdio>#include<cmath>#in

2017-08-11 15:48:09 237

原创【jzoj5248】【NOIP2017提高A组模拟8.10】【花花的聚会】【动态规划】【可持久化线段树】

题目大意解题思路设f[i]表示i到根最小花费，用可持久化线段树维护到根的路径上的f，区间求最小值即可。code#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define LF double#define LL long long#define ULL unsigned int#define fo(

2017-08-10 16:15:52 284

空空如也

空空如也