- 博客(4397)
- 收藏
- 关注
RSS订阅转载 【CF1215F】 Radio Stations
题目比较精妙的\(\text{2-sat}\)建图了还是按照套路把每个电台拆成\((0/1,i)\)表示不选/选前两种连边是板子就不解释了考虑如何限制选择一个唯一的\(f\)，并且还能限制不选\(f\notin [l_i,r_i]\)的电台考虑前缀优化建图，我们建\((0/1,i)\)表示在\([0,i]\)中不选/选某一个频率对于这\(2\times m\)个点有一些显然的...
2019-09-22 18:59:00
528
转载 [CERC2017]Gambling Guide
题目看起来非常随机游走，但是由于我们可以停在原地，所以变得不是非常一样设\(f_x\)表示从\(x\)到\(n\)的期望距离如果我们提前知道了\(f\)，那么我们随机到了一张到\(y\)的车票，发现\(f_y>f_x\)，那么我们不如停在原地再随一张所以就有\[f_x=\frac{\sum_{(x,y)\in e}1+\min(f_x,f_y)}{d_x}=1+\frac...
2019-09-22 15:02:00
494
转载 WmmmmJ-算法第二章上机实践报告（配有图解）
实践报告任选一题进行分析。内容包括：实践题目问题描述算法描述算法时间及空间复杂度分析（要有分析过程）心得体会（对本次实践收获及疑惑进行总结）1.实践报告： 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A...
2019-09-22 10:56:00
588
转载 【牛客挑战赛32E】树上逆序对
题目数据范围非常奇怪，询问的逆序对个数\(k\leq 30000\)，我们应该可以把所有的情况都求出来发现对于树上两点\(x,y\)，如果\(x\)是\(y\)的祖先，那么绝对值较大的点的符号决定了能否形成逆序对如果\(a_x>a_y\)，不取反\(a_x\)，那么无论\(a_y\)取反与否，肯定会形成逆序对，因为\(a_x>a_y>-a_y\)；反之如果取反\(...
2019-09-22 09:57:00
281
转载 [JSOI2019]精准预测
题目这么明显的限制条件显然是\(\text{2-sat}\)考虑按照时间拆点，\((0/1,x,t)\)表示\(x\)个人在时间\(t\)是生/死有一些显然的连边\[(0,x,t+1)->(0,x,t)\]就是如果想在\(t+1\)时刻还是活着那必须在\(t\)时刻还活着\[(1,x,t)->(1,x,t+1)\]就是如果\(t\)时刻死了，那么\(t+1\)时...
2019-09-21 21:27:00
169
转载 [NOI2017]游戏
题目来复习\(\text{2-sat}\)了首先对于\(\operatorname{'a'},\rm{'b'},\rm{'c'}\)这三种地图，能放在上面的车只有两种但是对于\(\rm{'x'}\)能放三种车，变成一个\(\text{3-sat}\)众所周知\(\text{3-sat}\)只能搜索，于是我们爆搜这个位置放什么车剩下的我们还是直接用\(\text{2-sat}\)...
2019-09-21 15:14:00
85
转载 【AGC014E】Blue and Red Tree
题目正着考虑把边割断感觉非常难以考虑，于是考虑一下将整个过程倒过来，也就是把红边树变成蓝边树不难发现最后一步我们割断的边肯定是两棵树上都有的边，毕竟最后一步的时候原树只剩下了一条边如果两棵树没有公共边，那么直接输出\(\text{NO}\)即可再来考虑一下\(n-2\)步是怎么操作的不难发现我们可能是继续操作一条公共边，把这条蓝边变成红边；或者是选择两个不能通过蓝边相连的点但是...
2019-09-20 14:59:00
96
转载 【ARC073F】Many Moves
题目一个显然的\(dp\)，设\(dp_{i,j}\)表示其中一个棋子在\(x_i\)点，另一个棋子在\(j\)点的最小花费显然\(dp_{i,j}\)有两种转移第一种是把\(x_i\)上的棋子移到\(x_{i+1}\)，那么那么就是\(dp_{i+1,j}=\min(dp_{i,j}+|x_{i+1}-x_i|)\)第二种就是把\(j\)上的棋子移动到\(x_{i+1}\)，那...
2019-09-19 18:44:00
198
转载 【ARC072E】Alice in linear land
题目瑟瑟发抖，这竟然只是个蓝题题意大概就是初始在\(0\)，要到坐标为\(D\)的地方去，有\(n\)条指令，第\(i\)条为\(d_i\)。当收到一条指令\(x\)后，如果向\(D\)方向走\(x\)后距离\(D\)更近，那么就走；否则就停留在原地。现在有\(Q\)次询问，第\(i\)次询问为\(q_i\)，问能不能仅改变\(d_{q_i}\)，使得其不能到达\(D\)点考虑一...
2019-09-19 16:53:00
106
转载 「LibreOJ NOI Round #2」签到游戏
题目瞎猜一下我们只要\(n\)次询问就能确定出\(\{A_i\}\)来感受一下大概是询问的区间越长代价就越小，比如询问\([l,n]\)或\([1,r]\)的代价肯定不会超过\([l,r]\)所以大胆猜一下我们询问的只有一些前缀和后缀首先我们肯定要询问一下\([1,n]\)的和，之后我们考虑顺次得到\(A_1\)到\(A_n\)的和想得到\(A_1\)，我们当然可以直接询问\(...
2019-09-18 16:09:00
194
转载 「LibreOJ NOI Round #2」单枪匹马
题目通过这道题成功发现我不会矩乘答案是一个连分数，看起来不像是一般的数据结构能做的样子，设\(x_{l,r},y_{l,r}\)分别表示\([l,r]\)询问的分子和分母于是有\[\frac{x_{l,r}}{y_{l,r}}=a_{l}+\frac{y_{l+1,r}}{x_{l+1,r}}=\frac{y_{l+1,r}+a_l\times x_{l+1,r}}{x_{l+1...
2019-09-18 15:09:00
107
转载 [POI2008]MAF-Mafia
题目大概理解一下这个图是\(n\)个点\(n\)条边的有向图，也就是一个基环内向树森林考虑一下一个大小为\(S\)的简单环怎么做画画图就知道，随便找个点顺着打过去，最少可以让\(\left \lceil \frac{S}{2}\right \rceil\)个人死；在一个点死之前让它去开一枪，最多可以让\(S-1\)个人死再来考虑一下套在环上的树首先这些树上有一些入度为\(0\)...
2019-09-17 18:40:00
115
转载 [BJOI2019]删数
题目考虑一个不用修改就能删空的序列长什么样子设\(cnt_i\)表示\(i\)出现的次数，我们可以视为在\(i\)位置有一根高度为\(cnt_i\)的柱子，我们把所有柱子像左边推到，如果这些柱子恰好能覆盖\([1,n]\)这个区间，那么就说明可以删空这样想想发现非常形象，一次删除操作就相当于把当前最右边的柱子推倒，柱子顶端落地的位置就相当于新的序列的长度如果不能覆盖\([1,n]...
2019-09-17 14:09:00
128
转载 [USACO18JAN]Stamp Painting
题目考虑正难则反，拿总方案数\(m^n\)减掉不合法的方案由于我们最后一次涂了一段长度为\(k\)的连续颜色段，所以合法的方案有一段长度至少为\(k\)的颜色相同段不合法的方案一定没有，于是我们求一下有多个颜色序列没有长度大于等于\(k\)的颜色相同段就好了显然我们强制往后加一段长度小于\(k\)的段就行了于是有\(f_i=(m-1)\sum_{j=i-k+1}^{i-1}f_...
2019-09-16 18:45:00
132
转载 【CF516D】Drazil and Morning Exercise
题目首先我们知道，在树上距离一个点最远的点一定是直径的两个端点之一首先两遍\(\rm dfs\)把直径求出来，定义\(d(u)\)表示点\(u\)距离其最远点的距离，有了直径我们就能求出\(d\)数组了当然可以树形\(\rm dp\)，设\(f_{x,i,j}\)表示在\(x\)子树内部选择一个最大值为\(i\)最小值为\(j\)的最大联通块是多少，显然这样的复杂度奇高无比考虑把...
2019-09-15 16:40:00
206
转载 【LGP5439】【XR-2】永恒
题目是个傻题显然枚举每一条路径经过了多少次，如果\(u,v\)在树上不是祖先关系的话经过\((u,v)\)这条路径的路径条数就是\(sum_u\times sum_v\)于是我们子树大小映射到\(\rm Trie\)上去，树形\(\rm dp\)一下就可以求出所有点对产生的贡献了但是这样祖先关系的节点就算错了，我们发现这也非常好算，\(\rm dfs\)的时候拿\(\rm LCT...
2019-09-10 21:23:00
100
转载 [SCOI2015]国旗计划
题目首先考虑一下环形的区间覆盖问题怎么做我们可以把环倍长成链，之后惊讶的发现我只会枚举一个\(i\)作为起点跑\([i,i+m]\)的区间覆盖看起来非常垃圾，但是会这样做就够了考虑枚举到的这个\(i\)作为一个某一个给定的区间的左端点的时候，想要覆盖\([i,i+m]\)这段区间这个给定的区间是必须选择的，于是我们对于每一个给定的区间\([l_i,r_i]\)，来算一下覆盖\([...
2019-09-10 17:28:00
226
转载 会计科目中的借贷理解
有借必有贷 借贷必相等二、资产=负债+所有者权益（等式一）由：所有者权益=利润+资本得：资产=负债+利润+资本（等式二）由：利润=收入-费用得：资产+费用=负债+收入+资本（等式三）左边表示钱的去处 记在借方右边表示钱的来源 记在贷方转载于:https://www.cnblogs.com/lixuwu/p/11497297.html...
2019-09-10 14:29:00
363
转载 git使用合集
背景：主要用来描述git在使用过程中的注意事项你可能会忽略的 Git 提交规范你可能会忽略的 Git 提交规范在开发git项目时候，通常会切换到新的分支上进行开发dev，每次更新完远端的分支后，可以通过rebase将当前分支合并到远端的分支，继续进行开发这一次彻底搞懂 Git Rebase转载于:https://www.cnblogs.com/lix...
2019-09-10 09:55:00
152
转载 [AH2017/HNOI2017]单旋
题目\(\rm splay\)水平太差，于是得手玩一下才能发现规律首先插入一个数，其肯定会成为其前驱的右儿子或者是后继的左儿子，进一步手玩发现前驱的右儿子或者是后继的左儿子一定只有一个是空的，我们找到这个空位置插入就好了于是我们需要一个\(\rm std::set\)来查找前驱后继，同时我们还需要维护每个点的左右儿子和父亲继续手玩发现由于只有对最大值和最小值的操作，所以对\(\r...
2019-09-09 15:45:00
106
转载 [eJOI2018]元素周期表
题目\((r_1,c_1),(r_2,c_1),(r_1,c_2)\)三个格子存在就说明\((r_2,c_2)\)存在，如果我们将\(r_1,c_2,c_1,r_2\)都看成一些点的话，那么这个关系就非常类似于\(r_1\)和\(c_1\)联通，\(r_2\)和\(c_1\)联通，\(c_2\)和\(r_1\)联通，那么就说明\(r_2\)和\(c_2\)联通于是我们将每个格子\((...
2019-09-08 21:43:00
157
转载 [HNOI2015]落忆枫音
题目对于一个\(\rm DAG\)答案非常显然，就是除去\(1\)以外所有节点入度的乘积矩阵树定理显然是可以证明的，但是一个更为直观的理解方法就是对于每一个点从能到达它的点中找一个父亲加上这条边之后，我们还是先求出所有节点入度的乘积，显然这样算出来的并不全是外向树，还有一些奇怪的环状物考虑减掉这些环状物的影响我们从图里搜出一个\(k\)个节点的环，我们强行使得这个环作为那个环状...
2019-09-08 20:23:00
167
转载 uoj33 【UR #2】树上GCD
题目大致是长剖+\(\rm dsu\ on\ tree\)的思想先做一个转化，改为对于\(i\in[1,n-1]\)求出有多少个\(f(u,v)\)满足\(i|f(u,v)\)，这样我们最后再做一个反演就好了既然我们要求有多少对\(f(u,v)\)是\(i\)或\(i\)的倍数，我们需要在长剖的时候快速合并两边的信息，这个信息长得非常别致，形如到当前节点距离为\(i\)或\(i\)...
2019-09-08 17:39:00
141
转载 uoj74 【UR #6】破解密码
题目发现这个题的本质就是在做\(\rm hash\)我们显然能够列出\(n\)个方程，之后高消，这是\(O(n^3)\)的但是观察一下第一个和第二个方程\[a_{1}26^{n-1}+a_{2}26^{n-2}+...+a_{n}26^{0}=b_1\]\[a_{2}26^{n-1}+a_{3}26^{n-2}+...+a_{1}26^{0}=b_2\]考虑让他们强行对齐一下...
2019-09-08 14:18:00
139
转载 20190907爆零记
今天突然\(\rm pdf\)题面了，认真打了打，于是自闭了\(\rm T1\)是个简单的结论题，给定\(n,m,q\)，求\([1,q]\)里不能被\(n\times x+m\times y\)表示的数有多少个一眼大凯的疑惑既视感首先设\(r=(n,m)\)，能表示的数就一定是\(r\)的倍数，于是我们让\(n=\frac{n}{r},m=\frac{m}{r}\)，求一下\([...
2019-09-08 10:39:00
82
转载 uoj278 【UTR #2】题目排列顺序
题目读进来\(f\)之后，把权值作为第一关键字从小到大排序，位置作为第二关键字从大到小排序，这样排序后的第\(i\)个位对应的位置就应该填数字\(i\)权值作为第一关键字，保证了出现在其之前的数权值必它小的填的数也比它小，权值必它大的填的数也比它大；权值相同时按照位置从大到小排序，这样权值相同的一组就是递减的，就不会相互影响了代码#include<bits/stdc++.h...
2019-09-06 21:40:00
96
转载 【LGP5127】子异和
题目子异和这个名字，真是思博显然一个集合的子集异或和为，\(2^{|S|-1}\times A\)，\(A\)为集合的或和于是现在的问题变成了树链异或一个数，求树链或和显然强行拆位是可以做的，复杂度\(O(n\log n\ \log mod)\)，还是\(\rm lct\)于是直接飞了通过一番玄妙重重的推理，我们发现，整体异或上\(c\)，对或和的影响是\[\cup'=(\c...
2019-09-06 20:05:00
99
转载 uoj388 【UNR #3】配对树
题目看起来啥都不会先来思考那个子问题，给出\(2\times k\)个树上关键点，让这些关键点两两匹配，使得\(k\)对匹配的边权和最小不妨考虑树上差分，众所周知，让路径\((x,y)\)上边权加\(1\)只需要另\(x,y\)点权加\(1\)，\(\rm LCA(x,y)\)点权减\(2\)，再求一下子树和即可先将\(2\times k\)个关键点的点权都加\(1\)，现在我们...
2019-09-06 16:29:00
108
转载 uoj192 【UR #14】最强跳蚤
题目和成爷达成一致，被卡随机的话就是过了考虑一个完全平方数的所有质因子次幂一定是偶数，于是对于每一条边我们都只保留其出现次数为奇数的质因子注意到有一个点的\(w\leq 80\)，于是考虑状压质因子，对于第\(i\)个质数，我们定义其权值为\(2^{i-1}\)，这样我们就把每一条边的权值都变成了一个二进制数，现在只需要求有多少条路径的异或和为\(0\)即可，显然求一下每个点到根路...
2019-09-05 20:15:00
159
转载 Zuul网关跨域问题
1.跨域就指着协议，域名，端口不一致，出于安全考虑，跨域的资源之间是无法交互的。简单说就是协议不通，域名不通，端口不同都会产生跨域问题Access-Control-Allow-Origin是HTML5中定义的一种解决资源跨域的策略。他是通过服务器端返回带有Access-Control-Allow-Origin标识的Response header，用来解决资源的跨域权限问题。2.单...
2019-09-05 13:58:00
386
转载 uoj22 【UR #1】外星人
题目好像虚高胡策搬过这道题设\(t=\min a_i\)，不难发现我们一旦对\(t\)取模之后，就一定小于\(t\)，也就是之后再对其他数取模就没有什么意义了当然一上来就可以对\(t\)取模，但是\(x\% t\)并不一定是最优答案，所以我们要通过其他的\(a_i\)把\(x\)调整一下，使得它模\(t\)的值尽量大同时我们还发现多次对一个数取模是没有意义的，于是我们直接设\(f...
2019-09-04 16:51:00
138
转载 uoj21 【UR #1】缩进优化
题目题意简介明了，需要找到一个\(T\)，最小化\[\sum_{i=1}^n\left \lfloor \frac{a_i}{T} \right \rfloor+\sum_{i=1}^na_i\%T\]非常显然的\(a_i\%T=a_i-\left \lfloor \frac{a_i}{T} \right \rfloor\times T\)于是\[\sum_{i=1}^n\le...
2019-09-03 21:32:00
107
转载 uoj140 【UER #4】被粉碎的数字
题目看起来就像是数位\(\rm dp\)不妨从竖式乘法的角度来考虑这个问题为了方便处理进位，我们得从低位向高位填数设\(dp[i][0/1][j][p][t]\)表示填到了第\(i\)位，卡不卡上界，\(f(x)=j\)，\(f(k\times x)=p\)（不计算最高位），需要向最高位进\(t\)的\(x\)有多少个这里的卡上界比较奇怪，如果这一位上填的数大于\(R\)这一位...
2019-09-03 20:13:00
227
转载 uoj139 【UER #4】被删除的黑白树
题目不难发现有一个暴力\(dp\)设\(dp[x][l]\)表示\(x\)点子树内所有叶子节点到\(x\)的路径上都有\(l\)和黑点时最多能染多个黑点转移就是\[dp[x][l]=\max(\sum_{v\in son(x)}dp[v][l],1+\sum_{v\in son(x)}dp[v][l-1])\]转移是\(O(n^2)\)的，复杂度跟深度有关，或许可以长剖但是不会...
2019-09-03 14:12:00
99
转载 uoj118 【UR #8】赴京赶考
题目不难发现我们直接走过去就行了考虑到第\(i\)行的构造方法就是把\(b\)数组作为模板，每个数和\(a_i\)异或一下就可以了于是不难发现对于一段连续相等的\(a\)，它们在矩阵上就形成了完全相同的好几行同时这个矩阵上只有两种本质不同的行，一种是\(b\)和\(1\)异或得到的，一种是和\(0\)异或得到的显然我们从\((x_s,y_s)\)走到\((x_e,y_e)\)从...
2019-09-02 21:08:00
116
转载 Unsupported major.minor version 52.0
背景：Unsupported major.minor version 52.0 是jdk的原因java.lang.UnsupportedClassVersionError: com/mysql/jdbc/Driver确实因为mysql-connector-java这个jar包的版本和tomcat版本不兼容导致的。1、jdk7+老版5.0驱动com/mysql/jdbc/D...
2019-09-02 20:56:00
240
转载 [MtOI2019]幽灵乐团
题目一个很暴力的辣鸡做法考虑到两个数的\(\gcd\)是所有质数次幂取\(\min\)，两个数的\(\rm lcm\)是所有质数次幂取\(\max\)，于是最后的答案一定是\(\prod p_i^{c_i}\)，而且这里最大的质数不会超过\(n\)，于是我们考虑算出每一个质数的次幂是多少于是我们成功的将\(\prod\)转换成了\(\sum\)，指数上得对\(\rm mod-1\)...
2019-09-02 17:37:00
173
转载 Spring Cloud 使用Feign调用服务传递Header中的参数
1.使用Feign 调用其他微服务，尤其是在多级调用的同时，需要将一些共同的参数传递至下一个服务，如：token。比较方便的做法是放在请求头中，在Feign调用的同时自动将参数放到restTemplate中。2.具体做法是首先实现RequestInterceptorimport feign.RequestInterceptor;import feign.RequestT...
2019-09-02 15:59:00
1421
转载 JDBC链接数据库MySQL 8.0 Public Key Retrieval is not allowed 错误的解决方法
现象Mybatis和Spring框架整合过程中报com.mysql.jdbc.exceptions.jdbc4.MySQLNonTransientConnectionException: Public Key Retrieval is not allowed解决办法在连接URL后面添加allowPublicKeyRetrieval=true转载于:https://www....
2019-08-29 13:45:00
242
转载 算法第一章作业（Google C++代码规范 & 数学之美读后感 & 本学期想要实现的软件）...
Google代码规范（点击图片进入）：现在开始就可以注意命名规范（命名约定）、函数注释和条件语句的格式等等二、数学之美读后感： 在阅读了数学之美后，我深刻的体会到“数学是解决信息检索和自然语言处理的最好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮的解决办法。”这句话的魅力，没想到简简单单的数学模型能解决语音识别、机器翻译等十分复...
2019-08-28 13:32:00
126
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人