- 博客(363)
- 资源 (4)
- 收藏
- 关注
RSS订阅
原创 矩阵乘法的一些应用
矩阵定义很重要矩阵的计算矩阵的线性运算矩阵加矩阵减数乘矩阵其他操作计算转置共轭共轭转置矩阵乘法例题例题1斐波那契数列problem构造矩阵式矩阵快速幂code矩阵乘法codecode例题2JZOJsenior1240Fibonacci sequenceproblemanalysiscode例题3NOI2012随机数生成器problem构造矩阵式快速
2017-09-18 20:35:35
15671
1
原创 【JZOJ3743】【BZOJ5158】Alice and Bob
descriptionanalysis可以贪心还原出原xxx序列，且xxx是nnn的排列；易知aaa由是连续若干段的单调不递减区间拼起来而成而且每一段区间内差值至多为111，大概像这样1,1,2,2,2,3,...x,1,1,1,2,...,y,1,...1,1,2,2,2,3,...x,1,1,1,2,...,y,1,...1,1,2,2,2,3,...x,1,1,1,2,.....
2020-01-03 21:36:04
719
原创 【JZOJ1913】【BZOJ2124】等差子序列
description给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3)，使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。analysis找出一个长度为333的等差序列即可满足要求，长度为333的都没有，更长的序列也不存在暴力可以枚举每一个a[i]a[i]...
2019-12-24 17:32:26
540
原创 【JZOJ1914】【BZOJ2125】最短路
description给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。analysis建出圆方树后，可以知道仙人掌上每一个方点连着的边双其实就是一个简单环tarjantarjantarjan缩环的时候可以先弄出每个环的边权和并做一个前缀和，这样环中两点距离就可求设dis[i]dis[i]dis[i]表示从根节点到iii节点的...
2019-12-23 22:10:44
462
原创 【JZOJ3156】病毒传播
description病毒扩散了！村庄中共有M 个人，编号为0 到M-1，病毒症状只会持续一天，每个人可能多次感染病毒。第一天，若干个病毒携带者感染了病毒，病毒扩散就是由病毒携带者引起的，从第二天开始的每一天，编号P 的人在以下条件下就会感染病毒：(a*b)mod M=P(其中a 为前一天感染病毒的某一个人的编号，b 是其中一个病毒携带者的编号，a 和b 可能相同)例如村庄共101...
2019-12-19 16:05:13
387
原创 【JZOJ1826】银河英雄传说
题目描述 公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴
2019-12-19 15:42:11
743
原创 【JZOJ5962】【NOIP2018】货币系统
description在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1…n] 的货币系统记作 (n,a)。在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。然而， 在网...
2019-12-19 15:40:35
446
原创 【JZOJ5966】【NOIP2018】保卫王国
descriptionZ国有n座城市，n-1条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。Z国的国防部长小Z要在城市中驻扎军队。驻扎军队需要满足如下几个条件：①一座城市可以驻扎一支军队，也可以不驻扎军队。②由道路直接连接的两座城市中至少要有一座城市驻扎军队。③在城市里驻扎军队会产生花费，在编号为i的城市中驻扎军队的花费是pi。小Z很快就规划出了一种驻扎...
2019-12-19 15:40:20
366
原创 【JZOJsenior1869】三国游戏
题目描述Description小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。 在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有N 位武将（N 为偶数且不小于4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合 作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了
2019-12-19 15:39:18
437
原创 【luoguP3701】「伪模板」主席树
descriptionbyx和诗乃酱都非常都非常喜欢种树。有一天，他们得到了两颗奇怪的树种，于是各自取了一颗回家种树，并约定几年后比一比谁种出来的树更加牛x。很快，这棵树就开花结果了。byx和诗乃酱惊讶的发现，这是一棵主席树，树上长满了主席和主席的朋友们。这棵树上一共有五种人，主席(J)，记者(HK)，高人(W)，女王(E)和膜法师(YYY)。他们发现，他们的主席树上的人数相同，都为N。研...
2019-12-19 15:36:47
244
1
原创 【luoguP4768】【NOI2018】归程
description本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 nn 个节点、mm 条边的无向连通图（节点的编号从 11 至 nn）。我们依次用 l,al,a 描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免 的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述...
2019-12-18 22:05:54
283
原创 【JZOJ6435】【luoguP5666】【CSP-S2019】树的重心
descriptionanalysis需要知道一棵树的重心一定在从根出发的重链上，可以考虑先进行树链剖分弄出重儿子和次重儿子，再倍增维护重儿子由于重链上有一个或两个重心，接下来求的重心都是深度较大的，只需判断其父节点是否也满足重心的性质即可现在要断掉一条边(x,y)(x,y)(x,y)，假设xxx是yyy的父亲，需要分别求出yyy的子树的重心、以及除了yyy的子树以外的树的...
2019-12-17 17:40:39
346
原创 【JZOJ6434】【luoguP5665】【CSP-S2019】划分
descriptionanalysis首先有一个结论，对于[1,i][1,i][1,i]区间划分最后一段的和尽量小，答案会更优，具体证明参考毛爷爷的博客设f[i]f[i]f[i]为满足[1,i][1,i][1,i]划分最优时、(f[i],i](f[i],i](f[i],i]这段和最小时的最右的端点，最优划分即为从nnn开始向fff不断统计由后一段比前一段大可知sum[f[...
2019-12-16 21:59:04
480
原创 【JZOJ6433】【luoguP5664】【CSP-S2019】Emiya 家今天的饭
descriptionanalysis首先可以知道不符合要求的食材仅有一个，于是可以容斥拿总方案数减去选不合法食材的不合法方案数枚举选取哪一个不合法食材，设f[i][j]f[i][j]f[i][j]表示到第iii种烹饪方法、操作权值为jjj的方案数给每一个操作赋权值，选当前行合法食材列为000，不选当前行为111，选当前行不合法食材列为222转移是比较容易的，可知选当...
2019-12-16 21:28:00
288
原创 【JZOJ6431】【luoguP5658】【CSP-S2019】括号树
descriptionanalysis用栈维护一下树上路径未匹配的左括号，然后在树上找右括号匹配，设f[i]f[i]f[i]为iii节点的贡献，g[i]g[i]g[i]是答案为左括号可以直接继承父节点的信息，为右括号且栈非空则可以匹配，贡献值是栈顶左括号的父节点的贡献+1+1+1这个其实就是当前子序列可以拼上左括号父亲的序列，然后每一位的答案就是父节点的答案加上当前点的贡...
2019-12-16 21:11:41
249
原创 【JZOJ3673】【luoguP4040】【BZOJ3874】宅男计划
description外卖店一共有N种食物，分别有1到N编号。第i种食物有固定的价钱Pi和保质期Si。第i种食物会在Si天后过期。JYY是不会吃过期食物的。比如JYY如果今天点了一份保质期为1天的食物，那么JYY必须在今天或者明天把这个食物吃掉，否则这个食物就再也不能吃了。保质期可以为0天，这样这份食物就必须在购买当天吃掉。JYY现在有M块钱，每一次叫外卖需要额外付给送外卖小哥外送费F元...
2019-12-14 20:24:50
230
原创 【JZOJ3674】【luoguP4042】【BZOJ3875】骑士游戏
description在这个游戏中，JYY一共有两种攻击方式，一种是普通攻击，一种是法术攻击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死，怪兽的尸体可以变出其他一些新的怪兽，注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽；而采用法术攻击则可以彻底将一个怪兽杀死。当然了，一般来说，相比普通攻击，法术攻击会消耗更多的体力值（但由于游戏系统bug，并不保...
2019-12-14 15:30:29
218
原创 【JZOJ3920】噪音
descriptionFJ有M个牛棚，编号1至M，刚开始所有牛棚都是空的。FJ有N头牛，编号1至N，这N头牛按照编号从小到大依次排队走进牛棚，每一天只有一头奶牛走进牛棚。第i头奶牛选择走进第p[i]个牛棚。由于奶牛是群体动物，所以每当一头奶牛x进入牛棚y之后，牛棚y里的所有奶牛们都会喊一声“欢迎欢迎，热烈欢迎”，由于声音很大，所以产生噪音，产生噪音的大小等于该牛棚里所有奶牛（包括刚进去的奶牛x在...
2019-12-10 16:40:36
190
原创 【JZOJ3918】蛋糕
description今天是Bessie的生日，他买了一个蛋糕和朋友们一起分享，蛋糕可以看成是一个R行C列的表格，共有R*C个格子，每个格子都有一个0至9的数字，表示该格子蛋糕拥有的巧克力。现在Bessie要把蛋糕横的切3刀再竖的切3刀，由于Bessie刀法厉害，所以每个格子蛋糕都是完整的，显然蛋糕会被切成16份，然后Bessie和他的15个朋友们每人拿一份，Bessie比较客气，总是等其他朋友...
2019-12-09 22:30:35
164
原创 【JZOJ6419】模拟旅行&【BZOJ5506】【luoguP5304】旅行者
description某国有n座城市，这些城市之间通过m条单向道路相连，已知每条道路的长度。不过，小X只对其中k座城市感兴趣。为了更好地规划模拟旅行路线，提升模拟旅行的体验，小X想要知道他感兴趣的城市之间两两最短路的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。作为一个肥宅，小X根本懒得写程序来解决这道问题，于是他把这个问题丢给了你。J 国有 nn 座城市，这些城市之间通过 m...
2019-11-12 10:15:41
227
原创 【JZOJ6421】匹配
descriptionanalysis对于普通树形DPDPDP可以设f[i][0/1],g[i][0/1]f[i][0/1],g[i][0/1]f[i][0/1],g[i][0/1]表示[1,i][1,i][1,i]的线段树的最大值、方案数000表示不选择根与某个儿子相连，111表示选择根与某个儿子相连，由i2,i−i2{i\over 2},i-{i\over 2}2i,i−2...
2019-11-12 09:39:28
229
原创 【JZOJ6411】上网
descriptionanalysis如果把所有大小关系连成边，小的往大的连，就可以直接上拓扑暴力连边时间复杂度O(n2)O(n^2)O(n2)，然而连边的过程，考虑用线段树优化线段树上的所有儿子节点向父亲节点连000边，每个操作被分成k+1k+1k+1个小区间，然后该操作的编号向kkk个区间最大值连111边对于线段树上表示小区间的log\loglog个区间，...
2019-11-09 14:55:56
255
原创 【BZOJ2938】【luoguP2444】病毒
description二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。示例：例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病...
2019-11-08 19:45:43
158
原创 【JZOJ6409】困难的图论
description给定由 n 个点 m 条边组成的无向连通图，保证没有重边和自环。你需要找出所有边，满足这些边恰好存在于一个简单环中。一个环被称为简单环，当且仅当它包含的所有点都只在这个环中被经过了一次。注意到这些边可能有很多条，你只需要输出他们编号的异或和即可。analysis然而复习了一波tarjantarjantarjan，其实这个简单环就是求点双求出每个点双，判断...
2019-11-07 15:46:59
574
原创 【JZOJ6403】a
descriptionanalysis考虑(0,0,0)(0,0,0)(0,0,0)走到某个点(i,j,k)(i,j,k)(i,j,k)的贡献，相当于插板问题i+ji+ji+j个空插kkk个板可以有空，iii个空插jjj个板可以有空，就是Ci+j+kk∗Ci+jjC^k_{i+j+k}*C^j_{i+j}Ci+j+kk∗Ci+jj对于每个障碍，要算出被它包含的障碍走到它...
2019-11-05 08:19:32
143
原创 【JZOJ6285】飘雪圣域
descriptionanalysis从求联通块出发根本没做法，于是考虑连通块里面的边对于一个询问[l,r][l,r][l,r]，一条边的左端点≥l≥l≥l且右端点≤r≤r≤r才在这个区间的点之间于是对于边和询问排序，依次把边加入树状数组，然后查询当前询问区间里的边条数就知道了联通块个数code#pragma GCC optimize("O3")#pragma ...
2019-11-02 08:53:52
164
原创 【JZOJ6389】小w学图论
description小w这学期选了门图论课，他在学习点着色的知识。他现在得到了一张无向图，并希望在这张图上使用最多n种颜色给每个节点染色，使得任意一条边关联的两个节点颜色不同。小w获得一张n个节点m条边的基图，并得到了一份神秘代码。他会根据这份代码的内容构建完整的无向图。while(1){int modify_tag=0;for(int x=1;x<=n;x++)for(int...
2019-10-27 11:39:23
461
原创 【JZOJ6388】小w的作业
descriptionanalysis二分一个角度，首先假设该弧度角θ∈[π2,π]\theta \in[{\pi \over 2},\pi]θ∈[2π,π]，要找的直线斜率k∈(−∞,tanθ]k\in(-∞,\tan\theta]k∈(−∞,tanθ]要找这种直线，两个点(xi,yi),(xj,yj)(x_i,y_i),(x_j,y_j)(xi,yi),(xj,yj...
2019-10-27 08:38:38
287
原创 【JZOJ6384】珂学家
descriptionanalysis注意配出来的饮料不可以再配成其他饮料，所以肯定有O(n2)O(n^2)O(n2)的枚举而且可口度两两互不相同，搞得我以为这是神仙题考虑把两个试剂[l1,r1],[l2,r2][l_1,r_1],[l_2,r_2][l1,r1],[l2,r2]合并，[l1+l2,r1+r2][l_1+l_2,r_1+r_2][l1+l2,r1...
2019-10-25 17:08:50
292
原创 【JZOJ5730】【luoguP2146】【Comet OJC0396】软件包管理器
descriptionLinux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件...
2019-10-21 22:42:07
119
原创 【JZOJ6379】小w与密码(password)
descriptionanalysis考虑sss的某个前缀aaa和ttt的某个前缀bbb拼成的一个字符串a+ba+ba+b如果该字符串可以被另几种a′+b′a'+b'a′+b′拼出来，钦定bbb最短的那种只算一次考虑a0+b0=a1+b1=...=ak+bka_0+b_0=a_1+b_1=...=a_k+b_ka0+b0=a1+b1=...=ak+bk，其中b0...
2019-10-07 09:33:57
367
原创 【JZOJ6378】小w与数字游戏(game)
descriptionanalysis对于nnn很大，一眼看出来肯定有两个相等的数减出来是000，答案肯定是000其实只要n>7n>7n>7，由于斐波那契数列，肯定能有几个数的和减去一个数凑出来000nnn很小就跑暴力code#pragma GCC optimize("O3")#pragma G++ optimize("O3")#includ...
2019-10-06 21:09:53
421
原创 【JZOJ6376】樱符[完全墨染的樱花]
descriptionanalysis无向图上任意两点最大流不超过222，说明该图是仙人掌由于最大流等于最小割，如果一条边在两个环里，断掉两个端点至少需要333的代价对于该仙人掌，求两点间的最小割，那么要么割一条桥边，要么割一个环上的两条边环上边权最小边一定要割，那就把这条边断开，环上其他边边权加上该边边权，相当于提前割然后图就变成了一棵树，任意两点间最小割即为...
2019-10-06 21:04:15
299
原创 【JZOJ6375】华灵[蝶妄想]
descriptionanalysis明显括号序长度是偶数，如果其中一个是奇数，那么只能让这奇数行或列是括号序对于两个都是偶数，需要分类讨论，假设n<mn<mn<m有一种是牺牲掉n2n\over 22n行，第一行全左括号，最后一行全右括号，比如这样，这个比较容易想到，答案是m+n2−1m+{n\over 2}-1m+2n−1有一种是牺牲掉第...
2019-10-05 20:22:13
179
原创 【JZOJ6368】质树(tree)
description大神 wyp 手里有棵二叉树，每个点有一个点权。大神 wyp 的这棵树是质树，因为随便找两个不同的点 u, v，只要 u 是 v 的祖先，都满足 u 和 v 的点权互质。现在你通过偷看了解到了大神 wyp 这棵树的中序遍历的点权值，你想复原出大神wyp 的树，或者指出不可能。阅读样例以更好地理解本题。analysis首先预处理质数，对于每个数，可以分解质因...
2019-09-29 20:58:08
215
原创 【BZOJ2298】【luoguP2519】problem a
description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)analysis这题转化模型很妙，容易知道最少没有说真话的数量=n−=n-=n−说真话最多的数量对于aia_iai个比iii大、bib_ibi个比iii小，可以看成iii分数排名第ai+1a_i+1ai+1名又由于有重分，...
2019-09-28 14:53:30
180
原创 【JZOJ5433】图
description有一个n个点A+B条边的无向连通图，有一变量x，每条边的权值都是一个关于x的简单多项式，其中有A条边的权值是k+x，另外B条边的权值是k-x，如果只保留权值形如k+x的边，那么这个图仍是一个连通图，如果只保留权值形如k-x的边，这个图也依然是一个连通图。给出q组询问，每组询问给出x的值，问此时这个无向连通图的最小生成树权值是多少。analysis首先容易知道图任...
2019-09-27 20:14:03
161
原创 【JZOJ6367】工厂(factory)
description大神 wyp 开了家工厂，工厂有 n 个工人和 p 条流水线。工厂的工人都是睡神，因此第 i 个工人只会在 si 至 ti 时刻才会工作。每个工人都会被分派到一条流水线上，然而，一条流水线只会在这条线的工人到齐时才能开工，其余时间即使有部分工人到了也只能休息。根据大神 wyp 的神谕，不能有流水线的工作时间为 0，也不能有工人没被分派到流水线上（即使这样会降低实际...
2019-09-26 22:17:52
358
原创 【JZOJ5431】序列操作
description一开始有n个非负整数hi，接下来会进行m次操作，第i次操作给出一个数c[i]，要求你选出c[i]个大于零的数并将它们减去1。问最多可以进行多少轮操作后无法操作（即没有c[i]个大于零的数）analysis明显每次都减去最大的那几个，减不了了就GGGGGG那么先把aaa排序了，考虑怎么一次次减掉aaa最前面的几个但是直接减最前面的次序会乱掉，比如5,5...
2019-09-23 22:41:18
133
subline-text-3插件MinGW.zip
2018-01-24
Sublime Text Build 3126.zip
2018-01-22
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人