头像

文思涌




离线:8小时前


活动打卡代码 AcWing 787. 归并排序

文思涌
19小时前
    private static int N=100010;
    private static int[] arr=new int[N];
    private static int[] temp=new int[N];
    public static void merge_sort(int l,int r) {
        if(l>=r)return ;
        int mid=l+r>>1;
        merge_sort(l, mid);
        merge_sort(mid+1, r);
        int i=l,j=mid+1;
        int k=0;
        while(i<=mid&&j<=r) {
            if(arr[i]<arr[j])temp[k++]=arr[i++];
            else temp[k++]=arr[j++];
        }
        while(i<=mid) temp[k++]=arr[i++];
        while(j<=r) temp[k++]=arr[j++];
        for(i=l,j=0;i<=r;i++,j++)
            arr[i]=temp[j];
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for(int i=0;i<n;i++)
            arr[i]=scanner.nextInt();
        merge_sort(0, n-1);
        for(int i=0;i<n;i++)
            System.out.print(arr[i]+" ");
    }



文思涌
20小时前
    private static int[] days= {0,31,28,31,30,31,30,31,31,30,31,30,31};
    public static boolean check_valid(int date) {
        int year=date/10000;//舍弃掉后面4位
        int month=date/100%100;//先舍弃掉后面2位,然后得到6位中的最后两位
        int day=date%100;//得到8位中的最后两位
        if(month<1||month>12)return false;//判断月份是否合法
        if(day<1||month!=2&&day>days[month])return false;//判断不是2月份的天数是否合法
        if(month==2) {
            int leap=0;
            if(year%100!=0&&year%4==0||year%400==0) {
                leap=1;//若闰年则有29天
            }
            if(day>28+leap)return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int date1=scanner.nextInt();
        int date2=scanner.nextInt();
        int res=0;
        for(int i=1000;i<10000;i++) {
            int date=i;
            int x=i;
            for(int j=0;j<4;j++) {
                date=date*10+x%10;
                x/=10;
            }
            if(date1<=date&&date<=date2&&check_valid(date))res++;
        }
        System.out.println(res);
    }


活动打卡代码 AcWing 466. 回文日期

文思涌
20小时前
    private static int[] days= {0,31,28,31,30,31,30,31,31,30,31,30,31};
    public static boolean check_valid(int date) {
        int year=date/10000;//舍弃掉后面4位
        int month=date/100%100;//先舍弃掉后面2位,然后得到6位中的最后两位
        int day=date%100;//得到8位中的最后两位
        if(month<1||month>12)return false;//判断月份是否合法
        if(day<1||month!=2&&day>days[month])return false;//判断不是2月份的天数是否合法
        if(month==2) {
            int leap=0;
            if(year%100!=0&&year%4==0||year%400==0) {
                leap=1;//若闰年则有29天
            }
            if(day>28+leap)return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int date1=scanner.nextInt();
        int date2=scanner.nextInt();
        int res=0;
        for(int i=1000;i<10000;i++) {
            int date=i;
            int x=i;
            for(int j=0;j<4;j++) {
                date=date*10+x%10;
                x/=10;
            }
            if(date1<=date&&date<=date2&&check_valid(date))res++;
        }
        System.out.println(res);
    }


活动打卡代码 AcWing 1204. 错误票据

最大难点:输入问题

int n=Integer.parseInt(reader.readLine());//将读取的字符串转换为整型 

//split里的参数是正则表达式,被空格(几个无所谓)之间分隔的两个字符串分别赋值给s[i]和s[i+1]
String[] s = reader.readLine().split("\\s+");

这题比较简单,用哈希表就能算了

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());//trim()的作用是可以去掉字符串两端的多余的空格
        //int n=(int)reader.read();
        int[] a = new int[100010];
        int[] num=new int[100010];
        int k=0;
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split("\\s+");
            for(int i = 0;i < s1.length;i++)
            {
                a[k ++] = Integer.parseInt(s1[i]);
            }
        }
        int min=0x3f3f3f3f;
        for(int i=0;i<k;i++) {
            num[a[i]]++;
            min=Math.min(min, a[i]);
        }
        int m=0,nn=0;
        for(int i=min;i<min+k;i++) {
            if(num[i]==0)m=i;
            if(num[i]>1)nn=i;
        }
        System.out.println(m+" "+nn);



最大难点:输入问题

int n=Integer.parseInt(reader.readLine());//将读取的字符串转换为整型 

//split里的参数是正则表达式,被空格(几个无所谓)之间分隔的两个字符串分别赋值给s[i]和s[i+1]
String[] s = reader.readLine().split("\\s+");

这题比较简单,用哈希表就能算了

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());//trim()的作用是可以去掉字符串两端的多余的空格
        int[] a = new int[100010];
        int[] num=new int[100010];
        int k=0;
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split("\\s+");
            for(int i = 0;i < s1.length;i++)
            {
                a[k ++] = Integer.parseInt(s1[i]);
            }
        }
        int min=0x3f3f3f3f;
        for(int i=0;i<k;i++) {
            num[a[i]]++;
            min=Math.min(min, a[i]);
        }
        int m=0,nn=0;
        for(int i=min;i<min+k;i++) {
            if(num[i]==0)m=i;
            if(num[i]>1)nn=i;
        }
        System.out.println(m+" "+nn);


活动打卡代码 AcWing 1245. 特别数的和

常用操作模板

1.将字符串变为整数

        String str="2021";
        int n=0;
        for(int i=0;i<str.length();i++) {
            n=n*10+str.charAt(i)-'0';
        }
        System.out.println(n);//2021

2.取每位数字

        int n=1234;
        while(n>0) {
            int yu=n%10;
            n=n/10;
            System.out.println(yu);//4 3 2 1
        }

答案:

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int sum=0;
        for(int i=1;i<=n;i++) {
            int k=i;
            while(k>0) {
                int yu=k%10;
                if(yu==2||yu==0||yu==1||yu==9) {
                    sum+=i;
                    break;
                }
                k/=10;
            }
        }
        System.out.println(sum);



常用操作模板

1.将字符串变为整数

        //简单的方法
        String str="2021";
        int n=Integer.parseInt(str);
        //第二种
        String str="2021";
        int n=0;
        for(int i=0;i<str.length();i++) {
            n=n*10+str.charAt(i)-'0';
        }
        System.out.println(n);//2021

2.取每位数字

        int n=1234;
        while(n>0) {
            int yu=n%10;
            n=n/10;
            System.out.println(yu);//4 3 2 1
        }

答案:

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int sum=0;
        for(int i=1;i<=n;i++) {
            int k=i;
            while(k>0) {
                int yu=k%10;
                if(yu==2||yu==0||yu==1||yu==9) {
                    sum+=i;
                    break;
                }
                k/=10;
            }
        }
        System.out.println(sum);


活动打卡代码 AcWing 1236. 递增三元组

1.二分

思路:由时间复杂度分析算法,由于它的数据范围是10^5,最先想到的是三重循环,但是若算法中超过两重循环的话(即10^10以上,一般控制在$O(10^7到10^8)$才不会超时),说明算法最坏得用$O(nlogn)$才不会超时。
通过上面分析说明最多枚举一个数组然后里面操作$O(logn)$的算法,刚好二分就符合该复杂度;
然后是遍历哪个呢,遍历A和遍历C一样,若遍历A的话,B和C就会相互影响两个又得多加些操作。
这时候就只能遍历B使得A和C的选择相互独立,用二分选择最大小于B的数A和最小大于B的数C然后两者相乘得n,表示以这个数B放中间有n种分配

注意事项:

1.题目中是“Ai<Bj<Ck”,不包含等于的情况,在代码判断中切记不要忘记了!!!
2.用整型会溢出,因为数据范围很大又要相乘说明有很多种选择方案,可能会爆int得用long存储
3.java里 int 类整数的最大值是 2 的 31 次方 - 1 = 2147483648 - 1 = 2147483647
long的最大值是2^63-1,值是9223372036854775807

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] a=new int[n],b=new int[n],c=new int[n];
        for(int i=0;i<n;i++)a[i]=scanner.nextInt();
        for(int i=0;i<n;i++)b[i]=scanner.nextInt();
        for(int i=0;i<n;i++)c[i]=scanner.nextInt();
        Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);//要用二分就得先从小到大排序
        long sum=0;
        for(int i=0;i<n;i++) {
            int l=0,r=n-1;
            while(l<r) {
                int mid=l+r+1>>1;
                if(a[mid]<b[i])l=mid;//找最后一个数是小于x的下标,让选择范围一直往右边缩小
                else r=mid-1;
            }
            if(a[l]>=b[i])continue;//若找出来的数不满足a<b
            int x=l;
            l=0;r=n-1;
            while(l<r) {
                int mid=l+r>>1;
                if(c[mid]>b[i])r=mid;//找第一个数是大于数b的下标,让选择范围一直往左边缩小
                else l=mid+1;
            }
            if(c[l]<=b[i])continue;//若找出来的数不满足c<b
            int y=l;
            sum+=(long)(x+1)*(n-y);//题目数据范围很大得用long存取
        }
        System.out.println(sum);

2.前缀和

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int N=100010;
        int[] a=new int[N],b=new int[N],c=new int[N];
        int[] cnta=new int[N],cntc=new int[N];//cnta[i]记录在数组a中,出现i的次数
        int[] as=new int[N],cs=new int[N];//as[i]表示前i个数出现在数组a中的次数总和
        for(int i=1;i<=n;i++)a[i]=scanner.nextInt()+1;//因为取值范围是0开始,为了防止下标越界都加上一,对结果无影响
        for(int i=1;i<=n;i++)b[i]=scanner.nextInt()+1;
        for(int i=1;i<=n;i++)c[i]=scanner.nextInt()+1;
        long sum=0;
        for(int i=1;i<=n;i++) {//分别记录出现在ac数组中各个数出现的次数
            cnta[a[i]]++;
            cntc[c[i]]++;
        }
        for(int i=1;i<N;i++) {//求前缀和
            as[i]=cnta[i]+as[i-1];
            cs[i]=cntc[i]+cs[i-1];
        }
        for(int i=1;i<=n;i++) {
            int x=as[b[i]-1];//b[i]本来可能取0的但是前面加一了,就不会越界了,在数组a中小于b[i]的总个数
            int y=cs[100001]-cs[b[i]];//在数组c中大于b[i]的总个数,若不用前缀和,得双重循环判断就会超时
            sum+=(long)x*y;
        }
        System.out.println(sum);



1.二分

思路:由时间复杂度分析算法,由于它的数据范围是10^5,最先想到的是三重循环,但是若算法中超过两重循环的话(即10^10以上,一般控制在$O(10^7到10^8)$才不会超时),说明算法最坏得用$O(nlogn)$才不会超时。
通过上面分析说明最多枚举一个数组然后里面操作$O(logn)$的算法,刚好二分就符合该复杂度;
然后是遍历哪个呢,遍历A和遍历C一样,若遍历A的话,B和C就会相互影响两个又得多加些操作。
这时候就只能遍历B使得A和C的选择相互独立,用二分选择最大小于B的数A和最小大于B的数C然后两者相乘得n,表示以这个数B放中间有n种分配

注意事项:

1.题目中是“Ai<Bj<Ck”,不包含等于的情况,在代码判断中切记不要忘记了!!!
2.用整型会溢出,因为数据范围很大又要相乘说明有很多种选择方案,可能会爆int得用long存储
3.java里 int 类整数的最大值是 2 的 31 次方 - 1 = 2147483648 - 1 = 2147483647
long的最大值是2^63-1,值是9223372036854775807

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] a=new int[n],b=new int[n],c=new int[n];
        for(int i=0;i<n;i++)a[i]=scanner.nextInt();
        for(int i=0;i<n;i++)b[i]=scanner.nextInt();
        for(int i=0;i<n;i++)c[i]=scanner.nextInt();
        Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);//要用二分就得先从小到大排序
        long sum=0;
        for(int i=0;i<n;i++) {
            int l=0,r=n-1;
            while(l<r) {
                int mid=l+r+1>>1;
                if(a[mid]<b[i])l=mid;//找最后一个数是小于x的下标,让选择范围一直往右边缩小
                else r=mid-1;
            }
            if(a[l]>=b[i])continue;//若找出来的数不满足a<b
            int x=l;
            l=0;r=n-1;
            while(l<r) {
                int mid=l+r>>1;
                if(c[mid]>b[i])r=mid;//找第一个数是大于数b的下标,让选择范围一直往左边缩小
                else l=mid+1;
            }
            if(c[l]<=b[i])continue;//若找出来的数不满足c<b
            int y=l;
            sum+=(long)(x+1)*(n-y);//题目数据范围很大得用long存取
        }
        System.out.println(sum);

2.前缀和

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int N=100010;
        int[] a=new int[N],b=new int[N],c=new int[N];
        int[] cnta=new int[N],cntc=new int[N];//cnta[i]记录在数组a中,出现i的次数
        int[] as=new int[N],cs=new int[N];//as[i]表示前i个数出现在数组a中的次数总和
        for(int i=1;i<=n;i++)a[i]=scanner.nextInt()+1;//因为取值范围是0开始,为了防止下标越界都加上一,对结果无影响
        for(int i=1;i<=n;i++)b[i]=scanner.nextInt()+1;
        for(int i=1;i<=n;i++)c[i]=scanner.nextInt()+1;
        long sum=0;
        for(int i=1;i<=n;i++) {//分别记录出现在ac数组中各个数出现的次数
            cnta[a[i]]++;
            cntc[c[i]]++;
        }
        for(int i=1;i<N;i++) {//求前缀和
            as[i]=cnta[i]+as[i-1];
            cs[i]=cntc[i]+cs[i-1];
        }
        for(int i=1;i<=n;i++) {
            int x=as[b[i]-1];//b[i]本来可能取0的但是前面加一了,就不会越界了,在数组a中小于b[i]的总个数
            int y=cs[100001]-cs[b[i]];//在数组c中大于b[i]的总个数,若不用前缀和,得双重循环判断就会超时
            sum+=(long)x*y;
        }
        System.out.println(sum);


活动打卡代码 AcWing 1210. 连号区间数

题目要点:

1.“某个排列”:说明每个数字只出现一次不重复
2.“连续”数列:指“12345”这样连续,而“1235”不满足

        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int[] arr=new int[10010];
        for(int i=1;i<=n;i++) {
            arr[i]=scanner.nextInt();
        }
        int sum=0;
        for(int l=1;l<=n;l++) {
            int min=arr[l];
            int max=arr[l];
            for(int r=l;r<=n;r++) {
                min=Math.min(min, arr[r]);
                max=Math.max(max, arr[r]);
                if(max-min==r-l)sum++;
            }
        }
        System.out.println(sum);