各位如果看到博客内有广告,可以动手点一点,谢谢

MENU

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

July 17, 2018 • Read: 493 • 算法

A.大吉大利,今晚吃鸡——枪械篇

image

思路

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

代码
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.六子冲

image

思路

棋盘上攻击方的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阶汉诺塔变形

image

思路

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

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

那么规律就来了,我们发现每两次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.恋与程序员

image

思路

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

这是一个很明显的搜索问题,用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.大吉大利,今晚吃鸡——跑毒篇

image

思路

模拟就完了,比较重要的一点是什么时候打药,打药的时机要贪心一下,因为打药要耗时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.圆圈

image

思路

规律就是对于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.方块与收纳盒

image

思路

这不就是个简单的爬楼梯问题吗,有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.找数字个数

image

思路

这....也太简单了,首先用个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

image

思路

这很明显是一个找规律的题,每次下一层一定会拿到一个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();
        }
    }
}
Archives Tip
QR Code for this page
Tipping QR Code