-含章可贞-
-含章可贞-
全部文章
分类
题解(7)
归档
标签
去牛客网
登录
/
注册
含章可贞的blog
全部文章
(共7篇)
题解 | #正则表达式匹配#
来抖个小机灵 import re string=input() pat=input() res=re.fullmatch(pat, string) if res!=None: print('true') else: print('false')
Python3
字符串
2022-05-24
2
278
题解 | #信封嵌套#
补一个python3答案: 方法: 按宽递增排序后,求长的最长严格上升子序列,同时要求宽不相等 注意:为保证宽不相等,可以使等宽区域内按长逆序排列,这样严格上升子序列在每组宽中只能取一个长,例: 输入排序前: [[3, 4], [2, 3], [4, 5], [1, 3], [2, 2], [3...
Python3
动态规划
2022-05-17
1
296
题解 | #合唱队形#
考虑分别以各个位置为中心折点,在每个位置求其: 之前的最长严格上升子序列长度(要求包括自己):实际就是题目DP14中dp数组 之后的最长严格下降子序列长度(要求包括自己):可通过两次数组反转得到 然后就是简单的加减法,得到以各个位置为中心折点时,最少要Out的人数,取最小 def maxIncS...
Python3
动态规划
2022-05-17
2
234
题解 | #拦截导弹#
Q1:很明确就是最长递减子序列的长度 Q2:根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度 n=eval(input()) heights=list(map(int,input().split())) dp=[1]*n # Q1:最长递减子序列 dp2=[1]*n #...
Python3
动态规划
2022-05-16
6
299
题解 | #[NOIP2002 普及组] 过河卒#
n,m,x,y=map(int,input().split()) assert(1<=n<=20) assert(1<=m<=20) assert(0<=x<=20) assert(0<=y<=20) board=[[1 for _ in range(...
Python3
动态规划
2022-05-16
1
253
题解 | #环形数组的连续子数组最大和#
将环转换为普通数组思考: 当目标是越过了末尾的环中子串,找到普通数组中和为负的最小子串,用和减去 找普通和最大的子串 两者比较取更大 特殊情况: 全负or全0:输出最大数 全正,直接取和 n=eval(input()) a=list(map(int,input().split())) dp1...
Python3
动态规划
2022-05-15
4
358
题解 | #链表内指定区间反转#
很简单,等比数列求通项,实际上就是2^(n-1),注意时间复杂度要O(1) import sys for line in sys.stdin: n = eval(line) a=2**(n-1) print(a)
Python3
2022-05-13
0
202