rk_no

题解

/ 注册

全部文章 / 题解（共71篇）

[ZJOI2006]物流运输（最短路辅助dp）

题目：个点的无向图，货车要连续天将货物从结点运到结点，货车走过一条边的代价=边的长度。其中会给一些限制，即结点在天内无法使用。货车每换一次运输路线需要花费的代价。问货车天将货物从结点运到结点的最小代价。做法：由于和的规模比较小。我们要打破固有的图论思维做这道题。设为货车前天运送货物的最小代价...

2020-10-14

1 558

Garland(树上dfs)

题目：给你一棵个结点的树，结点带权值。让你删去2条树边使其变成3棵点权和相等的非空树。输出任意方案。做法：我们求出个点的点权和。如果肯定无解。任一合法方案，删除2条边后，必定形成如下图形状的联通块，其中的点权和相同：和必定是某棵完整的子树。所以我们从根一遍，一旦找到某棵子树和为，说明找到了...

2020-10-13

1 577

筱玛爱线段树（差分数组）

题目：给定一个长度为的数组，刚开始每一项的值均为0。个操作：1 l r：数组A中区间的数+1。2 l r：区间的操作重做一遍。（数据保证小于当前操作编号）次操作后，输出数组。1e9+7输出。做法：由于2操作不会直接作用在数组上。所以我们的关注点在于个操作中所有1操作对应的次数。如果我们知道...

2020-10-12

2 598

Angry Cows(Silver)（二分）

题目：数轴上n个点。k个炸弹，每个炸弹可以将一个长2R+1的区间覆盖。问覆盖n个点的，R的最小值。n≤50000，k≤10 做法：很明显可以二分R的值。然后O(n)check。具体就是贪心地用区间的左端点覆盖当前最左边的点，这样每个区间都发挥最大的作用。然后看覆盖n个点需要用几个区间，设为cn...

2020-10-10

1 699

Minimizing maximizer（线段树）

题目：给一个长为的，落在上的区间序列，问最短的子序列，相邻区间有交集，连续覆盖上所有点。。做法：线段树上每个叶子表示上的一个点，维护当前延伸到需要的最短区间序列长度。一开始设结点1为0，其他点为。每次读入一个区间，左端点，即用已有的区间延伸到所需的最短区间序列长度，设为。然后用，线段树上区间...

2020-10-07

0 776

网络优化（线段树建图，sap最大流）

题目： n个用户上网，有m条网线。每条网线规定只[L,R]区间中的用户能上，且最多同时上v人。问最多能同时几人在线。组数不超过10n，m(1<=n，m<=10000) 做法：看这个题面，第一时间想到最大流。当然看到数据范围发现有点勉强。（但跑得还挺快）考虑朴素的建图：1、源点s和每个...

2020-10-01

1 931

毒瘤xor(贪心)

题目：小a有N个数a1, a2, ..., aN，给出q个询问，每次询问给出区间[L, R]，现在请你找到一个数X，使得1、 2、最大，表示异或操作。做法：由于异或位于位之间是不影响的，所以我们可以分别考虑X每个位选0还是选1。若[L,R]区间的数中第i位，0的数量＞1的数量，则X的第i位选...

2020-07-03

0 683

珂朵莉的数列(离散+线段树)

题目：珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出。对于100%的数据，n <=1000000 ,0 <= 序列中每个数 <= 1000000000 做法：换个角度，题目要我们求的是每个逆序对在多少个子区间内。那么对于一个逆序对，它的贡献就是理解...

2020-07-01

1 1150

小A买彩票（简单计数）

题目：小A最近开始沉迷买彩票，并且希望能够通过买彩票发家致富。已知购买一张彩票需要3元，而彩票中奖的金额分别为1,2,3,4元，并且比较独特的是这个彩票中奖的各种金额都是等可能的。现在小A连续购买了n张彩票，他希望你能够告诉他至少能够不亏本的概率是多少。输出一个最简分数a/b，表示小A不亏本的概率...

2020-06-30

0 682

借教室(线段树)

题目： n天，第i天有a[i]个教室可以借出。m个订单，第i个订单需要[li,ri]区间内借xi个教室。问到第几个订单无法满足。对于100%的数据，有1≤n, m≤106, 0≤ri, dj≤109, 1≤sj≤tj≤ n。做法：每个订单我们都分2步走：1、确定能不能满足；2、完成订单，把教室...

2020-06-30

0 950