7.19 系统管理员 2021-11-11 01:50 317阅读 0赞 ![1605842-20190721181554936-1236107559.png][] 如果不用树形dp,怎么做? 我们要使得士兵数量最少,那每个士兵要覆盖尽量多的节点 ![1605842-20190721181851825-987153794.png][] 我们找到最深的叶子节点 ![1605842-20190721181908757-2121964214.png][] 就是红色节点 我们以左边这个为例,如果要覆盖它,有4种放法 ![1605842-20190721182318826-746110312.png][] 节点上的数字是第几种放法 显然情况四覆盖的节点最多 所以我们找到深度最深的节点,在它的爷爷上放上士兵,然后把它爷爷覆盖到的节点从树上删掉,然后重复这个操作,直到树为空 我们维护一个堆就可以做到删除节点 复杂度:O(nlogn) ![1605842-20190719081427608-1358682970.png][] 染色方案是个什么意思? 如果我们有k种分组方案,每种方案都有M种颜色可以染,那最终的染色方案就Mk 举个栗子:N=6时,有4种分组方案,答案就是M的4次方 4种:1组,每组6人 2组,每组3人 3组,每组2人 6组,每组1人 所以有多少种方案就是看N有多少个因数 可以for一遍,O(√n)计算有多少个因子 然后快速幂计算Mk 增强版 在上面我们没有考虑人的顺序 所以我们考虑人的顺序 例子: ![1605842-20190721182738289-1414431048.png][] 例如上面的分两组,就有了三种分法(其实不全) 怎么算? 假设我们现在要把这些人分成r组 第一组的方案数 ![1605842-20190719082732382-761060134.png][] 第二组:这里因为第一组已经有N/r个人了,所以这里是N-N/r ![1605842-20190721183610452-320105433.png][] 第三组:因为又少了N/r个人,所以是N-2N/r ![1605842-20190719082824747-1121267758.png][] 第n组:到最后只剩下N/r个人了 ![1605842-20190719082836407-1059664927.png][] 我们发现这里考虑了每组的顺序,所以我们还要在除以r!(例如这么算会有(123,456)和(456,123),但它们是同一种情况) r!是r组的全排列 最终式子 ![1605842-20190719082959117-313233885.png][] 那这玩意咋算呢? 把组合数拆一下 ![1605842-20190719083227552-2063842485.png][] 以上是按照组合数公式拆分 我们发现可以约分 ![1605842-20190719083312301-1512039267.png][] 约分 分r组的最终式子: ![1605842-20190719083348324-681515605.png][] k的最终式子: ![1605842-20190721184233852-1536247949.png][] 最后求的是Mk%(109\-401) 那我们的k应该模多少呢?(109\-401)? 我们想起推逆元时用的欧拉定理: ![1605842-20190719083540444-279258147.png][] Mφ(1e9-401)≡1 (mod 109\-401) 那Mk≡Mk%φ(1e9-401) (mod 109-401) 那问题就转换成了这样 ![1605842-20190719083845917-19137198.png][] 我们发现N!没法算(N是2\*109) 这个题的模数很奇怪啊 它会不会是一个质数? 它的确是个质数 那φ(109\-401)=109\-402 进行一番分解质因数操作 ![1605842-20190719084234343-754379695.png][] 它的质因子都在10000以内,还不算太大 我们可以算N!mod这四个数分别是多少,然后乘起来,就是N!%109\-402 问题进一步被转化为N!%一个数是多少 假设我们要算N!%13 我们把N!奋进成这样的形式 ![1605842-20190719084551821-392139943.png][] 我们尝试把1~N中所有的数%13(对13的倍数特殊处理) 现在我们的模数很小,所以会有循环节(指1~N中的数%13之后会有循环节) ![1605842-20190719084836938-328742475.png][] 我们先不考虑13的倍数,那假设我们有q个循环节,则最后的答案(不包括13的倍数) 是(12!)q%13 我们再考虑13的倍数,把它们都拿出来,全部/13,把剩下的数%13计算 ![1605842-20190721191938400-2057464134.png][] 发现就是刚才的问题,那重复刚才的操作 这样就可以递归操作 复杂度log13N 大佬的式子(di就是要%的数) n!=1\*2..(di-1)\*di\*(di+1)\*..\*(q\*di)\*(q\*di+1)...\*n (mod di) =((di-1)! mod di)^q\*(n-q\*di)!\*q!\*(di)^q ( mod di) =(-1)^q\*(n-q\*di)!\*q!\*di^q ( mod di) 以下是对第二步的分析 ((di-1)! mod di)^q:上面刚讲了 (n-q\*di)!:因为N不一定是di的倍数,所以n-q\*di相当于n%di(计算剩下的“尾巴”)(例如n=1000,di=13的时候,q=7,n-q\*di=n%di=9,因此9就是这里的“尾巴”,这里(n-q\*di)!就是9!) q!\*(di)^q ( mod di):窝也不会了咕咕咕 ![1605842-20190719085658475-188564142.png][] ![1605842-20190719092212303-511662869.png][] 这是个Nim石子问题 我们先随便砍一刀 ![1605842-20190719091922971-771920202.png][] 这么砍相当于把黑格子到上边的距离变短 同理,在哪边砍,就相当于把黑格子到哪边的距离变短 这就相当于有四堆石子的Nim石子游戏问题,石子数量分别是(x-1),(y-1),(n-x),(m-y) 于是就可以把这四个都异或起来,就可以判定先手是否必胜 但是题目问有几种 我们可以枚举啊 ![1605842-20190719092331950-1775733243.png][] emmmmm 好大啊 长者说我国是数据结构强国,所以我们可以用数据结构(雾) 把式子变形 ![1605842-20190719092524955-2055439587.png][] ![1605842-20190719092517159-1409966328.png][] 枚举所有的x,把左边算出来的数塞到数组里,然后就枚举y,看右边的结果在数组里出现了多少次 可以搞个桶排一般的数组,或者是排序后二分 安利网站codechef.com(CC) ![1605842-20190719093249171-1206670034.png][] 分组不要求连续 哥德巴赫猜想?! ![1605842-20190719094042992-1004623078.png][] ![1605842-20190719094116602-198061488.png][] 第二个已经被证明(证明见百度) 第一个在long long范围内是对的 ![1605842-20190719094305955-472163400.png][] 一到n中所有数的和 s是偶数:输出2 s是奇数:N=2:s是质数:输出1 N≠2:看能拆成2个还是3个质数 拆成两个质数:这两个质数中一定有一个是2,所以看s-2是不是质数,如果是,输出2,不是,输出3 ![1605842-20190719094737730-290012257.png][] 平面最远点对???(才没有辣么难) 先看看什么是曼哈顿距离 ![1605842-20190719095358907-1262590411.png][] 我们不知道是第一头牛的y大还是第二头牛的y大 于是就有了两种情况 ![1605842-20190719095606494-717304720.png][] 第一种情况是第一头牛的y大于第二头牛的y 第二种情况是第二头牛的y大于第一头牛的y 所以我们先按x+y排序,最大的减最小的,再按x-y排序,最大的减最小的 ![1605842-20190719101222117-1681854558.png][] 不考虑复杂度神马的,我们可以算出来从第一个城市到第二个城市有多少条边 ![1605842-20190719101827429-2120018392.png][] 转移考虑从哪个点走过来 ![1605842-20190719101953202-1385742961.png][] 意思就是从起点走i步到j,中间一定会从起点走到k,再走一步到j,我们就枚举中间点k 复杂度:大概1024 能不能再快一点 如果把经过i条路到达的点的方案数看做一个矩阵 ![1605842-20190719102224352-1447739365.png][] ![1605842-20190719102325602-1205351488.png][] 复杂度:O(n3logd)(大概1010) 还是慢了点 我们看题目中别扭的地方 算a到b的道路数目很鬼畜,而且复杂度还和k没有关系 那我们从k入手进行优化 ![1605842-20190719102754416-1907754438.png][] 我们在存的时候就换一下维度,然后发现这时矩阵乘法 M=out\*in ![1605842-20190719102901343-2106099310.png][] 但是现在还是要n3,还是过不了 我们暴力的把括号打开 ![1605842-20190719103034218-1331692750.png][] 矩阵有结合律,所以可以随便加括号 ![1605842-20190719103125449-589954256.png][] 现在in\*out就是k\*k的矩阵 然后复杂度就变成了O(k3logd) 给一棵n个点的树,每个点有点权,保证点权在int范围内,有m次询问,每次给出两个点p1,p2,能否在p1到p2的路径上找出三个点,使得这三个点的点权能为一个三角形的三边长度 正难则反,我们想怎么不能构成三角形 如果出现这种情况就不能构成三角形了 ![1605842-20190719104625408-7442166.png][] 当取等号的时候,就是斐波那契数列了 斐波那契数列是不能够组成三角形,而且每个点的点权尽可能小的情况 我们注意到题目里说了每个点的点权小于int ,那我们沿着斐波那契数列写下去,发现会有f43(大概是这个数)爆int,那下一个路径上的点权一定是在int以内,此时一定可以组成三角形,因此如果路径上点的数量超过42,就一定能够构成三角形。 否则呢?暴力呗。 找路径:当然是倍增求LCA辣 求个毛啊一步一步跳就好了反正不超过42步还好写 转载于:https://www.cnblogs.com/lcez56jsy/p/11212077.html [1605842-20190721181554936-1236107559.png]: /images/20211109/9c42066e8e304324af39143082ff5c05.png [1605842-20190721181851825-987153794.png]: /images/20211109/41e64ea29f7a41da968f400b8343ff0d.png [1605842-20190721181908757-2121964214.png]: /images/20211109/68bc2a281ddb4a01b036ebec630a3a64.png [1605842-20190721182318826-746110312.png]: /images/20211109/150e773e6e824ae3a320e89fcc9bee7b.png [1605842-20190719081427608-1358682970.png]: /images/20211109/d480071c67be43d8ba71a7e71b649851.png [1605842-20190721182738289-1414431048.png]: /images/20211109/dc2db6b176f6439ea91f5608ab0ee4a1.png [1605842-20190719082732382-761060134.png]: /images/20211109/1486463900e24b25a80e4ea82ed492c7.png [1605842-20190721183610452-320105433.png]: /images/20211109/f08842a152b6473e87319b50dc7fc5e0.png [1605842-20190719082824747-1121267758.png]: /images/20211109/a7b216a24d844213ae58f19357e6b0e5.png [1605842-20190719082836407-1059664927.png]: /images/20211109/8eedc682294c44389ab7bc5224c1be97.png [1605842-20190719082959117-313233885.png]: /images/20211109/894040910dd1494da79bd218a2e2c21c.png [1605842-20190719083227552-2063842485.png]: /images/20211109/75395b97b42842049100a2c1e0a0035e.png [1605842-20190719083312301-1512039267.png]: /images/20211109/8978daba02064383bc235436488f73aa.png [1605842-20190719083348324-681515605.png]: /images/20211109/5042383b153b45e99182d3230305dcdb.png [1605842-20190721184233852-1536247949.png]: /images/20211109/4f141845f70841c4b1ddb1b24fd2f66b.png [1605842-20190719083540444-279258147.png]: /images/20211109/827c592b12af4fcfa24060f223adff0e.png [1605842-20190719083845917-19137198.png]: /images/20211109/7ba799caf82a4ee3845329929aedb5e4.png [1605842-20190719084234343-754379695.png]: /images/20211109/d080dcf7ac384659a0e54798de8c021b.png [1605842-20190719084551821-392139943.png]: /images/20211109/2ee7605b6c83434d8bef9574079bf147.png [1605842-20190719084836938-328742475.png]: /images/20211109/1b4cf8f88b4e4fe4a9b42e2c1ece7d92.png [1605842-20190721191938400-2057464134.png]: /images/20211109/b0f87e1764da4dbb858955e9a8bde1e9.png [1605842-20190719085658475-188564142.png]: /images/20211109/212171646b59401a994821f810afebce.png [1605842-20190719092212303-511662869.png]: /images/20211109/b6f7bd89cd8c4e5b8b508c1c6c8ff58e.png [1605842-20190719091922971-771920202.png]: /images/20211109/a892ce50e39f4d7686fb9364e803533c.png [1605842-20190719092331950-1775733243.png]: /images/20211109/900d178bd4014fac900a237bd04bc9b0.png [1605842-20190719092524955-2055439587.png]: /images/20211109/bb5818d1fafa4f5bb732f90b8660a981.png [1605842-20190719092517159-1409966328.png]: /images/20211109/cf4d0da0ba394d6f80b8c5d532d5b4ab.png [1605842-20190719093249171-1206670034.png]: /images/20211109/9a0e5b1213f7440aacf61483b989cf46.png [1605842-20190719094042992-1004623078.png]: /images/20211109/67f5def7469e4c28bc1d7a7406856e38.png [1605842-20190719094116602-198061488.png]: /images/20211109/94d1047cf3604623a2702f896c137c66.png [1605842-20190719094305955-472163400.png]: /images/20211109/0b257aa36a814615b344aa4969d16eb0.png [1605842-20190719094737730-290012257.png]: /images/20211109/46669591ae534dc997e6322eb10b1137.png [1605842-20190719095358907-1262590411.png]: /images/20211109/d1103277c906489e9ddea81d08700534.png [1605842-20190719095606494-717304720.png]: /images/20211109/b53d24534dd6438e828acbc7b162bfef.png [1605842-20190719101222117-1681854558.png]: /images/20211109/52070dfe4ffe4e479f24b4b71905121e.png [1605842-20190719101827429-2120018392.png]: /images/20211109/eef17057b61044dd93bffd7f92a2a753.png [1605842-20190719101953202-1385742961.png]: /images/20211109/151c69e2010a47d49628d5495442cf21.png [1605842-20190719102224352-1447739365.png]: /images/20211109/7909471b4eac4c54b1e228b197dfeefd.png [1605842-20190719102325602-1205351488.png]: /images/20211109/372601fd30654386b9a2fcb1dfbfb0c4.png [1605842-20190719102754416-1907754438.png]: /images/20211109/c138bb4daa414432befb90849f0d7b5a.png [1605842-20190719102901343-2106099310.png]: /images/20211109/f6bd090c87254b938337e1eece6e2da3.png [1605842-20190719103034218-1331692750.png]: /images/20211109/e5ec9afa1df64dc4970b4d2a1cbee9fb.png [1605842-20190719103125449-589954256.png]: /images/20211109/f3fbe2214582453ab66a156c52a4d466.png [1605842-20190719104625408-7442166.png]: /images/20211109/9c8ad155231d48b99b7e602eadc97afe.png
相关 Codeforces Round #719 (Div. 3) D. Same Differences 动态map维护 [Problem - D - Codeforces][] 题意: ![98d25cd6320e44d143d3cadbc49e4804.png][] 思路: 这种题,一 梦里梦外;/ 2024年03月29日 15:03/ 0 赞/ 73 阅读
相关 Codeforces Round #719 (Div. 3)(a,b,c) [题目https://codeforc.es/contest/1520][https_codeforc.es_contest_1520] 简单题 a b 「爱情、让人受尽委屈。」/ 2023年01月19日 07:29/ 0 赞/ 24 阅读
相关 719-计算机网络面试问答 计算机网络的各层协议及作用? 计算机网络体系可以大致分为一下三种,OSI七层模型、TCP/IP四层模型和五层模型。 OSI七层模型:大而全,但是比较复杂、而且是先有了理 系统管理员/ 2022年09月17日 04:22/ 0 赞/ 149 阅读
相关 719 找出第 k 小的距离对(二分查找、双指针) 1. 问题描述: 给定一个整数数组,返回所有数对之间的第 k 个最小距离。一对 (A,B) 的距离被定义为 A 和 B 之间的绝对差值。 示例 1: 输入: nums 古城微笑少年丶/ 2022年09月09日 12:44/ 0 赞/ 157 阅读
相关 719_AUTOSAR_TR_TimingAnalysis6_时序要求规范的语言 全部学习汇总: [https://github.com/GreyZhang/hack\_autosar][https_github.com_GreyZhang_h 古城微笑少年丶/ 2022年09月04日 01:00/ 0 赞/ 172 阅读
相关 FNBJ-7 行: 719 错误: 无法获取未定义或 null 引用的属性“childNodes” ![这里写图片描述][SouthEast] 点击【是】用IE自带的开发者工具进行调试。 如果是jquery库报错推断后台初始化前台控件逻辑存在问题 ![这里写图片描述 心已赠人/ 2022年06月16日 02:41/ 0 赞/ 233 阅读
相关 leetcode 719. Find K-th Smallest Pair Distance 第k小的绝对距离 + 暴力计算真棒 Given an integer array, return the k-th smallest distance among all the pairs. The dista 朴灿烈づ我的快乐病毒、/ 2022年06月03日 09:41/ 0 赞/ 160 阅读
相关 【跃迁之路】【719天】程序员高效学习方法论探索系列(实验阶段476-2019.2.9)... 实验说明 > 1. 从2017.10.6起,开启这个系列,目标只有一个:探索新的学习方法,实现跃迁式成长 > 2. 实验期2年(2017.10.06 - 2019.1 Bertha 。/ 2022年03月07日 02:46/ 0 赞/ 151 阅读
还没有评论,来说两句吧...