头像

暂时换个名字




离线:7小时前


活动打卡代码 AcWing 1532. 找硬币

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N,m;
    static int[] a;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[]=br.readLine().split("\\s+");N=Integer.parseInt(str[0]);m=Integer.parseInt(str[1]);
        a=new int[N];str=br.readLine().split("\\s+");
        while(--N>=0)a[N]=Integer.parseInt(str[N]);
        f();
    }
    public static void f() {
        Arrays.sort(a);
        int l=0,r=a.length-1;
        while (l < r) {
            if (a[l] + a[r] > m) {  r--;    }
            else if (a[l] + a[r] < m) { l++;}
            else if (a[l] + a[r] == m) {break;}
        }
        if (l < r) {
            System.out.println(a[l]+" "+a[r]);
        }else{
            System.out.println("No Solution");
        }
    }
}





import java.util.Scanner;
class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));
    }
    public static int f(int n) {
        int count=n;
        while(n>=3) {
            n-=2;
            count++;
        }
        return count;
    }    
}



原题链接
自己能想到的只有无脑暴力搜索,过了5个数据之后就超时了

import java.util.Scanner;

public class Main{
    static int n,s,a,b,res;
    static long[][] biao;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();s=sc.nextInt();a=sc.nextInt();b=0-sc.nextInt();biao=new long[n][n];
        f(1,0);System.out.println(res);
        //dp();
    }
    public static void f(int index,int num) {
        if(index>=n) {
            if((s-num)%n==0) {res++;}
            return;
        }
        f(index+1,num+a*index);
        f(index+1,num+b*index);
    }
}

参照题解

import java.util.Scanner;
public class Main {
    static int n,s,a,b,res;
    static long[][] biao;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();s=sc.nextInt();a=sc.nextInt();b=0-sc.nextInt();biao=new long[n][n];
        //f(1,0);System.out.println(res);
        dp();
    }
    public static void dp() {
        biao[0][0]=1;
        for(int i=1;i<n;i++) {
            for(int j=0;j<n;j++)
                biao[i][j]=(biao[i-1][(((j-i*a)%n)+n)%n]+biao[i-1][(j-i*b)%n])%100000007;
        }
        System.out.println(biao[n-1][((s%n)+n)%n]);//s可能取负值
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla


活动打卡代码 AcWing 1208. 翻硬币

import java.util.Scanner;
class Main{
    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);
        String a=sc.next();
        String b=sc.next();
        System.out.println(ditui(a.toCharArray(),b.toCharArray()));
    }
    public static int ditui(char[] a,char[] b) {
        int result=0;
        for(int i=0;i<a.length;i++) {
            if(a[i]==b[i])continue;
            else {
                if(a[i+1]=='*')a[i+1]='o';
                else a[i+1]='*';
                result++;
            }
        }
        return result;
    }
}


活动打卡代码 AcWing 788. 逆序对的数量

import java.util.Scanner;

public class Main {//这道题用归并的思想来做
    static int[] temps =  new int[100010];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();int[] arr = new int[n];
        for(int i=0;i<n;i++)arr[i]=sc.nextInt();
        System.out.println(merge(arr, 0, arr.length-1));
    }
    public static long merge(int[] arr,int l,int r) {       
        if(l>=r)return 0;
        int mid=l+r>>1,k=0,i=l,j=mid+1;
        long res=merge(arr,l,mid)+merge(arr,mid+1,r);
        while(i<=mid&&j<=r) {
            if(arr[i]<=arr[j]) {temps[k++]=arr[i++];}
            else {res+=mid-i+1;temps[k++]=arr[j++];}
        }
        while(i<=mid)temps[k++]=arr[i++];
        while(j<=r)temps[k++]=arr[j++];
        for(i=l,j=0;i<=r;i++,j++)arr[i]=temps[j];
        return res;
    }
}


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

import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();int[] arr = new int[n];
        while(--n>=0)arr[n]=sc.nextInt();
        sort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++)System.out.print(arr[i]+" ");
    }
    static int[] temps = new int[100010];
    public static void sort(int[] arr,int l,int r){
        if(l>=r)return;
        int mid=r+l>>1;
        sort(arr,l,mid);sort(arr,mid+1,r);
        int k=0,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(arr[i]<arr[j])temps[k++]=arr[i++];
            else temps[k++]=arr[j++];
        }
        while(i<=mid)temps[k++]=arr[i++];
        while(j<=r)temps[k++]=arr[j++];
        for(i=l,j=0;i<=r;i++,j++)arr[i]=temps[j];
    }
}


活动打卡代码 AcWing 786. 第k个数

import java.util.Scanner;
class Main{
    static public void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),k=sc.nextInt();
        int[] arr = new int[n];
        while(--n>=0)arr[n]=sc.nextInt();
        sort(arr,0,arr.length-1);
        System.out.println(arr[k-1]);

    }
    public static void sort(int[] arr,int l,int r){
        if(l>=r)return;
        int x=arr[l],i=l-1,j=r+1;
        while(i<j){
            do i++;while(arr[i]<x);
            do j--;while(arr[j]>x);
            if(i<j)swap(arr,i,j);
        }
        sort(arr,l,j);
        sort(arr,j+1,r);
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}


活动打卡代码 AcWing 785. 快速排序

import java.util.Scanner;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr = new int[n];
        while(--n>=0)arr[n]=sc.nextInt();
        quickSort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++)System.out.print(arr[i]+" ");
    }
    public static void quickSort(int[] arr,int l,int r){
        if(l>=r)return;
        int x=arr[l],i=l-1,j=r+1;
        while(i<j){
            do i++;while(arr[i]<x);
            do j--;while(arr[j]>x);
            if(i<j)swap(arr,i,j);
        }
        quickSort(arr,l,j);
        quickSort(arr,j+1,r);
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}



链接
因为整个排列没有重复的数字,所以这个区间的最大值-最小值=区间的长度-1时,这个区间排序后将是连续的
当S=aUb时,maxS=max(maxa,maxb),这样求出每个区间的最值

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++)arr[i]=sc.nextInt();
        f(arr);
    }
    public static void f(int[] arr) {
        int max,min,result=0;
        for(int i=0;i<arr.length-1;i++) {
            max=min=arr[i];
            for(int j=i+1;j<arr.length;j++)
                if((max=Math.max(arr[j],max))-(min=Math.min(arr[j],min))==j-i)result++; 
        }
        System.out.println(result+arr.length);
    }
}


活动打卡代码 AcWing 429. 奖学金

直接调库写

import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    static TreeSet<Student> tree = new TreeSet<Student>();
    static int num;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        while(n-->0) {
            tree.add(new Student(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }
        Iterator< Student> it = tree.iterator();
        for(int i=0;i<5;i++) System.out.println(it.next());
    }

}
class Student implements Comparable<Student>{
    int id;
    int YuWen,Count;
    Student(int YuWen,int ShuXue,int YinYu){
        this.id=++Main.num;
        this.YuWen=YuWen;
        this.Count=YuWen+ShuXue+YinYu;
    }
    public int compareTo(Student o) {
        if(this.Count!=o.Count)return o.Count-this.Count;//这样写是降序
        else {
            if(this.YuWen!=o.YuWen)return o.YuWen-this.YuWen;
            else return this.id-o.id;//id是要升序
        }
    }
    public String toString() {
        return this.id+" "+this.Count;
    }
}

手写排序单链表,在插入元素时,有序插入

import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    static TreeSet<Student> tree = new TreeSet<Student>();
    static int num;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        while(n-->0) {
            StudentLinked.add(new Student(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }
        Student stu = StudentLinked.head;
        for(int i=0;i<5;i++) {
            stu=stu.next;
            System.out.println(stu);
        }
    }
}
class Student implements Comparable<Student>{
    int id;
    int YuWen,Count;
    Student before,next;
    Student(){}
    Student(int YuWen,int ShuXue,int YinYu){
        this.id=++Main.num;
        this.YuWen=YuWen;
        this.Count=YuWen+ShuXue+YinYu;
    }
    public int compareTo(Student o) {
        if(this.Count!=o.Count)return o.Count-this.Count;//这样写是降序
        else {
            if(this.YuWen!=o.YuWen)return o.YuWen-this.YuWen;
            else return this.id-o.id;//id是要升序
        }
    }
    public String toString() {
        return this.id+" "+this.Count;
    }
}
class StudentLinked{
    static Student head = new Student(),p;
    static void add(Student s) {
        p=head;
        int flag=0;
        while(p.next!=null) {
            if(p.next.compareTo(s)>0) {s.next=p.next;p.next=s;flag=1;break;}
            else p=p.next;
        }
        if(flag==0)p.next=s;
    }
}