牛客网2017校招真题在线编程.md

星际穿越

题目描述

航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x2 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？

输入输出:

输入描述:

每个输入包含一个测试用例。每个测试用例包含一行一个整数 h （1 <= h <= 10^18）。

输出描述:

输出一行一个整数表示结果。

示例1

输入

10

输出

2

题解

二分法，很简单

def loss(n):
    return n*(n+1)

while(True):
    try:
        n=int(input())
        left=0
        right=n+1
        mid=(left+right)//2
        while(True):
            if(loss(mid)>n and loss(mid+1)>n):
                right=mid-1
                mid=(left+right)//2
            elif(loss(mid)<=n and loss(mid+1)<=n):
                left=mid+1
                mid=(left+right)//2
            elif(loss(mid)<=n and loss(mid+1)>n):
                break
        print(mid)
    except:
        break

藏宝图

题目描述

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

输入输出

输入描述:

每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述:

输出一行 “Yes” 或者 “No” 表示结果。

示例1

输入

x.nowcoder.com\
ooo

输出

Yes

题解

分析题意，子序列不需要字符连续，但相对位置使固定的。因此仅需要用字典记下s中每个字符的index，然后考虑t中字符，将s中相同字符中最小index的字符分配给t中（例如s='123123',t='13'，1的index为0或3，t中的1只需考虑s中index为0的那个即可，因为不要求连续，只要在左边就好），最后检查t的index是否递增即可。

while(True):
    try:
        s=input()
        t=input()
        dic={}
        judge='Yes'
        for i in range(len(s)):
            if s[i] not in dic:
                dic[s[i]]=[i,]
            else:
                dic[s[i]].append(i)
        l=[]
        for j in t:
            if j not in dic:
                judge='No'
                break
            else:
                if(dic[j]):
                    l.append(dic[j][0])
                    del dic[j][0]
                else:
                    judge='No'
                    break
        if(judge):
            for i in range(len(l)-1):
                if(l[i]>l[i+1]):
                    judge='No'
                    break
        print(judge)
    except:
        break