美团题解-1
- 题目描述： 小美现在相信一些数字能给他带来好运。这些数字至少满足以下两个特征中的一种：
数字是11的整数倍。
数字中至少包含两个1。
小美现在给你若干数字，希望你回答这个数字是不是幸运数。例如：132是11的12倍，满足条件1，101有两个1，满足条件2。
输入描述：
第一行一个数字n，表示小美有n组询问。接下来每一行一个正整数表示小美询问的数字。数据保证1 <= n <= 500, 每个询问的数字在[1,
1e9]范围内。 输出描述： 对于每组询问，如果是幸运数，输出yes，不是，输出no。
样例输入:
6
22
101
1234
555
10001
132
样例输出:
yes
yes
no
no
yes
yes
def count11(num):count = 0while num > 0:res = num % 10if res == 1:count += 1num = num // 10return countwhile True:try:n=int(input())for i in range(n):num=int(input())if num%11==0:print('yes')elif count11(num)>=2:print('yes')else:print('no')except:break
- 题目描述：
小美现在有一个序列，序列中仅包含1和 - 1两种数字。小美现在想要知道，有多少个连续的子序列，序列中的数字乘积为正。
输入描述：
第一行一个正整数n，表示小美手中的序列长度。
第二行n个空格隔开的数字，每个数字只能是1和 - 1中的一种。
对于80 % 的数据保证1 <= n <= 500
对于剩余20 % 的数据保证1 <= n <= 5000
输出描述：
一行一个正整数表示有多少连续的子序列满足题目要求。
样例输入:
4
1 1 - 1 - 1
样例输出:
6
提示:
共有6个连续子序列满足要求。
[1], [1], [1, 1], [-1, -1], [1, -1, -1], [1, 1, -1, -1]
#动态规划
def count():l=int(input())num=list(map(int,input().split()))dp=[[0]*2 for _ in range(l+1)]#dp[i][0]以nums[i-1]结尾的乘积为正的子序列个数for i in range(1,l+1):if num[i-1]==1:dp[i][0]=dp[i-1][0]+1 #加上自身dp[i][1]=dp[i-1][1]if num[i-1]==-1:dp[i][0]=dp[i-1][1] #上一个乘积为-1的带上-1，乘积即为1，不加自身dp[i][1]=dp[i-1][0]+1#加上自身，乘积为1的后加上-1，再加自身return sum(dp[i][0] for i in range(l+1))
print(count())#前缀和
def sumnarray(nums):ans=[0]*(len(nums)+1)ans[0]=1prod,l=1,0for i in range(len(nums)):ans[i+1]=ans[i]*nums[i]for i in range(1,len(nums)+1):for j in range(i):if ans[i]//ans[j]==1:l+=1return l
n=int(input())
nums=list(map(int,input.split()))
print(sumnarray(nums))
- 小美现在在厨房做饭。小美发现食材现在只够每种菜做一份。现在同一时刻（即不分先后顺序）来了n个顾客。每个顾客都有想两份的
菜。只有当顾客吃到全部自己想要的菜的时候，顾客才会满意。现在你的任务是，合理地接取顾客的订单要求，尽可能让更多的顾客意，
输出最多有多少顾客可以满意。
输入描述:
第一行两个正整数n, m
n表明有多少顾客前来点菜，m表示小美现在能做的菜的编号范围在[1, m]。
接下来n行，每行两个数字，表明一名顾客的所点的两道菜的编号。
其中80% 的数据保证2 <= n <= 10, 2 <= m <= 20
另外20 % 的数据保证2 <= n <= 20, 2 <= m <= 40
输出描述:
一行一个正整数表示最多有多少顾客可以满意。
样例输入：
3 4
1 2
2 3
3 4
样例输出：
2
n,m=map(int,input().split())
a,b=[0]*25, [0]*25
vis=[0]*45
ans=-1
def dfs(cur_user, cur_max):if cur_user==n:global ansans=max(ans,cur_max)returnif (vis[a[cur_user]]==0 and vis[b[cur_user]]==0):vis[a[cur_user]], vis[b[cur_user]]=1, 1dfs(cur_user+1, cur_max+1)vis[a[cur_user]], vis[b[cur_user]]=0, 0dfs(cur_user+1, cur_max)for i in range(n):a[i],b[i]=map(int, input().split())
dfs(0,0)
print(ans)
3.1 科大讯飞的一道类似题目
最近讯飞教育部门的小李正在整理教辅教材，在他面前的是一堆的书本，练习册以及答案，小李需要将这些书籍进行分类，组成书册（一本书，一本练习册，一本答案），但是许多书上面的字迹都已经模糊了，然而小李还是可以大致判断这是一本书还是练习册或答案，并且能够大致知道一本书和答案以及一本书和练习册的对应关系（即仅仅知道某书和某答案、某书和某练习册的对应关系，除此以外的均不可能对应）。在这种情况下，小李最多可能同时组合成多少个完整的书册。
输入描述：第一行包含三个正整数，M,N,K，分别表示书的个数、练习册的个数和答案的个数。
第二行包含一个正整数T,表示书和练习册可能的对应管子个数。
接下来T行每行包含两个正整数x、y，表示第x本书和第y本练习册可能对应。（1<=x<=M,1<=y<=N）
接下来包含一个正整数P，表示书和答案可能的对应关系个数。
接下来P行每行包含两个正整数x、y，表示第x本书和第y本答案可能对应。（1<=x<=M,1<=y<=K）
输出描述:组合成的完整书册数目。
示例1：
输入：
5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3
输出：
2
如题，M=5,N=3,K=4,表示书有5本，练习册有3本，答案有4本。T=5,表示书和练习册共有5个可能的对应关系。分别为：书4和练习册3、书2和练习册2、书5和练习册2、书5和练习册1、书5和练习册3。P=5，表示书和答案共有5个可能的对应关系，分别为：书1和答案3、书3和答案1、书2和答案3、书3和答案3、书4和答案3。所以，以上情况的话最多可以同时配成两个书册、分别为：书2+练习册2+答案2、书4+练习册3+答案3.
import collections
# m,n,k=5,5,4
m,n,k=list(map(int,input().split()))
res_m=[0]*(m+1)
res_n=[0]*(n+1)
res_k=[0]*(k+1)
# num_book=5
num_book=int(input())
book=collections.defaultdict(list)
res=collections.defaultdict(list)
# book={4:[[4,3]],2:[[2,2]],5:[[5,2],[5,1],[5,3]]}
for i in range(num_book):a,b=list(map(int, input().split()))book[a].append([a,b])
num_ans=int(input())
print(num_ans)
# num_ans=5
# res={2:[[2,2,2],[2,3,3]],4:[[4,3,3],[4,5,1]],3:[[3,2,2]]}
# res={2:[[2,2,2]],4:[[4,3,3]]}
for i in range(num_ans):a,b=list(map(int, input().split()))if a in book.keys():for r in book[a]:res[a].append([r[0],r[1],b])
record=-1
def dfs(keys,count,index,l):global recordif index==l:record=max(record,count)returnk=keys[index]for v in res[k]:if len(v)!=3:continueif not res_m[v[0]] and not res_n[v[1]] and not res_k[v[2]]:res_m[v[0]], res_n[v[1]], res_k[v[2]] = 1, 1, 1dfs(keys, count+1, index + 1,l)res_m[v[0]], res_n[v[1]], res_k[v[2]] = 0, 0, 0dfs(keys,count,index+1,l)keys=list()
for key in res.keys():keys.append(key)
dfs(keys,0,0,len(keys))
print(record)
- 题目描述：
小美现在打音游。这个音游的玩法是这样的：
1）共有n个房间。小美初始拥有一个指针，指在一号房间。
2）游戏共持续m秒，每秒会有一个房间产生炸弹，小美的指针不能在这个房间中。
3）每秒结束的瞬间，小美可以使用一次魔法，把指针切换到另一个房间中，该过程会消耗一个能量。
你的任务是计算小美无伤通过音游所需要消耗的最小能量。保证第一秒的炸弹不发生在一号房间中。
输入描述：
第一行两个正整数 n 和 m，表示房间有 n 个，游戏持续 m 秒。
第二行 m 个正整数，每个正整数在1~n 的范围内，第 i 个正整数表示第 i 秒时炸弹在哪个房间生成。
数字间有空格隔开
数据保证 n ＜ = 10, 1 <= m <= 10000
输出描述：
一行一个正整数，表示小美无伤通过音游所需要消耗的最少能量。
样例输入：
2 4
2 1 1 2
样例输出：
2
提示:
样例解释1
第一秒结束后花费1能量切换到房间2，第三秒结束后花费1能量切换到房间1，共消耗能量2。
输入样例2
3 10
2 3 1 3 2 1 1 2 3 1
输出样例2
3
样例解释2
第二秒结束后切换到房间2，第四秒结束后切换到房间3，第八秒结束后切换到房间2，共消耗能量3
n,m=map(int, input().split())
INF=10**8
dp=[[INF]*(n+1) for _ in range(m+1)] #第m秒在第n个房间
dp[1][1]=0
bomb=[0]
tmp=list(map(int, input().split()))
bomb.extend(tmp)
for i in range(2,m+1):for j in range(1,n+1):if j==bomb[i]:continuefor k in range(1,n+1):t=0 if k==j else 1dp[i][j]=min(dp[i][j],dp[i-1][k]+t)
print(dp)
res=INF
for i in range(1,n+1):res=min(res,dp[m][i])
print(res)
- 黑白树涂色
题目描述：
现在给你一颗树，每个树上的节点会被涂成黑色或白色。
现在定义好节点：
对于白色的节点：若该节点没有子节点，或该节点子节点中至少有一个为黑色节点，则该节点是好节点
对于黑色的节点：若该节点没有子节点，或该节点的所有子节点均为白色节点，则该节点是好节点
你的任务是找出这棵树上黑色的好节点和白色的好节点各有几个。
输入描述:
第一行一个正整数n，表示这棵树共有n个节点，编号1到n。
第二行n个空格隔开的正整数，代表每个节点的颜色。0是白色，1是黑色。
接下来n个空格隔开的正整数，第 i 个正整数v表示节点 i 的父节点是v。其中，数字0表示这个节点是根。
1 <= n <= 10000
输出描述:
一行两个正整数，以空格分开，第一个正整数表示白色的好节点有几个，第二个正整数表示黑色的好节点有几个。
样例输入:
6
1 0 1 1 0 0
0 1 2 1 4 4
样例输出:
3 2
import collections
n=int(input())
color=list(map(int,input().split()))
nums=list(map(int,input().split()))
res=[0]*2
mp=collections.defaultdict(int)
def dfs(m, tree):if not tree[m]:mp[color[m-1]]+=1returnblack=0for i in range(len(tree[m])):if color[tree[m][i]-1]==1:black+=1dfs(tree[m][i], tree)if color[m-1]==1 and black==0:mp[color[m - 1]] += 1if color[m-1]==0 and black>=1:mp[color[m-1]]+=1return mptree=[[] for _ in range(n+1)]
for i in range(len(nums)):tree[nums[i]].append(i+1)
print(tree)
print(dfs(tree[0][0],tree))
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！