Pikachu_杨京

未归档

动态规划(1) 并查集(2) 搜索(3) 最小生成树(2) 最短路径(3) 欧拉路径(1) 线段树(2) 背包问题(1) 贪心(2) 题解(3)

/ 注册

全部文章 / 未归档（共24篇）

Codeforces Round #270 D题：Design Tutorial: Inverse the Problem ，最短路+LCA+树上前缀和

Design Tutorial: Inverse the Problem 题意：给你一个距离矩阵，让你证明该矩阵是不是一颗加权树的距离矩阵。对于一个点u，与它距离最近的点一定是与它直接相连的，所以对矩阵求一次最短路，可以得到这颗树。然后只需要求出树上任意两点之间的距离是否与矩阵的距离相同就可以...

2019-07-15

0 779

牛客小白月赛16 小雨坐地铁分层图，最短路

小雨坐地铁官方题解：考虑分层图最短路。很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(n) 的，可能会超时。我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最...

2019-07-15

0 738

ArabellaCPC 2019 J. Thanos Power 动态规划

J. Thanos Power 题意：给你一个数N，让你求它最少通过多少次操作得到的。初值为0，每次操作只能增加，x >= 0; 0最少通过多少次操作得到的N，等价于N通过多少次操作得到的0 从高位往低位看，，，对于每一位上的数x，我有两种方法让它变成0，一直加 1，加到1...

2019-07-14

0 821

ArabellaCPC 2019 Meeting Bahosain 最大公约数

Meeting Bahosain 给你一个数组a和一个数组b，你可以让数组a中的数 +/- 数组b中的任一个数。目标使a数组中数相等。可以将a[n]的值转化为a[n-1]再转化为a[n-2]，……，最后使所有数都等于a[0]，那么就是对于所有a[i] - a[i-1]都能由b表示出来，就输出Y...

2019-07-14

0 724

Codeforces Round #573 (Div. 2) D - Tokitsukaze, CSL and Stone Game 博弈

D - Tokitsukaze, CSL and Stone Game 给n堆石子，每一堆有a[i] 个石头，现在二人玩游戏，每一人每一次选择一个非空的石头堆，从中拿出一个石头。如果当一个人操作之后，这n堆石头中有两堆中的石头数量是相同的，那么这个人就输掉。假设二人决定聪明，请判断是先手赢还是后...

2019-07-14

0 624

Codeforces Round #268 (Div. 2) 　D:Two Sets 并查集

　D:Two Sets 题意：将n个数分成两个集合。如果x属于集合A，那么a - x一定属于集合A，如果x属于集合B，那么b - x一定属于集合B 首先很容易想到将，x与a - x同时存在，那么将它们放在A集合，同理B 但是这是错的，举个例子，a=3,b=6, x: 1 2 4， x =...

2019-07-12

0 699

Codeforces Round #268 (Div. 2) C：24 Game 模拟

Codeforces Round #268 (Div. 2) 题意：初始你手中有n张牌，数字分别是1~n，然后你任选其中两张牌，用“+”，“-”，“*”，来组合出另一张牌(另一个数字)，并把使用过的牌扔掉，问最后能否剩下的最后一张牌为24？如果不能，输出NO；否则，输出YES，并将如何得...

2019-07-12

0 668

The 14-th BIT Campus Programming Contest 金色传说

金色传说参考于：xls tql 若存在a+b，那么一定存在一个a-b，两者求和，2*a，所以对于每个长度为n和合法式子，只需对每个式子第一个 +/- 前面数字求和，所以需要统计 + / - 号前面的a出现多少次。假设第一个 + / - 前面是一个长度为i的数字，那么 + / - 号后面...

2019-07-11

0 685

The 14-th BIT Campus Programming Contest L. 旅行的意义

旅行的意义参考于：xls tql d[i]表示以i为起点的期望天数，对于节点u，首先需要在u玩一天，第二天我可以有1 / (son + 1)概率去u的某一个子节点，也有1 / (son + 1)概率待在u，d[u] = 1，d[u] = d[u] + （d[vi] + 1）* 1 / (s...

2019-07-11

0 604

RMQ 算法 Balanced Lineup

Balanced Lineup RMQ： RMQ（Range Minimum/Maximum Query），即区间最值查询，这是一种在线算法，所谓在线算法，是指用户每次输入一个查询，便马上处理一个查询。RMQ算法一般用较长时间做预处理，时间复杂度为O(nlogn)，然后可以在O（1）的时间内处理...

2019-07-10

0 671