头像

CYHMMZDAN




离线:5小时前


最近来访(24)
用户头像
77777777777
用户头像
dqsjysgs
用户头像
吴晓冉
用户头像
小菜鸡--坤坤
用户头像
yxc的小迷妹
用户头像
爱算法爱生活
用户头像
wxy.
用户头像
𐂂暮杪十二
用户头像
xiaoYun
用户头像
violet_garden
用户头像
000111
用户头像
是一个行了的杨杨
用户头像
xiangjing
用户头像
戏子.
用户头像
Akarikito
用户头像
incra
用户头像
Jettblue
用户头像
自学IT林学人
用户头像
巷港
用户头像
acwhr


CYHMMZDAN
6小时前

算法2

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

java 代码

n=Scanf_Int();
        m=Scanf_Int();
        if (m==n){
            out.println(0);
            out.close();
            System.exit(0);
        }
        m1=Math.abs(n-m);
        while (m1!=0){
            if (m1>0){
                l++;
                m1--;
                sum+=l;
            }
            if (m1>0){
                r++;
                m1--;
                sum+=r;
            }
        }
        out.println(sum);



CYHMMZDAN
7小时前

算法2

java 代码

import java.io.*;
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.text.Format;
import java.text.SimpleDateFormat;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Map;
import java.util.HashMap;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static StringBuilder stringBuilder = new StringBuilder();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static String s = "";
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int n = 0;
    static int min = (int) 2e9;
    static int sum = 0;
    static long sum1 = 0;
    static int max = -1;
    static int m1=0;
    static int m2=0;
    static int m3=0;
    static int m = 0;
    static int ans = 0;
    static int l = 0;
    static int r = 0;
    StringBuilder stringBuilder1=new StringBuilder();
    static Map<Map<Integer,Integer> ,Integer> map= new TreeMap<Map<Integer, Integer>, Integer>();
    static Map<Integer,Integer> map1= new TreeMap<>();
    static Map<Integer,Integer> map2= new TreeMap<>();
    static Map<String,Integer> map3= new TreeMap<>();
    static int[] h = new int[(int) (5e+5)];
    static boolean[] booleans=new boolean[101];
    static int[][] b2 = new int[1000][1000];
    static int[] dp = new int[10005];
    static int[][] pd = new int[6][6];
    static int[][] fs = new int[6][6];
    static int[] a=new int[1000];
    static int[] f=new int[2022];
    static int[] b=new int[1000];
    static int[] a1={0,1,-1,0,0};
    static int[] b1={0,0,0,1,-1};
    static String[] s1=new String[1005];
    static Set<String> set=new TreeSet<>();
    static Stack<String> stack=new Stack<>();
    static Queue<Integer> queun=new LinkedList<Integer>();//单队列
    static Deque<Integer> deque=new ArrayDeque<>();//双队列
    static PriorityQueue<Integer> xiao = new PriorityQueue();
    static PriorityQueue<Integer> xiao1 = new PriorityQueue();
    static PriorityQueue<Integer> xiao2 = new PriorityQueue();
    static PriorityQueue<Integer> da_1 = new PriorityQueue(Collections.reverseOrder());
    static PriorityQueue<Long> da = new PriorityQueue(Collections.reverseOrder());
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        n=Scanf_Int();
        Node[] nodes=new Node[n];
        for (int i=0;i<n;i++){
             String s=Scanf_String();
             String s1=Scanf_String();
             if (s1.equals("rat")){
                 m=1;
             }
             else if (s1.equals("woman")||s1.equals("child")){
                 m=2;
             }
             else if (s1.equals("man")){
                 m=3;
             }
             else {
                 m=4;
             }
             nodes[i]=new Node(s,m,i);
        }
        Arrays.sort(nodes);
        for (int i=0;i<n;i++){
            out.println(nodes[i].s);
        }
        out.close();
    }

    public static void dfs(char[][] matrix, String str,int k,int y,int count) {
        if (count==str.length()){
            if (stringBuilder.toString().equals(str)){
                m=1;
            }
            else {
                return;
            }
        }
        if (m==1||count>str.length()){
            return;
        }
        for (int i=1;i<=4;i++){
            int l=k+a1[i];
            int r=y+b1[i];
            if (l>=0&&l<matrix.length&&r>=0&&r<matrix[0].length&&b2[l][r]==0){

                b2[l][r]=1;
                stringBuilder.append(matrix[l][r]);
                dfs(matrix,str,l,r,count+1);
                b2[l][r]=0;
                stringBuilder.delete(count,count+1);
            }
        }
    }
    public static boolean hasPath(char[][] matrix, String str) {

        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==str.charAt(0)) {
                    b2[i][j] = 1;
                    stringBuilder.append(matrix[i][j]);
                    dfs(matrix, str, i, j, 1);
                    b2[i][j] = 0;
                    stringBuilder.delete(0, 1);
                    if (m == 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static int dfs(int[][] a, int k,int y){
        if (b2[k][y]!=0){
            return b2[k][y];
        }
        b2[k][y]=1;
        for (int i=1;i<=4;i++){
            l=k+a1[i];
            r=y+b1[i];
            if (l>0&&l<=n&&r>0&&r<=n&&a[l][r]>a[k][y]){
                b2[k][y]=Math.max(b2[k][y],dfs(a,l,r)+1);
            }
        }
        return b2[k][y];
    }
    public static int max_4(int a,int b,int c,int d){
        int[] f=new int[5];
        f[1]=a;
        f[2]=b;
        f[3]=c;
        f[4]=d;
        Arrays.sort(f,1,5);
        return f[4];
    }
    public static int mod(int i,int n){
        return i%n;
    }
    public static boolean pd_sushu(int x){
        for (int i=2;i*i<=x;i++){
            if ((x%i)==0){
                return false;
            }
        }
        return true;
    }
    public static int find_daiquan(int n,int[] f,int[] front){
        if(f[n]==n)return f[n];
        int fn=find_daiquan(f[n],f,front);
        front[n]+=front[f[n]];
        return f[n]=fn;
    }
    public static int find_dei(int x,int[] f){
        if (f[x]==x){
            return x;
        }
        return f[x]=find_dei(f[x],f);
    }
    public static void unity1(int x,int y,int[] f,int[] z){
        int a=find_daiquan(x,f,z);
        int b=find_daiquan(y,f,z);
        f[a]=b;
    }

    public static void unity(int x,int y,int[] f){
        int a=find_dei(x,f);
        int b=find_dei(y,f);
        f[a]=b;
    }
    public static void add(int a,int b,int v,Node[] nodes){
        if (v==0){
            nodes[b].w=a;
            nodes[b].q=nodes[a].q;
            nodes[a].q=b;
            nodes[nodes[b].q].w=b;
        }
        else {
            nodes[b].q=a;
            nodes[b].w=nodes[a].w;
            nodes[a].w=b;
            nodes[nodes[b].w].q=b;
        }
    }
    public static void jian(int a,Node[] nodes){
        for (int i=nodes[0].w;i!=0;i=nodes[i].w){
            if (i==a){
                nodes[nodes[i].w].q=nodes[i].q;
                nodes[nodes[i].q].w=nodes[i].w;
            }
        }
    }

    public static long ef1(int[] a,int[] b ,int l,int r,int x){
        sum=0;
        int mid = (l + r) / 2;
        if (l>r){
            return sum;
        }
        if (b[x]<=a[1]){
            sum+=(a[1]-b[x]);
            return sum;
        }
        if (b[x]>=a[n]){
            sum+=(b[x]-a[n]);
            return sum;
        }
        if (b[x] >= a[mid - 1] && b[x] <= a[mid]) {
            sum += Math.min(a[mid] - b[x], b[x] - a[mid - 1]);
            return sum;
        }
        if (b[x]<a[mid]&&b[x]<a[mid-1]){
            return ef1(a,b,l,mid-1,x);
        }
        if (b[x]>a[mid]&&b[x]>a[mid-1]){
            return ef1(a,b,mid+1,r,x);
        }
        return sum;
    }

    public static int gys(int a,int b){
        if (a==0||b==0){
            return 0;
        }
        if (a%b==0){
            return b;
        }
        return gys(b,a%b);
    }

    public static int gbs(int a,int b){

        return a*b/gys(a,b);

    }

    public static long ks_mod(long a,long b){
        if (b==0){
            return 1%m1;
        }
        long x=1,y=a;
        while (b>0){
            if ((b&1)==1){
                x*=y;
                x%=m1;
            }
            y*=y;
            y%=m1;
            b>>=1;
        }
        return x;
    }

    public static double log2(int n){
        return Math.log(n)/Math.log(2);
    }

    public static void gb(int l,int r){
        if (l==r){
            return;
        }
        int mid=(l+r)/2;
        int z=mid+1,k=l,x=l,p=l;
        gb(l,mid);
        gb(mid+1,r);
        while (k<=mid&&z<=r){
            if (a[k]<=a[z]){
                b[x++]=a[k++];
            }
            else {
                b[x++]=a[z++];
                sum+=mid+1-k;
            }
        }
        while (k<=mid){
            b[x++]=a[k++];
        }
        while (z<=r){
            b[x++]=a[z++];
        }
        for (int i=l;i<=r;i++){
            a[i]=b[i];
        }
    }

    public static void cr(long[] a){
        for (int i=1;i<a.length;i++){
            long b=a[i];
            int b1=i-1;
            while (b1>=0&&b>a[b1]){
                a[b1+1]=a[b1];
                b1--;
            }
            a[b1+1]=b;
        }
    }

    static int Scanf_Int() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static long Scanf_Long() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    static double Scanf_Double() throws  IOException{
        in.nextToken();
        return in.nval;
    }
    static char Scanf_Char()throws IOException{//输入字符后可以空格,也可以换行
        in.nextToken();
        return in.sval.charAt(0);
    }
    static String Scanf_String() throws IOException{
        /*
         ***输入的字符串有空格的不能用这个***
         不能用这个来转变为字符数组和字符串数组,用bf.readLine();
         输入字符串后可以空格,也可以换行*/
        in.nextToken();
        return in.sval;
    }
}
class Node implements Comparable<Node> {
    int q,w;
    double e;
    String s;
    String s1;

    public Node(String s, String s1) {
        this.s = s;
        this.s1 = s1;
    }

    public Node( String s,int q, int w) {
        this.q = q;
        this.w = w;
        this.s = s;
    }

    public Node(int q, int w) {
        this.q = q;
        this.w = w;
    }

    public Node(int q, String s) {
        this.q = q;
        this.s = s;
    }

    public Node(int q, int w, double e) {
        this.q = q;
        this.w = w;
        this.e = e;
    }

    @Override
    public int compareTo(Node o) {
        if (o.q==this.q){
            return this.w-o.w;
        }
        else {
            return this.q-o.q;
        }
    }
}
class Node1 implements Comparable<Node1>{
    int t,l,r,x;
    long f;
    String s;

    public Node1( long f,int l) {
        this.l = l;
        this.f = f;
    }

    public Node1(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public Node1(int t, int x, String s) {
        this.t = t;
        this.x = x;
        this.s = s;
    }

    @Override
    public int compareTo(Node1 o) {
        return o.t-this.t;
    }




CYHMMZDAN
9小时前

算法2

这么少的代码,点个赞呗

java 代码

 n=Scanf_Int();
        for (int i=1;i<n;i++){
            f[i]=Scanf_Int();
        }
        l=Scanf_Int();
        r=Scanf_Int();
        for (int i=l;i<=r-1;i++){
            sum+=f[i];
        }
        out.println(sum);



CYHMMZDAN
9小时前

算法2

java 代码

import java.io.*;
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.text.Format;
import java.text.SimpleDateFormat;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Map;
import java.util.HashMap;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static StringBuilder stringBuilder = new StringBuilder();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static String s = "";
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int n = 0;
    static int min = (int) 2e9;
    static int sum = 0;
    static long sum1 = 0;
    static int max = -1;
    static int m1=0;
    static int m2=0;
    static int m3=0;
    static int m = 0;
    static int ans = 0;
    static int l = 0;
    static int r = 0;
    StringBuilder stringBuilder1=new StringBuilder();
    static Map<Map<Integer,Integer> ,Integer> map= new TreeMap<Map<Integer, Integer>, Integer>();
    static Map<Integer,Integer> map1= new TreeMap<>();
    static Map<Integer,Integer> map2= new TreeMap<>();
    static Map<String,Integer> map3= new TreeMap<>();
    static int[] h = new int[(int) (5e+5)];
    static boolean[] booleans=new boolean[101];
    static int[][] b2 = new int[1000][1000];
    static int[] dp = new int[10005];
    static int[][] pd = new int[6][6];
    static int[][] fs = new int[6][6];
    static int[] a=new int[1000];
    static int[] f=new int[2022];
    static int[] b=new int[1000];
    static int[] a1={0,1,-1,0,0};
    static int[] b1={0,0,0,1,-1};
    static String[] s1=new String[1005];
    static Set<String> set=new TreeSet<>();
    static Stack<String> stack=new Stack<>();
    static Queue<Integer> queun=new LinkedList<Integer>();//单队列
    static Deque<Integer> deque=new ArrayDeque<>();//双队列
    static PriorityQueue<Integer> xiao = new PriorityQueue();
    static PriorityQueue<Integer> xiao1 = new PriorityQueue();
    static PriorityQueue<Integer> xiao2 = new PriorityQueue();
    static PriorityQueue<Integer> da_1 = new PriorityQueue(Collections.reverseOrder());
    static PriorityQueue<Long> da = new PriorityQueue(Collections.reverseOrder());
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        char[] c=bf.readLine().toCharArray();
        for (int i=0;i<c.length;i++){
            dp[c[i]-48]++;
        }
        for (int i=0;i<=100;i++){
            if (dp[i]!=0){
                sum1+=Math.pow(dp[i],2);
            }
        }
        out.println(sum1);
        out.close();
    }

    public static void dfs(char[][] matrix, String str,int k,int y,int count) {
        if (count==str.length()){
            if (stringBuilder.toString().equals(str)){
                m=1;
            }
            else {
                return;
            }
        }
        if (m==1||count>str.length()){
            return;
        }
        for (int i=1;i<=4;i++){
            int l=k+a1[i];
            int r=y+b1[i];
            if (l>=0&&l<matrix.length&&r>=0&&r<matrix[0].length&&b2[l][r]==0){

                b2[l][r]=1;
                stringBuilder.append(matrix[l][r]);
                dfs(matrix,str,l,r,count+1);
                b2[l][r]=0;
                stringBuilder.delete(count,count+1);
            }
        }
    }
    public static boolean hasPath(char[][] matrix, String str) {

        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==str.charAt(0)) {
                    b2[i][j] = 1;
                    stringBuilder.append(matrix[i][j]);
                    dfs(matrix, str, i, j, 1);
                    b2[i][j] = 0;
                    stringBuilder.delete(0, 1);
                    if (m == 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static int dfs(int[][] a, int k,int y){
        if (b2[k][y]!=0){
            return b2[k][y];
        }
        b2[k][y]=1;
        for (int i=1;i<=4;i++){
            l=k+a1[i];
            r=y+b1[i];
            if (l>0&&l<=n&&r>0&&r<=n&&a[l][r]>a[k][y]){
                b2[k][y]=Math.max(b2[k][y],dfs(a,l,r)+1);
            }
        }
        return b2[k][y];
    }
    public static int max_4(int a,int b,int c,int d){
        int[] f=new int[5];
        f[1]=a;
        f[2]=b;
        f[3]=c;
        f[4]=d;
        Arrays.sort(f,1,5);
        return f[4];
    }
    public static int mod(int i,int n){
        return i%n;
    }
    public static boolean pd_sushu(int x){
        for (int i=2;i*i<=x;i++){
            if ((x%i)==0){
                return false;
            }
        }
        return true;
    }
    public static int find_daiquan(int n,int[] f,int[] front){
        if(f[n]==n)return f[n];
        int fn=find_daiquan(f[n],f,front);
        front[n]+=front[f[n]];
        return f[n]=fn;
    }
    public static int find_dei(int x,int[] f){
        if (f[x]==x){
            return x;
        }
        return f[x]=find_dei(f[x],f);
    }
    public static void unity1(int x,int y,int[] f,int[] z){
        int a=find_daiquan(x,f,z);
        int b=find_daiquan(y,f,z);
        f[a]=b;
    }

    public static void unity(int x,int y,int[] f){
        int a=find_dei(x,f);
        int b=find_dei(y,f);
        f[a]=b;
    }
    public static void add(int a,int b,int v,Node[] nodes){
        if (v==0){
            nodes[b].w=a;
            nodes[b].q=nodes[a].q;
            nodes[a].q=b;
            nodes[nodes[b].q].w=b;
        }
        else {
            nodes[b].q=a;
            nodes[b].w=nodes[a].w;
            nodes[a].w=b;
            nodes[nodes[b].w].q=b;
        }
    }
    public static void jian(int a,Node[] nodes){
        for (int i=nodes[0].w;i!=0;i=nodes[i].w){
            if (i==a){
                nodes[nodes[i].w].q=nodes[i].q;
                nodes[nodes[i].q].w=nodes[i].w;
            }
        }
    }

    public static long ef1(int[] a,int[] b ,int l,int r,int x){
        sum=0;
        int mid = (l + r) / 2;
        if (l>r){
            return sum;
        }
        if (b[x]<=a[1]){
            sum+=(a[1]-b[x]);
            return sum;
        }
        if (b[x]>=a[n]){
            sum+=(b[x]-a[n]);
            return sum;
        }
        if (b[x] >= a[mid - 1] && b[x] <= a[mid]) {
            sum += Math.min(a[mid] - b[x], b[x] - a[mid - 1]);
            return sum;
        }
        if (b[x]<a[mid]&&b[x]<a[mid-1]){
            return ef1(a,b,l,mid-1,x);
        }
        if (b[x]>a[mid]&&b[x]>a[mid-1]){
            return ef1(a,b,mid+1,r,x);
        }
        return sum;
    }

    public static int gys(int a,int b){
        if (a==0||b==0){
            return 0;
        }
        if (a%b==0){
            return b;
        }
        return gys(b,a%b);
    }

    public static int gbs(int a,int b){

        return a*b/gys(a,b);

    }

    public static long ks_mod(long a,long b){
        if (b==0){
            return 1%m1;
        }
        long x=1,y=a;
        while (b>0){
            if ((b&1)==1){
                x*=y;
                x%=m1;
            }
            y*=y;
            y%=m1;
            b>>=1;
        }
        return x;
    }

    public static double log2(int n){
        return Math.log(n)/Math.log(2);
    }

    public static void gb(int l,int r){
        if (l==r){
            return;
        }
        int mid=(l+r)/2;
        int z=mid+1,k=l,x=l,p=l;
        gb(l,mid);
        gb(mid+1,r);
        while (k<=mid&&z<=r){
            if (a[k]<=a[z]){
                b[x++]=a[k++];
            }
            else {
                b[x++]=a[z++];
                sum+=mid+1-k;
            }
        }
        while (k<=mid){
            b[x++]=a[k++];
        }
        while (z<=r){
            b[x++]=a[z++];
        }
        for (int i=l;i<=r;i++){
            a[i]=b[i];
        }
    }

    public static void cr(long[] a){
        for (int i=1;i<a.length;i++){
            long b=a[i];
            int b1=i-1;
            while (b1>=0&&b>a[b1]){
                a[b1+1]=a[b1];
                b1--;
            }
            a[b1+1]=b;
        }
    }

    static int Scanf_Int() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static long Scanf_Long() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    static double Scanf_Double() throws  IOException{
        in.nextToken();
        return in.nval;
    }
    static char Scanf_Char()throws IOException{//输入字符后可以空格,也可以换行
        in.nextToken();
        return in.sval.charAt(0);
    }
    static String Scanf_String() throws IOException{
        /*
         ***输入的字符串有空格的不能用这个***
         不能用这个来转变为字符数组和字符串数组,用bf.readLine();
         输入字符串后可以空格,也可以换行*/
        in.nextToken();
        return in.sval;
    }
}
class Node implements Comparable<Node> {
    int q,w;
    double e;
    String s;
    String s1;

    public Node(String s, String s1) {
        this.s = s;
        this.s1 = s1;
    }

    public Node(int q, int w) {
        this.q = q;
        this.w = w;
    }

    public Node(int q, String s) {
        this.q = q;
        this.s = s;
    }

    public Node(int q, int w, double e) {
        this.q = q;
        this.w = w;
        this.e = e;
    }

    @Override
    public int compareTo(Node o) {
        if (o.q==this.q){
            return this.w-o.w;
        }
        else {
            return this.q-o.q;
        }
    }
}
class Node1 implements Comparable<Node1>{
    int t,l,r,x;
    long f;
    String s;

    public Node1( long f,int l) {
        this.l = l;
        this.f = f;
    }

    public Node1(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public Node1(int t, int x, String s) {
        this.t = t;
        this.x = x;
        this.s = s;
    }

    @Override
    public int compareTo(Node1 o) {
        return o.t-this.t;
    }
}



CYHMMZDAN
10小时前

算法1

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

随机优化了一下,时间复杂度应该nn/43左右

java 代码

class Solution {
    public boolean searchArray(int[][] array, int target) {

        int m=0,m1=0;
        if(array.length!=0){
            m1=array[0].length;
        }
        for (int i=0;i<array.length;i++){

            for (int j=0;j<m1;j++){
                if (array[i][j]==target){
                    return true;
                }
                else if (array[i][j]>target){
                    m1=j;
                    break;
                }
            }
        }
        return false;
    }
}

算法2

从右上角开始枚举

时间复杂度(m+n)

java 代码

class Solution {
     public boolean searchArray(int[][] array, int target) {
       int l=0,r=0;
       if (array.length!=0){
           r=array[0].length-1;
       }
       while (l>=0&&l<array.length&&r>=0&&r<array[0].length){
           if (array[l][r]==target){
               return true;
           }
           else if (array[l][r]>target){
               r--;
           }
           else {
               l++;
           }
       }
       return false;
    }
}



算法2

java 代码

 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        n=Scanf_Int();
        m=Scanf_Int();
        for (int i=1;i<=m;i++){
            f[i]=1;
        }
        for (int i=1;i<=n;i++){
            l=Scanf_Int();
            r=Scanf_Int();
            for (int j=m;j>=l;j--){
                m1=dp[j-l]+r;
                if (m1>dp[j]){
                    dp[j]=m1;
                    f[j]=f[j-l];
                }
                else if (m1==dp[j]){
                     f[j]=(f[j]+f[j-l])%(((int) 1e+9)+7);
                }
            }
        }
        out.println(f[m]);
        out.close();



算法2

时间复杂度(nnlogS)

java 代码

import java.io.*;
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.text.Format;
import java.text.SimpleDateFormat;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Map;
import java.util.HashMap;

public class Main {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static StringBuilder stringBuilder = new StringBuilder();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static String s = "";
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int n = 0;
    static int min = (int) 2e9;
    static int sum = 0;
    static long sum1 = 0;
    static int max = -1;
    static int m1=0;
    static int m2=0;
    static int m3=0;
    static int m = 0;
    static int ans = 0;
    static int l = 0;
    static int r = 0;
    StringBuilder stringBuilder1=new StringBuilder();
    static Map<Map<Integer,Integer> ,Integer> map= new TreeMap<Map<Integer, Integer>, Integer>();
    static Map<Integer,Integer> map1= new TreeMap<>();
    static Map<Integer,Integer> map2= new TreeMap<>();
    static Map<String,Integer> map3= new TreeMap<>();
    static int[] h = new int[(int) (5e+5)];
    static boolean[] booleans=new boolean[101];
    static int[][] b2 = new int[1000][1000];
    static int[] dp = new int[200005];
    static int[][] pd = new int[6][6];
    static int[][] fs = new int[6][6];
    static int[] a=new int[20005];
    static Long[] f=new Long[2022];
    static int[] b=new int[20005];
    static int[] a1={0,1,-1,0,0};
    static int[] b1={0,0,0,1,-1};
    static String[] s1=new String[1005];
    static Set<String> set=new TreeSet<>();
    static Stack<String> stack=new Stack<>();
    static Queue<Integer> queun=new LinkedList<Integer>();//单队列
    static Deque<Integer> deque=new ArrayDeque<>();//双队列
    static PriorityQueue<Integer> xiao = new PriorityQueue();
    static PriorityQueue<Integer> xiao1 = new PriorityQueue();
    static PriorityQueue<Integer> xiao2 = new PriorityQueue();
    static PriorityQueue<Integer> da_1 = new PriorityQueue(Collections.reverseOrder());
    static PriorityQueue<Long> da = new PriorityQueue(Collections.reverseOrder());
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        n=Scanf_Int();
        m=Scanf_Int();
        for (int i=0;i<n;i++) {
            ans = 1;
            m1=Scanf_Int();
            m2=Scanf_Int();
            m3=Scanf_Int();
            while (ans <= m3) {
                m3-=ans;
                a[++l] = m1*ans;
                b[l] = m2*ans;
                ans*=2;
            }
            if (m3>0){
                a[++l]=m1*m3;
                b[l]=m2*m3;
            }
        }
        n=l;//个数变组数
        for (int i=1;i<=n;i++){
            for (int j=m;j>=a[i];j--){
                dp[j]=Math.max(dp[j],dp[j-a[i]]+b[i]);
            }
        }
        out.println(dp[m]);
        out.close();
    }
    public static void dfs_1(char[] c,int count,int t,int k){
        if (k==t){
            StringBuilder s1=new StringBuilder();
            for (int i=0;i<t*2;i++){
                s1.append(c[i]);
            }
            f[m++]=Long.valueOf(s1.toString());
            return;
        }
        if (k>t){
            return;
        }
        for (int i=count;i<t*2;i++){
            c[i]='4';
            dfs_1(c,i+1,t,k+1);
            c[i]='7';
        }
    }
    public static void dfs(char[][] matrix, String str,int k,int y,int count) {
        if (count==str.length()){
            if (stringBuilder.toString().equals(str)){
                m=1;
            }
            else {
                return;
            }
        }
        if (m==1||count>str.length()){
            return;
        }
        for (int i=1;i<=4;i++){
            int l=k+a1[i];
            int r=y+b1[i];
            if (l>=0&&l<matrix.length&&r>=0&&r<matrix[0].length&&b2[l][r]==0){

                b2[l][r]=1;
                stringBuilder.append(matrix[l][r]);
                dfs(matrix,str,l,r,count+1);
                b2[l][r]=0;
                stringBuilder.delete(count,count+1);
            }
        }
    }
    public static boolean hasPath(char[][] matrix, String str) {

        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==str.charAt(0)) {
                    b2[i][j] = 1;
                    stringBuilder.append(matrix[i][j]);
                    dfs(matrix, str, i, j, 1);
                    b2[i][j] = 0;
                    stringBuilder.delete(0, 1);
                    if (m == 1) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public static int dfs(int[][] a, int k,int y){
        if (b2[k][y]!=0){
            return b2[k][y];
        }
        b2[k][y]=1;
        for (int i=1;i<=4;i++){
            l=k+a1[i];
            r=y+b1[i];
            if (l>0&&l<=n&&r>0&&r<=n&&a[l][r]>a[k][y]){
                b2[k][y]=Math.max(b2[k][y],dfs(a,l,r)+1);
            }
        }
        return b2[k][y];
    }
    public static int max_4(int a,int b,int c,int d){
        int[] f=new int[5];
        f[1]=a;
        f[2]=b;
        f[3]=c;
        f[4]=d;
        Arrays.sort(f,1,5);
        return f[4];
    }
    public static int mod(int i,int n){
        return i%n;
    }
    public static boolean pd_sushu(int x){
        for (int i=2;i*i<=x;i++){
            if ((x%i)==0){
                return false;
            }
        }
        return true;
    }
    public static int find_daiquan(int n,int[] f,int[] front){
        if(f[n]==n)return f[n];
        int fn=find_daiquan(f[n],f,front);
        front[n]+=front[f[n]];
        return f[n]=fn;
    }
    public static int find_dei(int x,int[] f){
        if (f[x]==x){
            return x;
        }
        return f[x]=find_dei(f[x],f);
    }
    public static void unity1(int x,int y,int[] f,int[] z){
        int a=find_daiquan(x,f,z);
        int b=find_daiquan(y,f,z);
        f[a]=b;
    }

    public static void unity(int x,int y,int[] f){
        int a=find_dei(x,f);
        int b=find_dei(y,f);
        f[a]=b;
    }
    public static void add(int a,int b,int v,Node[] nodes){
        if (v==0){
            nodes[b].w=a;
            nodes[b].q=nodes[a].q;
            nodes[a].q=b;
            nodes[nodes[b].q].w=b;
        }
        else {
            nodes[b].q=a;
            nodes[b].w=nodes[a].w;
            nodes[a].w=b;
            nodes[nodes[b].w].q=b;
        }
    }
    public static void jian(int a,Node[] nodes){
        for (int i=nodes[0].w;i!=0;i=nodes[i].w){
            if (i==a){
                nodes[nodes[i].w].q=nodes[i].q;
                nodes[nodes[i].q].w=nodes[i].w;
            }
        }
    }

    public static long ef1(int[] a,int[] b ,int l,int r,int x){
        sum=0;
        int mid = (l + r) / 2;
        if (l>r){
            return sum;
        }
        if (b[x]<=a[1]){
            sum+=(a[1]-b[x]);
            return sum;
        }
        if (b[x]>=a[n]){
            sum+=(b[x]-a[n]);
            return sum;
        }
        if (b[x] >= a[mid - 1] && b[x] <= a[mid]) {
            sum += Math.min(a[mid] - b[x], b[x] - a[mid - 1]);
            return sum;
        }
        if (b[x]<a[mid]&&b[x]<a[mid-1]){
            return ef1(a,b,l,mid-1,x);
        }
        if (b[x]>a[mid]&&b[x]>a[mid-1]){
            return ef1(a,b,mid+1,r,x);
        }
        return sum;
    }

    public static int gys(int a,int b){
        if (a==0||b==0){
            return 0;
        }
        if (a%b==0){
            return b;
        }
        return gys(b,a%b);
    }

    public static int gbs(int a,int b){

        return a*b/gys(a,b);

    }

    public static long ks_mod(long a,long b){
        if (b==0){
            return 1%m1;
        }
        long x=1,y=a;
        while (b>0){
            if ((b&1)==1){
                x*=y;
                x%=m1;
            }
            y*=y;
            y%=m1;
            b>>=1;
        }
        return x;
    }

    public static double log2(int n){
        return Math.log(n)/Math.log(2);
    }

    public static void gb(int l,int r){
        if (l==r){
            return;
        }
        int mid=(l+r)/2;
        int z=mid+1,k=l,x=l,p=l;
        gb(l,mid);
        gb(mid+1,r);
        while (k<=mid&&z<=r){
            if (a[k]<=a[z]){
                b[x++]=a[k++];
            }
            else {
                b[x++]=a[z++];
                sum+=mid+1-k;
            }
        }
        while (k<=mid){
            b[x++]=a[k++];
        }
        while (z<=r){
            b[x++]=a[z++];
        }
        for (int i=l;i<=r;i++){
            a[i]=b[i];
        }
    }

    public static void cr(long[] a){
        for (int i=1;i<a.length;i++){
            long b=a[i];
            int b1=i-1;
            while (b1>=0&&b>a[b1]){
                a[b1+1]=a[b1];
                b1--;
            }
            a[b1+1]=b;
        }
    }

    static int Scanf_Int() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    static long Scanf_Long() throws IOException {
        in.nextToken();
        return (long) in.nval;
    }

    static double Scanf_Double() throws  IOException{
        in.nextToken();
        return in.nval;
    }
    static char Scanf_Char()throws IOException{//输入字符后可以空格,也可以换行
        in.nextToken();
        return in.sval.charAt(0);
    }
    static String Scanf_String() throws IOException{
        /*
         ***输入的字符串有空格的不能用这个***
         不能用这个来转变为字符数组和字符串数组,用bf.readLine();
         输入字符串后可以空格,也可以换行*/
        in.nextToken();
        return in.sval;
    }
}
class Node implements Comparable<Node> {
    int q,w;
    double e;
    String s;
    String s1;

    public Node(String s, String s1) {
        this.s = s;
        this.s1 = s1;
    }

    public Node(int q, int w) {
        this.q = q;
        this.w = w;
    }

    public Node(int q, String s) {
        this.q = q;
        this.s = s;
    }

    public Node(int q, int w, double e) {
        this.q = q;
        this.w = w;
        this.e = e;
    }

    @Override
    public int compareTo(Node o) {
        if (o.q==this.q){
            return this.w-o.w;
        }
        else {
            return this.q-o.q;
        }
    }
}
class Node1 implements Comparable<Node1>{
    int t,l,r,x;
    long f;
    String s;

    public Node1( long f,int l) {
        this.l = l;
        this.f = f;
    }

    public Node1(int l, int r) {
        this.l = l;
        this.r = r;
    }

    public Node1(int t, int x, String s) {
        this.t = t;
        this.x = x;
        this.s = s;
    }

    @Override
    public int compareTo(Node1 o) {
        return o.t-this.t;
    }
}



算法2

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

java 代码

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        // '\0'表示空格字符;
        char[] c=bf.readLine().toCharArray();
        StringBuilder stringBuilder=new StringBuilder();
        for (int i=0;i<c.length;i++){
            if (m==0&&String.valueOf(c[i]).equals(" ")){
                stringBuilder.append(" ");
                m=1;
            }
            if (m==0&&!String.valueOf(c[i]).equals(" ")){
                stringBuilder.append(c[i]);
            }
            if (m==1&&!String.valueOf(c[i]).equals(" ")){
                stringBuilder.append(c[i]);
                m=0;
            }
        }
        out.println(stringBuilder);
        out.close();



算法2

01背包会吧,就是由一个物品变为多个,那么直接分开成一个一个的,一样套01背包公式,拆开用一个while循环,也就多了一个这个

java 代码

 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        n=Scanf_Int();
        m=Scanf_Int();
        while (n-->0){
            l=Scanf_Int();
            r=Scanf_Int();
            m1=Scanf_Int();
            while (m1-->0){
                for (int i=m;i>=l;i--){
                    dp[i]=Math.max(dp[i],dp[i-l]+r);
                }
            }
        }
        out.println(dp[m]);
        out.close();



算法2

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

java 代码

Scanner sc=new Scanner(System.in);
        //sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
        while (sc.hasNext()) {
            String[] s1 = sc.nextLine().split(" ");
            max = -1;
            for (int i = 0; i < s1[0].length(); i++) {
                if (s1[0].charAt(i) - 48 > max) {
                    max = s1[0].charAt(i) - 48;
                    m = i;
                }
            }
                StringBuilder stringBuilder = new StringBuilder();
                stringBuilder.append(s1[0]);
                System.out.println(stringBuilder.insert(m + 1, s1[1]));
            }