头像

henhen敲

吉林大学




离线:12天前


新鲜事 原文

henhen敲
4个月前
今天拼多多笔试 遇到一道背包问题 大家各抒己见
图片



henhen敲
6个月前
卡特兰数 只不过需要在(1, 0) 和 (0, 1)处分别做一下
(n-m)/(m+n)
import java.util.Scanner;

class Main{

    public static void main(String[] args) {
        int m, n, t;
        Scanner in = new Scanner(System.in);
        t = in.nextInt();
        int cnt = 1;
        while(cnt<=t){
            n = in.nextInt();
            m = in.nextInt();
            System.out.print("Case #"+ cnt++ +": ") ;
            System.out.println(String.format("%.8f", (n-m)*1.0/(m+n)));
        }
    }
}



henhen敲
7个月前
取石子游戏不同玩法的解决方案

玩法一(1堆n个石子每次最多取m个)
显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
import java.util.*;
import java.io.*;

class Main{

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }

    static Integer[] a;
    static boolean[] st;
    static int length, n, sum;
     static void swap(int i,int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    static void reverse()
    {
        int i = 0;
        int j = n - 1;
        while(i <= j) 
        {
            swap(i,j);
            i ++;
            j --;
        }
    }
    public static boolean DFS(int c, int cur, int start){
        if(c*length==sum) return true;
        if(cur==length) return DFS(c+1, 0, 0);
        if(cur>length) return false;
        for(int i=start; i<n; i++){
            if(st[i]) continue;
            st[i] = true;
            if(DFS(c, cur+a[i], i+1)) return true;
            st[i] = false;
            if(cur==0) return false;
            if(cur+a[i]==length) return false;
            while(i<n-1&&a[i]==a[i+1]) i++;
        }
        return false;
    }

    public static void main(String[] args) throws Exception{
        n = nextInt();
        while(n!=0){
            a = new Integer[n];
            st = new boolean[n];
            length = sum = 0;

            for(int i=0; i<n; i++){
                a[i] = nextInt();
                length = Math.max(length, a[i]);
                sum += a[i];
            }
            Arrays.sort(a);//这里用Arrays.sort(a,(o1, o2)->o2-o1;就会超时
            reverse();
            while(length<=sum){
                if(sum%length==0&&DFS(0, 0, 0)) break;
                length++;
            }
            out.println(length);
            n = nextInt();
        }
        out.close();
    }
}



henhen敲
7个月前
import java.io.*;

class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    public static void main(String[] args)throws Exception{
        int n = nextInt();
        int[][] g = new int[n][n];
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                g[i][j] = nextInt();
        int[][] f = new int[1<<n][n];
        for(int i=2; i<(1<<n); i++)
            for(int j=0; j<n; j++)
                if(((i>>j)&1)==1){
                    int m = i - (1<<j);
                    int min = 0x3f3f3f3f;
                    int t, k;
                    for(k=m, t=0; k!=0; k>>=1, t++)
                        if((k&1)==1)
                            min = Math.min(min, f[m][t]+g[t][j]);
                    f[i][j] = min;

                }
        int ans = 0x3f3f3f3f;
        for(int i=1; i<n; i++)
            ans = Math.min(ans, f[(1<<n)-1][i] + g[i][0]);
        out.print(ans);
        out.close();
    }
}



henhen敲
7个月前
/**

* Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                ans.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop().right;
        }
        return ans;
    }
}
中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}
后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                map.put(root, map.getOrDefault(root, 0)+1);
                root = root.left;
            }
            root = stack.pop();
            int flag = map.get(root);
            if(flag<2){
                stack.push(root);
                map.put(root, map.getOrDefault(root, 0)+1);
                root = root.right;
            } 
            else{
                ans.add(root.val);
                root = null;
            }
        }
        return ans;
    }
}



henhen敲
7个月前
import java.io.*;

class Main{
    static StreamTokenizer in = new StreamTokenizer(new  BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }

    static boolean[] r, c, a45, a135;
    static char[][] g;
    static int n;

    public static void DFS(int i, int j, int cnt){
        if(i==n&&cnt==0){
           for(int x=0; x<n; x++){
               for(int y=0; y<n; y++)
                out.print(g[x][y]);
            out.println("");
           }
           out.println("");
           return; 
        }
        if(i==n) return;
        g[i][j] = '.';
        DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt);
        if(!r[i]&&!c[j]&&!a45[j-i+n]&&!a135[i+j]){
            r[i] = true;
            c[j] = true;
            a45[j-i+n] = true;
            a135[j+i] = true;
            g[i][j] = 'Q';
            DFS((j+1)%n==0?i+1:i, (j+1)%n, cnt-1);
            r[i] = false;
            c[j] = false;
            a45[j-i+n] = false;
            a135[j+i] = false;
        }
    }

    public static void main(String[] args)throws Exception{
        n = nextInt();
        r = new boolean[n];
        c = new boolean[n];
        a45 = new boolean[2*n];
        a135 = new boolean[2*n];
        g = new char[n][n];
        DFS(0, 0, n);
        out.close();
    }

}



henhen敲
7个月前
悬线法 通俗的讲 就是从矩阵中每一点发出一条射线 要么撞到障碍点 要么撞到矩阵边界 然后求出以该射线的长度
为长 从左右选出适合的点连成宽 所围成的最大矩形面积 
import java.io.*;
import java.util.*;

class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter  out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    static String next()throws Exception{
        in.nextToken();
        return in.sval;
    }

    public static void main(String[] args) throws Exception{
        int n, m;
        n = nextInt(); m = nextInt();
        int[][] g =new int[n][m];
        int max = 0;
        int[][] left, right, up;
        left = new int[n][m];
        right = new int[n][m];
        up = new int[n][m];
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++){
                String t = next();
                g[i][j] = t.equals("F")?1:0;
                left[i][j] = j; right[i][j] = j;
                up[i][j] = 1;
            }

        for(int i=0; i<n; i++)
            for(int j=1; j<m; j++)
                if(g[i][j]!=0&&g[i][j-1]!=0) left[i][j] = left[i][j-1];

        for(int i=0; i<n; i++)
            for(int j=m-2; j>=0; j--)
                if(g[i][j]!=0&&g[i][j+1]!=0) right[i][j] = right[i][j+1];

        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(g[i][j]!=0){
                    int l, r;
                    l = left[i][j]; r = right[i][j];
                    if(i>0&&g[i-1][j]!=0){
                        up[i][j] = up[i-1][j] + 1;
                        l = Math.max(l, left[i-1][j]);  
                        r = Math.min(r, right[i-1][j]);
                    }
                    left[i][j] = l;
                    right[i][j] = r;
                    max = Math.max((r-l+1)*up[i][j], max);
                }

        out.println(max*3);
        out.close();
    }
}



henhen敲
7个月前
import java.io.*;
import java.util.*;

class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    static int[] a, path;
    static int n;

    static void DFS(int d, int st){
        if(d>=n){
            for(int i=0; i<n; i++) out.print(path[i]+" ");
            out.println("");
            return;
        }
        for(int i=0; i<n; i++){
            if(i>0&&((st>>(i-1))&1)==0&&a[i]==a[i-1]) continue;
            if(((st>>i)&1)==0){
                path[d] = a[i];
                DFS(d+1, st+(1<<i));
            }  
        }

    }

    public static void main(String[] args)throws Exception{
        n = nextInt();
        a = new int[n];
        path = new int[n];
        for(int i=0; i<n; i++) a[i] = nextInt();
        Arrays.sort(a);
        DFS(0, 0);
        out.close();
    }
}




henhen敲
7个月前
只考虑两组情况就行 然后依次迭代 a是有序的 
a1, a2, a3,……, an;

b1, b2, b3,……, bn;
import java.io.*;
import java.util.*;

class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt()throws Exception{
        in.nextToken();
        return (int)in.nval;
    }
    static class Pair{
        int first, second;
        public Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }

    static int[] a, b, c;
    static int n, m;

    static void merge(){
        PriorityQueue<Pair> heap = new PriorityQueue<>((o1, o2)->o1.second-o2.second);
        for(int i=0; i<n; i++) heap.offer(new Pair(0, a[0]+b[i])); 
        for(int i=0; i<n; i++){
            Pair e = heap.poll();
            int f = e.first; int s = e.second;
            c[i] = s; 
            if(f<n-1)heap.offer(new Pair(f+1, s - a[f] + a[f+1])); 
        }
        for(int i=0; i<n; i++) a[i] = c[i];
    }

    public static void main(String[] args)throws Exception{
        int T = nextInt();
        while(T--!=0){
            m = nextInt(); n = nextInt();
            a = new int[n]; b = new int[n]; c = new int[n];
            for(int i=0; i<n; i++)a[i] = nextInt();
            Arrays.sort(a);
            for(int i=0; i<m-1; i++){
                for(int j=0; j<n; j++)b[j] = nextInt();
                merge(); 
            } 
            for(int i=0; i<n; i++) out.print(a[i]+" ");
            out.println("");
        }
        out.close();
    }
}




henhen敲
7个月前
import java.io.*;
import java.util.*;

class Main{

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int nextInt() throws Exception{
        in.nextToken();
        return (int)in.nval;
    }



    public static void main(String[] args)throws Exception{
        int n = nextInt();
        long[] a = new long[n];
        long sum = 0;
        for(int i=0; i<n; i++){
            a[i] = nextInt();
            sum += a[i];
        } 
        long ave = sum / n;
        a[n-1] = ave - a[n-1];
        for(int i=n-2; i>0; i--)
            a[i] = ave + a[i+1] - a[i];

        a[0] = 0;
        Arrays.sort(a);
        long res = 0;
        for(int i=0; i<n; i++) res += Math.abs(a[i] - a[n/2]);
        out.print(res);
        out.close();
    }
}