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();
}
}
}