1.最少步数【省模拟赛】
问题描述
小蓝要上一个楼梯,楼梯共有 n 级台阶(即小蓝总共要走 nn级)。小蓝每一步可以走 1 级、2 级或 3 级台阶。
请问小蓝至少要多少步才能上到楼梯顶端?
输入格式
输入一行包含一个整数 n。
输出格式
输出一行包含一个整数,表示答案。
样例输入1
9
样例输出1
3
样例输入2
10
样例输出2
4
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
int ans=0;
if(n==0)ans=0;
else if(n<=3)ans=1;
else {
ans+=(n/3);
n=n-(n/3)*3;
ans+=(n/2);
n=n-(n/2)*2;
ans+=n;
}
System.out.println(ans);
}
}
2.赢球票
题目描述
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片(上面写着 1⋯N 的数字),打乱顺序,排成一个圆圈。
你可以从任意一张卡片开始顺时针数数: 1,2,3 ⋯⋯
如果数到的数字刚好和卡片上的数字相同,则把该卡片收入囊中,从下一个卡片重新数数。
直到再无法收获任何卡片,游戏结束。囊中卡片数字的和就是赢得球票的张数。
比如:
卡片排列是:1 2 3
我们从 1 号卡开始数,就把 1 号卡拿走。再从 2 号卡开始,但数的数字无法与卡片对上,很快数字越来越大,不可能再拿走卡片了。因此这次我们只赢得了 1 张球票。
还不算太坏!如果我们开始就傻傻地从 2 或 3 号卡片数起,那就一张卡片都拿不到了。
如果运气好,卡片排列是 2 1 3,那我们可以顺利拿到所有的卡片!
本题的目标:已知顺时针卡片序列,随便你从哪里开始数,求最多能赢多少张球票(就是收入囊中的卡片数字之和)
输入描述
第一行一个整数 N (N≤100),表示卡片数目。
第二行 N 个整数,表示顺时针排列的卡片。
输出描述
输出一行,一个整数,表示最好情况下能赢得多少张球票。
输入输出样例
输入
3
1 2 3
输出
1
AC代码
javascript">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
ArrayList<Integer> a=new ArrayList<>();
int ans=0;
for(int i=0;i<n;i++) {
a.add(scan.nextInt());
}
for(int i=0;i<n;i++) {
ArrayList<Integer> temp=new ArrayList<>(a);
int idx=i,sum=0,num=1;
while(num<=n&&temp.size()!=0) { //数到n或者被取完了
if(temp.get(idx)==num) {
sum+=temp.remove(idx);
num=1;//重新开始数
}else {
idx++;
num++;
}
if(idx==temp.size())idx=0;//数组到末尾,重新置为0
}
ans=Math.max(ans, sum);
}
System.out.println(ans);
}
}
3.拉马车
题目描述
小的时候,你玩过纸牌游戏吗?
有一种叫做"拉马车"的游戏,规则很简单,却很吸引小朋友。
其规则简述如下:
假设参加游戏的小朋友是 A 和 B ,游戏开始的时候,他们得到的随机的纸牌序列如下:
A方:[K,8,X,K,A,2,A,9,5,A]
B方:[2,7,K,5,J,5,Q,6,K,4]
其中的 X表示 "10",我们忽略了纸牌的花色。
从 A 方开始,A、B双方轮流出牌。
当轮到某一方出牌时,他从自己的纸牌队列的头部拿走一张,放到桌上,并且压在最上面一张纸牌上(如果有的话)。
此例中,游戏过程:
A出 K,B 出 2,A 出 8,B 出 7,A 出 X,此时桌上的序列为:
K,2,8,7,X
当轮到 B 出牌时,他的牌 K 与桌上的纸牌序列中的 K 相同,则把包括 K 在内的以及两个 K 之间的纸牌都赢回来,放入自己牌的队尾。注意:为了操作方便,放入牌的顺序是与桌上的顺序相反的。
此时,A、B双方的手里牌为:
A 方:[K,A,2,A,9,5,A]
B 方:[5,J,5,Q,6,K,4,K,X,7,8,2,K]
赢牌的一方继续出牌。也就是 B 接着出 5,A 出 K,B 出 J,A 出 A,B 出 5,又赢牌了。此时桌上的序列为:
5,K,J,A,5
此时双方手里牌:
A 方:[2,A,9,5,A]
B 方:[Q,6,K,4,K,X,7,8,2,K,5,A,J,K,5]
注意:更多的时候赢牌的一方并不能把桌上的牌都赢走,而是拿走相同牌点及其中间的部分。但无论如何,都是赢牌的一方继续出牌,有的时候刚一出牌又赢了,也是允许的。
当某一方出掉手里最后一张牌,但无法从桌面上赢取牌时,游戏立即结束。
对于本例的初始手牌情况下,最后 A 会输掉,而 B 最后的手里牌为:
9K2A62KAX58K57KJ5
本题的任务就是已知双方初始牌序,计算游戏结束时,赢的一方手里的牌序。当游戏无法结束时,输出 -1。
输入描述
输入为 2 行,2 个串,分别表示 A、B 双方初始手里的牌序列。我们约定,输入的串的长度不超过 30。
输出描述
输出为 1 行,1 个串,表示 AA 先出牌,最后赢的一方手里的牌序。
输入输出样例
输入
96J5A898QA
6278A7Q973
输出
2J9A7QA6Q6889977
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
StringBuilder a=new StringBuilder(scan.nextLine());
StringBuilder b=new StringBuilder(scan.nextLine());
StringBuilder table=new StringBuilder();
boolean flag=true;// true则a出牌,false则b出牌
int idx=0;
while(a.length()>0&&b.length()>0) {
if(flag) {
idx=table.indexOf(String.valueOf(a.charAt(0)));
// StringBuilder的indexOf方法可返回字符/字符串在字符串中第一次出现的下标,若字符串里有返回下标,若无返回-1
if(idx==-1) {
table.append(a.charAt(0));
a.delete(0, 1);
flag=false;
}else {
win(a,table,idx);// a收牌后继续出牌
}
}else {
idx=table.indexOf(String.valueOf(b.charAt(0)));
if(idx==-1) {
table.append(b.charAt(0));
b.delete(0, 1);
flag=true;
}else {
win(b,table,idx);// a收牌后继续出牌
}
}
}
if(a.length()==0){
System.out.println(b);
}
else {
System.out.println(a);
}
}
public static void win(StringBuilder hand,StringBuilder table,int idx) {
table.append(hand.charAt(0));
hand.delete(0, 1);
StringBuilder temp=new StringBuilder(table.substring(idx));
hand.append(temp.reverse());
table.delete(idx, table.length());
}
}
4.正则问题
题目描述
考虑一种简单的正则表达式:
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是: xxxxxx,长度是 6。
输入描述
一个由 x()| 组成的正则表达式。输入长度不超过 100,保证合法。
输出描述
这个正则表达式能接受的最长字符串的长度。
输入输出样例
输入
((xx|xxx)x|(x|xx))xx
输出
6
AC代码
java">import java.util.*;
class pair{
int x;
int y;
pair(int x,int y){
this.x=x;
this.y=y;
}
}
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
String s=scan.nextLine();
Stack<pair> stack=new Stack<>();
int len=0;
int ans=0;
for(char c:s.toCharArray()) {
if(c=='x') {
len++;
}else if(c=='(') {
stack.push(new pair(len,ans));
len=0;
ans=0;
}else if(c==')') {
pair temp=stack.pop();// 栈先进后出
len=temp.x+Math.max(len, ans);
ans=temp.y;
}else if(c=='|') {
ans=Math.max(ans,len);
len=0;
}
}
System.out.println(Math.max(ans, len));
}
}
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
static int pos=-1;
static String s=null;
public static void main(String[] args) {
s=scan.nextLine();
System.out.println(dfs());
}
private static int dfs() {
int cur=0; //目前x的最大个数
int max=0; //最终x的最大个数
while(pos<s.length()-1) {
pos++;
char c=s.charAt(pos);
if(c=='(') { //进入下一层
cur+=dfs();
}else if(c=='x') {
cur++;
}else if(c=='|') {
max=Math.max(cur, max);
cur=0;
}else {
break; //遇到')',跳出本轮循环
}
}
return Math.max(max, cur);
}
}
5.对局匹配
题目描述
小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分,代表他的围棋水平。
小明发现网站的自动对局系统在匹配对手时,只会将积分差恰好是 K 的两名用户匹配在一起。如果两人分差小于或大于 K,系统都不会将他们匹配。
现在小明知道这个网站总共有 N 名用户,以及他们的积分分别是 A1,A2,⋯AN。
小明想了解最多可能有多少名用户同时在线寻找对手,但是系统却一场对局都匹配不起来(任意两名用户积分差不等于 K)?
输入描述
输入描述
第一行包含两个个整数 N,K。
第二行包含 N 个整数 A1,A2,⋯AN。
其中,1≤N≤10^5,0≤Ai≤10^5,0≤K≤10^5。
输出描述
输出一个整数,代表答案。
输入输出样例
输入
10 0
1 4 2 8 5 7 1 4 2 8
输出
6
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
int k=scan.nextInt();
int[] a=new int[n];
int count=0;
for(int i=0;i<n;i++)a[i]=scan.nextInt();
Arrays.sort(a); // 从小到大
for(int i=0,t=0;i<n;i++) {
if(a[i]==-1)continue; // 用户被匹配过,跳过
for(int j=t+1;j<n;j++) {
if(a[j]==-1)continue;
if(Math.abs(a[j]-a[i])==k) {
a[i]=-1; // 将两个用户标记为已匹配
a[j]=-1;
t=j;
count++; // 匹配成功,匹配对数加一
}else if(a[j]-a[i]>k)break;
}
}
System.out.println(n-count); // 输出无法匹配的用户数目
}
}
6.分考场(DFS)
题目描述
n 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求是少需要分几个考场才能满足条件。
输入描述
输入格式:
第一行,一个整数 n (1≤n≤100),表示参加考试的人数。
第二行,一个整数 m,表示接下来有 m 行数据。
以下 m 行每行的格式为:两个整数 a,b,用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。
输出描述
输出一行一个整数,表示最少分几个考场。
输入输出样例
输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
输出
4
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
static int sum=110; //最多可以安排的教室
static int[][] nums=new int[sum][sum]; //安排座位nums[i][j]:第i考场的j座位
static boolean rela[][]=new boolean[sum][sum]; //标记相互认识的
static int n=scan.nextInt();
static int m=scan.nextInt();
public static void main(String[] args) {
for(int i=1;i<=m;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
// a和b不能再同一个考场
rela[a][b]=true;
rela[b][a]=true;
}
dfs(1,1); //从第一个学生,第一个考场安排
System.out.println(sum);
}
public static void dfs(int x,int k) { //x代表第几个学生,k代表第几个考场
if(k>=sum)return; //要求最少考场数目,sum为当前的答案,如果比这个值还大就不要
if(x>n) {//学生安排完,更新
sum=Math.min(sum, k);
return;
}
for(int i=1;i<=k;i++) {
int j=0; //j为座位号
while(nums[i][j]!=0&&!rela[x][nums[i][j]]) {
j++;//如果该考场没有认识的
}
//跳出循环
if(nums[i][j]==0) {//有位置
nums[i][j]=x; //x可以进行i考场
dfs(x+1,k); //k不变
nums[i][j]=0;
}
}
//遍历完所有已存在的考场,发现都有认识的人,就要重新再开一个考场
nums[k+1][0]=x;
dfs(x+1,k+1);
nums[k+1][0]=0;
}
}
7.合根植物
题目描述
w 星球的一个种植园,被分成 m×n个小格子(东西方向 m 行,南北方向 n 列)。每个格子里种了一株合根植物。
这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象,你能说出这个园中一共有多少株合根植物吗?
输入描述
第一行,两个整数 m,n,用空格分开,表示格子的行数、列数(1≤m,n≤1000)。
接下来一行,一个整数 k (0≤k≤10^5 ),表示下面还有 k 行数据。
接下来 k 行,每行两个整数 a,b,表示编号为 a 的小格子和编号为 b 的小格子合根了。
格子的编号一行一行,从上到下,从左到右编号。
比如:5×4 的小格子,编号:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
输出描述
输出植物数量。
输入输出样例
输入
5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17
输出
5
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
static int m=scan.nextInt();
static int n=scan.nextInt();
static int k=scan.nextInt();
static int[] p=new int[n*m+10];
public static int find(int x) {
if(x==p[x])return x;
else return p[x]=find(p[x]);
}
public static void main(String[] args) {
for(int i=1;i<=n*m;i++) {
p[i]=i;
}
for(int i=1;i<=k;i++) {
int a=scan.nextInt();
int b=scan.nextInt();
int fa=find(a);
int fb=find(b);
if(fa!=fb) {
p[fa]=fb;
}
}
Set<Integer>s=new HashSet<>();
for(int i=1;i<=n*m;i++) {
int fa=find(i);
s.add(fa);
}
System.out.println(s.size());
}
}
8.四平方和
题目描述
四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去,就正好可以表示为 4 个数的平方和。
对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对 4 个数排序:
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列,最后输出第一个表示法。
输入描述
程序输入为一个正整数 N(N<5×10^6)。
输出描述
要求输出 4 个非负整数,按从小到大排序,中间用空格分开
输入输出样例
输入
12
输出
0 2 2 2
AC代码
(1)通过87%样例
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
ArrayList<Integer> a=new ArrayList<>();
for(int i=0;i<=Math.sqrt(n);i++) { //只需在1到根号n下找
a.add(i); //0、1、2....
}
for(int i1=0;i1<=a.size();i1++) {
for(int i2=0;i2<=a.size();i2++) {
for(int i3=0;i3<=a.size();i3++) {
for(int i4=0;i4<=a.size();i4++) {
if(n==i1*i1+i2*i2+i3*i3+i4*i4) {
System.out.println(i1+" "+i2+" "+i3+" "+i4);
return;
}
}
}
}
}
}
}
(2)过100%样例(为了防止重复,只有最外层循环是从0开始的)
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
ArrayList<Integer> a=new ArrayList<>();
for(int i=0;i<=Math.sqrt(n);i++) {
a.add(i); //0、1、2....
}
for(int i1=0;i1<=a.size();i1++) {
for(int i2=i1;i2<=a.size();i2++) {
for(int i3=i2;i3<=a.size();i3++) {
for(int i4=i3;i4<=a.size();i4++) {
if(n==i1*i1+i2*i2+i3*i3+i4*i4) {
System.out.println(i1+" "+i2+" "+i3+" "+i4);
return;
}
}
}
}
}
}
}
9.数字诗意
问题描述
在诗人的眼中,数字是生活的韵律,也是诗意的表达。
小蓝,当代顶级诗人与数学家,被赋予了"数学诗人"的美誉。他擅长将冰冷的数字与抽象的诗意相融合,并用优雅的文字将数学之美展现于纸上。
某日,小蓝静坐书桌前,目光所及,展现着 n 个数字,它们依次为 a1,a2,…,an,熠熠生辉。小蓝悟到,如果一个数能够以若干个(至少两个)连续的正整数相加表示,那么它就蕴含诗意。例如,数字 6 就蕴含诗意,因为它可以表示为 1+2+3。而 8 则缺乏诗意,因为它无法用连续的正整数相加表示。
小蓝希望他面前的所有数字都蕴含诗意,为此,他决定从这 n 个数字中删除一部分。请问,小蓝需要删除多少个数字,才能使剩下的数字全部蕴含诗意?
输入格式
第一行包含一个整数 n,表示展示的数字个数。
第二行包含 n 个整数 a1,a2,…,an,表示展示的数字。
输出格式
输出一个整数,表示小蓝需要删除的数字个数,以使剩下的数字全部蕴含诗意。
样例输入
3
3 6 8
样例输出
1
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
// 奇数3=1+2,5=2+3,7=3+4,...,29=14+15...都成立
// 偶数4=2+2=1+3不行,6=1+2+3行,8=1+2+3+2=4+4不行,10=1+2+3+4行
// 偶数得到规律:偶数/2%2==0不行,偶数/2%2==1行
// 因此可以得到3、5、6、7、9、10、、、行,2的幂不行
int n=scan.nextInt();
int ans=0; //不满足的
for(int i=1;i<=n;i++) {
Long a=scan.nextLong();
if(a<3)ans++;
else { // 2的幂如8:8/2=4,4/2=2,2/2=1
while((a%2==0)&&a>1) {
a/=2;
}
if(a==1)ans++;
}
}
System.out.println(ans);
}
}
10.商品库存管理(差分数组)
问题描述
在库存管理系统中,跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品,这些商品根据类别和规格被有序地分类并编号,编号范围从 1 至 n。初始时,每种商品的库存量均为 0。
为了高效地监控和调整库存量,小蓝的管理团队设计了 m 个操作,每个操作涉及到一个特定的商品区间,即一段连续的商品编号范围(例如区间 [L,R])。执行这些操作时,区间内每种商品的库存量都将增加 1。然而,在某些情况下,管理团队可能会决定不执行某些操作,使得这些操作涉及的商品区间内的库存量不会发生改变,维持原有的状态。
现在,管理团队需要一个评估机制,来确定如果某个操作未被执行,那么最终会有多少种商品的库存量为 0。对此,请你为管理团队计算出,每个操作未执行时,库存量为 0 的商品的种类数。
输入格式
第一行包含两个整数 n 和 m,分别表示商品的种类数和操作的个数。
接下来的 m 行,每行包含两个整数 L 和 R,表示一个操作涉及的商品区间。
输出格式
输出共 m 行,每行一个整数,第 i 行的整数表示如果不执行第 i 个操作,则最终库存量为 0 的商品种类数。
样例输入
5 3
1 2
2 4
3 5
样例输出
1
0
1
样例说明
考虑不执行每个操作时,其余操作对商品库存的综合影响:
-
不执行操作 1:剩余的操作是操作 2(影响区间 [2,4])和操作 3(影响区间 [3,5])。执行这两个操作后,商品库存序列变为 [0,1,2,2,1]。在这种情况下,只有编号为 1 的商品的库存量为 0。因此,库存量为 0 的商品种类数为 1。
-
不执行操作 2:剩余的操作是操作 1(影响区间 [1,2])和操作 3(影响区间 [3,5])。执行这两个操作后,商品库存序列变为 [1,1,1,1,1]。在这种情况下,所有商品的库存量都不为0。因此,库存量为 0 的商品种类数为 0。
-
不执行操作 3:剩余的操作是操作 1(影响区间 [1,2])和操作 2(影响区间 [2,4])。执行这两个操作后,商品库存序列变为 [1,2,1,1,0]。在这种情况下,只有编号为 5 的商品的库存量为 0。因此,库存量为0 的商品种类数为 1。
AC代码
java">import java.util.*;
public class exercise1 {
static Scanner scan=new Scanner(System.in);
public static void main(String[] args) {
int n=scan.nextInt();
int m=scan.nextInt();
int[] d=new int[n+2]; //差分数组
int[][] op=new int[m+1][2];
for(int i=1;i<=m;i++) {
int l=scan.nextInt();
int r=scan.nextInt();
op[i][0]=l;
op[i][1]=r;
d[l]++;
d[r+1]--;
}
for(int i=1;i<=n;i++) {
d[i]+=d[i-1];// 变成原来的数组
}
int ans1=0;
for(int i=1;i<=n;i++) {
if(d[i]==0)ans1++;
}
for(int i=1;i<=m;i++) {
int l=op[i][0];
int r=op[i][1];
int ans2=0;
for(int j=l;j<=r;j++) {
if(d[j]==1)ans2++;
}
System.out.println(ans1+ans2);
}
}
}