洛谷 P1080 [NOIP2012 提高组] 国王游戏
题目描述
恰逢H国国庆,国王邀请 nnn 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 nnn 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 nnn,表示大臣的人数。
第二行包含两个整数 aaa 和 bbb,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 nnn 行,每行包含两个整数 aaa 和 bbb,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
输出格式
一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例
输入 #1
123453 1 1 2 3 7 4 4 6
输出 #1
12
说明/提示
【输入输出样例说明】 ...
洛谷 P4447 [AHOI2018初中组]分组
题目描述
小可可的学校信息组总共有 nnn 个队员,每个人都有一个实力值 aia_iai。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的 nnn 个队员分成若干个小组去参加这场比赛。
但是每个队员都不会愿意与实力跟自己过于悬殊的队员组队,于是要求分成的每个小组的队员实力值连续,同时,一个队不需要两个实力相同的选手。举个例子:[1,2,3,4,5][1, 2, 3, 4, 5][1,2,3,4,5] 是合法的分组方案,因为实力值连续;[1,2,3,5][1, 2, 3, 5][1,2,3,5] 不是合法的分组方案,因为实力值不连续;[0,1,1,2][0, 1, 1, 2][0,1,1,2] 同样不是合法的分组方案,因为出现了两个实力值为 111 的选手。
如果有小组内人数太少,就会因为时间不够而无法获得高分,于是小可可想让你给出一个合法的分组方案,满足所有人都恰好分到一个小组,使得人数最少的组人数最多,输出人数最少的组人数的最大值。
注意:实力值可能是负数,分组的数量没有限制。
输入格式
输入有两行:
第一行一个正整数 nnn,表示队员数量 ...
洛谷 P5019 [NOIP2018 提高组] 铺设道路
题目描述
春春是一名道路工程师,负责铺设一条长度为 nnn 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 nnn 块首尾相连的区域,一开始,第 iii 块区域下陷的深度为 did_idi。
春春每天可以选择一段连续区间 [L,R][L,R][L,R],填充这段区间中的每块区域,让其下陷深度减少 111。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 000。
春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 000。
输入格式
输入文件包含两行,第一行包含一个整数 nnn,表示道路的长度。第二行包含 nnn 个整数,相邻两数间用一个空格隔开,第 iii 个整数为 did_idi。
输出格式
输出文件仅包含一个整数,即最少需要多少天才能完成任务。
输入输出样例
输入 #1
126 4 3 2 5 3 5
输出 #1
19
说明/提示
【样例解释】
一种可行的最佳方案是,依次选择:[1,6][1,6][1,6]、[1,6][1,6][1,6]、[1,2][1,2][1,2]、[1,1][1,1][1,1]、[4,6][ ...
洛谷 P1228 地毯填补问题
题目描述
相传在一个古老的阿拉伯国家里,有一座宫殿。宫殿里有个四四方方的格子迷宫,国王选择驸马的方法非常特殊,也非常简单:公主就站在其中一个方格子上,只要谁能用地毯将除公主站立的地方外的所有地方盖上,美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住,毯子的形状有所规定,只能有四种选择(如图):
并且每一方格只能用一层地毯,迷宫的大小为 2k×2k2^k\times 2^k2k×2k 的方形。当然,也不能让公主无限制的在那儿等,对吧?由于你使用的是计算机,所以实现时间为 1s1\mathrm s1s。
输入格式
输入文件共 222 行。
第一行:kkk,即给定被填补迷宫的大小为 2k×2k2^k\times 2^k2k×2k(0<k≤100\lt k\leq 100<k≤10);
第二行:x,yx,yx,y,即给出公主所在方格的坐标(xxx 为行坐标,yyy 为列坐标),xxx 和 yyy 之间有一个空格隔开。
输出格式
将迷宫填补完整的方案:每一行为 x y cx\ y\ cx y c(x,yx,yx,y 为毯子拐角的行坐标和列坐标,ccc 为使用毯子的形状, ...
洛谷 P1990 覆盖墙壁
题目描述
你有一个长为 nnn 宽为 222 的墙壁,给你两种砖头:一个长 222 宽 111,另一个是L型覆盖 333 个单元的砖头。如下图:
120 00 00
砖头可以旋转,两种砖头可以无限制提供。你的任务是计算用这两种来覆盖 2×n2\times n2×n 的墙壁的覆盖方法。例如一个 2×32\times 32×3 的墙可以有 555 种覆盖方法,如下:
12012 002 011 001 011 012 112 022 011 001
注意可以使用两种砖头混合起来覆盖,如 2×42\times 42×4 的墙可以这样覆盖:
1201120012
给定 nnn,要求计算 2×n2\times n2×n的墙壁的覆盖方法。由于结果很大,所以只要求输出最后 444 位。例如 2×132\times 132×13 的覆盖方法为 134651346513465,只需输出 346534653465 即可。如果答案少于 444 位,就直接输出就可以,不用加 000,如 n=3n=3n=3,时输出 555。
输入格式
一个整数 nnn(1≤n≤10000001\le n\le 10000 ...
POJ 2778 DNA Sequence
Description
It’s well known that DNA Sequence is a sequence only contains A\text AA, C\text CC, T\text TT and G\text GG, and it’s very useful to analyze a segment of DNA Sequence. For example, if a animal’s DNA sequence contains segment ATC\text{ATC}ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don’t contain those segments.
Suppose that DNA sequences of a species ...
HDU 2256 Problem of Precision
Problem Description
You know the date type double can guarantee the precision about 15 or 16 digits.
But in this problem, you have to calculate ⌊(2+3)2n⌋ mod 1024\left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{2n}\right\rfloor\bmod 1024⌊(2+3)2n⌋mod1024.
For example, when n=2n=2n=2, (2+3)4=97.9897⋯\left(\sqrt{2}+\sqrt{3}\right)^4=97.9897\cdots(2+3)4=97.9897⋯, ⌊(2+3)4⌋ mod 1024=97\left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{4}\right\rfloor\bmod 1024=97⌊(2+3)4⌋mod1024=97.
Input
The first line of i ...
洛谷 P1928 外星密码
有了防护伞,并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力,小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码,才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码,外星人对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式(DDD 是一个整 数且 1≤D≤991≤D≤991≤D≤99),比如说字符串“CBCBCBCB”就压缩为“[4CB]”或者“[2[2CB]]”,类似于后面这种压缩之后再压缩的称为二重压缩。如果是“[2[2[2CB]]]”则是三重的。现在我们给你外星人发送的密码,请你对其进行解压缩。
输入格式
第一行:一个字符串。
输出格式
第一行:一个字符串。
输入输出样例
输入 #1
1AC[3FUN]
输出 #1
1ACFUNFUNFUN
说明/提示
【数据范围】
对于 50%50\%50% 的数据:解压后的字符串长度在 100010001000 以内,最多只有三重压缩。
对于 100%100\%100% 的数据:解压后的字符串长度在 200002000020000 以内,最多只有十重压缩。 ...
图形渲染管线与着色器
图形渲染管线
在OpenGL中,任何事物都在3D空间中,而屏幕和窗口却是2D像素数组,这导致OpenGL的大部分工作都是关于把3D坐标转变为适应你屏幕的2D像素。3D坐标转为2D坐标的处理过程是由OpenGL的图形渲染管线管理的。图形渲染管线可以被划分为两个主要部分:第一部分把你的3D坐标转换为2D坐标,第二部分是把2D坐标转变为实际的有颜色的像素。
着色器
图形渲染管线接受一组3D坐标,然后把它们转变为你屏幕上的有色2D像素输出。图形渲染管线可以被划分为几个阶段,每个阶段将会把前一个阶段的输出作为输入。
有些着色器允许开发者自己配置,这就允许我们用自己写的着色器来替换默认的。这样我们就可以更细致地控制图形渲染管线中的特定部分了,而且因为它们运行在GPU上,所以它们可以给我们节约宝贵的CPU时间。
着色器(Shader)是运行在GPU上的小程序。这些小程序为图形渲染管线的某个特定部分而运行。从基本意义上来说,着色器只是一种把输入转化为输出的程序。着色器也是一种非常独立的程序,因为它们之间不能相互通信;它们之间唯一的沟通只有通过输入和输出。
图形渲染管线的第一个部分是顶点着色器,它把一 ...
洛谷 P1164 小A点菜
题目背景
uim神犇拿到了uoi的ra(镭牌)后,立刻拉着基友小A到了一家餐馆,很低端的那种。
uim指着墙上的价目表(太低级了没有菜单),说:“随便点”。
题目描述
不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩 mmm 元(m≤10000m \le 10000m≤10000)。
餐馆虽低端,但是菜品种类不少,有 nnn 种(n≤100n \le 100n≤100),第 iii 种卖 aia_iai 元(ai≤1000a_i \le 1000ai≤1000)。由于是很低端的餐馆,所以每种菜只有一份。
小A奉行“不把钱吃光不罢休”,所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。
由于小A肚子太饿,所以最多只能等待 111 秒。
输入格式
第一行是两个数字,表示 nnn 和 mmm。
第二行起 nnn 个正数 aia_iai(可以有相同的数字,每个数字均在 100010001000 以内)。
输出格式
一个正整数,表示点菜方案数,保证答案的范围在 int 之内。
输入输出样例
输入 #1
124 41 1 2 2
输出 #1
13
说明/提示
2020 ...