洛谷 P1080 国王游戏

题目描述

恰逢 HH国国庆，国王邀请nn 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数nn，表示大臣的人数。

第二行包含两个整数 aa和 bb，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 nn行，每行包含两个整数aa 和 bb，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

输入输出样例

输入 #1复制

1
2
3
4
5

3 
1 1 
2 3 
7 4 
4 6 

输出 #1复制

1

2

洛谷 P2201 数列编辑器

题目描述

小Z是一个爱好数学的小学生。最近，他在研究一些关于整数数列的性质。

为了方便他的研究，小Z希望实现一个叫做“Open Continuous Lines Processor”的数列编辑器。

一开始，数列编辑器里没有数字，只有一个光标。这个数列编辑器需要支持五种操作。

• I x 在当前光标前插入数字 x。

• D 删除当前光标前的数字。

• L 光标向前移动一个数字。

• R 光标向后移动一个数字。

• Q k 设光标之前的数列是{a1，a2，……，an}，输出第k位及之前最大的前缀和，保证k≤n。

输入格式

第一行包含一个数字 N ，表示操作的个数。

接下来包含 N 行，每行包含一条命令。

输出格式

对于每个Q k 命令，输出一个整数表示这个操作的答案。

输入输出样例

输入 #1复制

1
2
3
4
5
6
7
8
9

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2

输出 #1复制

1
2

2
3

说明/提示

【数据规模】

对于 50% 的数据，N ≤ 1000；

对于 80% 的数据，N ≤ 100000；

对于 100% 的数据，N ≤ 1000000，插入的数字绝对值大小不会超过 1000。

洛谷P1367 蚂蚁

题目描述

有许多蚂蚁在一根无限长的木棍上，每一只蚂蚁都有一个初始位置和初始朝向（任意两只蚂蚁的初始位置不同）。蚂蚁们以每秒一个单位的速度向前移动，当两只蚂蚁相遇时，它们会掉头（掉头时间忽略不计）。现给出每只蚂蚁的初始位置和初始朝向，请你计算出它们在t秒后的位置和朝向。

输入格式

第一行，两个空格隔开的整数n，t（代表蚂蚁数n和时间t）

第2~n+1行每行两个整数，第i+1行代表第i只蚂蚁的初始位置ai（ai的绝对值在1000000以内）及初始朝向bi（bi=1时蚂蚁朝右，bi=-1时蚂蚁朝左）

输出格式

n行，每行两个整数，第i行代表t秒后第i只蚂蚁的位置及朝向（-1表示朝左，1表示朝右，0表示正在转向中）

输入输出样例

输入 #1复制

1
2
3
4
5

4 1
1 1
5 1
3 -1 
10 1

输出 #1复制

1
2
3
4

2 0
6 1
2 0
11 1

说明/提示

【数据范围】

对于40%的数据，n<=100

对于80%的数据，n<=10000,t<=1000

对于100%的数据，n<=100000,t<=100000

洛谷P1464 Function

题目描述

对于一个递归函数w(a,b,c)w(a,b,c)

• 如果a \le 0a≤0 or b \le 0b≤0 or c \le 0c≤0就返回值11.
• 如果a>20a>20 or b>20b>20 or c>20c>20就返回w(20,20,20)w(20,20,20)
• 如果a<ba<b并且b<cb<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)
• 其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)

这是个简单的递归函数，但实现起来可能会有些问题。当a,b,ca,b,c均为15时，调用的次数将非常的多。你要想个办法才行.

absi2011 : 比如 w(30,-1,0)w(30,−1,0)既满足条件1又满足条件2 这种时候我们就按最上面的条件来算 所以答案为1

输入格式

会有若干行。

并以-1,-1,-1−1,−1,−1结束。

保证输入的数在[-9223372036854775808,9223372036854775807][−9223372036854775808,9223372036854775807]之间，并且是整数。

输出格式

输出若干行，每一行格式：

1

w(a, b, c) = ans

注意空格。

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0,0)、BB 点 (n,m)(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1A1,A2,…,A**s1，B1,B2,…,Bs2B1,B2,…,B**s2，C1,C2,…,Cs3C1,C2,…,C**s3，D1,D2,…,Ds4D1,D2,…,D**s4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

洛谷 p1249 最大乘积

题目大意

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

洛谷P1012 [NOIP1998 提高组] 拼数

题目描述

设有 nn 个正整数 a_1 \dots a_na1…a**n，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 nn。

第二行有 nn 个整数，表示给出的 nn 个整数 a_ia**i。

输出格式

一个正整数，表示最大的整数

输入输出样例

输入 #1

1
2

3
13 312 343

输出 #1

1

34331213

输入 #2

1
2

4
7 13 4 246

输出 #2

1

7424613

说明/提示

对于全部的测试点，保证 1 \leq n \leq 201≤n≤20，1 \leq a_i \leq 10^91≤a**i≤109。

题目有点脑筋急转的意思，刚开始看到有点无从下手，看了题解后才发现这题目很巧妙。几个数字组成一个最大的数字，就相当于结果的字符串，字典序最大，这样一来就可以用排序做了。

STL的比较函数也很有意思

洛谷P1923 求第k小的数

题目描述

输入 nn(n<5000000n<5000000 且 nn 为奇数) 个数字 a_i(0<a_i<10^9)a**i(0<a**i<109) ，输出这些数字的第 kk 小的数。最小的数是第 0 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

洛谷 P5461 赦免战俘

自从选拔赛以来就没怎么认真刷题，总是感觉有点累，有点缺少动力。晚上做了到洛谷的基础题，调了1个多小时。。。

明明是一道很简单的递归题，还做了这么久，挺打击的，感觉自己真的是菜。递归可以说是所有算法的基础中的基础了，如果递归都理解的这么吃力，学习其他算法的困难可想而知，感觉自己还差得远，有点迷茫。

题目背景

借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！

题目描述

现有 2^n\times 2^n (n\le10)2n×2n(n≤10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 nn，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。