来源http://poj.org/problem?id=2248  An addition chain for n is an integer sequence <a0,a1,a2,…,am><a0,a1,a2,…,am> with the following four properties: a0 = 1 am = n a0< a1< a2<…< am-1< a m For each k ( 1≤k≤m1≤k≤m) there exist two (not neccessarily different) integers i a...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1694&pid=2 题目描述        佳佳是一名出色的棋手，声称任何人他都可以从一个位置到另一个骑士这么快。你能打败他吗？  问题         你的任务是写一个程序来计算一个骑士达到从另一点所需要的最少步数。         对于不熟悉象棋的人，可能的骑士动作如图所示。  输入 输入开始与一个单一的行本身的情况下。  下一步跟踪N个场景。每个场景由三行包含整数。第一行指定棋盘边的长度L（4 < L = < 300）。整个板尺寸L×L的第二和第三行包含整数对{ 0，…...

链接：http://acm.ocrosoft.com/problem.php?cid=1713&pid=2 题目描述 John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会...

题目描述 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。 贝茜让 N 头奶牛坐成一个圈。除了 1 号与 N 号奶牛外，i 号奶牛与i−1 号和 i+1 号奶牛相邻，N 号奶牛与 1 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个 1 到 106 的数字。 接着每一头奶牛 i 从桶中取出一张纸条 Ai，每头奶牛轮流走一圈，同时拍打所有编号能整除在纸条上的数字的牛的头，然后走回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛。 输入 第一行包含一个整数 N； 接下来第二到第 N+1 行每行包含一个整数 Ai。 对于全部数据，1≤N≤105。 ...

题目描述 已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质数。 输入 输入只有一行，包含一个正整数 n。 对于 30% 的数据，n≤1000； 对于全部数据，6≤n≤2×109。 输出 输出只有一行，包含一个正整数 p，即较大的那个质数。 样例输入 21 样例输出 7 思路：这就是到判断质数的题目，但暴力肯定不行，我们可以优化一下，比如增大步长，或者用线性筛，这道题我用的是增大步长的方法 代码： #include<bits/stdc++.h> using namespace std; bool su(int a) {     if(a==...

链接：http://acm.ocrosoft.com/problem.php?cid=1702&pid=0 题目描述 给出两个正整数 A,B，求它们的最大公约数。 输入 输入共两行，第一行一个正整数 A，第二行一个正整数 B。 对于 60% 的数据，1≤A,B≤1018； 对于 100% 的数据，1≤A,B≤103000。 输出 在第一行输出一个整数，表示 A,B 的最大公约数。 样例输入 18 24 样例输出 6 思路： 这道题是一道大数的约数题，用普通的辗转相除法肯定会TLE因此我们要用大数的转转相除法 代码： #include<iostrea...

题目描述 输入正整数 x，求 x 的大于 1 的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足最大长度的序列的个数。 输入 多组数据，每组数据一行，包含一个正整数 x。 对于全部数据，1≤x≤220。 输出 对于每组数据，输出序列的最大长度以及满足最大长度的序列的个数。 样例输入 2 3 4 10 100 样例输出 1 1 1 1 2 1 2 2 4 6 思路：显然答案为多重集的排列数。设S={n1∗a1,n2∗a2,..,nk∗ak} 全排列的个数为n!/(n1!+n2!......+nk!) 代码： #include <b...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=0 题目描述：有一串含有N个数的数列，有M个询问，每个询问有两个数字X，Y，求出X到Y这段区间内的最大值。 输入： 第一行为一个N和M分别表示数字的个数和询问的个数，第二行为N个数。接下来M行，每行都有两个整数X，Y。 1 <= X, Y <= 1e5 输出： 输出共M行，每行输出一个数。 样例输入： 10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8 样例输出： 5 8 题目类型：RMQ 思路： 这是一道RMQ模板题，...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=1 题目描述： 每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: ...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=3 题目描述：Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了~  机器人们都想知道谁是最敏捷的，于是它们进行了如下一个比赛。 首先，它们面前会有一排共n个数，它们比赛看谁能最先把每连续k个数中最大和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写的更快。 但是Wind也想知道答案，你能帮助他吗？  输入： 第一行为n，k两个数,(1<=k<=n<=100 000)。 第二行共n个数，为数字序列，所有数字均在l...

转载自https://blog.csdn.net/zufesatoshi/article/details/95549459 40行的高精除，你们敢信？ #include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; int a[maxn], b[maxn], c[maxn], d[maxn]; char sa[maxn], sb[maxn]; bool bi(int a[], int b[]){ if(a[0] < b[0]) return 0; if(a[0] > b[...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1627&pid=15 题目描述 题目可见：https://www.luogu.org/problemnew/show/P3957 跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。 跳房子的游戏规则如下： 在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定： 玩家每次都...

  一）408.奶牛碑文 约翰和他的奶牛在大草原漫游，在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言，只包括三个大写字母 C、O 和 W。尽管约翰看不懂，但是令他高兴的是，C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在，他想知道有多少次 COW 出现在文本中。如果 COW 内穿插了其他字符，只要 COW 字符出现在正确的顺序，约翰也不介意。甚至，他也不介意出现不同的 COW 共享一些字母。例如，CWOW 出现了 1 次 COW，CCOW 算出现了2 次 COW，CCOOWW 算出现了 8 次 COW。 【输入格式】 第 1 行为 1 个整数 N。 第 2 行...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1695&pid=7 题目描述：人Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别，可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号（范围在1到N之间），并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐，校长想设法使每个职员和他（她）的直接上司不会同时参加聚会。      你的任务是设计一份参加聚会者的名单，使总的欢乐度最高。 输入 输入的第一行是一个整数N，1<= N <= 6000  以下的N行是对应的N...