头像

fly123


访客:138

离线:1天前



fly123
8天前
import java.util.*;
class Main{
    static int N=12;
    static int M=1<<N;
    static boolean[] st=new boolean[M];
    static long[][] f=new long[N][M];


    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(true){
            int n=sc.nextInt();
            int m=sc.nextInt();
            if(n==0&&m==0)break;
             ArrayList<ArrayList<Integer>> state=new ArrayList<ArrayList<Integer>>(); //每次都要刷新
            for(int i=0;i<(1<<n);i++){
                int cnt=0;
                boolean is_valid=true;//中间量用来暂存是否有效
                for(int j=0;j<n;j++){
                    if((i>>j&1)!=0){//当遇到1时说明连续的0结束了,然后判断一下0的个数,如果是奇数置为不合法
                        if((cnt&1)!=0){
                            is_valid=false;
                        break;//如果不合法,说明已经有连续0的个数是奇数,不满足条件了
                        }
                        cnt=0;
                    }
                    else{
                        cnt++;//计数0的个数
                    }
                }
                if((cnt&1)!=0)is_valid=false;
                st[i]=is_valid;
            }

            for(int i=0;i<(1<<n);i++){//预处理可以从前一列的状态转换到当前列的状态state
                ArrayList<Integer> list =new ArrayList<Integer>();
                for(int j=0;j<(1<<n);j++){
                    if((i&j)==0&&st[i|j]==true){
                        list.add(j);
                    }
                }
                state.add(list);//
            }

            for(int i=0;i<N;i++){//初始化状态数组
                Arrays.fill(f[i],0);
            }
            f[0][0]=1;//初始值为1,只可以是状态为0的

            for(int i=1;i<=m;i++){//
                for(int j=0;j<(1<<n);j++){
                    for(int x:state.get(j)){
                        f[i][j]+=f[i-1][x];//状态计算就是将前面的所有状态都累加起来。
                    }
                }
            }
            System.out.println(f[m][0]);//0-m-1列都已经填充完成,而且没有延申到m列的,说明恰好填满了。
        }
    }
}



fly123
16天前

import java.util.*;
//java中的Math.abs()可以用于浮点数取绝对值
//String.format("%.2f",x)  %.2f"为保留两位小数,x为要输出的数字
class Main{
    static int N=110;
    static double[][] a=new double[N][N+1];
    static int n=0;
    static double eps=0.000001;
    public static int guass(double[][] a){
       int row,col;
       //遍历每一列
        for(row=0,col=0;col<n;col++){
            int t=row;
            //找一列中的最大值
            for(int i=row;i<n;i++){
                if(Math.abs(a[i][col])>Math.abs(a[t][col])){
                    t=i;
                }
            }
            //如果找出的最大值为0,继续下一列寻找非0的最大值
            if(Math.abs(a[t][col])<eps)continue;
            //交换
            for(int i=col;i<=n;i++){
                double temp=a[t][i];
                a[t][i]=a[row][i];
                a[row][i]=temp;
            }

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

                   }
                }
            }

            //进行下一行的处理
            row++;
        }
        //0解或者无穷解
        if(row<n){
            //阶梯状,更新不了下面的说明往下的都是0;判断下面每一行的最后结果,如果不是0,说明无解
            for(int i=row;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;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        for(int i=0;i<n;i++){
            for(int j=0;j<=n;j++){
                a[i][j]=sc.nextDouble();
            }
        }
      int t=guass(a);
      if(t==0){
          for(int i=0;i<n;i++){
              System.out.println(String.format("%.2f",a[i][n]));
          }
      }
      else if(t==1){
             System.out.println("Infinite group solutions");
         }else{
             System.out.println("No solution");
         }
    }
}



fly123
1个月前

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String res="";//存放结果字符串
        for(int i=0;i<n;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            String s=sc.next();
            int length=s.length();
           ArrayList number=new ArrayList<>();//存放字符串中的数
            for(int j=0;j<length;j++){
                if(s.charAt(j)>='0'&&s.charAt(j)<='9')number.add(s.charAt(j)-'0');
                else if(s.charAt(j)>='A'&&s.charAt(j)<='Z')number.add(s.charAt(j)-'A'+10);
                else if(s.charAt(j)>='a'&&s.charAt(j)<='z')number.add(s.charAt(j)-'a'+36);
            }
            Collections.reverse(number);//
            ArrayList<Integer> ans=new ArrayList<>();//存放余数

           while(number.size()>0){
               int r=0;
               for(int k=number.size()-1;k>=0;k--){
                   int temp=(int)number.get(k)+a*r;//要将Integer向下转型为int,不然会报错
                   r=temp%b;
                   number.set(k,temp/b);//set方法的形参是(修改的索引位置,要修改为多少)
               }

              ans.add(r);
              while(number.size()>0&&number.get(number.size()-1).equals(0))number.remove(number.size()-1);//注意下标别越界,remove方法会删除元素,并且会更新size
           }
            Collections.reverse(ans);
            for(int x:ans){
                if(x>=0&&x<=9)res+=(char)(x+'0');//这里必须要加强转,不然会变成int型,结果会错
                if(x>=10&&x<=35)res+=(char)(x-10+'A');
                if(x>=36)res+=(char)(x-36+'a');
            }
             System.out.println(a+" "+s);
            System.out.println(b+" "+res);
        System.out.println();
            res="";//每次要将其重置,当然也可以放在循环里面,免得要重置了
        }
    }
}


活动打卡代码 AcWing 795. 前缀和

fly123
1个月前

前缀和

import java.util.*;

//前缀和:求前n项和,时间复杂度为O(n)
//作用:方便求取数组中一段数字的和,比如l到r
//公式:s[r]-s[l-1]
//注意在存时,从下标1开始存,方便公式的统一化,不然第一个的前缀和就不能用公式来做,就需要单独分开考虑了
class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int[] a=new int[n+1];
int[] s=new int[n+1];
// s[0]=0;
for(int i=1;i<=n;i)a[i]=sc.nextInt();
for(int i=1;i<=n;i
)s[i]=s[i-1]+a[i];
for(int i=0;i<m;i++){
int l=sc.nextInt();
int r=sc.nextInt();
System.out.println(s[r]-s[l-1]);
}
}
}