这次会中奖的！！！

题解

未归档(1) 随笔(3)

/ 注册

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

题解 | #在二叉树中找到两个节点的最近公共祖先#

写个倍增LCA二叉树倍增按照2的次幂来增加，即1, 2, 4, 8... 首先我们先预处理出每个节点2^j级祖先用f[i][j] 表示i节点的2^j级祖先查询时从大向小跳，即按照8, 4, 2, 1来；具体:先把两个节点提到同一高度，在统一开始跳。一直跳到父亲节点相同，即为最近公共祖先。 /**...

2021-08-03

0 553

剑指顺序改为倒序

#include <iostream> #include <algorithm> #include <stdlib.h> #include <vector> using namespace std; typedef long long LL; in...

2021-03-04

0 752

棋盘覆盖

题目链接题意：给一个nn的棋盘，棋盘上有m个障碍，要求用12的多米诺骨牌进行掩盖。且任意两张骨牌都不重叠，障碍上不能有骨牌。思路： 1*2的骨牌且骨牌不能有重叠，这个性质很容易想到二分图。怎样建这个图呢？将棋盘上的点提出来，每个点与它相邻的四个点进行连边操作，这样见图就完成了建图...

2020-12-09

3 705

Tree Partition

Tree Partition 题意: 给一棵树,n个点n-1条边,没给点都有点权。要求剪掉k-1条边形成由k颗树组成的森林。树的权值为中所有点权之和问：怎样剪使得树的权值的最大值最小, 大小为多少？解题：看到“最大值最小”这类词, 先是想到了二分，二分出权值，再根据权值对树进行剪边操作，觉得可...

2020-12-07

1 910

Color Graph

K.Color Graph 题意：给一个无向图n个点m条边，给一些边涂红色。要求红色边不能有奇环.求能染红的最多的边。解题：题目中讲到了奇环，这很容易往二分图上想。定理：一个无向图是二分图，当且仅当图中不存在奇环接下里就是找是二分图的最多的边。我们一般是分两个集合进行操作，在这个题中由...

2020-12-07

2 709

石头剪刀布

石头剪刀布解题：求最高分由于输了不扣分所以肯定是能赢就赢，求出赢最多的次数，肯定就是min(a1, b2) + min(b1, c2) + min(c1, a2);再次基础上求出平局最多即为所求：这里就是用他们原来的减去赢了的，在取对应位置最小值min(a2 - min(c1, a2),a1...

2020-12-07

1 997

牛客小白月赛30- I 区间异或

区间异或题目描述：有一个长度为 n 的数组 a[i] , 有 m 次询问，每次询问给一个值 x ，找出一个最短的区间，使得这个区间的异或和 ≥ x , 输出区间长度。如果找不到输出 -1. 输入描述: 第一行两个整数 n , m (1 ≤ n ≤ 3000 and 0 ≤ m ...

2020-12-06

2 717