Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for there queries.
Input
In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 <= X <= 2 31 – 1).
Output
There are N lines in total, the i-th of which contains the answer for the i-th query.
Sample Input
2
8
10
Sample Output
1 15
9 11
本题就考了树状数组的最最基本操作,对于会树状数组的人来说是太水了。
附个精简得不得了的代码,时间效率是O(1)
#include <stdio.h>
int main()
{
int T, x;
scanf("%d", &T);
while (T--)
{
scanf("%d", &x);
printf("%d %d\n", x-(x&(-x))+1, x+(x&(-x))-1);
}
return 0;
}
闫学灿acwing_分组背包问题有 N 种物品和一个容量是 V 的背包。物品一共有三类:第一类物品只能用1次(01背包);第二类物品可以用无限次(完全背包);第三类物品最多只能用 si 次(多重背包);每种体积是 vi,价值是 wi。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。si=−1 表示第 i 种
最受欢迎的 Linux 怎么是它,Ubuntu 排第六????作者:Linux猿????简介:CSDN博客专家????,C/C++、面试、刷题、算法尽管咨询我,关注我,有问题私聊!????关注专栏:Linux(优质好文持续更新中……)????不多废话,先来看一下排名:图1DistroWatch网站排名上面是排名前30位的最受欢迎的Linux操作系统,可以看到,比较熟悉的操作系统也名列前茅,比如:Ubuntu、Debian、Fedora、Arch、CentOS、UbuntuKylin以及deepin等。上面的排名是
MINI PCI-E接口_pcie接口原理图1、PCIe3.0X4下图只用了2Lanes,pcie接口分x1、x4、x8、x16接口,向下兼容。含一对差分CLK时钟信号上图:pciex4引脚定义2、minipcie和msata接口一样minipcie和msata接口定义是一样的,可以相互交换使用。都是只有1对Tx和1对Rx,没有差分CLK时钟信号。下图是msata接口,常用于系统盘。上图:msata盘上图:minipcie引脚定义上图:msata引脚定义…