本文共 11644 字，大约阅读时间需要 38 分钟。

**重叠的装饰

题目描述： 我们部门需要装饰墙，但是墙非常非常的长，有一千万米。我们会按顺序贴很多海报在上面，这些海报相互之间会重叠，请问下，最后还能看到哪些？（只看到一部分也算）

输入描述:

N表示N张海报 接下来每一行代表海报的左右边界（上下默认全满），Li，Ri，均为整数，大于0，小于一千万。海报按输入顺序张贴。 输出描述: 有多少张海报是可见的

排队唱歌

题目描述：

我们部门要排队唱歌，大家乱哄哄的挤在一起，现在需要按从低到高的顺序拍成一列，但每次只能交换相邻的两位，请问最少要交换多少次

输入描述:

第一行是N（N<50000）,表示有N个人 然后每一行是人的身高Hi（Hi<2000000,不要怀疑，我们以微米计数），持续N行，表示现在排列的队伍 输出描述: 输出一个数，代表交换次数。 求逆序对数

#include
   
    using namespace std; int main(){
       int n, i, j, ans = 0, temp;    cin >> n;    vector
    
      a(n);    for(i = 0; i < n; i++)        cin >> a[i];    for(i = 0; i < n; i++)        for(j = 0; j < i; j++)//****            if(a[j] > a[i])                ans++;    cout << ans << endl;    return 0;}
    
   

使用bisect模块，创建新的有序数组，数字在原数组中的位置与新的有序数组中的位置差，即为移动次数。其中，通过bisect.bisect_left() 返回插入的位置。通过 bisect.insort()插入数组并排序。

import bisectn = int(input())nums = []for _ in range(n):  nums.append(int(input()))result = 0lst = [nums[0]]for i in range(1, n):  idx = bisect.bisect_left(lst, nums[i])  bisect.insort(lst, nums[i])  result += i - idx  print(result)

**K点游戏

题目描述： 小招喵某日闲来无事，想验一下自己的人品，于是给自己定了一个游戏规则： 这个游戏有三个因素：N，K，W 游戏开始的时候小招喵有0点，之后如果发现自己手上的点不足K点，就随机从1到W的整数中抽取一个（包含1和W），抽到哪个数字的概率都是相同的。 重复上述过程，直到小招喵获得了K或者大于K点，就停止获取新的点，这时候小招喵手上的点小于等于N的概率是多少？

输入：N = 5， K = 1， W = 5

输出：1.00000 说明：开始有0点，不足1点，从[1,5]中随机取一个整数（一共5个数字，所以每个数字取到的概率都是1/5），获得后得分无论如何都大于了1点，停止，概率为1

输入：N = 6， K = 1， W = 10

输出：0.60000 说明：开始有0点，不足1点，从[1,10]中随机取一个整数（一共10个数字，所以每个数字取到的概率都是1/10），获得后有6/10的概率小于6点，且满足大于1点的条件，概率为0.6 输入描述: 输入为3个整数，分别对应N，K，W，中间用空格隔开

其中0 <= K <= N <= 10000，1 <= W <= 10000

输出描述: 输出为概率值，保留5位小数 由题目要求知道，N是点数的上限，K是点数的下限，W是随机取点数的上限。 动态规划：设 dp[i] 是初始点为 i 时的符合题目要求的概率。 当初始点 i 位于 [K,N] 时，此时的 dp[i] =1。 当初始点 i 位于 [N+1,K−1+W] 时 ，此时的dp[i]=0 。 关键的递归是： 通过这种递归，我们可以做一个朴素的动态编程解决方案，如下所示：

#psuedocodedp[k] = 1.0 when K <= k <= N, else 0.0# dp[x] = the answer when Alice has x pointsfor k from K-1 to 0:    dp[k] = (dp[k+1] + ... + dp[k+W]) / Wreturn dp[0]

但是这导致 O(K*W + (N-K)) 的时间复杂度，每个计算dp[k]需要O(W)，但是工作非常相似。但实际上，

所以我们可以维持一个变量S=dp(i+1)+dp(i+2)+⋯+dp(i+W). 想要计算 dp[i−1]，只需要在 dp[i] 的公式基础上加一项 dp[i]，再减一项 dp[i+W] 即可。

两点疑问：

如何得出递推公式

为什么S = min( N - K + 1, W )

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int main(){
       int n,k,w;    cin>>n>>k>>w;    vector
       
         dp(k+w);    for(int i=k;i<=n;i++)        dp[i]=1;    for(int i=n+1;i
        
         =0;i--) { dp[i]=temp/w; temp+=dp[i]-dp[i+w]; } cout<
         
          <
          
           <
          
         
        
       
      
     
    
   

class Solution {
       public double new21Game(int N, int K, int W) {
           double[] dp = new double[N + W + 1];        // dp[x] = the answer when Alice has x points        for (int k = K; k <= N; ++k)            dp[k] = 1.0;        double S = Math.min(N - K + 1, W);        // S = dp[k+1] + dp[k+2] + ... + dp[k+W]        for (int k = K - 1; k >= 0; --k) {
               dp[k] = S / W;            S += dp[k] - dp[k + W];        }        return dp[0];    }}

class Solution(object):    def new21Game(self, N, K, W):        dp = [0.0] * (N + W + 1)        # dp[x] = the answer when Alice has x points        for k in xrange(K, N + 1):            dp[k] = 1.0        S = min(N - K + 1, W)        # S = dp[k+1] + dp[k+2] + ... + dp[k+W]        for k in xrange(K - 1, -1, -1):            dp[k] = S / float(W)            S += dp[k] - dp[k + W]        return dp[0]

挑选课代表（区间选点，贪心）

        

题目描述： 我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述:

第一行是N（N<10000）,表示有N个区间，之间可以重复 然后每一行是ai,bi，持续N行，表示现在区间。均小于100000 输出描述: 输出一个数，代表最少选取数量。 将所有的区间按照右端点从小到大排序，若右端点相同，则按照左端点从大到小排序。这样就可以保证，如果存在区间的包含关系，那么被包含的区间一定出现在包含区间之上。接下来，，只要选择区间的右端点即可。

#include
   
    using namespace std;#define N 10000struct area {
       int a, b;}; bool cmp(pair
    
      x, pair
     
       y){
       return x.second < y.second;}  int main(){
   //    freopen("input.txt", "r", stdin);    int n, i;    cin >> n;    vector
      
       
         > a(n);    for(i = 0; i < n; i++) {
           cin >> a[i].first >> a[i].second;    }    sort(a.begin(), a.end(), cmp);    int p1 = -1, p2 = -1, ans = 0;    for(i = 0; i < n; i++) {
           if(a[i].first > p1) {
               ans++;            p1 = p2;            p2 = a[i].second;        }        if(a[i].first > p1) {
               ans++;            p1 = a[i].second - 1;        }    }    cout << ans << endl;    return 0;}
       
      
     
    
   

#include
   
    #include
    
     #include
     
      using namespace std;int main(){
       int n;    cin>>n;    vector
      
       
        > record;    for(int i=0;i
        
         >a>>b; record.push_back(make_pair(a,b)); } sort(record.begin(),record.end()); int count = 2; //l和r表示选点区间 int l = record[0].first; int r = record[0].second; for(int i=1;i
         
          =l&&record[i].first<=r){ l = record[i].first; r = min(r,record[i].second); }else{ count += 2; l = record[i].first; r = record[i].second; } } cout<
          
           <
          
         
        
       
      
     
    
   

import java.util.*;public class Main {
       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int[][] arr = new int[n][2];        for(int i = 0; i < n; i ++) {
               arr[i][0] = sc.nextInt();            arr[i][1] = sc.nextInt();        }          Arrays.sort(arr, (e1, e2) -> e1[1] - e2[1]);          LinkedList
   
     list = new LinkedList<>();        list.add(arr[0][1] - 1);        list.add(arr[0][1]);        for(int i = 1; i < n; i ++) {
               if(arr[i][0] > list.peekLast()) {
    // 相离                list.add(arr[i][1] - 1);                list.add(arr[i][1]);            } else if(arr[i][0] > list.get(list.size() - 2)) {
                   list.add(arr[i][1]);            }        }                 System.out.println(list.size());    }}
   

目的地最短步数

题目描述：

考虑你从家出发步行去往一处目的地，该目的地恰好离你整数单位步长（大于等于1）。你只能朝向该目的地或者背向该目的地行走，而你行走的必须为单位步长的整数倍，且要求你第N次行走必须走N步。 请就给出目的地离你距离，判断你是否可以在有限步内到达该目的地。如果可以到达的话，请计算到达目的地的最短总步数(不能到达则输出-1)。

输入描述:

1个整数：目的地离你距离T 输出描述: 1个整数：最短总步数（进行了多少次行走）

不用贪心，不用BFS！

根据题意画出一棵二叉树，根节点值为0，表示到家的距离

第二层，向左向右走一步，从左往右子节点值为-1，1，即±{1}

第三层，向左向右走两步，从左往右子节点值为-3，1，-1，3，即±{1，3}

第四层，向左向右走三步，从左往右子节点值为-6，0，2，4，-4，2，0，6，即±{0，2，4，6}

…

归纳总结：

第i层，设sum=1+2+3+…+i-1，

sum为奇数，第i层所到达的范围为[-sum,sum]内的所有奇数，

sum为偶数，第i层所到达的范围为[-sum,sum]内的所有偶数

sum可以无穷大，所以总是能够达到的.

现在求最短步数，即T出现的最早的一层i，这需要两个条件：

T和sum同奇偶

sum≥T

根据上述结论计算sum即可，注意循环退出后i-1才是正确答案

#include 
   
    using namespace std;int main(void){
       int T, i, sum = 1;    cin>>T;    for(i = 2; (sum-T)&1 || sum < T ; ++i)        sum += i;    cout<
    
     <
    
   

"""广度优先遍历算法[0]             第0层，[1, -1]         第1层，上层的结果 +1，-1[3, -1, 1, -3]  第2层，上层的结果 +2，-2...             第i层，上层的结果 +i，-i"""def BFS(n):    bfs = set([0])    i = 0    while True:        i += 1        pre = bfs.copy()        bfs = set()        for num in pre:            if num+i==n or num-i==n:                return i            else:                bfs.add(num+i)                bfs.add(num-i)n = int(input())print(BFS(n))

方格走法（排列组合）

题目描述：

有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。

输入描述:

输入包括一行，空格隔开的两个正整数x和y，取值范围[1,10]。 输出描述: 输出一行，表示走法的数目

因为只能向右走和向下，所以无论怎么走，向右的总距离和向下总距离都只能是x和y（即网格大小，曼哈顿距离不变），可以转换成分开的组合问题，假设用0代表向右，1代表向下，过渡转化成用x个0和Y个1能组成多少个不同的数，由划分组合公式可知，组合数合理是：

def cal_couple(num,i):    sum = 1    dvi_sum = 1    for i in range(i):        sum = sum*(num-i)        dvi_sum = dvi_sum * (i+1)    return (sum/dvi_sum)if __name__ == '__main__':    x,y = list(map(int,input().split()))    print('%d' %(cal_couple(x+y,x)))

import java.util.*;public class Main {
       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int m = sc.nextInt();         int res = 1;        for(int i = 1; i <= n; i ++) {
               res = res * (m + i) / i;        }         System.out.println(res);    }}

dp解法：dp[i][j]表示到（i，j）的方法数

import java.util.*;public class Main {
       public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);        int n = sc.nextInt();        int m = sc.nextInt();         int[][] dp = new int[n + 1][m + 1];        for(int i = 0; i <= n; i ++) {
               for(int j = 0; j <= m; j ++) {
                   if(i == 0 || j == 0) {
                       dp[i][j] = 1;                } else {
                       dp[i][j] = dp[i - 1][j] + dp[i][j - 1];                }            }        }         System.out.println(dp[n][m]);    }}

可能的句子

译文描述：

给定字符串s和单词字典dict，在s中添加空格以构建一个句子，其中每个单词都是有效的词典单词。返回所有可能的句子。

输入描述:

s =“catsanddog” dict =“cat”, “cats”, “and”, “sand”, “dog” 输出描述: [cats and dog, cat sand dog]

""""深度优先搜索DFS"""import sys def dfs(s, dic, arr, ans):    if not s:        ans.append(' '.join(arr))    for w in dic:        if s.startswith(w):            dfs(s[len(w):], dic, arr + (w,), ans) if __name__ == "__main__":    # sys.stdin = open("input.txt", "r")    s = input().strip()    s = s[s.index('"') + 1:-1]    dic = input().strip()    dic = eval("{" + dic[dic.index('"'):] + "}")    ans = []    dfs(s, dic, tuple(), ans)    print('[' + ', '.join(ans) + ']')

链表合并

题目描述：

请编写一段代码，实现两个单向有序链表的合并

输入描述:

第一行一个链表，如1 2 3 4 5 第二行一个链表，如2 3 4 5 6 输出描述: 输出：1 2 2 3 3 4 4 5 5 6 vector模拟list

#include 
   
    #include 
    
      using namespace std; vector
     
       merge(const vector
      
        &vec1, const vector
       
         &vec2){
       vector
        
          vec3; int i = 0; int j = 0; while(i < vec1.size() && j < vec1.size()){ if(vec1[i] <= vec2[j]){ vec3.push_back(vec1[i++]); } else{ vec3.push_back(vec2[j++]); } } while(i < vec1.size()){ vec3.push_back(vec1[i++]); } while(j < vec2.size()){ vec3.push_back(vec2[j++]); } return vec3; } int main(){ vector
         
           vec1, vec2; int temp; while(cin >> temp){ vec1.push_back(temp); if(getchar()=='\n') break; } while(cin >> temp){ vec2.push_back(temp); if(getchar() == '\n') break; } vector
          
            vec3(merge(vec1, vec2)); for(auto ele : vec3) cout << ele << " "; cout << endl; return 0;}
          
         
        
       
      
     
    
   

括号配对

题目描述：

括号配对问题

输入描述:

给定一个字符串S，请检查该字符串的括号是否配对，只含有"[", “]”, “(”, “)” 输出描述: 配对，返回true；不配对，返回false

s = input() def calc(s):  l = []  for e in s:    if e =='(' or e == '[':      l.append(e)    elif e == ']':      if len(l) > 0:        t = l[len(l) - 1]        if t != '[':          return False        l = l[0: len(l) - 1]      else:        return False    elif e == ')':      if len(l) > 0:        t = l[len(l) - 1]        if t != '(':          return False        l = l[0: len(l) - 1]      else:        return False  return Trueif calc(s):  print('true')else:  print('false')

#include
   
    #include
    
     #include
     
      using namespace std; int main(){
       string s;    cin>>s;    stack
      
        tmp;    bool flag=false;    for(int i=0;i
      
     
    
   

字符串加法

题目描述：

输入两个字符串a和b，字符串内容为二进制数字，求两个字符串相加的结果，加法计算方法以二进制方式计算，并返回对应的字符串结果。要求程序尽可能的高效。

#include 
   
    using namespace std; int main(){
       string a, b, s="";    cin>>a>>b;    int m = a.length(), n = b.length();    int c = 0;    if(m>n)        b = string(m-n, '0') + b;    else        a = string(n-m, '0') + a;    for(int i=max(m,n)-1;i>=0;i--){
           c += a[i]-'0' + b[i]-'0';        s = char((c&1)+'0') + s;        c >>= 1;    }    if(c==1)        s = '1' + s;    cout<
    <
   

""""进制间转换↓          2进制             8进制             10进制            16进制 2进制          -          bin(int(x, 8))    bin(int(x, 10))    bin(int(x, 16)) 8进制   oct(int(x, 2))           -          oct(int(x, 10))    oct(int(x, 16)) 10进制  int(x, 2)         int(x, 8)                 -          int(x, 16) 16进制  hex(int(x, 2))    hex(int(x, 8))    hex(int(x, 10))      -""" if __name__ == "__main__":    a = [int(x, 2) for x in input().strip().split()]    print(str(bin(sum(a)))[2:])

转载地址：http://tbqen.baihongyu.com/