T1简单没套路，T3 a不完。。所以只有T2和T4
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/** * 第二题 * 给定一个m*n的由0 1组成的矩阵。每个1代表一个士兵 * 上下左右相连的兵可以组成一个团 * 现在可以移动一个士兵的位置，可以把他从任何位置移动到任何另一个位置 * 问，能组成的最大团的士兵数。 * 样例 4 4 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1 8 * * 这题是考bfs的。。。利用bfs将士兵组成团，然后对于每个团进行编号。 * 在没有士兵位置的地方，计算临近四个位置所在的团的人数之和。就是将士兵移到这个位置所组成的最大团的人数。 * 如果人数和最大团相同，那么这个士兵就是从这几个团中移到这里的，否则就是从其他团移到这里，这时就要加1构成最大值。 * * *记住不能胡乱粘贴。。。因不注意修改条件直接复制粘贴导致结果总是1 。。。debug到笔试结束，痛苦。。。 */
public class T2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
Node arr[][] = new Node[n][m];
boolean use[][] = new boolean[n][m];
int num1 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
arr[i][j] = new Node(i, j, sc.nextInt());
if (arr[i][j].data == 1) {
num1++;
}
}
}
int zln = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j].data == 1 && use[i][j] == false) {
Queue<Node> q = new LinkedList<Node>();
q.add(arr[i][j]);
use[i][j] = true;
while (!q.isEmpty()) {
Node te = q.poll();
te.zl = zln;
if (te.i - 1 >= 0 && !use[te.i - 1][te.j] && arr[te.i - 1][te.j].data == 1) {
q.add(arr[te.i - 1][te.j]);
use[te.i - 1][te.j] = true;
}
if (te.i + 1 < n && !use[te.i + 1][te.j] && arr[te.i + 1][te.j].data == 1) {
q.add(arr[te.i + 1][te.j]);
use[te.i + 1][te.j] = true;
}
if (te.j - 1 >= 0 && !use[te.i][te.j - 1] && arr[te.i][te.j - 1].data == 1) {
q.add(arr[te.i][te.j - 1]);
use[te.i][te.j - 1] = true;
}
if (te.j + 1 < m && !use[te.i][te.j + 1] && arr[te.i][te.j + 1].data == 1) {
q.add(arr[te.i][te.j + 1]);
use[te.i][te.j + 1] = true;
}
}
zln++;
}
}
}
int ans[] = new int[zln];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j].data != 0)
ans[arr[i][j].zl]++;
}
}
int out = 0;
HashSet<Integer> hs = new HashSet<Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int teout = 0;
if (arr[i][j].data == 0) {
if (i - 1 >= 0 && arr[i - 1][j].data == 1) {
hs.add(arr[i - 1][j].zl);
}
if (i + 1 < n && arr[i + 1][j].data == 1) {
hs.add(arr[i + 1][j].zl);
}
if (j - 1 >= 0 && arr[i][j - 1].data == 1) {
hs.add(arr[i][j - 1].zl);
}
if (j + 1 < m && arr[i][j + 1].data == 1) {
hs.add(arr[i][j + 1].zl);
}
}
for (Integer integer : hs) {
teout += ans[integer];
}
hs.clear();
if (teout != num1) {
teout++;
}
out = Math.max(teout, out);
}
}
System.out.println(out);
}
}
class Node {
int data;
int zl;
int i;
int j;
public Node() {
}
public Node(int i, int j, int data) {
this.i = i;
this.j = j;
this.data = data;
}
}
import java.util.HashSet;
import java.util.Scanner;
/** * 第四题 * 给定一个数n(n<1000000000) 和 一个数组a[m] m (1<=m<=10,1<=a[i]<=20) * 如果n对于一个数 ai有n%ai==0,则认为两个数相关。 * 问在 1 - n中有多少个相关 * 样例 10 2 2 3 5 * 这题是考容斥原理的题。当然要提前处理一下数值，不能有倍数关系。 * 去除倍数关系之后进行计算值就可 */
public class T4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
int m = sc.nextInt();
HashSet<Integer> hs = new HashSet<Integer>();
long ans = 0;
for(int i = 0;i < m; i++) {
hs.add(sc.nextInt());
}
int arr[] = new int[hs.size()];
int temp = 0;
for (Integer integer : hs) {
arr[temp++] = integer;
}
for(int i = 0;i<arr.length;i++) {
for(int j = i+1;j<arr.length;j++) {
if(Math.max(arr[i], arr[j])%Math.min(arr[i], arr[j])==0) {
hs.remove(Math.max(arr[i], arr[j]));
}
}
}
arr = new int[hs.size()];
temp = 0;
for (Integer integer : hs) {
arr[temp++] = integer;
}
for(int i = 1;i<1<<arr.length;i++) {
int num = 0;
long test = 1;
for(int t = i,j=0;t!=0;t>>=1,j++) {
if((t&1)!=0) {
num++;
test *= arr[j];
}
}
if((num&1)==0) {
ans-=n/test;
}else {
ans+=n/test;
}
}
System.out.println(ans);
}
static int gcd(int a, int b) {
if(b==0) {
return a;
}else {
return gcd(b,a%b);
}
}
}
京公网安备 11010502036488号