企业建站个人建站源码,没有域名怎么访问网站,天河做网站开发,无敌神马在线观看免费完整题目1:题目 2335: 信息学奥赛一本通T1422-活动安排
设有n个活动的集合E{1,2,…,n}#xff0c;其中每个活动都要求使用同一资源#xff0c;如演讲会场等#xff0c;而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi…题目1:题目 2335: 信息学奥赛一本通T1422-活动安排
设有n个活动的集合E{1,2,…,n}其中每个活动都要求使用同一资源如演讲会场等而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。也就是说当si≥fj或sj≥fi时活动i与活动j相容。选择出由相互兼容的活动组成的最大集合。
输入格式
第1行一个整数n(n≤1000)接下来n行每行两个整数si和fi。
输出格式
输出尽可能多的互相兼容的活动个数。
样例输入
4 1 3 4 6 2 5 1 7
样例输出
2
python代码
nint(input())
t[]
a1#互相兼容的活动数量for i in range(n):t.append(input().split())
for i in range(n):for j in range(2):t[i][j]int(t[i][j])
t.sort(keylambda x:x[0],reverseTrue)#按照活动开始的时间进行降序排列
for i in range(n-1):if t[i][0]t[i1][0]:if t[i][1]t[i1][1]:t[i][1],t[i1][1]t[i1][1],t[i][1]#左端点相同将结束时间晚的放在后面lastxt[0][0]#最晚结束的活动的开始时间
for k in range(1,n):if t[k][1]lastx:#某一活动在它 开始之前结束lastxt[k][0]a1
print(a)知识点
先把活动开始的时间进行降序排列之后若左端点相同将结束时间晚的放在后面指针首先指向最晚结束的活动的开始时间若是某一个活动的结束时间在它之前那么这两个活动兼容另外一种思路先把活动结束的时间进行升序排列之后若左端点相同将结束时间晚的放在后面指针首先指向最早结束的活动的结束时间若是某一个活动的开始时间在它之后那么这两个活动兼容
题目2P1002 [NOIP2002 普及组] 过河卒
棋盘上 A 点有一个过河卒需要走到目标 B 点。卒行走的规则可以向下、或者向右。同时在棋盘上 C 点有一个对方的马该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示 A 点 (0,0)、B 点 (n,m)同样马的位置坐标是需要给出的。
输入格式
一行四个正整数分别表示 B 点坐标和马的坐标。
输出格式
一个整数表示所有的路径条数。
样例输入
6 6 3 3
样例输出
6
python代码
x,y,n,mmap(int,input().split())
x1
y1
n1
m1#便于计算索引值从1开始ma[[0]*25 for _ in range(25) ]#马的位置
step[[0]*25 for _ in range(25)]#坐标ma[n][m]1
step[1][1]1ma[n-2][m-1]1#马能到达的位置
ma[n-2][m1]1
ma[n2][m-1]1
ma[n2][m1]1
ma[n-1][m-2]1
ma[n-1][m2]1
ma[n1][m-2]1
ma[n1][m2]1for i in range(1,x1):for j in range(1,y1):if (i!1 or j!1) and(not ma[i][j]):step[i][j]step[i-1][j]step[i][j-1]
print(step[x][y])知识点
二维列表的建立方式最初我以为ma[[0]*5]*5来建立的后来运行的时候一直报错才知道这种方法会指向列对某一值修改会对整列进行修改那么正确的创建方式为ma[[0]*5 for _ in range(5)]找到正常情况下的递推公式step[i][j]step[i-1][j]step[i][j-1]只能向右或向下最后 把非正常情况的点 去除
题目3
你的程序将由操作数序列 1,2,…,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数
输出格式
输出文件只有一行即可能输出序列的总数目
样例输入
3
样例输出
5
python代码
nint(input())
ans1
for i in range(1,n1):ansans*(4*i-2)//(i1)
print(f{ans:d})
知识点
卡特兰数进出栈序列n 个元素进栈序列为1234…n则有多少种出栈序列
结论 C n C n − 1 ∗ 4 ∗ n − 2 n 1 C_{_{n}}C_{_{n-1}}* \frac{4*n-2}{n1} CnCn−1∗n14∗n−2
题目4:# [NOIP2001 普及组] 数的计算
题目描述
给出正整数 n n n要求按如下方式构造数列
只有一个数字 n n n 的数列是一个合法的数列。在一个合法的数列的末尾加入一个正整数但是这个正整数不能超过该数列最后一项的一半可以得到一个新的合法数列。
请你求出一共有多少个合法的数列。两个合法数列 a , b a, b a,b 不同当且仅当两数列长度不同或存在一个正整数 i ≤ ∣ a ∣ i \leq |a| i≤∣a∣使得 a i ≠ b i a_i \neq b_i aibi。
输入格式
输入只有一行一个整数表示 n n n。
输出格式
输出一行一个整数表示合法的数列个数。
样例 #1
样例输入 #1
6样例输出 #1
6提示
样例 1 解释
满足条件的数列为 6 6 6 6 , 1 6, 1 6,1 6 , 2 6, 2 6,2 6 , 3 6, 3 6,3 6 , 2 , 1 6, 2, 1 6,2,1 6 , 3 , 1 6, 3, 1 6,3,1
数据规模与约定
对于全部的测试点保证 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1≤n≤103。
python代码
def count(n):global ansfor i in range(1,n1):for j in range(1,int(i/2)1):f[i]f[j]f[i]1nint(input())
ans1#自身
f[0]*1001
if n1:print(ans)
else:count(n)print(f[n])
知识点
先找规律,然后代码实现f(1)1,f(2)2,f(3)2f(4)f(1)f(2)1f(5)f(1)f(2)1f(6)f(1)f(2)f(3)1f(7)f(1)f(2)f(3)1
题目5# 黑白棋子的移动
题目描述
有 2 n 2n 2n 个棋子排成一行开始为位置白子全部在左边黑子全部在右边如下图为 n 5 n5 n5 的情况 移动棋子的规则是每次必须同时移动相邻的两个棋子颜色不限可以左移也可以右移到空位上去但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子不能平移要求最后能移成黑白相间的一行棋子。如 n 5 n5 n5 时成为 任务编程打印出移动过程。
输入格式
一个整数 n n n。
输出格式
若干行表示初始状态和每次移动的状态用 o \verb!o! o 表示白子 * \verb!*! * 表示黑子 - \verb!-! - 表示空行。
样例 #1
样例输入 #1
7样例输出 #1
ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
oooo****--o*o*o*
ooo--***o*o*o*o*
ooo*o**--*o*o*o*
o--*o**oo*o*o*o*
o*o*o*--o*o*o*o*
--o*o*o*o*o*o*o*python代码
def printx():#打印单元for i in range(2*n2):print(c[i],end)print()def move(n):if n4:#n4时已经为最小问题需要列举c[3],c[8]c[8],c[3]c[4],c[9]c[9],c[4] printx()#打印第一步c[3],c[7]c[7],c[3]c[4],c[8]c[8],c[4]printx()#打印第二步c[1],c[7]c[7],c[1]c[2],c[8]c[8],c[2]printx()#打印第三步c[1],c[6]c[6],c[1]c[2],c[7]c[7],c[2]printx()#打印第四步c[0],c[6]c[6],c[0]c[1],c[7]c[7],c[1]printx()#打印第五步else:c[n-1],c[2*n]c[2*n],c[n-1]c[n],c[2*n1]c[2*n1],c[n]printx()c[n-1],c[2*n-2]c[2*n-2],c[n-1]c[n],c[2*n-1]c[2*n-1],c[n]printx()move(n-1)nint(input())
c[]#存放元素
for i in range(n):print(o,end)c.append(o)for j in range(n,2*n):print(*,end)c.append(*)
c.append(-)
c.append(-)#一共2n2个值索引到c[2n1]
print(--)
move(n)
知识点
首先找规律之后从最小的单元开始即n4会发现n5移动2步后就会变为n4的问题依次形成递归的思路注意每一步调用printx()函数对于未完全输出一行数据end,一行输出完毕利用print()换行
题目6# [NOIP1998 普及组] 幂次方
题目描述
任何一个正整数都可以用 2 2 2 的幂次方表示。例如 $13727232^0 $。
同时约定次方用括号来表示即 a b a^b ab 可表示为 a ( b ) a(b) a(b)。
由此可知 137 137 137 可表示为 2 ( 7 ) 2 ( 3 ) 2 ( 0 ) 2(7)2(3)2(0) 2(7)2(3)2(0)
进一步 7 2 2 2 2 0 7 2^222^0 722220 ( 2 1 2^1 21 用 2 2 2 表示)并且 3 2 2 0 322^0 3220。
所以最后 137 137 137 可表示为 2 ( 2 ( 2 ) 2 2 ( 0 ) ) 2 ( 2 2 ( 0 ) ) 2 ( 0 ) 2(2(2)22(0))2(22(0))2(0) 2(2(2)22(0))2(22(0))2(0)。
又如 1315 2 10 2 8 2 5 2 1 13152^{10} 2^8 2^5 21 1315210282521
所以 1315 1315 1315 最后可表示为 2 ( 2 ( 2 2 ( 0 ) ) 2 ) 2 ( 2 ( 2 2 ( 0 ) ) ) 2 ( 2 ( 2 ) 2 ( 0 ) ) 2 2 ( 0 ) 2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(0) 2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(0)。
输入格式
一行一个正整数 n n n。
输出格式
符合约定的 n n n 的 0 , 2 0, 2 0,2 表示在表示中不能有空格。
样例 #1
样例输入 #1
1315样例输出 #1
2(2(22(0))2)2(2(22(0)))2(2(2)2(0))22(0)提示
【数据范围】
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 2 × 10 4 1 \le n \le 2 \times {10}^4 1≤n≤2×104。
python代码
def culi(n):m0#记录幂if n1:#最小问题print(2(0),end)elif n2:print(2,end)elif n3:while na[m1]:#找到最大的幂m1#print(m)n-a[m]print(2,end)if m2:print((,end)culi(m)print(),end)if n!0:#子问题print(,end)culi(n)nint(input())
a[]
for i in range(16):a.append(pow(2,i))
culi(n)
知识点
数学分治递归的思想当n3,拆分成n1或n2的问题由于最大的数值不是很大2^15所以利用查表确定最大的索引值之后进行两次递归。
