头像

昆卡

1




离线:1个月前


最近来访(2)
用户头像
Antonioxv
用户头像
Deepsea


昆卡
4个月前

···
import java.util.*;

public class Main{
static int N = 110,n;
static double eps = 1e-6;
static double[][] a = new double[N][N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=0;i[HTML_REMOVED]Math.abs(a[t][c])) t=i;
}
if(Math.abs(a[t][c])[HTML_REMOVED]=c;i–) a[r][i]/=a[r][c];
for(int i=r+1;i[HTML_REMOVED]eps)
for(int j=n;j>=c;j–) a[i][j]-=a[r][j]*a[i][c];
}

        r++;
    }
    if(r<n){
       for(int i=r;i<n;i++) if(Math.abs(a[i][n])>eps) return 2;
        return 1;
    }
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++) a[i][n] -= a[i][j]*a[j][n];
    }
    return 0;
}
 public static int guass(){
   int r,c;
   //遍历每一列
    for(r=0,c=0;c<n;c++){
        int t=r;
        //找一列中的最大值
        for(int i=r;i<n;i++){
            if(Math.abs(a[i][c])>Math.abs(a[t][c])){
                t=i;
            }
        }
        //如果找出的最大值为0,继续下一列寻找非0的最大值
        if(Math.abs(a[t][c])<eps)continue;
        //交换
        for(int i=c;i<=n;i++){
            double temp=a[t][i];
            a[t][i]=a[r][i];
            a[r][i]=temp;
        }

        //将当前的非0第一位数置为1,构造阶梯矩阵的斜边
        //这里要注意从后往前去更新数据,因为这里变化是根据第一个数变化的,要保持它的数据最后变化或者找个数存一下
        for(int i=n;i>=c;i--){
            a[r][i]/=a[r][c];
        }
        //下面一步就是用上面那一行来更新下面的所有行,同样要注意从后往前更新数据
        //注意只需要对首位非0的行进行更新就行
        for(int i=r+1;i<n;i++){
            if(Math.abs(a[i][c])>eps) {
            for(int j=n;j>=c;j--){
                   a[i][j]-=a[r][j]*a[i][c];

               }
            }
        }

        //进行下一行的处理
        r++;
    }
    //0解或者无穷解
    if(r<n){
        //阶梯状,更新不了下面的说明往下的都是0;判断下面每一行的最后结果,如果不是0,说明无解
        for(int i=r;i<n;i++){
            if(Math.abs(a[i][n])>eps)return 2;
        }
        return 1;
    }
    //处理唯一解,从下往上得出解
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]-=a[j][n]*a[i][j];//a[j][n]这里的横坐标为j是因为需要从这一行往下清空干净,可以举个3*4的例子
        }
    }
    //唯一解
    return 0;
}

}
···




昆卡
4个月前
import java.util.*;
import java.io.*;

public class Main{
    public static int N = 100010,n,m;
    public static void main(String[] args) throws Exception{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        for(int i=0;i<n;i++){
            in.nextToken();
            int u = (int)in.nval;
            int c =0;
            while(u!=0){
                c++;
                u-=(u&(-u));
            }
            out.print(c+" ");
        }
        out.flush();
    }

}



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

昆卡
4个月前
//分治思想
//在归并排序途中,如有遇到左边比右边大,就让答案加上mid-i+1
import java.util.*;
import java.io.*;

public class Main{
    public static int N = 100010,n,m;
    static long res;
    static int[] f = new int[N];
    public static void main(String[] args) throws Exception{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        for(int i=1;i<=n;i++){
            in.nextToken();
            f[i]=(int)in.nval;
        }
        merge(1,n);
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++){
            sb.append(f[i]+" ");
        }
        System.out.print(res);
    }
    public static void merge(int l,int r){
        if(l>=r) return;
        int mid=l+r>>1;
        merge(l,mid);
        merge(mid+1,r);
        int[] g = new int[r];
        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){
            if(f[i]<=f[j]) g[k++] = f[i++];
            else {
                g[k++] = f[j++];
                res+=mid-i+1;

            }
        }
       while(i<=mid){
            g[k++] = f[i++];
        }
        while(j<=r){
            g[k++] = f[j++];
        }
        for(i=l,j=0;i<=r;i++,j++){
            f[i] = g[j];
        }
    }

}



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

昆卡
4个月前
import java.util.*;
import java.io.*;

public class Main{
    public static int N = 100010,n,m;
    static int[] f = new int[N];
    public static void main(String[] args) throws Exception{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        for(int i=1;i<=n;i++){
            in.nextToken();
            f[i]=(int)in.nval;
        }
        merge(1,n);
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++){
            sb.append(f[i]+" ");
        }
        System.out.print(sb.toString().trim());
    }
    public static void merge(int l,int r){
        if(l>=r) return;
        int mid=l+r>>1;
        merge(l,mid);
        merge(mid+1,r);
        int[] g = new int[r];
        int i=l,j=mid+1,k=0;
        while(i<=mid&&j<=r){
            if(f[i]<f[j]) g[k++] = f[i++];
            else g[k++] = f[j++];
        }
       while(i<=mid){
            g[k++] = f[i++];
        }
        while(j<=r){
            g[k++] = f[j++];
        }
        for(i=l,j=0;i<=r;i++,j++){
            f[i] = g[j];
        }
    }

}



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

昆卡
4个月前
import java.util.*;
import java.io.*;

public class Main{
    public static int N = 100010,n,m;
    static int[] f = new int[N];
    public static void main(String[] args) throws Exception{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n=(int)in.nval;
        for(int i=1;i<=n;i++){
            in.nextToken();
            f[i]=(int)in.nval;
        }
        quick(1,n);
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++){
            sb.append(f[i]+" ");
        }
        System.out.print(sb.toString().trim());
    }
    public static void quick(int l,int r){
        if(l>=r) return;
        int i= l-1,j=r+1,x= f[l+r>>1];
        while(i<j){
            do{i++;}while(f[i]<x);
            do{j--;}while(f[j]>x);
            if(i<j){
                int t =f[j];
                f[j] = f[i];
                f[i] = t;
            }
        }
        quick(l,j);
        quick(j+1,r);
    }

}



活动打卡代码 AcWing 838. 堆排序

昆卡
4个月前
import java.util.*;
import java.io.*;

public class Main{
    static int N=100010,n,m;
    static int[] heap = new int[N];
    public static void main(String[] args) throws Exception{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int)in.nval;
        in.nextToken();
        m = (int)in.nval;
        for(int i=1;i<=n;i++){
            in.nextToken();
            heap[i]= (int)in.nval;
        }
        for(int i=n/2;i!=0;i--) down(i);
        StringBuilder sb = new StringBuilder();
        while(m!=0){
            sb.append(heap[1]+" ");
            m--;
            heap[1] = heap[n--];
            down(1);
        }
        System.out.print(sb.toString().trim());
    }
    public static void up(int x){//大根堆
        int u = x;
        if(2*x<=n&&heap[2*x]>heap[u]) u=2*x;
        if(2*x+1<=n&&heap[2*x+1]>heap[u]) u=2*x+1;
        if(u!=x){
            int t = heap[u];
            heap[u] = heap[x];
            heap[x] = t;
            up(u);
        }
    }
    public static void down(int x){//x是节点编号
        int u = x;
        if(2*x<=n&&heap[2*x]<heap[u]) u=2*x;
        if(2*x+1<=n&&heap[2*x+1]<heap[u]) u=2*x+1;
        if(u!=x){
            int t = heap[u];
            heap[u] = heap[x];
            heap[x] = t;
            down(u);
        }
    }
}



昆卡
5个月前
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++){
            int x = sc.nextInt();
            if(isprim(x)) System.out.println("Yes");
            else System.out.println("No");
        }
    }
    public static boolean isprim(int n){
        if(n<2) return false;
        for(int i=2;i<=n/i;i++){
            if(n%i==0) return false;
        }
        return true;
    }
}


活动打卡代码 AcWing 2060. 奶牛选美

昆卡
5个月前

···
import java.util.;
import java.io.
;

//将两个斑点内的所有点都记录下来,对两个斑点内的所有点进行枚举,
//求最短曼哈顿距离(两个端点之间x的水平距离加上y的垂直距离)就是答案
public class Main{
static int N = 55,n,m,idx;
static int[][] g = new int[N][N],dir={{-1,0},{0,1},{1,0},{0,-1}};
static List[HTML_REMOVED] list1 = new ArrayList<>();
static List[HTML_REMOVED] list2 = new ArrayList<>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(” “);
n = Integer.valueOf(s[0]);
m = Integer.valueOf(s[1]);
for(int i=0;i<n;i){
String u = br.readLine();
for(int j=0;j<m;j
){
if(u.charAt(j)==’.’) g[i][j] = 0;
else g[i][j] = 1;
}
}
for(int i=0;i<n;i){
for(int j=0;j<m;j
){
if(g[i][j] == 1){
dfs(i,j);
idx;
}
}
}
int res = 0x3f3f3f3f;
for(int i=0;i<list1.size();i
){
for(int j=0;j<list2.size();j++){
node n1 = list1.get(i);
node n2 = list2.get(j);
int x1 = n1.x;
int y1 = n1.y;
int x2 = n2.x;
int y2 = n2.y;
res = Math.min(res,Math.abs(x1-x2)+Math.abs(y1-y2)-1);
}
}
System.out.print(res);

}
public static void dfs(int x,int y){
    g[x][y] = 0;
    if(idx==0)
    list1.add(new node(x,y));
    else list2.add(new node(x,y));
    for(int i=0;i<4;i++){
        int dx = x+dir[i][0],dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&g[dx][dy]==1){
            dfs(dx,dy);
        }
    }
}

}
class node{
public int x,y;
public node(int x,int y){
this.x=x;
this.y=y;
}
}
···



活动打卡代码 AcWing 872. 最大公约数

昆卡
5个月前
import java.util.*;

public class Main{
    static int n;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i=0;i<n;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(gcd(a,b));
        }
    }
    public static int gcd(int a,int b){
        return b!=0 ? gcd(b,a%b):a;
    }
}



昆卡
5个月前
import java.util.*;

public class Main{
    static int N = 100010,n,m,idx,cnt;
    static int[] h = new int[N],ne = new int[N],val=new int[N],d=new int[N],ans= new int[N];
    static Queue<Integer> qu = new LinkedList<>();
    public static void main(String[] args){
        Arrays.fill(h,-1);
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a,b);
            d[b]++;
        }
        for(int i=1;i<=n;i++){
            if(d[i]==0) qu.add(i);
        }
        while(!qu.isEmpty()){
            int x = qu.poll();
            ans[cnt++] = x;
            for(int i=h[x];i!=-1;i=ne[i]){
                int j =val[i];
                d[j]--;
                if(d[j]==0) qu.add(j);
            }
        }

        if(cnt!=n) System.out.print(-1);
        else{
            for(int i=0;i<cnt;i++){
                System.out.print(ans[i]+" ");
            }
        }
    }
    public static void add(int a,int b){
        ne[idx] = h[a];
        val[idx] = b;
        h[a] = idx++;
    }
}