算法训练第二周题解汇总

C - Cross

[ABC300C] Cross - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

题解：看数据范围比较小，这题也能直接暴力。遍历矩阵，一旦遇到一个'#'，就以他为中心搜索它的周围，看他是否能够成一个十字架，取最长的长度。题目保证不会有两个十字架之间共享一个角的情况出现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;/**@filename: Main*@author: lyh*@date:2023/5/3 10:26*@version 1.0*@description TODO*/
public class Main {private static final int[][] next={{1,1},{-1,-1},{-1,1},{1,-1}};private static int h;private static int w;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);h=scanner.nextInt();w=scanner.nextInt();int lenth=Math.min(h,w);int[] ans=new int[lenth+1];Listlist=new ArrayList<>();for(int i=0;ilist){int size=1;while(true){for(int a=0;a<4;a++){int dx=i+next[a][0]*size;int dy=j+next[a][1]*size;if(dx<0||dy<0||dx>=h||dy>=w||list.get(dx).charAt(dy)=='.'){return size-1;}}size++;}}
}

D - Find by Query  

[ABC299D] Find by Query - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

因为本题是一个交互题，交互格式如下：

题解：题目说最多问20个问题，为什么限定在这个数字呢？实际上容易发现这个数差不多是log n级别的，我们首先想到二分做法。

因为这个序列只有两种数字，0 或 1。不难发现，假如有一段区间S(left),S(left)+1​,S(left)+2​……S(right)，只要 S(left) !=S(right)​，那么无论中间是什么数，总会找到答案。而题目给出S1=0和Sn​=1，首先把 l 指针指向第一个位置，r 指针指向最后一个位置。接下来我们要做的是维护这两个指针并时刻满足 S(l)​=0 且S(r) =1。在最终必定会有一个时刻，R=L+1，此时直接得到答案为 L。

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int left=1,right=n;while(left+2<=right){//left和right存在≤1个元素时int mid=(left+right)>>1;System.out.println("?"+mid);String midEle=scanner.next();if(midEle.charAt(0)=='0')left=mid;else right=mid;}System.out.println("!"+left);}
}

E - Dango 

[ABC299C] Dango - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

题解：非常简单的一个题，遍历一遍字符串，当碰到 '-' 时就分别向前、向后搜索 'o'，不断取最大值。

import java.util.Scanner;/**@filename: Test*@author: lyh*@date:2023/5/7 9:28*@version 1.0*@description TODO*/
public class Main{public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n=scanner.nextInt();String s=scanner.next();int ans=-1;for(int i=0;i=0&&s.charAt(index)=='o'){onum++;index--;}if(onum>0)ans=Math.max(onum,ans);index=i+1;onum=0;while(index0)ans=Math.max(onum,ans);}}System.out.println(ans);}
}

F - Cards Query Problem 

[ABC298C] Cards Query Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

题解：很简单的模拟题，没什么好说的 

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int q = scanner.nextInt();List>list=new ArrayList<>(n+1);//盒子的集合，盒子里存着数字for(int i=0;i<=n;i++)list.add(new ArrayList<>());HashMap>map=new HashMap<>();//key为数字，value为所在盒子的有序集合for(int a=0;avalue=new TreeSet<>();value.add(j);map.put(i,value);}map.get(i).add(j);break;case 2:i=scanner.nextInt();Listbox=list.get(i);Collections.sort(box);for (Integer e:box) {System.out.print(e+" ");}System.out.println();break;case 3:i=scanner.nextInt();TreeSetbox2=map.get(i);for(Integer e:box2){System.out.print(e+" ");}System.out.println();break;}}}
}

H - Writing a Numeral 

[ABC298D] Writing a Numeral - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

题解：刚开始ans=1，

• 如果是 1 操作， ans = ans * 10 + x 

• 如果是 2 操作，我们先获取 ans 的首位数字，并且获取它的所在位(从右往左），分别存储到 x,y，最后 ans 减去 x * pow(10, y - 1) 即可。当然这里的pow需要用快速幂（需要用long，因为很可能会出现两个大质数相乘超int）。还要特别注意的是，这里在减了之后有可能ans是负的，我们需要将ans调回正数，注意在加上mod（998244353​​​​​​​）之前还要取模一次，因为很可能加上一次后还是负的，所以要先取模

• 如果是 3 操作，直接输出即可

import java.util.*;public class Main {private static final int mod=998244353;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);Listlist=new LinkedList<>();list.add(1L);long value=1;int q=scanner.nextInt();for(int i=0;i0){if(num%2==1)result=result*base%mod;num/=2;base=base*base%mod;}return result;}
}

J - M<=ab

[ABC296D] M<=ab - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

大意：

题解：首先根据数据范围选择long类型，从小到大枚举 a，再求出最小的 b，若 a <= n && b <= n，则此对 a,b 满足条件，更新答案。需要注意的是我们在枚举a的时候，要将 for 循环中的 m 改成 m * 2，如果为m的话，枚举 a 时离正确答案可能会小一点点，比方说当N、M分别为4、15时，

a 只会枚举到 ​，也就是 3。 当 a=3 时，b=5，即 b 不满足条件。但实际上我们a,b都取4的话是满足条件的。所以这里需要将m 改成 m * 2

import java.util.Scanner;/**@filename: Main*@author: lyh*@date:2023/5/3 10:26*@version 1.0*@description TODO*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n=scanner.nextLong();long m=scanner.nextLong();long ans=Long.MAX_VALUE;for(long i=1;i*i<=m*2;i++){//m*2long j;if(m%i==0)j=m/i;else j=m/i+1;if(i<=n&&j<=n)ans=Math.min(ans,i*j);}if(ans!=Long.MAX_VALUE) System.out.println(ans);else System.out.println(-1);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！