选数问题

题目描述

在给定的 $N$ 个数中选出 $R \times C$ 个数，然后填入 $R \times C$ 的矩阵中，每一行的 $D(i)$ 定义为本行最大值与最小值的差，然后要令所有行中 $D(i)$ 的最大值 $F$ 尽量小，其中 $1 \leq i \leq R$。请你求出满足条件的 $F$。

输入格式

第一行是三个整数：$N, R, C$，其中, $1 \leq R,C \leq 10^4$，$R \times C \leq N \leq 5 \times 10^5$。
第二行是 $N$ 个整数 $P_i$，$0 < P_i \leq 10^9$

输出格式

输出一个整数，即满足条件的最小的 $F$。

传递消息

题目背景

POJ 1125

题目描述

股票经纪人以对传闻的准确判断而闻名。你已签定一个合同，就是研究一种方法，在股票经纪人中间传播假情报，以便雇主在股票市场中赢得先机。为了得到最大效益，你必须尽可能快地散布传闻。

不幸的是，股票经纪人只信任来自他们“可靠来源”的消息。这意味着，在散播传闻时，你必须考虑他们所接触的人际关系。某个股票经纪人需要花一些时间把传闻传递给他的每一位同事。你的任务是写一个程序，确定从哪个证券经纪人开始散播传闻最快，以及传闻传递到整个证券界时所需要最少时间。这个时间是指最后一个人收到传闻的时间。
每个股票经纪人从1开始编号，一直到股票经纪人的总数。

单词翻译

题目描述

众所周知，Mr.Zeng 不会说英语，他会使用 $A$ 语言。因为我们的国家已经加入世贸组织，他感受到了压力，已经在开始学习英语。现在需要你用计算机来帮助他做一些翻译工作。

输入格式

输入 $N(1 \leq N \leq 100005)$ 个词典条目，每个字典条目占一行，分别包含一个英语单词,一个空格和一个该英语单词对应的A语言单词。词典中每个 $A$ 语言单词出现一次。

接着一个空行。

然后是多达 $M(1 \leq M \leq 100005)$ 个需要翻译的A语言单词，每行一个单词。

输入的每个单词最多 $10$ 个小写字母。

Trie 树(c++实现)

原理

Trie 树，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
详见 Trie 树

Shortest Prefixes

题目背景

POJ 2001

题目描述

给出 $n$ 个单词（$1 \leq n \leq 1000$），求出每个单词的非公共前缀，如果没有，则输出自己。

输入格式

输入 N 个单词，每行一个，每个单词都是由 1～20 个小写字母构成。

输出格式

输出 N 行，每行由一个空格的两部分，第一部分是输入的单词，第二部分是该单词在所有单词中的非公共前缀，如果没有，则输出自己。

C++加速输入

cin, cout

cin 的速度其实并不慢,流的读取速度相当快,其速度与设定缓存区大小,硬盘速度有关。C++ 为了兼容 C 的 IO(scanf,printf), 使 cin, cout 与之同步,导致 cin 速度不如 scanf。

我们可以取消 cin 与其的绑定,并取消 cin 与 cout 的绑定,加速读取,使 cin 的速度与 scanf 相差无几,甚至超过scanf。

注意：取消绑定之后不能再使用 scanf, printf, 否则会出现读取失败或提前输出的问题,getchar() 可以使用。

音乐播放测试

树状数组求逆序对

树状数组

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

众数

题目描述

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

输入格式

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

输出格式

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

统计数字

题目背景

NOIP 2007提高组试题1。

题目描述

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

输入格式

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

输出格式

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

明明的随机数

题目背景

NOIP 2006 普及组试题1。

题目描述

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

输入格式

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

输出格式

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

奖学金

题目背景

NOIP2007 普及组试题1

题目描述

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

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

第 k 小整数

题目描述

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

输入格式

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

输出格式

第 $k$ 个最小整数的值；若无解，则输出 NO RESULT。

军事机密

题目描述

军方截获的信息由 $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$，每个整数之间用一个空格分隔。

输出格式

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

欢迎来到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