2018 年全国多校算法寒假训练营练习比赛（第二场）

A. 吐泡泡展开目录

思路展开目录

模拟题，数据小，暴力以下就行了

代码展开目录

#include <iostream>
#include <cstring>
using namespace std;
int move_One(int i,int len,char* s) {
    for(int j = i;j < len - 1;j++) 
        s[j] = s[j + 1];
    return len - 1;
}
int move_Two(int i,int len,char* s) {
    for(int j = i;j < len - 2;j++) 
        s[j] = s[j + 2];
    return len - 2;
}
int main() {
    char s[1000];
    while(scanf("%s",s) != EOF) {
        int len = strlen(s);
        for(int i = 0;i < len - 1;i++) {
            bool flag = false;
            if(s[i] == 'o' && s[i + 1] == 'o') {
                s[i] = 'O';
                len = move_One(i + 1,len,s);
                flag = true;
            }
            if(flag) {
                i = -1;
                continue;
            }
            if(s[i] == 'O' && s[i + 1] == 'O') {
                len = move_Two(i,len,s);
                flag = true;
            }
            if(flag) {
                i = -1;
                continue;
            }
        }
        for(int i = 0;i < len;i++)
            printf("%c",s[i]);
        printf("\n");    
    }
    return 0;
} 

B.TaoTao 要吃鸡展开目录

思路展开目录

背包问题，只是特殊处理一下 h 为 0 和不为 0 的情况就行

若 h=0，卡不了 bug，就是正常的 o-1 背包

若 h 不等于 0，可以卡 bug，假设第 i 件武器是卡 bug 放进去的，那么只要 01 背包计算能承受总重量为 m+h-1 的时候的最大价值 + 第 k 件武器的价值即可

代码展开目录

import java.util.*;
public class Main {
    public static int[] w = new int[105];
    public static int[] v = new int[105];
    public static int[] dp = new int[300];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(true) {
            int n,m,h;
            n = cin.nextInt();
            if(n == 0)
                break;
            m = cin.nextInt();
            h = cin.nextInt();
            for(int i = 0;i < n;i++) {
                w[i] = cin.nextInt();
                v[i] = cin.nextInt();
            }
            int ans = 0;
            for(int i = 0;i < 300;i++) 
                dp[i] = 0;
            if(h == 0) {//没有包，不能卡bug
                for(int i = 0;i < n;i++)
                    for(int j = m;j >= w[i];j--)
                        dp[j] = Math.max(dp[j],dp[j - w[i]] + v[i]);
                ans = dp[m];
            } else {//有背包，能卡bug
                for(int i = 0;i < n;i++) {
                    for(int tmp = 0;tmp < 300;tmp++) 
                        dp[tmp] = 0;
                    for(int j = 0;j < n;j++) {
                        //i不能再考虑
                        if(i == j)
                            continue;
                        for(int k = m + h - 1;k >= w[j];k--)
                            dp[k] = Math.max(dp[k],dp[k - w[j]] + v[j]);
                    }
                    ans = Math.max(ans,dp[m + h - 1] + v[i]);
                }
            }
            System.out.println(ans);
        }
    }
}

D.YB 要打炉石展开目录

思路展开目录

最长非降子序列问题，由于范围比较小，直接 $O (N^2)$

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        if(n < 30)
            System.out.println("no");
        else {
            int ans = 0;
            int[] num = new int[105];
            int[] dp = new int[105];
            for(int i = 0;i < n;i++) {
                num[i] = cin.nextInt();
                dp[i] = 1;
            }
            for(int i = 0;i < n;i++) {
                for(int j = 0;j < i;j++) {
                    if(num[i] >= num[j])
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                ans = Math.max(ans,dp[i]);
            }
            if(ans >= 30)
                System.out.println("yes");
            else
                System.out.println("no");
        }
    }
}

G 送分了 QAQ展开目录

思路展开目录

打表枚举，首先计算出 [1,1000000] 满足条件的数的个数，v [i] 表示 [1,i] 之间满足条件的数的个数，那么 [L,R] 之间满足条件的数的个数就是 v [R] - v [L]，还要判断 L 是否满足，L 满足就加一个

代码展开目录

import java.util.*;
public class Main {
    public static int[] v = new int[1000001];
    public static boolean check(int x) {
        String s0 = "";
        String s1 = "38";
        String s2 = "4";
        s0 += x;
        if(s0.contains(s1) || s0.contains(s2))
            return true;
        return false;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        for(int i = 1;i <= 1000000;i++) {
            v[i] = v[i - 1];
            if(check(i))
                v[i]++;
        }
        while(true) {
            int n = cin.nextInt();
            int m = cin.nextInt();
            if(n == 0 && m == 0)
                break;
            else {
                long ans = v[m] - v[n];
                if(check(n))
                    ans++;
                System.out.println(ans);
            }
        }
    }
}

H. 了断局展开目录

思路展开目录

规律就是 a [i] = a [i - 1] + a [i - 2] + a [i - 3]（i>=4）

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long[] ans = new long[60];
        ans[1] = 0;
        ans[2] = ans[3] = 1; 
        for(int i = 4;i <= 50;i++)
            ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
        while(cin.hasNext()) {
            int n = cin.nextInt();
            System.out.println(ans[n]);
        }
    }
}