头像

CZL

孤独比**舒服




离线:4小时前


最近来访(695)
用户头像
bre
用户头像
jdkjrejvm
用户头像
shinax
用户头像
天道酬薪
用户头像
爱笑的砂糖橘
用户头像
yxc的小迷妹1
用户头像
小狗泪奔
用户头像
哦呼_2
用户头像
草雨田yy
用户头像
山山海
用户头像
XuYangyang
用户头像
花事了
用户头像
xioachou
用户头像
zg080
用户头像
GabrielxD
用户头像
ac0111
用户头像
WeiXingJi
用户头像
不AC
用户头像
1024M
用户头像
yan扬

活动打卡代码 AcWing 4653. 数位排序

CZL
2天前
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Integer a[] = new Integer[n];
        for(int i = 0; i < n; i ++ )
            a[i] = i + 1;
        Arrays.sort(a, (o1, o2) -> f(o1, o2));
        System.out.println(a[m - 1]);
    }

    static int f(int o1, int o2) {
        int o1_sum = 0, o2_sum = 0;
        String s1 = o1 + "", s2 = o2 + "";
        for(int i = 0; i < s1.length(); i ++ ) {
            o1_sum += s1.charAt(i) - '0';
        }
        for(int i = 0; i < s2.length(); i ++ ) {
            o2_sum += s2.charAt(i) - '0';
        }
        if(o1_sum != o2_sum)
            return o1_sum - o2_sum;
        return o1 - o2;
    }
}


分享 BubbleSort

CZL
12天前
import java.util.*;
public class Main {
    static int N = 100010;
    static int a[] = new int[N];

    static void BubbleSort(int n) {
        for(int i = 0; i < n - 1; i ++ ) {
            boolean flag = false;
            for(int j = 0; j < n - i - 1; j ++ ) {
                if(a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = true;
                }
            }
            if(!flag) return;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < n; i ++ ) {
            a[i + 1] = sc.nextInt();
        }
//        qsort(1, n);
        BubbleSort(n);
        for(int i = 0; i < n; i ++ ) {
            System.out.println(a[i + 1]);
        }
    }
}



CZL
12天前
import java.util.*;
public class Main {
    static int N = 100010;
    static int a[] = new int[N];

    static void qsort(int l, int r) {
        if(l >= r) return;
        int low = partion(l, r);
        qsort(l, low - 1);
        qsort(low + 1, r);
    }

    static int partion(int l, int r) {
        int p = a[l];
        while(l < r) {
            while(l < r && a[r] >= p) r -- ;
            a[l] = a[r];
            while(l < r && a[l] <= p) l ++ ;
            a[r] = a[l];
        }
        a[l] = p;
        return l;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < n; i ++ ) {
            a[i + 1] = sc.nextInt();
        }
        qsort(1, n);
        for(int i = 0; i < n; i ++ ) {
            System.out.println(a[i + 1]);
        }
    }
}



CZL
19天前

从官网档的Snake Bot代码,你能打败我?

我这贪吃蛇无敌了

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Bot {
    public static int INT = 0x3f3f3f3f;
    public static int[][] path;
    public static int[][] g = new int[13][14];
    public static int pathLen = -1;
    public static boolean flag = true;
    public static int nextDirection = -1;


    static class Cell {//蛇身体(单格)
        public int x, y;

        public Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private boolean check_tail_increasing(int step) {//检查蛇什么时候会变长
        if (step <= 10) return true;
        return step % 3 == 1;
    }

    public List<Cell> getCells(int sx, int sy, String steps) {//获取游戏中两条蛇的身体位置
        steps = steps.substring(1, steps.length() - 1);
        List<Cell> res = new ArrayList<>();

        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        int x = sx, y = sy;
        int step = 0;
        res.add(new Cell(x, y));
        for (int i = 0; i < steps.length(); i++) {
            int d = steps.charAt(i) - '0';
            x += dx[d];
            y += dy[d];
            res.add(new Cell(x, y));
            if (!check_tail_increasing(++step)) {
                res.remove(0);
            }
        }
        return res;
    }

    //读取数据
    public void get() {
        File file = new File("input.txt");
        try {
            Scanner scanner = new Scanner(file);
            System.out.println(nextMove(scanner.next()));
        } catch (FileNotFoundException e) {
            throw new RuntimeException(e);
        }
    }

    public Integer nextMove(String input) {
        String[] strs = input.split("#");
        for (int i = 0, k = 0; i < 13; i++) {
            for (int j = 0; j < 14; j++, k++) {
                if (strs[0].charAt(k) == '1') {//找到地图中所有的墙
                    g[i][j] = 1;//1:障碍物,0:空地
                }
            }
        }

        int aSx = Integer.parseInt(strs[1]), aSy = Integer.parseInt(strs[2]);
        int bSx = Integer.parseInt(strs[4]), bSy = Integer.parseInt(strs[5]);

        List<Cell> aCells = getCells(aSx, aSy, strs[3]);
        List<Cell> bCells = getCells(bSx, bSy, strs[6]);

        for (Cell c : aCells) g[c.x][c.y] = 2;//将地图中两条蛇身体的位置标记成障碍物
        for (Cell c : bCells) g[c.x][c.y] = 3;

        //        打印地图
        //        printMap();

        //        a蛇头坐标
        int aHeadX = aCells.get(aCells.size() - 1).x;
        int aHeadY = aCells.get(aCells.size() - 1).y;
        //        b蛇头坐标
        int bHeadX = bCells.get(bCells.size() - 1).x;
        int bHeadY = bCells.get(bCells.size() - 1).y;

        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        //        Scanner input2 = new Scanner(System.in);
        //        System.out.println("请输入顶点数和边数:");
        //顶点数
        int vertex = 13 * 14;
        //边数
        int edge = 0;

        int[][] matrix = new int[vertex][vertex];
        //初始化邻接矩阵
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = INT;
            }
        }

        //初始化路径数组
        path = new int[matrix.length][matrix.length];

        //初始化边权值

        for (int i = 0; i < 13; i++) {
            for (int j = 0; j < 14; j++) {
                if (g[i][j] == 1 || g[i][j] == 2) continue;
                //                右
                int dxx = 0, dyy = 1;
                int mx = i + dxx, my = j + dyy;
                if (my < 14 && (g[mx][my] == 0 || g[mx][my] == 3 || (mx == aHeadX && my == aHeadY))) {
                    matrix[i * 14 + j][mx * 14 + my] = 1;
                    matrix[mx * 14 + my][i * 14 + j] = 1;
                }
                //                下
                dxx = 1;
                dyy = 0;
                mx = i + dxx;
                my = j + dyy;
                if (mx < 13 && (g[mx][my] == 0 || g[mx][my] == 3 || (mx == aHeadX && my == aHeadY))) {
                    matrix[i * 14 + j][mx * 14 + my] = 1;
                    matrix[mx * 14 + my][i * 14 + j] = 1;
                }
            }
        }
        //        for (int i = 0; i < edge; i++) {
        ////            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
        //            int source = input2.nextInt();
        //            int target = input2.nextInt();
        //            int weight = input2.nextInt();
        //            matrix[source][target] = weight;
        //        }
        for (int i = 0; i < 4; i++) {
            int mx = aHeadX + dx[i], my = aHeadY + dy[i];
            if (g[mx][my] == 0) {
                matrix[aHeadX * 14 + aHeadY][mx * 14 + my] = 1;
                matrix[mx * 14 + my][aHeadX * 14 + aHeadY] = 1;
            } else {
                matrix[aHeadX * 14 + aHeadY][mx * 14 + my] = INT;
                matrix[aHeadX * 14 + aHeadY][mx * 14 + my] = INT;
            }
        }


        //调用算法计算最短路径
        floyd(matrix, aHeadX * 14 + aHeadY);

        if (nextDirection != -1) return nextDirection;

        for (int i = 0; i < 4; i++) {
            int x = aCells.get(aCells.size() - 1).x + dx[i];
            int y = aCells.get(aCells.size() - 1).y + dy[i];
            if (x >= 0 && x < 13 && y >= 0 && y < 14 && g[x][y] == 0) {
                return i;//选择一个合法的方向前进一格
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        new Bot().get();
    }

    //非递归实现
    public static void floyd(int[][] matrix, Integer sources) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                path[i][j] = -1;
            }
        }

        for (int m = 0; m < matrix.length; m++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][m] + matrix[m][j];
                        //记录经由哪个点到达
                        path[i][j] = m;
                    }
                }
            }
        }

        int minLength = INT, position = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (i != j && i == sources && g[j / 14][j % 14] == 3) {
                    if (matrix[i][j] == INT) {
                        //                        System.out.printf("(%d,%d)到(%d,%d)不可达\n", i / 14, i % 14, j / 14, j % 14);
                        //                        System.out.println(i + "到" + j + "不可达");
                    } else {
                        //                        System.out.print(i + "到" + j+"的最短路径长度是:" + matrix[i][j] + "\t");
                        //                        System.out.print("(" + i / 14 + "," + i % 14 + ")" + "到(" + j / 14 + "," + j % 14 + ")的最短路径长度是:" + matrix[i][j] + "\t");
                        //                        System.out.print("最短路径为:" + i + "->");
                        //                        System.out.printf("最短路径为:(%d,%d)->", i / 14, i % 14);
                        findPath(i, j);
                        //                        System.out.println(j);
                        //                        System.out.printf("(%d,%d)\n", j / 14, j % 14);

                        if (matrix[i][j] < minLength) {
                            minLength = matrix[i][j];
                            position = pathLen;
                            //                            System.out.println(position/14+" "+position%14);
                        }
                    }
                }
            }
        }
        if (minLength != INT) {
            int headX = sources / 14, headY = sources % 14;
            int nextX = position / 14, nextY = position % 14;
            int dx = nextX - headX, dy = nextY - headY;
            if (dx == -1 && dy == 0) {
                nextDirection = 0;
            } else if (dx == 0 && dy == 1) {
                nextDirection = 1;
            } else if (dx == 1 && dy == 0) {
                nextDirection = 2;
            } else if (dx == 0 && dy == -1) {
                nextDirection = 3;
            }
        }
    }

    //递归寻找路径
    public static void findPath(int i, int j) {
        int m = path[i][j];
        if (m == -1) {
            return;
        }

        findPath(i, m);
        //        System.out.print(m + "->");
        //        System.out.printf("(%d,%d)->", m / 14, m % 14);
        if (flag) {
            pathLen = m;
            flag = false;
        }

        findPath(m, j);
    }
}



CZL
1个月前

学累了敲个算法感觉真不错

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N;

int n, m;
struct Node
{
    int id;
    Node *next;
    Node(int _id): id(_id), next(NULL) {}
}*head[N];
int d[N], q[N];


void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++ )
        if(!d[i])
            q[ ++ tt] = i;

    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(auto p = head[t]; p; p = p->next)
            if( -- d[p->id] == 0)
                q[ ++ tt] = p->id;
    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d[b] ++ ;
        add(a, b);
    }

    if(!topsort()) puts("-1");
    else
    {
        for(int i = 0; i < n; i ++ ) 
            printf("%d ", q[i]);
    }

    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

CZL
3个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 1000010;

char p[N], s[M];
int ne[N];

int main()
{
    int n, m;
    scanf("%d%s", &n, p + 1);
    scanf("%d%s", &m, s + 1);

    for(int i = 2, j = 0; i <= n; i ++ )
    {
        while(j && p[j + 1] != p[i]) j = ne[j];
        if(p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }

    for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(p[j + 1] == s[i]) j ++ ;
        if(j == n)
        {
            cout << i - n << " ";
            j = ne[j];
        }
    }

    return 0;
}


活动打卡代码 AcWing 3537. 树查找

CZL
4个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        IR sc = new IR();
        int n = sc.nextInt();
        int a[] = new int[n + 1];
        int p = 1;
        for(int i = 1; i <= n; i ++ ) {
            a[i] = sc.nextInt();
        }
        int k = sc.nextInt();
        int cnt = (int)Math.pow(2, k - 1);
        int pre = cnt - 1;
        if(pre >= n) System.out.println("EMPTY");
        else {
            for(int i = pre + 1; i <= Math.min(cnt + pre, n); i ++ ) {
                System.out.print(a[i] + " ");
            }
        }

    }
    static class IR {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st;

        static boolean hasNext() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    return false;
                }
            }
            return true;
        }
        String next() {
            if(hasNext())
                return st.nextToken();
            return null;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}


活动打卡代码 AcWing 149. 荷马史诗

CZL
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;


int main()
{
    int n, k;
    cin >> n >> k;
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    while(n -- )
    {
        LL x;
        cin >> x;
        q.push({x, 0});
    }

    while((q.size() - 1) % (k - 1))
        q.push({0, 0});

    LL res = 0;
    while(q.size() > 1)
    {
        LL s = 0;
        int d = 0;
        for(int i = 0; i < k; i ++ ) {
            auto t = q.top();
            q.pop();
            s += t.x;
            d = max(d, t.y);
        }
        res += s;
        q.push({s, d + 1});
    }
    cout << res << " " << endl;
    cout << q.top().y << endl;

    return 0;
}


活动打卡代码 AcWing 148. 合并果子

CZL
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    while (n -- )
    {
        int x;
        cin >> x;
        q.push(x);
    }
    int res = 0;
    while(q.size() > 1) 
    {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        res += a + b;
        q.push(a + b);
    }

    cout << res;

    return 0;
}


活动打卡代码 AcWing 3765. 表达式树

CZL
4个月前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     string val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 */
class Solution {
public:
    string dfs(TreeNode *root) {
        if(!root) return "";
        if(!root -> left && !root -> right) return root -> val;
        return '(' + dfs(root -> left) + root -> val + dfs(root -> right) + ')';
    }

    string expressionTree(TreeNode* root) {
        return dfs(root -> left)  + root -> val + dfs(root ->right);
    }
};