报数游戏
import java.util.Scanner;
//分析：
//20和24的最小公倍数是120
//题目给出了前10个数，发现第10个数是120，说明每10个数出现一个公倍数
//第20个数出现 120*2
//第30个数出现 120*3
//...
//第202420242020个数出现 120*20242024202
//第202420242024个数出现 120*20242024202+48
//每10个是一轮 每一轮的数之间相差相同
public class Main {
public static void main(String[] args) {
long a=20242024202l*120;
System.out.println(48+a);
}
}
类斐波那契循环数
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
//分析：
//从1e7开始从大到小遍历 用check方法来检查是否是目标数
//主要看check方法怎么写 用到了队列来维护n个数的数列
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int test=10000000;
for(int i=test;i>=197;i--){
//检查i是不是斐波那契循环数
if(check(i)){
System.out.println(i);
return;
}
}
System.out.println(197);
scan.close();
}
//检查n是不是斐波那契环数
static boolean check(int n){
//记录n的值
int memo=n;
//将n从地位开始进栈
Stack<Integer> stack=new Stack();
while(n!=0){
stack.add(n%10);
n=n/10;
}
//队列来维护大小为sz的数列 sz就是几位数
Queue<Integer> queue=new LinkedList();
int sum=0;//维护队列中sz个元素的总和
while(!stack.isEmpty()){
int poll=stack.pop();
queue.add(poll);
sum+=poll;
}
int sz=queue.size();//几位数
while(true){
int cur=sum;
if(cur>memo){
return false;
}
if(cur==memo){
return true;
}
//太小了 把cur入队列 队列出一个
int poll=queue.poll();
sum=sum-poll+cur;
queue.add(cur);
}
}
}
scan.hasNext() 方法的作用是检查输入源中是否还有下一个。
分布式队列
import java.util.LinkedList;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static LinkedList<Integer>[] arr;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
arr=new LinkedList[n];//[0,n-1]条队列
for(int i=0;i<n;i++) {
arr[i]=new LinkedList<Integer>();
}
while(scan.hasNext()) {
String s=scan.next();
switch (s) {
case "add":
int num=scan.nextInt();
add(num);
break;
case "sync":
num=scan.nextInt();
sync(num);//同步num队列
break;
case "query":
int res=check();//检查队列中最小的个数
System.out.println(res);
break;
}
}
}
private static int check() {
// TODO Auto-generated method stub
int min=Integer.MAX_VALUE;
for(int i=0;i<arr.length;i++) {
min=Math.min(min,arr[i].size());
}
return min;
}
private static void sync(int num) {
// TODO Auto-generated method stub
int sz=arr[num].size();
if(sz>=arr[0].size()) {
return;
}
int get=arr[0].get(sz);
arr[num].add(sz, get);
}
private static void add( int num) {
// TODO Auto-generated method stub
arr[0].add(num);
}
}
食堂
思路：目的是座位坐得越满越好，首先考虑满座的情况，然后考虑空一座 ，接着空两座，空三座等等。在考虑满座的情况时也要注意顺序！ 先选择拼接人数少的。
import java.util.ArrayList;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
//暴力枚举
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int t=scan.nextInt();
while(t--!=0) {
int a2=scan.nextInt();
int a3=scan.nextInt();
int a4=scan.nextInt();
int b4=scan.nextInt();
int b6=scan.nextInt();
int meet=0;
//满座 a4-->b4
while(a4>=1&&b4>=1){
meet+=4;
a4--;
b4--;
}
//满座 a3+a3-->b6
while(a3>=2&&b6>=1){
meet+=6;
a3-=2;
b6--;
}
//满座 a4+a2-->b6
while(a4>=1&&a2>=1&&b6>=1){
meet+=6;
a2--;
a4--;
b6--;
}
//满座 a2+a2-->b4
while(a2>=2&&b4>=1){
meet+=4;
a2-=2;
b4--;
}
//满座 a2+a2+a2-->b6
while(a2>=3&&b6>=1){
meet+=6;
a2-=3;
b6--;
}
//空一座 a2+a3-->b6
while(a2>=1&&a3>=1&&b6>=1){
meet+=5;
a2--;
a3--;
b6--;
}
//空一座 a3-->b4
while(a3>=1&&b4>=1){
meet+=3;
a3--;
b4--;
}
//空两座 a2+a2-->b6
while(a2>=2&&b6>=1){
meet+=4;
a2-=2;
b6--;
}
//空两座 a4-->b6
while(a4>=1&&b6>=1){
meet+=4;
a4--;
b6--;
}
//空两座 a2-->b4
while(a2>=1&&b4>=1){
meet+=2;
a2--;
b4--;
}
//空三座 a3-->b6
while(a3>=1&&b6>=1){
meet+=3;
a3--;
b6--;
}
//空四座 a2-->b6
while(a2>=1&&b6>=1){
meet+=2;
a2--;
b6--;
}
System.out.println(meet);
}
scan.close();
}
}
最优分组
分析：
一共有n只，每个小组k只，所以一共有n/k 个小组
有病毒的概率是p 没有病毒的概率就是1-p
一个小组没有病毒的概率是(1-p)^ k,有病毒的概率是1-(1-p)^k
一共有n/k个小组 我们知道：有毒的小组数量=总小组数量 * 一个小组有毒的概率
这些小组中有病毒的小组有(n/k) * (1-p)^k 个
这些小组中没有病毒的个数是(n/k) * (1-(1-p)^k) 个
测试剂的期望=(n/k) * (1-p)^k + (n/k) * (1-(1-p)^k) * (k+1)
在上面公式中n和p已知的,k在变,所以我们枚举k的取值记录最小值
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
double p=scan.nextDouble();
double q=1-p;//没毒的概率
int kMax=n;
int res=Integer.MAX_VALUE;//记录最小的k
double memoS=Double.MAX_VALUE;
for(int k=1;k<=kMax;k++) {
if(n%k!=0) {
continue;
}
int sz=n/k;//小组数量
double S=0;
if(k==1){//小组一人
S=Math.pow(q, k)*sz+(1-Math.pow(q, k))*(k)*sz;//期望值为S
}else{
S=Math.pow(q, k)*sz+(1-Math.pow(q, k))*(k+1)*sz;//期望值为S
}
if(S<memoS) {
res=k;
memoS=S;
}
}
System.out.println(res);
scan.close();
}
}
星际旅行
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();//n个星球
int m=scan.nextInt();//m个门
int q=scan.nextInt();//q个盲盒
LinkedList<Integer>[] graph=new LinkedList[n+1];
for(int i=0;i<=n;i++) {
graph[i]=new LinkedList<>();
}
//创建无向图
for(int i=0;i<m;i++){
int a=scan.nextInt();
int b=scan.nextInt();
graph[a].add(b);
graph[b].add(a);
}
int count=0;//记录可以到达的星球个数
for(int i=0;i<q;i++){
int x=scan.nextInt();//起点位置
int y=scan.nextInt();//最大步数
//bfs遍历 从x节点遍历y层遇到的所有节点个数
count += bfs(graph,x,y);
}
double res= count*1.0/q;
System.out.printf("%.2f",res);
scan.close();
}
private static int bfs(LinkedList<Integer>[] graph, int start, int steps) {
Queue<Integer> queue=new LinkedList<>();
int count=0;//数一数入队列的节点（星系）
int sz=graph.length;//个数
int[]visit=new int[sz];//防止重复计数
Arrays.fill(visit, -1);//-1代表没有访问 ，1表示访问了
queue.add(start);
count++;
visit[start]=1;
while(!queue.isEmpty()) {
int nums=queue.size();
if(steps<=0){
break;
}
for(int i=0;i<nums;i++) {
int cur=queue.poll();
for(int neibor:graph[cur]) {
if(visit[neibor]==-1) {//没有访问的星球
queue.add(neibor);
visit[neibor]=1;
count++;
}
}
}
steps--;
}
return count;
}
}