1.黛玉泡茶【算法赛】

问题描述

话说林黛玉闲来无事，打算在潇湘馆摆个茶局，邀上宝钗、探春她们一起品茗赏花。黛玉素来讲究，用的茶杯也各有不同，大的小的，高的矮的，煞是好看。这不，她从柜子里拿出了 NN 只茶杯，这 NN 只茶杯的容量分别是 C1,C2,…,CNC1​,C2​,…,CN​ 。为了泡茶，黛玉还特意准备了一个容量为 MM 的茶壶。

天气炎热，姐妹们都想着多喝点，所以至少得斟满 KK 杯茶才够大家喝。可是这茶壶来回取水太麻烦了，黛玉想尽量少跑几趟。

对此，请你帮黛玉算算，她最少需要用茶壶取多少次水，才能斟满至少 KK 杯茶呢？

输入描述

第一行包含三个整数 NN、MM 和 KK（1≤K≤N≤1031≤K≤N≤103，1≤M≤1031≤M≤103），分别表示茶杯的数量、茶壶的容量以及黛玉想要斟满的茶杯数量。

第二行包含 NN 个整数 C1,C2,…,CNC1​,C2​,…,CN​（1≤Ci≤1031≤Ci​≤103），表示每个茶杯的容量。

输出描述

输出一个整数，表示黛玉最少需要用茶壶取水的次数。

样例输入

2 3 1
5 7

样例输出

2

AC代码

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int k=scan.nextInt();int[] c=new int[n];for(int i=0;i<n;i++)c[i]=scan.nextInt();Arrays.sort(c);int sum=0;for(int i=0;i<k;i++)sum+=c[i];int ans=0;ans=(int)Math.ceil((sum*1.0)/m);System.out.println(ans);scan.close();}
}

 2.整数对F1【算法赛】

问题描述

输入格式

第一行包含一个整数 NN（1≤N≤1051≤N≤105），表示数列的长度。

第二行包含 NN 个整数 A1,A2,⋯,ANA1​,A2​,⋯,AN​（−105≤Ai≤105−105≤Ai​≤105）。

输出格式

输出一个整数，表示所有 F1(l,r)F1(l,r) 的总和。

样例输入

2
1 2

 

样例输出

6

AC代码

每个元素的贡献：元素 a[i] 对总和的贡献是它的值乘以它在所有区间中出现的次数。元素 a[i] 出现在所有以 i 为左端点和右端点的区间中。因此，它的贡献是： a[i]×i×(n−i+1)。其中，i 是区间的左端点，n−i+1 是区间的右端点。

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();}Long sum=0L;for(int i=1;i<=n;i++) {sum+=(long)a[i]*i*(n-i+1);}System.out.println(sum);scan.close();}
}

 3.购物车里的宝贝【算法赛】

问题描述

双十一前夕，小蓝的购物车里已经塞满了 nn 件宝贝，价格分别是 a1,a2,…,ana1​,a2​,…,an​。为了在双十一当天顺利付款，小蓝决定把这些宝贝分成两批下单。

只是，小蓝最近学习了“异或运算”，她希望这两批订单里，宝贝价格的异或和都完全一样！

具体来说，她要将这 nn 个宝贝分成两个集合 S1,S2S1​,S2​，使得集合 S1S1​ 中所有元素（宝贝价格）的异或和等于集合 S2S2​ 中所有元素（宝贝价格）的异或和。

现在，请你帮小蓝判断一下，她购物车里的宝贝能否这样划分？如果可以，输出 YES；否则，就输出 NO。

输入格式

第一行包含一个整数 nn（2≤n≤1052≤n≤105），表示有 nn 件宝贝。

第二行包含 nn 个整数 a1,a2,…,ana1​,a2​,…,an​（1≤ai≤1051≤ai​≤105），分别表示 nn 件宝贝的价格。

输出格式

输出一行，包含一个字符串 YES 或 NO。

样例输入

3
1 2 3

样例输出

YES

AC代码

如果满足两个集合的异或和相等，那么再异或一下，一定等于0。因此，可以直接异或所有元素，当最后结果为0时，输出YES，否则输出NO。

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];int ans=0;for(int i=0;i<n;i++) {a[i]=scan.nextInt();ans^=a[i];}if(ans==0) {//肯定可以分成两个异或结果相同的集合System.out.println("YES");}else {System.out.println("NO");}scan.close();}
}

4.路径之谜

题目描述

小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n×nn×n 个方格。如下图所示。

按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 nn 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入描述

第一行一个整数 NN (0≤N≤200≤N≤20)，表示地面有 N×NN×N 个方格。

第二行 NN 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 NN 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出描述

输出一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯⋯

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

AC代码

import java.util.*;
public class exercise1{static Scanner scan = new Scanner(System.in);static int n=scan.nextInt();static int[] dx= {0,1,0,-1};static int[] dy= {1,0,-1,0};static int[] b=new int[n];static int[] x=new int[n];static int[] route=new int[n*n];static int[][] v=new int[n][n];public static boolean pd() {for(int i=0;i<n;i++) {if(b[i]!=0||x[i]!=0)return false;}return true;}public static void dfs(int sx,int sy,int step) {v[sx][sy]=1;route[step]=sx*n+sy;b[sy]--;x[sx]--;if(sx==n-1&&sy==n-1&&pd()) {for(int i=0;i<=step;i++) {System.out.print(route[i]+" ");}System.out.println();return;}for(int i=0;i<4;i++) {int xx=sx+dx[i];int yy=sy+dy[i];if(xx>=0&&xx<n&&yy>=0&&yy<n&&v[xx][yy]!=1) {if(b[yy]>0&&x[xx]>0) {v[xx][yy]=1;dfs(xx,yy,step+1);v[xx][yy]=0;}}}b[sy]++;x[sx]++;}public static void main(String[] args) {for(int i=0;i<n;i++)b[i]=scan.nextInt();for(int i=0;i<n;i++)x[i]=scan.nextInt();dfs(0,0,0);}
}

 5.Excel地址

题目描述

Excel 单元格的地址表示很有趣，它使用字母来表示列号。

比如，

A 表示第 1 列，

B 表示第 2 列，

Z 表示第 26 列，

AA 表示第 27 列，

AB 表示第 28 列，

BA 表示第 53 列，

⋯⋯

当然 Excel 的最大列号是有限度的，所以转换起来不难。

如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？

本题目即是要求对输入的数字, 输出其对应的 Excel 地址表示方式。

输入描述

输入一个整数 nn，其范围 [1,2147483647]。

输出描述

输出 nn 对应的 Excel 地址表示方式。

输入输出样例

输入

26

输出

Z

AC代码

import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();StringBuilder ans=new StringBuilder();while(n>0) {n--;int c=n%26;ans.append((char)('A'+c));n/=26;}System.out.println(ans.reverse());}
}

 6.k倍区间

题目描述

给定一个长度为 NN 的数列，A1,A2,⋯ANA1​,A2​,⋯AN​，如果其中一段连续的子序列 Ai,Ai+1,⋯AjAi​,Ai​+1,⋯Aj​ ( i≤ji≤j ) 之和是 KK 的倍数，我们就称这个区间 [i,j][i,j] 是 K 倍区间。

你能求出数列中总共有多少个 KK 倍区间吗？

输入描述

第一行包含两个整数 NN 和 KK( 1≤N,K≤1051≤N,K≤105 )。

以下 N 行每行包含一个整数 AiAi​ ( 1≤Ai≤1051≤Ai​≤105 )

输出描述

输出一个整数，代表 K 倍区间的数目。

输入输出样例

输入

5 2
1
2
3
4
5

 

输出

6

AC代码 

（1）暴力（过30%样例）

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+1];int[] pre=new int[n+1];for(int i=1;i<=n;i++) {a[i]=scan.nextInt();pre[i]=pre[i-1]+a[i];}int ans=0;for(int i=1;i<=n;i++) {for(int j=i;j<=n;j++) {if((pre[j]-pre[i-1])%k==0)ans++;}}System.out.println(ans);}
}

（2）利用余数为0，100%过样例

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+1];long[] v=new long[k];long sum=0;for(int i=1;i<=n;i++) {a[i]=scan.nextInt();sum+=a[i];v[(int)(sum%k)]++;//余数存起来}long ans=0;ans+=v[0];//k倍去区间模k为0for(int i=0;i<k;i++) {//v[i]表示以i为前缀和模k余数的个数，任选2个相减即为区间和且模k为0ans+=(v[i]*(v[i]-1))/2;}System.out.println(ans);}
}

7.分巧克力

问题描述

儿童节那天有 KK 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 NN 块巧克力，其中第 ii 块是 Hi×WiHi​×Wi 的方格组成的长方形。为了公平起见，

小明需要从这 NN 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数;

2. 大小相同;

例如一块 6×56×5 的巧克力可以切出 66 块 2×22×2 的巧克力或者 22 块 3×33×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入描述

第一行包含两个整数 N,KN,K (1≤N,K≤1051≤N,K≤105)。

以下 N 行每行包含两个整数 Hi,WiHi​,Wi​ (1≤Hi,Wi≤1051≤Hi​,Wi​≤105)。

输入保证每位小朋友至少能获得一块 1x1 的巧克力。

输出描述

输出切出的正方形巧克力最大可能的边长。

输入输出样例

输入

2 10
6 5
5 6

输出

2

AC代码

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[] h=new int[n];int[] w=new int[n];int l=1;int r=100000;for(int i=0;i<n;i++) {h[i]=scan.nextInt();w[i]=scan.nextInt();}int ans=0;while(l<=r) {int mid=(l+r)/2;int sum=0;for(int i=0;i<n;i++) {sum+=(h[i]/mid)*(w[i]/mid);}if(sum>=k) {ans=Math.max(ans,mid);//最大边长l=mid+1;}else{r=mid-1;}}System.out.println(ans);}
}

 8.九宫幻方

题目描述

小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将 1~9 不重复的填入一个 3*3 的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀："二四为肩，六八为足，左三右七，戴九履一，五居其中"，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

4 9 2

3 5 7

8 1 6

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。

而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序。

输入描述

输入仅包含单组测试数据。

每组测试数据为一个 3*3 的矩阵，其中为 0 的部分表示被小明抹去的部分。

给出的矩阵至少能还原出一组可行的三阶幻方。

输出描述

如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出"Too Many"（不包含引号）。

输入输出样例

输入

0 7 2
0 5 0
0 3 0

输出

6 7 2
1 5 9
8 3 4

 AC代码

import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);static int[] arr=new int[10];static boolean[] v=new boolean[10];static int[] res=new int[10];static int[] m=new int[10];static int ans=0;public static void dfs(int idx) {if(idx==10) {int a=m[1]+m[2]+m[3];int b=m[4]+m[5]+m[6];int c=m[7]+m[8]+m[9];int d=m[1]+m[4]+m[7];int e=m[2]+m[5]+m[8];int f=m[3]+m[6]+m[9];int g=m[1]+m[5]+m[9];int h=m[3]+m[5]+m[7];if(a==b&&b==c&&c==d&&d==e&&e==f&&f==g&&g==h) {boolean flag=true;for(int i=1;i<10;i++) {if(arr[i]!=0&&arr[i]!=m[i]) { // 不是0的要相等才可以flag=false; // 不然就是非法的break;}}if(flag) { // 合法则贡献答案ans++;for(int i=1;i<10;i++) {res[i]=m[i];}}}return;}for(int i=1;i<10;i++) {if(v[i])continue;v[i]=true;m[idx]=i;dfs(idx+1);v[i]=false;}}public static void main(String[] args) {for(int i=1;i<10;i++) {arr[i]=scan.nextInt();}dfs(1);if(ans>1)System.out.println("Too Many");else {for(int i=1;i<10;i++) {System.out.print(res[i]+" ");if(i%3==0)System.out.println();}}}
}

9.青蛙跳杯子（BFS）

题目描述

XX 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

XX 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

∗WWWBBB∗WWWBBB

其中，WW 字母表示白色青蛙，BB 表示黑色青蛙，∗∗ 表示空杯子。

XX 星的青蛙很有些癖好，它们只做 3 个动作之一：

1. 跳到相邻的空杯子里。

2. 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。

3. 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上图的局面，只要 1 步，就可跳成下图局面：

WWW∗BBBWWW∗BBB

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入描述

输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。

输出描述

输出要求为一个整数，表示至少需要多少步的青蛙跳。

输入输出样例

输入

*WWBB
WWBB*

输出

2

 AC代码

import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);static String start;static String end;static int res=0;static Map<String,Integer> map=new HashMap<>();static int[] d=new int[] {3,2,1,-1,-2,-3};public static void BFS() {Queue<String> q=new LinkedList<String>();q.add(start);while(q.size()!=0) {int siz=q.size();res++;while(siz-- !=0) {String s=q.poll();if(s.equals(end)) {System.out.println(map.get(s));return;}for(int i=0;i<s.length();i++) {char c=s.charAt(i);if(c!='*') { // 有青蛙for(int j=0;j<6;j++) { // 枚举可跳位置int dd=i+d[j];if(dd>=0&&dd<s.length()&&s.charAt(dd)=='*') {// 保证不越界且是空位置StringBuilder sb=new StringBuilder(s);sb.setCharAt(i,'*');sb.setCharAt(dd, c); // 使用StringBuilder方便修改字符String sbs=sb.toString();if(!map.containsKey(sbs)) {map.put(sbs, res);q.add(sbs);}}}}}}}}public static void main(String[] args) {start=scan.nextLine();end=scan.nextLine();BFS();}
}

10.

AC代码

（1）过75%样例

import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static boolean check(int a,int b,int c) {if(a<1960||a>2059)return false;if(b<1||b>12)return false;int[] daysInMonth= {0,31,28,31,30,31,30,31,31,30,31,30,31};if(a%4==0 && (a%100!=0 ||a%400==0)) {  // 判断闰年daysInMonth[2]+=1; // 是闰年则2月为29天}if(c<1||c>daysInMonth[b])return false;return true;}public static void main(String[] args) {String s=scan.nextLine();int a=(s.charAt(0)-'0')*10+(s.charAt(1)-'0');int b=(s.charAt(3)-'0')*10+(s.charAt(4)-'0');int c=(s.charAt(6)-'0')*10+(s.charAt(7)-'0');PriorityQueue<String> q=new PriorityQueue<>();if(check(a+2000,b,c)) {String temp=String.valueOf(a+2000)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(c<10)temp+="0";temp+=String.valueOf(c);q.add(temp);}if(check(c+2000,a,b)) {String temp=String.valueOf(c+2000)+"-";if(a<10)temp+="0";temp+=String.valueOf(a)+"-";if(b<10)temp+="0";temp+=String.valueOf(b);q.add(temp);}if(check(c+2000,b,a)) {String temp=String.valueOf(c+2000)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(a<10)temp+="0";temp+=String.valueOf(a);q.add(temp);}if(check(a+1900,b,c)) {String temp=String.valueOf(a+1900)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(c<10)temp+="0";temp+=String.valueOf(c);q.add(temp);}if(check(c+1900,a,b)) {String temp=String.valueOf(c+1900)+"-";if(a<10)temp+="0";temp+=String.valueOf(a)+"-";if(b<10)temp+="0";temp+=String.valueOf(b);q.add(temp);}if(check(c+1900,b,a)) {String temp=String.valueOf(c+1900)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(a<10)temp+="0";temp+=String.valueOf(a);q.add(temp);}while(!q.isEmpty()) {System.out.println(q.poll());}}
}

（2）不使用PriorityQueue，使用TreeSet（去重），过100%样例

import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static boolean check(int a,int b,int c) {if(a<1960||a>2059)return false;if(b<1||b>12)return false;int[] daysInMonth= {0,31,28,31,30,31,30,31,31,30,31,30,31};if(a%4==0 && (a%100!=0 ||a%400==0)) {  // 判断闰年daysInMonth[2]+=1; // 是闰年则2月为29天}if(c<1||c>daysInMonth[b])return false;return true;}public static void main(String[] args) {String s=scan.nextLine();int a=(s.charAt(0)-'0')*10+(s.charAt(1)-'0');int b=(s.charAt(3)-'0')*10+(s.charAt(4)-'0');int c=(s.charAt(6)-'0')*10+(s.charAt(7)-'0');TreeSet<String> q=new TreeSet<>();if(check(a+2000,b,c)) {String temp=String.valueOf(a+2000)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(c<10)temp+="0";temp+=String.valueOf(c);q.add(temp);}if(check(c+2000,a,b)) {String temp=String.valueOf(c+2000)+"-";if(a<10)temp+="0";temp+=String.valueOf(a)+"-";if(b<10)temp+="0";temp+=String.valueOf(b);q.add(temp);}if(check(c+2000,b,a)) {String temp=String.valueOf(c+2000)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(a<10)temp+="0";temp+=String.valueOf(a);q.add(temp);}if(check(a+1900,b,c)) {String temp=String.valueOf(a+1900)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(c<10)temp+="0";temp+=String.valueOf(c);q.add(temp);}if(check(c+1900,a,b)) {String temp=String.valueOf(c+1900)+"-";if(a<10)temp+="0";temp+=String.valueOf(a)+"-";if(b<10)temp+="0";temp+=String.valueOf(b);q.add(temp);}if(check(c+1900,b,a)) {String temp=String.valueOf(c+1900)+"-";if(b<10)temp+="0";temp+=String.valueOf(b)+"-";if(a<10)temp+="0";temp+=String.valueOf(a);q.add(temp);}for (Object object : q) {System.out.println(object);}}
}

（3）TreeSet+SimpleDateFormat日期判断优化（过100%样例）,参考题解

import java.util.*;
import java.text.SimpleDateFormat; //引入public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {String temp=scan.nextLine();String date[]=temp.split("/"); // 使用split分隔开String y=date[0],m=date[1],d=date[2], // 3种情况写出来yMd=(Integer.parseInt(y)<60?"20"+y:"19"+y)+"-"+m+"-"+d,mDy=(Integer.parseInt(d)<60?"20"+d:"19"+d)+"-"+y+"-"+m,dMy=(Integer.parseInt(d)<60?"20"+d:"19"+d)+"-"+m+"-"+y;TreeSet<String> set=new TreeSet<>();// 使用treeset自动排序和去重if(check(yMd)) set.add(yMd);if(check(mDy)) set.add(mDy);if(check(dMy)) set.add(dMy);for (Object object : set) {System.out.println(object);}}static boolean check(String date) { // 0判断日期是否合法SimpleDateFormat format=new SimpleDateFormat("yyyy-MM-dd");format.setLenient(false);// 严格模式，不允许非法日期（如2019-02-30）try {format.parse(date); // 尝试解析日期}catch(Exception e) {return false; // 如果抛出异常，则日期无效}return true;}
}