头像

java的同学




离线:9小时前




import java.io.*;

class Main {

    static int N = 100010;
    static int n, maxLen;
    static int[] a = new int[N];

    static int head, tail;
    static int[] queue = new int[N];
    static boolean[] isIn = new boolean[N];

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        n = Integer.parseInt(in.readLine());
        String[] strs = in.readLine().split(" ");
        for (int i = 1; i <= n; i++) a[i] = Integer.parseInt(strs[i - 1]);
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        for (int i = 1; i <= n; i++) {
            if (isIn[a[i]]) {
                for (int x = queue[head]; x != a[i]; ) {
                    isIn[x] = false;
                    x = queue[++head];
                }
                head++;
            }
            queue[tail++] = a[i];
            isIn[a[i]] = true;
            maxLen = Math.max(maxLen, tail - head);
        }
        out.write(maxLen + "");
        out.flush();
        out.close();
        osw.close();
    }
}



import java.io.*;
import java.util.Arrays;

class Main {

    static int N = 310;

    //存储高度
    static int r, c;
    static int[][] h = new int[N][N];

    //f存储某点开始下滑的最大长度
    static int[][] f = new int[N][N];
    //是否已确定最大长度
    static boolean[][] flag = new boolean[N][N];
    //最大长度
    static int res;

    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};

    static boolean check(int x, int y) {
        return x < r && y < c && x >= 0 && y >= 0;
    }

    static void dfs(int x, int y) {
        int height = h[x][y];
        f[x][y] = 1;
        flag[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + mx[i];
            int ny = y + my[i];
            if (check(nx, ny) && h[x][y] > h[nx][ny]) {
                //如果未确定最长滑行距离,进入搜索
                if (!flag[nx][ny]) dfs(nx, ny);
                f[x][y] = Math.max(f[x][y], f[nx][ny] + 1);
            }
        }
        res = Math.max(res, f[x][y]);
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        r = Integer.parseInt(strs[0]);
        c = Integer.parseInt(strs[1]);


        //r行c列
        for (int i = 0; i < r; i++) {
            strs = in.readLine().split(" ");
            for (int j = 0; j < c; j++) h[i][j] = Integer.parseInt(strs[j]);
        }

        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) {
                if (!flag[i][j]) {
                    dfs(i,j);
                }
            }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 901. 滑雪

import java.io.*;
import java.util.Arrays;

class Main {

    static int N = 310;

    //存储高度
    static int r, c;
    static int[][] h = new int[N][N];

    //f存储某点开始下滑的最大长度
    static int[][] f = new int[N][N];
    //是否已确定最大长度
    static boolean[][] flag = new boolean[N][N];
    //最大长度
    static int res;

    static int[] mx = {-1,1,0,0};
    static int[] my = {0,0,-1,1};

    static boolean check(int x, int y) {
        return x < r && y < c && x >= 0 && y >= 0;
    }

    static void dfs(int x, int y) {
        int height = h[x][y];
        f[x][y] = 1;
        flag[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + mx[i];
            int ny = y + my[i];
            if (check(nx, ny) && h[x][y] > h[nx][ny]) {
                //如果未确定最长滑行距离,进入搜索
                if (!flag[nx][ny]) dfs(nx, ny);
                f[x][y] = Math.max(f[x][y], f[nx][ny] + 1);
            }
        }
        res = Math.max(res, f[x][y]);
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        r = Integer.parseInt(strs[0]);
        c = Integer.parseInt(strs[1]);


        //r行c列
        for (int i = 0; i < r; i++) {
            strs = in.readLine().split(" ");
            for (int j = 0; j < c; j++) h[i][j] = Integer.parseInt(strs[j]);
        }

        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++) {
                if (!flag[i][j]) {
                    dfs(i,j);
                }
            }
        System.out.println(res);
    }
}



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

class Main {

//邻接表存储树
static int idx;
static int[] h = new int[6010];
static int[] e = new int[6010];
static int[] ne = new int[6010];
static {
    for (int i = 0; i < 6010; i++) Arrays.fill(h, -1);
}

//是否有父节点(用于找根)
static boolean[] hasFather = new boolean[6010];

//存储快乐值
static int[] v = new int[6010];

static int[][] f = new int[6010][2];

static void insert(int k, int l) {
    e[idx] = l;
    ne[idx] = h[k];
    h[k] = idx++;
    hasFather[l] = true;
}

static void dfs(int x) {
    //若是叶节点
    if (h[x] == -1) {
        f[x][0] = 0;
        f[x][1] = v[x];
        return;
    }
    //遍历所有子节点
    for (int i = h[x]; i != -1; i = ne[i]) {
        int son = e[i];
        dfs(son);
        f[x][0] += Math.max(f[son][0], f[son][1]);
        f[x][1] += f[son][0];
    }
    f[x][1] += v[x];
}

public static void main(String[] args) throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader in = new BufferedReader(isr);
    int n = Integer.parseInt(in.readLine());
    for (int i = 1; i <= n; i++) v[i] = Integer.parseInt(in.readLine());
    String[] strs = null;
    for (int i = 1; i < n; i++) {
        strs = in.readLine().split(" ");
        int l = Integer.parseInt(strs[0]);
        int k = Integer.parseInt(strs[1]);
        insert(k, l);
    }

    int root = 1;
    while (hasFather[root]) root ++;
    dfs(root);
    System.out.println(Math.max(f[root][0], f[root][1]));
}

}




import java.io.*;
import java.util.Arrays;

class Main {
    //注意:INF不能设为最大int,相加时会溢出到负值
    static final int INF = 0x3fffffff;
    static final int N = 20;
    static int[][] w = new int[N][N];
    static void insert(int a, int b, int v) {
        w[a][b] = w[b][a] = v;
    }
    //第一维表示状态,第二维表示当前点
    static int[][] f = new int[1 << N][N];
    static {
        for (int i = 0; i < 1<<N; i++) Arrays.fill(f[i], INF);
        f[1][0] = 0;
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        for (int i = 0; i < n; i++) {
            strs = in.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int v = Integer.parseInt(strs[j]);
                insert(i, j, v);
            }
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        //遍历每种状态
        for (int i = 1; i < 1<<n; i++)
            //遍历每个点
            for (int j = 0; j < n; j++)
                //如果当前状态有这个点
                if (((i >> j) & 1) == 1) {
                    //求前驱状态pre
                    int pre = i - (1 << j);
                    //对于前驱状态,遍历每个点
                    for (int k = 0; k < n; k++)
                        //如果前驱状态的k点可以走到j点
                        if (((pre >> k) & 1) == 1)
                            f[i][j] = Math.min(f[i][j], f[pre][k] + w[k][j]);
                }
        out.write(f[(1 << n) - 1][n - 1] + "");
        out.flush();
        out.close();
        osw.close();
    }
}


活动打卡代码 AcWing 91. 最短Hamilton路径

import java.io.*;
import java.util.Arrays;

class Main {
    //注意:INF不能设为最大int,相加时会溢出到负值
    static final int INF = 0x3fffffff;
    static final int N = 20;
    static int[][] w = new int[N][N];
    static void insert(int a, int b, int v) {
        w[a][b] = w[b][a] = v;
    }
    //第一维表示状态,第二维表示当前点
    static int[][] f = new int[1 << N][N];
    static {
        for (int i = 0; i < 1<<N; i++) Arrays.fill(f[i], INF);
        f[1][0] = 0;
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader in = new BufferedReader(isr);
        String[] strs = in.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        for (int i = 0; i < n; i++) {
            strs = in.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int v = Integer.parseInt(strs[j]);
                insert(i, j, v);
            }
        }
        in.close();
        isr.close();

        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);

        //遍历每种状态
        for (int i = 0; i < 1<<n; i++)
            //遍历每个点
            for (int j = 0; j < n; j++)
                //如果当前状态有这个点
                if (((i >> j) & 1) == 1) {
                    //求前驱状态pre
                    int pre = i - (1 << j);
                    //对于前驱状态,遍历每个点
                    for (int k = 0; k < n; k++)
                        //如果前驱状态的k点可以走到j点
                        if (((pre >> k) & 1) == 1)
                            f[i][j] = Math.min(f[i][j], f[pre][k] + w[k][j]);
                }
        out.write(f[(1 << n) - 1][n - 1] + "");
        out.flush();
        out.close();
        osw.close();
    }
}



import java.io.*;
import java.util.*;

class Main {

    //存储状态合法性
    static int kinds;
    static boolean[] flag = new boolean[4096];

    static long[][] f = new long[12][4096];

    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;

            label:
            for (int k = 0; k < 1<<n; k++) {
                int cnt = 0;
                flag[k] = true;
                //每个状态一定是n位二进制表示
                for (int t = 0; t < n; t++) {
                    int x = k >> t;
                    if ((x&1) == 1) {
                        if ((cnt&1) == 1) {
                            flag[k] = false;
                            //已经出现连续奇数个1了,检查下个状态
                            continue label;
                        } else cnt = 0;
                    } else cnt++;
                }
                if ((cnt&1) == 1) flag[k] = false;
            }

            //存储每种合法状态的前一种状态
            Map<Integer, List<Integer>> pres = new HashMap<>();

            for (int k = 0; k < 1 << n; k++) {
                //此处不能过滤,因为p | k才是列状态
                //if (!flag[k]) continue;
                for (int p = 0; p < 1 << n; p++)
                    if ((p & k) == 0 && flag[p | k]) {
                        if ( pres.get(k) != null)  pres.get(k).add(p);
                        else {
                            List<Integer> list = new ArrayList<>();
                            list.add(p);
                            pres.put(k, list);
                        }
                    }
            }

            //关键,每次都要重新初始化f数组,否则会因之前的状态影响结果
            //因为i表示的是列数,所以f数组使用到了1~m行
            for (int i = 0; i <= m; i++) Arrays.fill(f[i], 0);
            //从第零列只能伸出0个
            f[0][0] = 1;

            for (int i = 1; i<= m; i++)
                for (int j = 0; j < 1<<n; j++) {
                    List<Integer> list = pres.get(j);
                    if (list == null) continue;
                    for (int x : list) f[i][j] += f[i - 1][x];
                }
            out.write(f[m][0]+"\n");
        }

        br.close();
        isr.close();

        out.flush();
        out.close();
        osw.close();
    }
}




状态压缩dp

1100ms左右 比优化版略慢

y总讲的f[i][j]感觉不好理解,比如f[m][0]是结果,而m列前一列并不需要没有伸出来到最后一列
把j看成当前列伸到下一列的状态就好理解了,代码是一样的,有时间详细写下

import java.io.*;
import java.util.*;

class Main {

    //存储状态合法性
    static int kinds;
    static boolean[] flag = new boolean[4096];

    static long[][] f = new long[12][4096];

    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;

            label:
            for (int k = 0; k < 1<<n; k++) {
                int cnt = 0;
                flag[k] = true;
                //每个状态一定是n位二进制表示
                for (int t = 0; t < n; t++) {
                    int x = k >> t;
                    if ((x&1) == 1) {
                        if ((cnt&1) == 1) {
                            flag[k] = false;
                            //已经出现连续奇数个1了,检查下个状态
                            continue label;
                        } else cnt = 0;
                    } else cnt++;
                }
                if ((cnt&1) == 1) flag[k] = false;
            }

            //关键,每次都要重新初始化f数组,否则会因之前的状态影响结果
            //因为i表示的是列数,所以f数组使用到了1~m行
            for (int i = 0; i <= m; i++) Arrays.fill(f[i], 0);
            //从第零列只能伸出0个
            f[0][0] = 1;

            for (int i = 1; i<= m; i++)
                for (int j = 0; j < 1<<n; j++)
                    for (int k = 0; k < 1<<n; k++)
                        if ((j&k) == 0 && flag[j|k]) f[i][j] += f[i-1][k];
            out.write(f[m][0]+"\n");
        }

        br.close();
        isr.close();

        out.flush();
        out.close();
        osw.close();
    }
}

优化

800ms 左右

import java.io.*;
import java.util.*;

class Main {

    //存储状态合法性
    static int kinds;
    static boolean[] flag = new boolean[4096];

    static long[][] f = new long[12][4096];

    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);

        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            in.nextToken();
            int m = (int) in.nval;
            if (n == 0 && m == 0) break;

            label:
            for (int k = 0; k < 1<<n; k++) {
                int cnt = 0;
                flag[k] = true;
                //每个状态一定是n位二进制表示
                for (int t = 0; t < n; t++) {
                    int x = k >> t;
                    if ((x&1) == 1) {
                        if ((cnt&1) == 1) {
                            flag[k] = false;
                            //已经出现连续奇数个1了,检查下个状态
                            continue label;
                        } else cnt = 0;
                    } else cnt++;
                }
                if ((cnt&1) == 1) flag[k] = false;
            }

            //存储每种合法状态的前一种状态
            Map<Integer, List<Integer>> pres = new HashMap<>();

            for (int k = 0; k < 1 << n; k++) {
                //此处不能过滤,因为p | k才是列状态
                //if (!flag[k]) continue;
                for (int p = 0; p < 1 << n; p++)
                    if ((p & k) == 0 && flag[p | k]) {
                        if ( pres.get(k) != null)  pres.get(k).add(p);
                        else {
                            List<Integer> list = new ArrayList<>();
                            list.add(p);
                            pres.put(k, list);
                        }
                    }
            }

            //关键,每次都要重新初始化f数组,否则会因之前的状态影响结果
            //因为i表示的是列数,所以f数组使用到了1~m行
            for (int i = 0; i <= m; i++) Arrays.fill(f[i], 0);
            //从第零列只能伸出0个
            f[0][0] = 1;

            for (int i = 1; i<= m; i++)
                for (int j = 0; j < 1<<n; j++) {
                    List<Integer> list = pres.get(j);
                    if (list == null) continue;
                    for (int x : list) f[i][j] += f[i - 1][x];
                }
            out.write(f[m][0]+"\n");
        }

        br.close();
        isr.close();

        out.flush();
        out.close();
        osw.close();
    }
}



这题分情况有点麻烦,按照y总讲的思路写的,代码不简洁,可读性差,没思路的就别看了

import java.io.*;

class Main {

    static int[] a = new int[10];
    static void reverse(int len) {
        int i = 1, j = len;
        while (j > i) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            j--;
            i++;
        }
    }
    static int generateA(int n) {
        int len = 0;
        while(n > 0) {
            a[++len] = n%10;
            n /= 10;
        }
        reverse(len);
        return len;
    }
    static int power10(int time) {
        int ans = 1;
        while (time > 0) {
            ans *= 10;
            time --;
        }
        return ans;
    }
    static int gerPre(int i) {
        int ans = 0;
        for (int k = 1; k < i; k++) ans = ans * 10 + a[k];
        return ans;
    }
    static int getSuf(int i, int len) {
        int ans = 0;
        for (int k = i + 1; k <= len; k++) ans  = ans * 10 + a[k];
        return ans;
    }
    static int getCnt(int n, int x) {
        int len = generateA(n);
        int cnt = 0;
        for (int i = 1; i <= len; i++) {

            //前缀不等时
            int pre = gerPre(i);
            int power = power10(len - i);
            if (x == 0 && pre != 0) cnt += (pre - 1) * power;
            else cnt += (pre) * power;

            if (pre == 0 && x == 0) continue;
            //前缀相等时
            int suf = getSuf(i,len);
            if (a[i] < x) continue;
            else if (a[i] == x) cnt += suf + 1;
            else cnt += power;
        }
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            if (a == 0 && b == 0) break;
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            for (int x = 0; x < 10; x++) {
                int cnt = getCnt(b,x) - getCnt(a - 1,x);
                out.write(cnt+" ");
            }
            out.write("\n");
        }
        br.close();
        isr.close();
        out.flush();
        out.close();
        osw.close();
    }
}


活动打卡代码 AcWing 338. 计数问题

import java.io.*;

class Main {

    static int[] a = new int[10];
    static void reverse(int len) {
        int i = 1, j = len;
        while (j > i) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            j--;
            i++;
        }
    }
    static int generateA(int n) {
        int len = 0;
        while(n > 0) {
            a[++len] = n%10;
            n /= 10;
        }
        reverse(len);
        return len;
    }
    static int power10(int time) {
        int ans = 1;
        while (time > 0) {
            ans *= 10;
            time --;
        }
        return ans;
    }
    static int gerPre(int i) {
        int ans = 0;
        for (int k = 1; k < i; k++) ans = ans * 10 + a[k];
        return ans;
    }
    static int getSuf(int i, int len) {
        int ans = 0;
        for (int k = i + 1; k <= len; k++) ans  = ans * 10 + a[k];
        return ans;
    }
    static int getCnt(int n, int x) {
        int len = generateA(n);
        int cnt = 0;
        for (int i = 1; i <= len; i++) {

            //前缀不等时
            int pre = gerPre(i);
            int power = power10(len - i);
            if (x == 0 && pre != 0) cnt += (pre - 1) * power;
            else cnt += (pre) * power;

            if (pre == 0 && x == 0) continue;
            //前缀相等时
            int suf = getSuf(i,len);
            if (a[i] < x) continue;
            else if (a[i] == x) cnt += suf + 1;
            else cnt += power;
        }
        return cnt;
    }
    public static void main(String[] args) throws IOException {
        OutputStreamWriter osw = new OutputStreamWriter(System.out);
        BufferedWriter out = new BufferedWriter(osw);
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        StreamTokenizer in = new StreamTokenizer(br);
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            if (a == 0 && b == 0) break;
            if (a > b) {
                int temp = a;
                a = b;
                b = temp;
            }
            for (int x = 0; x < 10; x++) {
                int cnt = getCnt(b,x) - getCnt(a - 1,x);
                out.write(cnt+" ");
            }
            out.write("\n");
        }
        br.close();
        isr.close();
        out.flush();
        out.close();
        osw.close();
    }
}