文章目录

• • 1.买不到的数目（完全背包👍）
  • • 结论👍👍👍
  • 2.蚂蚁感冒（数学）

1.买不到的数目（完全背包👍）

思路：其实题意就是给你两个整数，可以随便用，和完全背包给你若干物品的重量，数量有无数个，去凑差不多，很多题目就是有基础的变形转换而来的，需要多灵活变通。

此题目还学到了一个结论：
给定a,b，若d=gcd(a,b) > 1则一定不能凑出最大数
结论：
如果a,b均是正整数且互质，那么由ax+by，x>=0,y>=0不能凑出的最大数是(a-1)(b-1)-1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (1e6 + 10);static boolean[] dp = new boolean[N];static int n = 0,m = 0,ans = 0;public static void main(String[] args) throws Exception{String[] nm = br.readLine().split(" ");n = Integer.parseInt(nm[0]);m = Integer.parseInt(nm[1]);dp[0] = true;for(int i = 1; i <= 1e6; i++) {if(i - n >= 0) {dp[i] |= dp[i - n];}if(i - m >= 0) {dp[i] |= dp[i - m];}}for(int i =(int) 1e6; i >= 1; i--) {if(!dp[i]) {System.out.println(i);break;}}}
}

完全背包的写法：（有两种物品的重量，凑）

#include 
using namespace std;
const int N = 1e6 + 100;
int dp[N];
int n, m;
int a[3];
int main()
{cin >> n >> m;a[1] = n; a[2] = m;dp[0] = 1;for (int j = 1; j <= 2; j ++) {for (int i = a[j]; i <= 1e6; i ++) {dp[i] |= dp[i-a[j]];}}for (int i = 1e6 ; i >= 1; i --) {if (dp[i] == 0)  {cout <<  i;break;}}
}

下面这个题同样的做法：

结论👍👍👍

：如果a,b均是正整数且互质，那么由ax+by,x>=0,y>=0,不能凑出来的最大数是ab-a-b（（a-1)*(b-1)）

2.蚂蚁感冒（数学）

思路：此题还是很简单的，我们可以看出只要分类讨论一下感冒的蚂蚁的方向和位置即可，如果感冒的蚂蚁方向是-的，那么我们需要首先看一下有没有一个位置比他小，然后然后是正的（为什么要这样呢，如果有的话，我们可以通过这个蚂蚁去感染那些方向也是-的蚂蚁，只有至少存在一个+方向的蚂蚁的时候，其他-方向的蚂蚁才可能被敢染），如果敢染的蚂蚁是+的同理。
❗：（1）如果感冒的蚂蚁是负方向的，我们必须先看是否存在比它位置小，且方向是＋的，否则即使存在位置比它大的-的，也是无法感染的。
（2）注意细节，多想想各种情况就好啦😀

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (100);static int n = 0,m = 0,ans = 0;static int[] a = new int[N];public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[]aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {a[i] = Integer.parseInt(aa[i - 1]);}int p = a[1];if(p < 0) {for(int i = 1; i <= n; i++) {if(Math.abs(a[i]) < Math.abs(p) && a[i] > 0) {ans++;}}for(int i = 1; i <= n; i++) {if(ans != 0) {if(Math.abs(a[i]) > Math.abs(p) && a[i] < 0) {ans++;}}}}else {for(int i = 1; i <= n; i++) {if(Math.abs(a[i]) > p && a[i] < 0) {ans++;}}for(int i = 1; i <= n; i++) {if(ans != 0) {if(a[i] < p && a[i] > 0) {ans++;}}}}System.out.println(ans + 1);}
}