树状数组

树状数组求逆序对

树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree) 是一个查询和修改复杂度都为 $O(\log n)$ 的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;
经过简单修改可以在 $O(\log n)$ 的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。

查看更多

分享到

「SuperOJ 7」众数

众数

题目描述

由文件给出 $N$ 个 $1$ 到 $30000$ 间无序数正整数,其中 $1 \leq N \leq 10000$,同一个正整数可能会出现多次,出现次数最多的整数称为众数。求出它的众数及它出现的次数。

输入格式

输入文件第一行是正整数的个数 $N$,第二行开始为 $N$ 个正整数。

输出格式

输出文件有若干行,每行两个数,第 $1$ 个是众数,第 $2$ 个是众数出现的次数。

查看更多

分享到

「NOIP 2007」统计数字

统计数字

题目背景

NOIP 2007提高组试题1。

题目描述

某次科研调查时得到了 $n$ 个自然数,每个数均不超过 $1500000000(1.5 \times 10^9)$。已知不相同的数不超过 $10000$ 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。

输入格式

输入文件包含 $n + 1$ 行:
第 $1$ 行是整数 $n$,表示自然数的个数。
第 $2$ ~ $n+1$ 行每行一个自然数。

输出格式

输出文件包含 $m$ 行($m$ 为 $n$ 个自然数中不相同数的个数),按照自然数从小到大的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。

查看更多

分享到

「NOIP 2006」明明的随机数

明明的随机数

题目背景

NOIP 2006 普及组试题1。

题目描述

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数($N \leq 100$),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成去重排序的工作。

输入格式

输入文件有 $2$ 行:
第 $1$ 行为 $1$ 个正整数,表示所生成的随机数的个数:$N$
第 $2$ 行有 $N$ 个用空格隔开的正整数,为所产生的随机数。

输出格式

输出文件也是 $2$ 行:
第 $1$ 行为 $1$ 个正整数 $M$,表示不相同的随机数的个数。
第 $2$ 行为 $M$ 个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

查看更多

分享到

「NOIP 2007」奖学金

奖学金

题目背景

NOIP2007 普及组试题1

题目描述

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末,每个学生都有 $3$ 门课的成绩:语文,数学,英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学排在前面,这样,每个学生的排序是唯一确定的。

任务:先根据输入的 $3$ 门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前 $5$ 名学生的学号和总分。

查看更多

分享到

「SuperOJ 3」第 k 小整数

第 k 小整数

题目描述

现有 $n$ 个正整数,$n \leq 10000$,要求出这 $n$ 个正整数中的第 $k$ 个最小整数(相同大小的整数只计算一次),$k \leq 4000$,正整数均小于 $30000$。

输入格式

第一行为 $n$ 和 $k$;
第二行开始为 $n$ 个正整数的值,整数间用空格隔开。

输出格式

第 $k$ 个最小整数的值;若无解,则输出 NO RESULT

查看更多

分享到

「SuperOJ 2」军事机密

军事机密

题目描述

军方截获的信息由 $N(1 \leq N \leq 30000)$ 个整数组成,因为是敌国的高端秘密,所以一时不能破获。最原始的想法就是对这 $N$ 个整数进行小到大排序。排序后每个数都对应一个序号,然后对第 $i$ 个是什么数感兴趣,现在要求编程完成。

输入格式

第一行整数 $N$。
第二行是 $N$ 个截获的数字,相邻数字由一个空格隔开。
第三行是一个数字 $K (1 \leq K \leq N)$。
从第四行开始,共有 $K$ 个排序后的序号 $X_1, X_2, X_3, \cdots X_k$,每行一个。

输出格式

输出数据有 $K$ 行,每行一个整数。这个整数就是每个序号 $X_i$ 对应的数。

查看更多

分享到

A+B Problem

A+B Problem

题目背景

新手入门。

题目描述

计算两个整数的和。

输入格式

输入只有一行,包括两个整数 $a, b$,每个整数之间用一个空格分隔。

输出格式

输出只有一行,包含一个整数为 $a + b$ 的计算结果。

查看更多

分享到

Hello World

欢迎来到XeHoTh!

这是一个文章测试

Java 代码高亮测试

1
2
3
4
5
public class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello World");
}
}

c/c++ 代码高亮测试

1
2
3
4
5
#include <iostream>
int main() {
std::cout << "Hello World";
return 0;
}

bash测试

1
2
3
$ 这是一个bash
> 这是一个bash
->这是一个bash

查看更多

分享到