夢に僕らで帆を張って
来るべき日のために夜を超え

标签 codeforces 下的文章

November 11, 2019

CF543B Destroying Roads

题意在这个国家有$n$个城市,城市间由$m$条双向公路连接。城市被编号为$1$到$n$ 。如果城市$a$和$b$被公路连接,那么你可以双向通行。你可以在这个公路网上通过公路从一个城市移动到另一个城市。走过每条公路均耗时$1$小时你想要破坏最多的公路,但是破坏后必须满足从指定城市$s_1$ 到$t_1$最短不超过$l_1$小时,且从指定城市$s_2$到$t_2$最短不超过$l_2$​ 小时计算...
November 11, 2019

CF449B Jzzhu and Cities

题意$n$个点,$m$条带权边的无向图,另外还有$k$条特殊边,每条边连接$1$和$i$问最多可以删除这$k$条边中的多少条,使得每个点到$1$的最短距离不变数据范围:$1 \le n,k \le 10^5,1\le m \le 3\times 10^5$题解最短路计数,判断这几条边是否再最短路上或这几个点有没有别的最短路可以达到代码:#include<iostream> #in...
October 31, 2019

CF786B Legacy

题意有$3$种连边方式$u \rightarrow v$ 点向点$u \rightarrow [l,r]$ 点向区间$[l,r] \rightarrow u$ 区间向点求从$s$出发的最短路数据范围:$1 \le n,q \le 10^5$题解显然对于向区间建边不能一个一个建,那么能不能直接向整个区间建边呢?联想到线段树的一个节点维护一个区间的信息,那么可以向这个节点建边;这便是线段树优化建...
October 29, 2019

CF1225C p-binary

题意求满足$$\sum_{i=1}^x (2^k+p)=n$$的最小$x$,其中$k$为任意自然数数据范围:$1 \le n \le 10^9,-1000 \le p \le 1000$题解先移项,得$$\sum_{i=1}^x 2^k=n-xp$$在二进制下,左边能组合出$1$的数量$\le x$的任意数那么从小到大枚举这个$x$,验证即可至于枚举的上界,因为$k$为自然数($\ge 0$...
October 27, 2019

CF600E Lomsat gelral

题意一棵树有$n$个结点,每个结点都是一种颜色,每个颜色有一个编号,求树中每个子树的颜色编号的众数的和数据范围:$1 \le n \le 10^5$题解算法: 树上启发式合并发现每计算一棵子树需要清空做下的标记,但最后一颗子树不用清空(显然选择重儿子)像树剖一样先处理出重儿子先计算轻儿子,再暴力清空(消除对其兄弟的影响)计算重儿子,不清空合并轻重儿子的值复杂度证明类似树剖,一个节点会被清空仅...
October 24, 2019

CF525E Anya and Cubes

题意给你$n$个数,可以使用$k$次操作,每次操作可以使序列中的一个数$a_i$变为$a_i!$,求选出任意个数使他们和的等于$S$的方案数数据范围:$1 \le n \le 25,0 \le k \le n,1 \le s \le 10^{16}$题解折半搜索注意到$s \le 10^{16}$,因此只有$\le 19$的$a_i$需要考虑阶乘另外,由于选择状态过多,难以记录;所以记录选择...
October 21, 2019

CF1228E Another Filling the Grid

题意一个$n \times n$的矩形,每个格子里可以填$[1,k]$内的整数,求保证每行每列的最小值为$1$的方案数数据范围:$1 \le n \le 250,1 \le k \le 10^9$题解直接计算难以解决,考虑容斥原理枚举有$i$行$j$列的最小值$> 1$,选择方案有$$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j$$乘...
October 21, 2019

CF1248E Queue in the Train

题意$n$个人会在$t_i$时刻产生接水的想法,若$1 \dots i-1$没有人在排队,那么他会去排队;每个人接水的时间为$p$,求每个人接水完成的时间数据范围:$1 \le n \le 100000,1 \le p \le 10^9,0 \le t_i \le 10^9$题解模拟题用$3$个优先队列,分别储存原序列产生接水想法的人正在排队的人按题意模拟即可#include<iost...