「SuperOJ 376」选数问题

选数问题

题目描述

在给定的 $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」传递消息

传递消息

题目背景

POJ 1125

题目描述

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

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

「SuperOJ 230」单词翻译

单词翻译

题目描述

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

输入格式

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

接着一个空行。

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

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

Trie 学习笔记

Trie 树(c++实现)

原理

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

「POJ 2001」Shortest Prefixes

Shortest Prefixes

题目背景

POJ 2001

题目描述

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

输入格式

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

输出格式

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

C++加速输入

C++加速输入

cin, cout

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

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

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

音乐播放测试

音乐播放测试

树状数组

树状数组求逆序对

树状数组

树状数组(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
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×