leeyupeng

leeyupeng@126.com

0%

发表于 更新于 分类于 ， 阅读次数： Valine：

1365F - Swaps Again

问题描述

Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer n and two arrays a and b, of size n. If after some (possibly zero) operations described below, array a can be transformed into array b, the input is said to be valid. Otherwise, it is invalid.

An operation on array a is:

select an integer k (1≤k≤⌊n2⌋)
swap the prefix of length k with the suffix of length k
For example, if array a initially is {1,2,3,4,5,6}, after performing an operation with k=2, it is transformed into {5,6,3,4,1,2}.

Given the set of test cases, help them determine if each one is valid or invalid.

Input
The first line contains one integer t (1≤t≤500) — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer n (1≤n≤500) — the size of the arrays.

阅读全文 »

发表于 分类于 ， 阅读次数： Valine：

滑动谜题

问题描述

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

BFS

问题分析

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

安装栅栏

问题描述

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

扫描线算法

问题分析

$(x,y)$是否$(x_1,y_1)$ $(x_2,y_2)$三点共线

$\frac{y_2-y} {x_2-x}$ = $\frac{y_2-y_1} {x_2-x_1}$

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

冗余连接 II

问题描述

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u and v和顶点的边，其中父节点u是子节点v的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

并查集

思路分析

阅读全文 »

发表于 分类于 ， 阅读次数： Valine：

冗余连接

问题描述

在本问题中, 树指的是一个连通且无环的无向图。

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

Kruskal算法+并查集

思路分析

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

二进制

二进制与Swap

1
2
3
4
5
void Swap(int& a,int& b){
  a^=b;
  b^=a;
  a^=b;
}

最后一位1

判断是否是2的幂（只有一个1）

数组中只出现一次的数

数组中只有一个数字出现了一次，其他数字都出现了两次，找出只出现了一次的这个数字

二进制与组合

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

leetcode.354. 俄罗斯套娃信封问题

问题描述

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

动态规划

思路分析

dp[i] 代表以i为结尾的最长上升子序列

阅读全文 »