算法训练第一周题解汇总-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法训练第一周题解汇总。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A - Sort the Subarray

算法训练第一周题解汇总

大意：在s1找一个最大的 [l，r] 子区间，使其经过从小到大的排序后能够变成 s2

题解：先确定最小的区间，然后慢慢扩大。

最小区间的确定：s1和s2第一个不相等的数开始，到最后一个不相等的数结尾

向两边扩大区间：如果本来就是从小到大排序的，那么就算sort也无影响，否则停止扩展

import java.util.Scanner;

/*
 *@filename: Demo1
 *@author: lyh
 *@date:2023/4/24 19:09
 *@version 1.0
 *@description TODO
 */
public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0){
            int n=scanner.nextInt();
            int[] vis1=new int[n+1];
            int[] vis2=new int[n+1];
            for(int i=1;i<=n;i++){
                vis1[i]=scanner.nextInt();
            }
            boolean flag=true;
            int left=0,right=0;
            for(int i=1;i<=n;i++){
                vis2[i]=scanner.nextInt();
                if(flag&&vis2[i]!=vis1[i]){
                    left=i;
                    flag=false;
                }else if(vis2[i]!=vis1[i]){
                    right=i;
                }
            }
            while(left-1>0){
                if(vis2[left]>=vis2[left-1]){
                    left--;
                }
                else break;
            }
            while(right+1<=n){
                if(vis2[right]<=vis2[right+1]){
                    right++;
                }
                else break;
            }
            System.out.println(left+" "+right);
        }
    }
}

B - Tear It Apart

算法训练第一周题解汇总

大意：给定一个字符串，操作多次后只剩下同一字符，每次操作消除不相邻的多个字符，求最小操作次数

题解：剩下的那个同一字符将字符串分成了多个区间端，就像隔离带一样。并且我们只要处理最长子串就可以了(因为其他的肯定能顺带移除完毕)。

如何寻找该同一字符：遍历字符串每种已有的字母，计算他们分割子串里的最长子串长度，取最小

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/*
 *@filename: Demo2
 *@author: lyh
 *@date:2023/4/25 14:46
 *@version 1.0
 *@description TODO
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            String s=scanner.next();
            int length=s.length();
            Map<Character,Integer>map=new HashMap<>(30);
            for(int i=0;i<length;i++){
                if(!map.containsKey(s.charAt(i)))map.put(s.charAt(i),1);
            }
            int minn=Integer.MAX_VALUE;
            for (Map.Entry<Character,Integer>entry:map.entrySet()) {
                  int count=0,temp=0;
                  for(int i=0;i<length;i++){
                      if(s.charAt(i)!=entry.getKey()){
                          count++;
                      }else{
                          temp=Math.max(temp,count);
                          count=0;
                      }
                  }
                  temp=Math.max(temp,count);//最后也要比较一次！
                  minn=Math.min(temp,minn);
            }
            int ans=0;
            while(minn>0){
                minn=minn>>1;//因为不相邻就可以一起消除
                ans++;
            }
            System.out.println(ans);
        }
    }
}

C - Yura's New Name

算法训练第一周题解汇总

大意：给出一个仅由 ^ 和 _ 组成的字符串，你可以在任意位置添加^或 _ 字符，使得字符串满足：

任意字符要么属于某一子串 ^_^ 的一部分，要么属于某一子串 ^^ 的一部分。

求最少添加的字符数量。

题解：感觉和括号匹配是一个题型。开头要求一定得是'^'，两个连续的'_'中间需要加'^'，以'_'结尾需要加'^'。特殊情况只有一个'^'需要注意判断。

import java.util.ArrayList;
import java.util.Scanner;

/*
 *@filename: Demo2
 *@author: lyh
 *@date:2023/4/25 14:46
 *@version 1.0
 *@description TODO
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            int ans=0;
            String s=scanner.next();
            int length=s.length();
            if(length==1&&s.charAt(0)=='^'){
                ans++;
                System.out.println(ans);
                continue;
            }
            if(s.charAt(0)!='^')ans++;
            for(int i=0;i<length-1;i++){
                if(s.charAt(i)==s.charAt(i+1)&&s.charAt(i)=='_'){
                    ans++;
                }
            }
            if(s.charAt(length-1)=='_')ans++;
            System.out.println(ans);
        }
    }
}

D - JoJo's Incredible Adventures

算法训练第一周题解汇总

大意：有一串由0,1构成的字符串，每次循环右移一位，行编号从0一直到n-1。求这些行里由1构成的最大矩形面积。

题解：我们其实可以观察到一串连续的1经过右移后是会形成一对正三角和倒三角的，而矩形就在三角内。

算法训练第一周题解汇总

我们可以先找到最长的连续字符'1'的串，由于不断右移过程中，连续的 1 的个数可能增加，如下

算法训练第一周题解汇总

我们让s+s（成环），这样遍历就可以找到最长的连续字符'1'的串，设该长为k，矩形的面积可能为1*k、2*(k-1)、3*(k-2)......遍历一遍取最大值即可

注意：特殊情况k等于n，即全是字符'1'，这时面积等于n的平方，需要特判，并且需要用long类型接收

import java.util.*;
import java.util.function.Consumer;

/*
 *@filename: Demo2
 *@author: lyh
 *@date:2023/4/25 14:46
 *@version 1.0
 *@description TODO
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
           String s=scanner.next();
           s=s+s;
           long maxL=0,count=0,length=s.length();
           for(int i=0;i<length;i++){
               if(s.charAt(i)=='1'){
                   count++;
                   maxL=Math.max(maxL,count);
               }
               else{
                   count=0;
               }
           }
           if(maxL==length){
               System.out.println((maxL>>1)*(maxL>>1));
               continue;
           }
           long ans=0;
           for(int i=1;i<=(maxL+1)/2;i++){
               ans=Math.max(ans,i*(maxL+1-i));
           }
            System.out.println(ans);
        }
    }
}

E - Constructive Problem

算法训练第一周题解汇总

大意：题意大致为将一个非负整数数组中没有出现过的最小非负整数MEX = x，经过一次操作，该操作为将该数组的一个连续子序列全部变为k，k为非负整数，可以使得该数组的MEX 变成x+1，

例如：0 2 2 0

其中第一个未出现的数为1，要把他变成2，只要将所有的2变为1即可

题解：分两种情况

如果MEX=n，那么就一定不成立。因为该整数数组是连续并且没有冗余的。如0,1,2,3,4......，每一个数都作出了它的贡献
如果MEX!=n，那么就一定成立。这说明：小于MEX的数有多余的或者有>=MEX+1的，当然可能两种都有。观察例子可以发现，要让MEX加1，必须要将原来数组中等于MEX+1的数全部消除掉并且变成MEX，并且由于每次操作只能操作一个连续子序列，我们需要记录MEX的最小下标和最大下标。如果数组里没有等于MEX+1的，我们可以在——小于MEX的数有多余的或者>MEX+1的 数随便选一个将其改为MEX，然后检验是否成立

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

/*
 *@filename: Demo4
 *@author: lyh
 *@date:2023/4/28 1:54
 *@version 1.0
 *@description TODO
 */
public class Demo4 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            List<Integer> list = new ArrayList<>(n);
            for (int i = 0; i < n; i++) {
                int x = scanner.nextInt();
                list.add(x);
            }
            int MEX = getMEX(n, list);
            if (MEX == n) {//0,1,2,3,4,5,6这样
                System.out.println("No");
                continue;
            }
            int minIndex = 0, maxIndex = 0;//MEX的最小下标，和最大下标
            boolean first = false;//为false表示minIndex,maxIndex没有进行第一次初始化
            for (int i = 0; i < n; i++) {
                if (list.get(i) == MEX + 1) {
                    if (!first) {
                        minIndex = i;
                        maxIndex = i;
                        first = true;
                    } else {
                        maxIndex = i;
                    }
                }
            }
            if (!first) {//没有 等于MEX + 1的，那么从>mex+1的或者小于mex的数并且有多余的 拿一个当MEX
                HashSet<Integer> hashSet = new HashSet<>();
                for (int i = 0; i < n; i++) {
                    if (list.get(i) > MEX + 1) {
                        list.set(i, MEX);
                        break;
                    }
                    if (hashSet.contains(list.get(i))) {
                        list.set(i, MEX);
                        break;
                    }
                    else hashSet.add(list.get(i));
                }

            } else {
                for (int i = minIndex; i <= maxIndex; i++) {
                    list.set(i, MEX);
                }
            }
            if (getMEX(n, list) == MEX + 1) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    public static int getMEX(int n, List<Integer> list) {
        HashSet<Integer> hashSet = new HashSet<>(list);
        int MEX = n;
        for (int i = 0; i < n; i++) {
            if (!hashSet.contains(i)) {
                MEX = i;
                break;
            }
        }
        return MEX;
    }
}

F - Li Hua and Maze

算法训练第一周题解汇总

大意：求最少设置多少个障碍物，可以使起点永远无法到达终点。只能上下左右走。

题解：很简单，封住起点或终点，取封这两个需要的最小障碍物数

import java.util.Scanner;

/*
 *@filename: Demo1
 *@author: lyh
 *@date:2023/4/24 19:09
 *@version 1.0
 *@description TODO
 */
public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int x1= scanner.nextInt();
            int y1= scanner.nextInt();
            int x2= scanner.nextInt();
            int y2= scanner.nextInt();
            int getOutStep1=getStep(x1,y1,n,m);
            int getInStep2=getStep(x2,y2,n,m);
            System.out.println(Math.min(getOutStep1, getInStep2));
        }
    }

    public static int getStep(int x1,int y1,int n,int m){
        int ans=0;
        if(x1-1>=1){
            ans++;
        }
        if(x1+1<=n){
            ans++;
        }
        if(y1+1<=m){
            ans++;
        }
        if(y1-1>=1){
            ans++;
        }
        return ans;
    }
}

G - Li Hua and Pattern

算法训练第一周题解汇总

大意：李华有一个大小为 n×n 的图案，每个格子为蓝色或红色。他可以进行恰好 k 次操作。每一次操作，他选择一个格子并改变其颜色（红变蓝，蓝变红）。每个格子可以被选择任意多次。是否可能使得操作后的图案中心对称（翻转180度看起来一样）？

题解：首先，遍历每个点，看它与其中心对称的点相比颜色是否一样，如果不一样则需要翻转一次，因为是中心对称，我们只需要遍历前面一半的点就可以了。特别注意的是如果n为奇数需要特别多遍历一行。

如果修改次数大于k，那肯定不行。如果小于k，分n的奇偶性判断：

若n为奇数，一定可以，因为正中心的小正方形无论翻转多少次都不影响整体，可以消耗多余的操作次数
若n为偶数，剩下多余的次数也要为偶数才行

import java.util.Scanner;

/*
 *@filename: Demo1
 *@author: lyh
 *@date:2023/4/24 19:09
 *@version 1.0
 *@description TODO
 */
public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            int n=scanner.nextInt();
            int k=scanner.nextInt();
            int[][] vis=new int[n+1][n+1];
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    vis[i][j]=scanner.nextInt();
                }
            }
            int mod=0;
            for(int i=1;i<=(n>>1);i++){
                for(int j=1;j<=n;j++){
                    if(vis[i][j]!=vis[n-i+1][n-j+1])mod++;
                }
            }
            if((n&1)==1){
                for(int i=1;i<=(n>>1);i++){
                    if(vis[(n>>1)+1][i]!=vis[(n>>1)+1][n-i+1])mod++;
                }
                if(mod<=k){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }else{
                if(mod<=k&&((k-mod)&1)==0){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }
        }
    }

}

I - Lucky Numbers

算法训练第一周题解汇总

大意：给你两个数，请在该区间找个数，该数已有的数位(个位、十位、百位等)上最大的数-最小的数的差最大

题解：最大也只能是9，暴力求解，一旦发现最大差等于9，退出循环，需要注意的是最大差在迭代的时候只有>=当前最大差就可以迭代，并记录该数。否则遇到一组完全相等的数或者个位数时无输出，实际上是需要输出一个在区间的数的。


import java.util.Scanner;

/*
 *@filename: Demo3
 *@author: lyh
 *@date:2023/4/27 15:07
 *@version 1.0
 *@description TODO
 */
public class Demo3 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            int left=scanner.nextInt();
            int right=scanner.nextInt();
            int ans=0,cha=0;
            for(int i=left;i<=right;i++){
                int temp=getDifference(i);
                if(temp>=cha){
                   cha=temp;
                   ans=i;
                   if(cha==9)break;
                }
            }
            System.out.println(ans);
        }
     }
     public static int getDifference(int x){
         int maxNum=0;
         int minNum=10;
         while(x>0){
             maxNum=Math.max(maxNum,x%10);
             minNum=Math.min(minNum,x%10);
             x/=10;
         }
         return maxNum-minNum;
     }
}

J - Playing in a Casino

算法训练第一周题解汇总

大意：给出一个T组样例，每组样例给出一个n和m表示给出n条数据，每条有m个数据

每次选两条，每个数据一一对应相减取绝对值，求绝对值的和是多少。

题解：首先一眼模拟暴力，但是时间复杂度n立方，果然超时。

我们可以考虑对列排序，因为改变行的位置不会影响结果。经过从小到大排序后，就简化为两两数字差值的问题了。

先假设有一些数字的差值为1,2,3,4,5，我们会发现

每个差值的最后相加的数量=该层及前面的层数*该层有多少个

最后需要注意答案要用long类型接收

算法训练第一周题解汇总

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/*
 *@filename: Demo1
 *@author: lyh
 *@date:2023/4/24 19:09
 *@version 1.0
 *@description TODO
 */
public class Demo1 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
           int n=scanner.nextInt();
           int m=scanner.nextInt();
            List<List<Integer>> vis=new ArrayList<>();
            for(int i=1;i<=n;i++){
                List<Integer> x=new ArrayList<>();
                for(int j=1;j<=m;j++){
                    int num=scanner.nextInt();
                    x.add(num);
                }
                vis.add(x);
            }
            long sum=0;
            for(int i=0;i<m;i++){
                int finalI = i;//闭包
                vis.sort(new Comparator<List<Integer>>() {//对列排序
                    @Override
                    public int compare(List<Integer> o1, List<Integer> o2) {
                        return o1.get(finalI)-o2.get(finalI);
                    }
                });
                List<Integer>column=new ArrayList<>();
                for(int j=1;j<n;j++){
                    column.add(vis.get(j).get(i)-vis.get(j-1).get(i));
                }
                int size=column.size();
                for(int j=0;j<size;j++){
                    sum=sum+ (long) column.get(j) *(size-j)*(j+1);
                }
            }
            System.out.println(sum);
        }
    }

}

K - Showstopper

算法训练第一周题解汇总

大意：两组数a、b，a1,a2,......an，b1,b2......bn。每次操作可以把对位的an与bn交换，问是否可以经过多次操作使得an和bn(即最后一个数)分别在数组a、数组b中最大

题解：整体是先从末尾出发往前走，首先处理一下末尾：

如果末尾不是最大的，并且对位元素要大一些，那就交换(贪心思想)。

然后往前遍历，如果当前元素大于末尾元素，并且对位元素也大于末尾元素（说明交换也无法挽救），那么就达不到要求。

import java.util.*;

/*
 *@filename: Demo2
 *@author: lyh
 *@date:2023/4/25 14:46
 *@version 1.0
 *@description TODO
 */
public class Demo2 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
            int n = scanner.nextInt();
            List<Integer> vis1 = new ArrayList<>();
            List<Integer> vis2 = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int x = scanner.nextInt();
                vis1.add(x);
            }
            for (int i = 0; i < n; i++) {
                int x = scanner.nextInt();
                vis2.add(x);
            }
            int maxElement1 = Collections.max(vis1);//最大元素
            int maxElement2 = Collections.max(vis2);//最大元素
            if (maxElement1 > vis1.get(n - 1) && vis2.get(n - 1) > vis1.get(n - 1)) {
                int temp = vis1.get(n - 1);
                vis1.set(n - 1, vis2.get(n - 1));
                vis2.set(n - 1, temp);
            } else if (maxElement2 > vis2.get(n - 1) && vis1.get(n - 1) > vis2.get(n - 1)) {
                int temp = vis1.get(n - 1);
                vis1.set(n - 1, vis2.get(n - 1));
                vis2.set(n - 1, temp);
            }
            int pointer = n - 2;
            boolean ans = true;
            while (pointer >= 0) {
                if (vis1.get(pointer) > vis1.get(n - 1)) {
                    if (vis2.get(pointer) > vis1.get(n - 1)||vis1.get(pointer)>vis2.get(n-1)) {
                        System.out.println("NO");
                        ans = false;
                        break;
                    }
                }
                if (vis2.get(pointer) > vis2.get(n - 1)) {
                    if (vis1.get(pointer) > vis2.get(n - 1)||vis2.get(pointer)>vis1.get(n-1)) {
                        System.out.println("NO");
                        ans = false;
                        break;
                    }
                }
                pointer--;
            }
            if(ans) System.out.println("YES");
        }
    }
}

L - Three Sevens

算法训练第一周题解汇总

大意：给定m天，每天n个人可以中奖，当前中奖的人不能参加后面的比赛，输出可能的方案

题解：先用一个hashmap存储玩家可能获奖的最近的那一天，然后遍历每一天，把该天可能获奖的玩家编号添加到答案集合里面(一个就可以了)，最后判断答案集合长度，若小于n则无法构造。

重点！！！

玛德这题我交了8次才过！都是泪啊

算法训练第一周题解汇总

我原本只用了一个hashmap，然后每次都需要遍历他寻找改天可能获奖的玩家，这样太耗时间了

算法训练第一周题解汇总 后面我又加了一个HashMap存储 value-key 映射。

这样根据 value 查找 key，时间复杂度为 O(1)!


import java.util.*;

/*
 *@filename: Demo3
 *@author: lyh
 *@date:2023/4/27 15:07
 *@version 1.0
 *@description TODO
 */
public class Demo3 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
           int m=scanner.nextInt();
           HashMap<Integer,Integer> playerDay=new HashMap<>(5000);//key为玩家编号，value为天数
           for(int i=1;i<=m;i++){
               int n=scanner.nextInt();
               for(int j=1;j<=n;j++){
                   int x=scanner.nextInt();
                   playerDay.put(x,i);//存储玩家可能获奖的最近的那一天
               }
           }
           List<Integer>ans=new ArrayList<>();
           HashMap<Integer,Integer> dayPlayer=new HashMap<>(5000);//key为玩家编号，value为天数
            // 构建 value-key 映射
            for (Map.Entry<Integer, Integer> entry : playerDay.entrySet()) {
                dayPlayer.put(entry.getValue(), entry.getKey());
            }
           for(int i=1;i<=m;i++){//遍历每一天
               if(dayPlayer.get(i)!=null)ans.add(dayPlayer.get(i));
           }
           if(ans.size()<m) System.out.println(-1);
           else{
               for (int i = 0; i < m; i++) {
                   System.out.print(ans.get(i)+" ");
                   if(i==m-1) System.out.println();
               }
           }
        }
    }
}

N - Sum on Subarrays

算法训练第一周题解汇总

大意：

算法训练第一周题解汇总

题解：这题有很多种构造方法，很明显我们要统一用一种排列方式。因为不能出现和为 0 的情况，所以我这里是用2构造，不是用1，并且我们统一把正数放在前面。

算法训练第一周题解汇总

设马上要填充的 2是第x个2，每个2会贡献 x种子串和为正数的情况(它本身，以及和前面的数组合)。这实际上是一个等差数列，上面是刚好填充的情况，如果k是11，那么再加一个2的话，子串和为正的情况会变成15(10+5)，这个时候我们需要填充负数，并且需要使组合完只会增加1种子串和为正的情况。假设前面已经有了n个2，那么这个负数加上前面n个2的和需要>0，但是加上前面n-1个2(第 2 个'2' 至第 n 个'2')的和需要<0，这样才能保证只会增加1种子串和为正的情况。

如果构造的情况刚好等于k，此时n个数还没填满，我们后面全部填负无穷(-1000)即可文章来源地址https://www.toymoban.com/news/detail-427570.html

import java.util.*;

/*
 *@filename: Demo3
 *@author: lyh
 *@date:2023/4/27 15:07
 *@version 1.0
 *@description TODO
 */
public class Demo3 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        while(t-->0) {
           int n=scanner.nextInt();
           int k=scanner.nextInt();
           int num2=0;//2的数量
           int contribution=0;
           for(int i=1;i<=n;i++){
               int temp=num2+1;
               if((1+temp)*temp/2<=k){//等差数列求和
                   contribution=(1+temp)*temp/2;
                   num2++;
                   System.out.print(2+" ");
               }else{
                   int difference=k-contribution;
                   //5 8
                   //2 2 2 -3
                   //1 2 3 2
                   int fill=-(num2-difference)*2-1;
                   System.out.print(fill+" ");
                   for(int j=1;j<=n-i;j++) System.out.print(-1000+" ");
                   break;
               }
           }
           System.out.println();
        }
    }
}

到了这里，关于算法训练第一周题解汇总的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！