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

A. 大吉大利，今晚吃鸡 —— 枪械篇展开目录

思路展开目录

说实话，一开始看到这个题，还以为是动态规划，后来想了一下好像并不存在什么子问题，就是单纯要求个最大值而已，枪的威力由强本身的威力加上配件的加成，那么配件加成就显得尤为重要，我在代码中有一步处理，对于同种的配件，如果一个加成比另一个的大，那就用大的覆盖掉小的，小的根本就不用管了

代码展开目录

import java.util.Scanner;
class gun {
    public int p;//枪支威力
    public int k;//枪支可装配的配件数量
    public int[] kind = new int[1002];//可装配配件的种类
}
public class Main {
    static gun[] g = new gun[1002];//声明对象数组
    public static Double[] pei = new Double[1002];
    public static void main(String[] args) {
        int n,m;
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            n = cin.nextInt();
            m = cin.nextInt();
            //实例化对象数组，不然不能用
            for(int i = 0;i < 1002;i++) {
                g[i] = new gun();
            }
            for(int i = 0;i < 1002;i++)
                pei[i] = 0.0;
            //输入枪的信息
            for(int i = 0;i < n;i++) {
                g[i].p = cin.nextInt();
                g[i].k = cin.nextInt();
                for(int j = 0;j < g[i].k;j++)
                    g[i].kind[j] = cin.nextInt();
            }
            //输入配件的信息
            for(int i = 0;i < m;i++) {
                int q = cin.nextInt();
                Double b = cin.nextDouble();
                if(pei[q] < b)
                    pei[q] = b;
            }
            //计算最大威力
            Double max = 0.0;
            for(int i = 0;i < n;i++) {
                Double tmp = 1.0;
                for(int j = 0;j < g[i].k;j++)
                    tmp += pei[g[i].kind[j]];
                if(g[i].p * tmp > max)
                    max = g[i].p * tmp;
            }
            System.out.printf("%.4f\n",max);
        }
    }
}

这里定义的对象数组类似于 c/c++ 中的结构体，将枪的信息包装起来，一开始无论怎么运行都会报错，查了原因才发现我没有 18~20 行的实例化对象数组，因为这个东西我用的也少，所以没有注意到，为了确保计算的精准，我用的都是 double 的包装类，基本浮点数据类型是无法保存一个确定的浮点数的，只能近似，但是用 Double 包装类就可以

B. 最强的决斗者一切都是必然的！展开目录

思路展开目录

这道题还是比较好做的，首先找到哪些牌是在同一个连锁内，记录有多少组连锁，然后在从后往前枚举这些卡的效果，因为题目说了后出的牌先发动效果

代码展开目录

import java.util.Scanner;
class card {
    public int s;//牌的速度
    public int t;//牌的效果
    public int x;//造成的伤害
}
public class Main {
    static card[] c = new card[1002];//声明对象数组
    public static int[] lian = new int[1002];//连锁
    public static int[] tail = new int[1002];
    public static int sum = 0;
    public static void main(String[] args) {
        int n;
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            n = cin.nextInt();
            for(int i = 1;i <= n;i++) {
                c[i] = new card();
                c[i].s = cin.nextInt();
                c[i].t = cin.nextInt();
                if(c[i].t == 1 || c[i].t == 2) 
                    c[i].x = cin.nextInt();
            }
            lian[1] = 1;
            int ans = 0;//记录有多少组连锁
            for(int i = 2;i <= n;i++) {
                if(c[i].s >= c[i - 1].s)
                    lian[i] = lian[i - 1] + 1;//连锁编号加加
                else {
                    lian[i] = 1;
                    tail[ans] = i - 1;
                    ans++;
                }
            }
            tail[ans] = n;
            int sum = 0;
            for(int i = 0;i <= ans;i++) {
                for(int j = tail[i];j > tail[i] - lian[tail[i]];j--) {
                    if(c[j].t == 1)sum += c[j].x;
                    if(c[j].t == 2)sum += c[j].x * lian[j];
                    if(c[j].t == 3)break;
                    if(c[j].t == 4)j--;
                }
            }
            System.out.println(sum);
        }
    }
}

ans 记录的是有多少组连锁，方便后面计算的时候进行循环，lian [i] 表示第 i 张卡在其自己所属的连锁内的连锁编号，比方说样例中的 3 3，对应的数组就是 lian [8] = 2，tail [i] 表示的是第 i 组连锁的最大下标值，对于样例来说，tail [0]=4,tail [1]=6,tail [2]=9，针对样例，我写了个 tail 和 lian 这两个数组的值，见下：

9
1 1 300  lian[1] = 1 ans = 0
2 2 400  lian[2] = 2 ans = 0
2 3      lian[3] = 3 ans = 0
2 2 500  lian[4] = 4 ans = 0
1 1 1000 lian[5] = 1 tail[0] = 4 ans = 1
3 4      lian[6] = 2 ans = 1
2 1 600  lian[7] = 1 tail[1] = 6 ans = 2
3 3      lian[8] = 2 ans = 2
3 4      lian[9] = 3 tail[2] = 9

如果效果是 3，那就直接 break，这一连锁里的所有卡都不用看了，效果全部无效了；如果效果是 4，直接 j--，跳过前面的一张卡

C. 六子冲展开目录

思路展开目录

棋盘上攻击方的 2 个棋子 (2 子必须相连并主动移动其中的 1 个) 与被攻方的 1 个棋子皆处在一条直线上并相邻时，被攻方的这个棋子就被消灭

每次移动后判断一下，移动后棋子的那一行和一列，判断是否可以消灭其他子

若一行中有 4 子或 3 子不连通或攻击方的子数只有一个或 3 个 则无法消灭任何棋子

代码展开目录

import java.util.Scanner;
public class Main {
    static int n;
    static int p;
    static int q;
    static int cas = 0;
    static int x[] = new int[15];
    static int y[] = new int[15];
    static int map[][] = new int[10][10];
    static int dr[][] = {{0,0},{-1,0},{1,0},{0,-1},{0,1}};
    public static void init() {
        for(int i = 0;i < 10;i++)
            for(int j = 0;j < 10;j++)
                map[i][j] = 0;
        x[11] = x[10] = x[9] = x[8] = 1;
        x[2] = x[3] = x[4] = x[5] = 4;
        x[1] = x[6] = 3;
        x[12] = x[7] = 2;
        y[11] = y[12] = y[1] = y[2] = 1;
        y[10] = y[3] = 2;
        y[9] = y[4] = 3;
        y[8] = y[7] = y[6] = y[5] = 4;
        for(int i = 1;i <= 12;i++)
            map[x[i]][y[i]] = i;
    }
    public static void update() {
        map[x[p]][y[p]] = 0;
        x[p] += dr[q][0];
        y[p] += dr[q][1];
        map[x[p]][y[p]] = p;
        check(1);
        check(2);
    }
    public static void check(int t) {
        int bk,wt,num,last;
        bk = wt = num = last = 0;
        for(int i = 1;i <= 4;i++) {
            if(t == 1)
                num = map[x[p]][i];
            else 
                num = map[i][y[p]];
            if(num == 0 && (i == 2 || i == 3))
                return;
            if(num > 6) {
                if(last == 1 && wt == 1)
                    return;
                wt++;
                last = 2;
            } else if(num > 0) {
                if(last == 2 && bk == 1)
                    return;
                bk++;
                last = 1;
            }
        }
        if((bk == 2 && wt == 1 && p <= 6) || (bk == 1 && wt == 2 && p > 6)) {
            for(int i = 1;i <= 4;i++) {
                if(t == 1)
                    num = map[x[p]][i];
                else
                    num = map[i][y[p]];
                if((wt == 1 && num > 6) || (bk == 1 && num <= 6))
                        map[x[num]][y[num]] = 0;
            }
        }
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            n = cin.nextInt();
            init();
            for(int i = 0;i < n;i++) {
                p = cin.nextInt();
                q = cin.nextInt();
                update();
            }
            System.out.println("#Case " + ++cas + ":");
            for(int i = 1;i <= 4;i++) {
                for(int j = 1;j <= 4;j++) 
                    System.out.printf("%3d",map[i][j]);
                System.out.println();
            }
        }
    }
}

D.N 阶汉诺塔变形展开目录

思路展开目录

注意题目中的要求和普通的汉诺塔问题不一样，多了个条件：每次只能将一个圆盘从一个塔座移动到相邻的塔座上

先手动模拟一下过程，这里推荐一个汉诺塔在线游戏，边看边动手可能更容易理解，假设是 3 阶的汉诺塔，对于从小到大的汉诺塔分别编号为 1-3，移动汉诺塔的编号就是：11211211311211211311211211，详情见下面动图

那么规律就来了，我们发现每两次 1 就会出现一次 2，每两次 2 就会出现一次 3，每两次 3 就会出现一次 4......

如果我们把所有大于 1 的编号都看成 1，那么 k 步 1 出现的次数是 $\frac {k}{1}$

如果我们把所有编号大于 2 的都看成 2，那么 k 步 2 出现的次数是 $\frac {k}{3}$

如果我们把所有编号大于 3 的都看成 3，那么 k 步 3 出现的次数是 $\frac {k}{3^2}$

如果我们把所有编号大于 4 的都看成 4，那么 k 步 4 出现的次数是 $\frac {k}{3^3}$......

$\frac {k}{3^{i-1}}$ 可以表示这个循环的步数，对 6 进行取余就知道 i 走到哪里了

代码展开目录

#include <iostream>
#include <vector>
using namespace std;
long long n,k;
int main() {
    while(cin >> n >> k) {
        vector<int> v[3];
        long long base = 1;
        for(int i = 1;i <= n;i++) {
            int t = (k / base) % 6;
            if(t > 2)
                t = 5 - t;
            v[t].push_back(i);
            base *= 3;
        } 
        for(int i = 0;i < 3;i++) {
            if(v[i].size()) {
                for(int j = v[i].size() - 1;j >= 0;j--) {
                    cout << v[i][j];
                    if(j != 0)
                        cout << " ";
                }
            } else
                cout << "0";
            cout << endl;
        }
    }
    return 0;
} 

E. 恋与程序员展开目录

思路展开目录

总结一下题目，给你一个图，每条边都有耗费，现在你要从 1 号点走到 c 号点，问最少的耗费是多少，样例构成的图是这样
边上的数字表示需要几号卡片，括号里的值代表卡片的价值，也就是耗费，红色的点代表最终要达到的点

这是一个很明显的搜索问题，用 bfs 或者 dfs 都可以实现，这里我用的 dfs，有两点要注意就是买过的卡片可以无限次用，无非就是多加个数组判断一下这个卡片买过没有，买过就不用增加价值了，没买过就买就行了。还有一个就是走过的点就不能再走了

代码展开目录

import java.util.*;
public class Main {
    public static int[][] map = new int[102][102];//map为图
    public static int[] card = new int[102];//card[i]表示编号为i的卡片的价值
    public static boolean[] v = new boolean[102];//点有没有被走过
    public static boolean[] use = new boolean[102];//卡有没有被用过
    public static int ans;
    public static void dfs(int point,int begin,int end,int sum) {
        if(begin == end) {
            ans = Math.min(sum,ans);
            return;
        }
        for(int i = 1;i <= point;i++) {
            if(map[begin][i] != 0 && !v[i]) {//begin到i有边，并且i这个点没被走过
                v[i] = true;
                if(use[map[begin][i]])//卡被用过，就是买过了
                    dfs(point,i,end,sum);
                else {//卡没被用过
                    use[map[begin][i]] = true;
                    dfs(point,i,end,sum + card[map[begin][i]]);
                    use[map[begin][i]] = false;
                }
                v[i] = false;    
            }
        }    
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            ans = Integer.MAX_VALUE;
            int n = cin.nextInt();//事件（点）的数量
            int m = cin.nextInt();//关卡（边）的数量
            int k = cin.nextInt();//卡片数量
            int c = cin.nextInt();//终点编号
            for(int i = 0;i < 101;i++) {
                for(int j = 0;j < 101;j++) {
                    map[i][j] = 0;    
                }
                card[i] = 0;
                v[i] = false;
                use[i] = false;
            }
            for(int i = 0;i < m;i++) {
                int u = cin.nextInt();
                int v = cin.nextInt();
                int e = cin.nextInt();
                map[u][v] = e;
            }
            for(int i = 0;i < k;i++) {
                int a = cin.nextInt();
                int b = cin.nextInt();
                card[a] = b;
            }
            dfs(n,1,c,0);
            System.out.println(ans);
        }
    }
}

F. 大吉大利，今晚吃鸡 —— 跑毒篇展开目录

思路展开目录

模拟就完了，比较重要的一点是什么时候打药，打药的时机要贪心一下，因为打药要耗时 6 秒，如果剩余血量还能撑 (6,7] 秒之间，就可以打药了

代码展开目录

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while((T--) != 0) {
            int a = cin.nextInt();//扣血速度 %a/s
            int b = cin.nextInt();//角色和安全区的距离
            int c = cin.nextInt();//急救包的数量
            int hp = 100;
            boolean flag = true;
            while((--b) != 0) {
                hp -= a;
                if(hp <= 0) {
                    flag = false;
                    break;
                }
                if(hp > 6 * a && hp <= 7 * a && c >= 1) {
                    hp = 80;
                    --c;
                }
            }
            if(flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}

吐槽一下这个题出的不是很好，说明没有说清楚，如果每秒扣血是 100%，距离安全区还剩 1m，那到底是 YES 还是 NO，其实也就是第 13 行，究竟应该是 b-- 还是 --b 的问题

G. 圆圈展开目录

思路展开目录

规律就是对于 n，输出的图形是

空格 f (n - 1)

f (n - 1) 空格 f (n - 1)

空格 f (n - 1)

代码展开目录

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e4+10;
int len[10] = {1};
vector<int> map[N];
void slove(int n,int h,int l) {
    if(n == 0) {
        map[h].push_back(l); 
        return;
    }
    slove(n - 1,h,l + len[n - 1]);
    slove(n - 1,h + len[n - 1],l);
    slove(n - 1,h + len[n - 1],l + 2 * len[n - 1]);
    slove(n - 1,h + 2 * len[n - 1],l + len[n - 1]);
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i = 1;i < 8;i++) 
        len[i] = len[i - 1] * 3;
    int T,n;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i = 1;i <= len[n];i++) 
            map[i].clear();
        slove(n,1,1);
        for(int i = 1;i <= len[n];i++) {
            int len = map[i].size();
            for(int j = 0;j < len;j++) {
                int k = (j == 0) ? 1 : map[i][j - 1] + 1;
                for(;k < map[i][j];k++) 
                    cout << " ";
                cout << "O";
            }
            cout << endl;
        }
    }
    return 0;
}

H. 方块与收纳盒展开目录

思路展开目录

这不就是个简单的爬楼梯问题吗，有 n 阶楼梯，每次可以跨一阶或两阶，问有多少种不同的方式爬上楼顶，简单的动态规划，直接上代码了没什么好说的

代码展开目录

import java.util.*;
public class Main {
    static long result[] = new long[100];
    public static long dp(int idx) {
        if(idx < 0) 
            return 0;
        if(idx == 0)
            return 1;
        if(result[idx] != -1)
            return result[idx];
        return result[idx] = dp(idx - 1) + dp(idx - 2);
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while((T--) != 0) {
            int n = cin.nextInt();
            for(int i = 0;i < 100;i++)
                result[i] = -1;
            System.out.println(dp(n));
        }
    }
}

I. 找数字个数展开目录

思路展开目录

这.... 也太简单了，首先用个 set 保存 a 和 b 中出现的数，然后枚举 1 到 1000，首先如果是倍数就直接 pass，然后再看是否包含 set 中的数

代码展开目录

package baidu;
import java.util.*;
public class Main {
    static Set<Integer> s = new HashSet<Integer>();
    public static boolean check(int i,int a,int b) {
        if(i % a == 0 || i % b == 0)
            return true;
        return false;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while((T--) != 0) {
            s.clear();
            int ans = 0;
            int a = cin.nextInt();
            int b = cin.nextInt();
            int a1 = a;
            int b1 = b;
            while(a1 != 0) {
                s.add(a1 % 10);
                a1 /= 10;
            }
            while(b1 != 0) {
                s.add(b1 % 10);
                b1 /= 10;
            }
            for(int i = 1;i <= 1000;i++) {
                if(check(i,a,b)) {
                    continue;
                } else {
                    int t = i;
                    boolean flag = false;
                    while(t != 0) {
                        if(s.contains(t % 10)) {
                            flag = true;
                            break;
                        }
                        t /= 10;
                    }
                    if(flag)
                        continue;
                    ans++;
                }
                    
            }
            System.out.println(ans);
        }
    }
}

J. 闯关的 lulu展开目录

思路展开目录

这很明显是一个找规律的题，每次下一层一定会拿到一个 0，但是为什么有的层没有 0 呢，是因为 0 “进位” 了

规律：
2个0变成1个1，3个1变成1个2，4个2变成1个3
奇数层多1个0，偶数层多3个0（1和0和1和1）
1 0
2 0000 -> 11
3 00000 -> 110
4 00000000 -> 1111 -> 21
5 000000000 -> 11110 -> 210
6 000000000000 -> 111111 -> 22
7 0000000000000 -> 1111110 -> 220

代码展开目录

package baidu;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        while((T--) != 0) {
            int[] num = new int[100000];
            int n = cin.nextInt();
            String c;
            if(n % 2 == 0) {//偶数层
                num[0] = 0;
                num[1] = n;
            } else {
                num[0] = 1;
                num[1] = n - 1;
            }
            int k = 3;
            int p = 1;
            while(num[p] != 0) {
                num[p + 1] = num[p] / k;
                num[p] = num[p] % k;
                p++;k++;
            }
            for(int i = p - 1;i >= 0;i--) 
                if(num[i] > 0) 
                    for(int j = 0;j < num[i];j++) 
                        System.out.print(i);
            System.out.println();
        }
    }
}