头像

硬拉tom


访客:775

在线 



java 代码

import java.util.*;
public class Main{
    static int N=300010;
    static int[] a=new int[N];
    static int[] s=new int[N];//前缀和数组
    static List<int[]> adds=new ArrayList<>();
    static List<int[]> querys=new ArrayList<>();//所有询问
    static List<Integer> ids=new ArrayList<>();//所有用到的下标
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<n;i++){
            int x=sc.nextInt();
            int c=sc.nextInt();
            adds.add(new int[]{x,c});
            ids.add(x);
        }
        for(int i=0;i<m;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            ids.add(l);
            ids.add(r);
            querys.add(new int[]{l,r});
        }
        Collections.sort(ids);//排序

        int j=0;
        for(int i=1;i<ids.size();i++){//去重
            if(ids.get(i)!=ids.get(j)){
                ids.set(++j,ids.get(i));
            }
        }

        for(int i=ids.size()-1;i>j;i--){//去重后删多余的元素
            ids.remove(ids.size()-1);
        }

        for(int[] t:adds){
            int x=find(t[0]);
            int c=t[1];
            a[x]+=c;
        }
        for(int i=1;i<=ids.size();i++){//处理前缀和数组
            s[i]=s[i-1]+a[i];
        }

        for(int[] t:querys){
            int l=find(t[0]);
            int r=find(t[1]);
            System.out.println(s[r]-s[l-1]+" ");
        }

    }
    static int find(int x){//二分找元素离散化后的下标
        int l=0,r=ids.size()-1,mid;
        while(l<r){
            mid=l+(r-l)/2;
            if(ids.get(mid) < x){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l+1;//下标从1开始,所以加1
    }
}


活动打卡代码 AcWing 802. 区间和

import java.util.*;
public class Main{
    static int N=300010;
    static int[] a=new int[N];
    static int[] s=new int[N];//前缀和数组
    static List<int[]> adds=new ArrayList<>();
    static List<int[]> querys=new ArrayList<>();//所有询问
    static List<Integer> ids=new ArrayList<>();//所有用到的下标
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=0;i<n;i++){
            int x=sc.nextInt();
            int c=sc.nextInt();
            adds.add(new int[]{x,c});
            ids.add(x);
        }
        for(int i=0;i<m;i++){
            int l=sc.nextInt(),r=sc.nextInt();
            ids.add(l);
            ids.add(r);
            querys.add(new int[]{l,r});
        }
        Collections.sort(ids);//排序

        int j=0;
        for(int i=1;i<ids.size();i++){//去重
            if(ids.get(i)!=ids.get(j)){
                ids.set(++j,ids.get(i));
            }
        }

        for(int i=ids.size()-1;i>j;i--){//去重后删多余的元素
            ids.remove(ids.size()-1);
        }

        for(int[] t:adds){
            int x=find(t[0]);
            int c=t[1];
            a[x]+=c;
        }
        for(int i=1;i<=ids.size();i++){//处理前缀和数组
            s[i]=s[i-1]+a[i];
        }

        for(int[] t:querys){
            int l=find(t[0]);
            int r=find(t[1]);
            System.out.println(s[r]-s[l-1]+" ");
        }

    }
    static int find(int x){//二分找元素离散化后的下标
        int l=0,r=ids.size()-1,mid;
        while(l<r){
            mid=l+(r-l)/2;
            if(ids.get(mid) < x){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return l+1;//下标从1开始,所以加1
    }
}



活动打卡代码 AcWing 798. 差分矩阵

import java.util.*;
import java.io.*;
public class Main{
    static int N=1010;
    static int M=1010;
    static int[][] a=new int[N][M];//原数组
    static int[][] b=new int[N][M];//差分数组    
    public static void main(String[] args) throws Exception{
        Scanner sc=new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                insert(i,j,i,j,sc.nextInt());
            }
        }
        int x1,y1,x2,y2,c;
        for(int i=0;i<q;i++){
            x1=sc.nextInt();
            y1=sc.nextInt();
            x2=sc.nextInt();
            y2=sc.nextInt();
            c=sc.nextInt();
            insert(x1,y1,x2,y2,c);
        }
        for(int i=1;i<=n;i++){//对差分数组求前缀和即是原数组
            for(int j=1;j<=m;j++){
                b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
                bw.write(b[i][j]+" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();

    }
    static void insert(int x1,int y1,int x2,int y2,int c){
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;
    }
}


活动打卡代码 AcWing 797. 差分

import java.util.*;
public class Main{
    static int N=100010;
    static int[] a=new int[N];//前缀数组     ai=b1+b2+...bi
    static int[] b=new int[N];//差分数组
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();

        }
        for(int i=1;i<=n;i++){
            insert(i,i,a[i]);
        }
        for(int i=1;i<=m;i++){
            insert(sc.nextInt(),sc.nextInt(),sc.nextInt());
        }
        for(int i=1;i<=n;i++){
            b[i]+=b[i-1];
            System.out.print(b[i]+" ");
        }
    }
    static void insert(int l,int r,int c){
        b[l]+=c;
        b[r+1]-=c;
    }
}



java 代码


import java.util.*;
public class Main{
    static int N=100010;
    static int[] a=new int[N];
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        qsort(a,0,n-1);
        for(int i=0;i<n;i++){
            System.out.print(a[i]+" ");
        }
    }
    static void qsort(int[] a,int s,int e){
        if(s>=e){
            return;
        }
        int b=a[s+(e-s)/2],i=s-1,j=e+1,t;//下面i是先自增再判断,j先自减再判断,所以i=s-1,j=e+1
        while(i<j){
            do i++;
            while(a[i] < b);

            do j--;
            while(a[j] > b);

            if(i<j){
                t=a[j];
                a[j]=a[i];
                a[i]=t;
            }
        }
        qsort(a,s,j);//此时i>j,所以此处j不能换成i
        qsort(a,j+1,e);
    }
}


活动打卡代码 AcWing 796. 子矩阵的和

import java.util.*;
import java.io.*;
public class Main{
    static int N=1010;
    static int M=1010;
    static int[][] a=new int[N][M];
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String[] t;
        t=br.readLine().split(" ");
        int n=Integer.valueOf(t[0]);
        int m=Integer.valueOf(t[1]);
        int p=Integer.valueOf(t[2]);
        for(int i=1;i<=n;i++){
            t=br.readLine().split(" ");
            for(int j=1;j<=m;j++){
                a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+Integer.valueOf(t[j-1]); //  s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + n
            }
        }
        int x1,y1,x2,y2;
        for(int i=0;i<p;i++){
            t=br.readLine().split(" ");
            x1=Integer.valueOf(t[0]);
            y1=Integer.valueOf(t[1]);
            x2=Integer.valueOf(t[2]);
            y2=Integer.valueOf(t[3]);
            bw.write((a[x2][y2] - a[x2][y1-1] -a[x1-1][y2] + a[x1-1][y1-1])+"\n");  //二维前缀和公式  左上角x1,y1 到右下角x2,y2的元素和= s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]
        }
        bw.close();
        br.close();
    }
}



java 代码

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        System.out.println(add(sc.next(),sc.next()));
    }
    static String add(String A,String B){
        if(A.length() < B.length()){
            return add(B,A);
        }
        int n=A.length(),m=B.length(),t=0;//t进位
        List<Integer> c=new ArrayList<>();//下标0是个位
        for(int i=n-1,j=m-1;i>=0;i--){
            t+=A.charAt(i)-'0';
            if(j>=0){
                t+=B.charAt(j--)-'0';
            }
            c.add(t%10);
            t/=10;
        }
        if(t>0){
            c.add(t);
        }
        StringBuilder sb=new StringBuilder();
        for(int i=c.size()-1;i>=0;i--){
            sb.append(c.get(i));
        }
        return sb.toString();
    }

}



java 代码

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        div(sc.next(),sc.next());
    }
    static void div(String A,String B){
        int n=A.length(),b=Integer.valueOf(B),r=0;//r余数
        List<Integer> c=new ArrayList<>();//下标0是个位
        for(int i=0;i<n;i++){
            r=r*10+A.charAt(i)-'0';
            c.add(r/b);
            r%=b;
        }
        Collections.reverse(c);//翻转
        while(c.size()>1 && c.get(c.size()-1)==0){//去掉前导0
            c.remove(c.size()-1);
        }
        StringBuilder sb=new StringBuilder();
        for(int i=c.size()-1;i>=0;i--){
            sb.append((char)(c.get(i)+'0'));
        }
        System.out.println(sb.toString());
        System.out.println(r+"");
    }
}


活动打卡代码 AcWing 794. 高精度除法

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        div(sc.next(),sc.next());
    }
    static void div(String A,String B){
        int n=A.length(),b=Integer.valueOf(B),r=0;//r余数
        List<Integer> c=new ArrayList<>();//下标0是个位
        for(int i=0;i<n;i++){
            r=r*10+A.charAt(i)-'0';
            c.add(r/b);
            r%=b;
        }
        for(int i=0,j=c.size()-1;i<j;i++,j--){//翻转数组
            int t=c.get(i);
            c.set(i,c.get(j));
            c.set(j,t);
        }
        while(c.size()>1 && c.get(c.size()-1)==0){//去掉前导0
            c.remove(c.size()-1);
        }
        StringBuilder sb=new StringBuilder();
        for(int i=c.size()-1;i>=0;i--){
            sb.append((char)(c.get(i)+'0'));
        }
        System.out.println(sb.toString());
        System.out.println(r+"");
    }
}



硬拉tom
10天前

java 代码

import java.util.*;
public class Main{
    static List<Integer> c=new ArrayList<>();
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        System.out.println(mul(sc.next(),sc.next()));
    }
    static String mul(String a,String b){
        int n=a.length(),j=Integer.valueOf(b),t=0;//t是进位值
        for(int i=n-1;i>=0||t>0;i--){
            if(i>=0){
                t+=j*(a.charAt(i)-'0');
            }
            c.add(t%10);
            t/=10;
        }
        while(c.size()>1 && c.get(c.size()-1)==0){//去掉前导0
            c.remove(c.size()-1);
        }
        StringBuilder sb=new StringBuilder();
        for(int i=c.size()-1;i>=0;i--){
            sb.append((char)(c.get(i)+'0'));
        }
        return sb.toString();
    }
}