头像

一念花开




离线:8天前


最近来访(3)
用户头像
tseven
用户头像
因为太懒只想睡觉QwQ
用户头像
潘潘_the_panda

活动打卡代码 AcWing 423. 采药

[//]: # 01背包问题,由于每个物品只用一次,可以优化到一维数组,具体的优化过程忘记了。但是由于每个物品只用一次,可以从大的物品先开始遍历


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    static int N=105;
    static StreamTokenizer st;
    static int T,M;
    static int time[]=new int[N];
    static int vlaue[]=new int[N];
    static int f[]=new int[1005];
    public static void main(String[] args)throws Exception {
       // System.setIn(new FileInputStream("E:\\data\\ax340.txt"));
        st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        T=nextInt();
        M=nextInt();
        for(int i=0;i<M;i++){
            time[i]=nextInt();
            vlaue[i]=nextInt();
        }
        for(int i=0;i<M;i++){
            for(int j=T;j>=time[i];j--){
                f[j]=Math.max(f[j],f[j-time[i]]+vlaue[i]);
            }
        }
        System.out.println(f[T]);

    }


    static int nextInt() throws Exception{
        st.nextToken();
        return (int)st.nval;
    }
}



活动打卡代码 AcWing 1275. 最大数

一念花开
3个月前

import java.io.*;

public class acw1275 {
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static Node[] tr;
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int m = Integer.valueOf(ss[0]), p = Integer.valueOf(ss[1]);
        tr = new Node[m * 4];
        int last = 0, n = 1, x;
        buildTree(1, 1, m);
        while(m -- > 0){
            ss = read.readLine().split(" ");
            x = Integer.valueOf(ss[1]);
            if("Q".equals(ss[0])){
                last = query(1, n - x + 1, n);
                log.write(last + "\n");
            }else{
                modify(1, n + 1, (last + x) % p);  //注意,这里根节点是1, 修改的数是从n + 1开始。
                n++;
            }
        }
        log.flush();

    }

    public static int query(int u, int l, int r){
        if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
        int mid = tr[u].l + tr[u].r >> 1;
        int v = 0;
        if(l <= mid) v = query(u << 1, l, r);
        if(r > mid) v = Math.max(v, query(u << 1 | 1, l, r));
        return v;
    }

    public static void pushUp(int u){
        tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
    }

    public static void modify(int u, int x, int c){
        if(tr[u].l == x && tr[u].r == x){
            tr[u].v = c;
        }else{
            int mid = tr[u].l + tr[u].r >> 1;
            if(x <= mid) modify(u << 1, x, c);
            else modify(u << 1 | 1, x, c);
            pushUp(u);
        }
    }


    public static void buildTree(int u, int l, int r){
        tr[u] = new Node(l, r);
        if(l == r) return;
        int mid = l + r >> 1;
        buildTree(u << 1, l , mid);
        buildTree(u << 1 | 1, mid + 1, r);
    }

    static class Node{
        int l, r, v;
        Node(int l, int r){
            this.l = l;
            this.r = r;
        }
    }

}



活动打卡代码 AcWing 173. 矩阵距离

一念花开
3个月前

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.io.*;
public class acw173 {

    static int N=1010;
    static  int n,m;
    static char g[][]=new char[N][N];
    static int dist[][]=new int[N][N];
    static int dx[]={-1,0,1,0};
    static int dy[]={0,1,0,-1};

    public static void main(String[] args)throws Exception {

        Scanner sc=new Scanner(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        n=sc.nextInt();
        m=sc.nextInt();
        for(int i=0;i<n;i++){
            char[] array=sc.next().toCharArray();
            for(int j=0;j<m;j++){
                g[i][j]=array[j];
            }
        }
        bfs();

        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < m;j ++)
            {
                out.write(dist[i][j] + " ");
            }
            out.write("\n");
        }
        out.flush();
    }

    static void bfs(){
        Queue<PIIs> queue=new LinkedList<>();
        for(int i=0;i<n;i++){
            Arrays.fill(dist[i],-1);
        }
        for(int i=0;i<n;i++){
           for(int j=0;j<m;j++){
                if(g[i][j]=='1'){
                    dist[i][j]=0;
                    queue.offer(new PIIs(i,j));
                }
           }
        }
        while (!queue.isEmpty()){
            PIIs t= queue.poll();
            for(int i=0;i<4;i++){
                int x=t.x+dx[i];
                int y=t.y+dy[i];
                if(x<0 || x>=n || y<0 || y>=m)continue;
                if(dist[x][y] !=-1)continue;
                dist[x][y]=dist[t.x][t.y]+1;
                queue.offer(new PIIs(x,y));
            }
        }
    }

    static class PIIs{
        int x;
        int y;

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



活动打卡代码 AcWing 1137. 选择最佳线路

一念花开
4个月前

[//]: # 主要思路,建立虚拟原点

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int N = 1010;
    static int M = 21010;
    static int n;
    static int m;
    static int s;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int INF = 0x3f3f3f3f;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static int spfa()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, INF);
        q.add(0);
        dist[0] = 0;
        st[0] = true;

        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }

        if(dist[s] == INF) return -1;
        return dist[s];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true)
        {
            String tmp = br.readLine();
            if(tmp == null) break;
            String[] s1 = tmp.split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            s = Integer.parseInt(s1[2]);
            Arrays.fill(h, -1);
            idx = 0;
            while(m -- > 0)
            {
                String[] s2 = br.readLine().split(" ");
                int a = Integer.parseInt(s2[0]);
                int b = Integer.parseInt(s2[1]);
                int c = Integer.parseInt(s2[2]);
                add(a,b,c);
            }
            int cnt = Integer.parseInt(br.readLine().trim());
            String[] s3 = br.readLine().split(" ");
            for(int i = 0;i < cnt;i ++)
            {
                int b = Integer.parseInt(s3[i]);
                add(0,b,0);
            }

            System.out.println(spfa());
        }
    }
}



活动打卡代码 AcWing 341. 最优贸易

一念花开
4个月前

[//]: # 正向求最小值,逆向求最大值,然后相减就可以获得答案了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int N = 100010;
    static int M = 2000010;
    static int n;
    static int m;
    static int[] w = new int[N];
    static int[] hs = new int[N];
    static int[] ht = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static boolean[] st = new boolean[N];
    static int[] cnt = new int[N];
    static int INF = 0x3f3f3f3f;
    static int[] dmin = new int[N];
    static int[] dmax = new int[N];
    static void add(int[] h,int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //type == 0表示从1到k正向求最小值
    //type == 1表示从n到k反向求最大值
    static void spfa(int[] h,int[] dist,int type)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        if(type == 0) 
        {
            Arrays.fill(dist, INF);
            q.add(1);
            dist[1] = w[1];
            st[1] = true;
        }
        else
        {
            Arrays.fill(dist, -INF);
            q.add(n);
            dist[n] = w[n];
            st[n] = true;
        }

        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if((type == 0 && dist[j] > Math.min(dist[t], w[j])) || (type == 1 && dist[j] < Math.max(dist[t], w[j])))
                {
                    if(type == 0) dist[j] = Math.min(dist[t], w[j]);
                    else dist[j] = Math.max(dist[t], w[j]);

                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++) w[i] = Integer.parseInt(s2[i - 1]);
        Arrays.fill(hs, -1);
        Arrays.fill(ht, -1);
        while(m -- > 0)
        {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            int c = Integer.parseInt(s3[2]);
            add(hs,a,b);
            add(ht,b,a);//建立反向边
            if(c == 2)
            {
                add(hs,b,a);
                add(ht,a,b);
            }

        }

        spfa(hs,dmin,0);
        spfa(ht,dmax,1);

        int res = -INF;
        for(int i = 1;i <= n;i ++) res = Math.max(res, dmax[i] - dmin[i]);
        System.out.println(res);
    }
}





一念花开
4个月前

[//]: # 新引入了一个知识点,需要存储每个连通块的数量,这个就存到根节点上


import java.io.*;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N=100010;
    static int p[]=new int[N];
    static int size[]=new int[N];
    static int n,m;
    public static void main(String[] args) throws Exception{
       // System.setIn(new FileInputStream("E:\\data\\ax340.txt"));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
            n=Integer.parseInt(st.nextToken());
            m=Integer.parseInt(st.nextToken());
            for(int i=1;i<=n;i++){
                p[i]=i;
                size[i]=1;
            }
            while (m-->0){
                st=new StringTokenizer(br.readLine());
                String s=st.nextToken();

                if("C".equals(s)){
                    int a=Integer.parseInt(st.nextToken());
                    int b=Integer.parseInt(st.nextToken());
                    a=find(a);
                    b=find(b);
                    if(a !=b){
                        p[a]=b;
                        size[b]+=size[a];
                    }
                }else if("Q1".equals(s)){
                    int a=Integer.parseInt(st.nextToken());
                    int b=Integer.parseInt(st.nextToken());
                    a=find(a);
                    b=find(b);
                    if(a==b){
                        System.out.println("Yes");
                    }else  {
                        System.out.println("No");
                    }
                }else {
                    int a=Integer.parseInt(st.nextToken());
                    System.out.println(size[find(a)]);
                }
            }
    }
    static int find(int a){
          if(p[a] !=a){
              p[a]=find(p[a]);
          }
          return p[a];
    }

}



活动打卡代码 AcWing 340. 通信线路

一念花开
5个月前
package month12;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main{
    static int N = 1010;
    static int M = 10010 * 2;
    static int m;
    static int n;
    static int k;
    static int INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];
    static int[] id = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans = INF;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean check(int x)
    {
        PriorityQueue<PIIs> q = new PriorityQueue<PIIs>();
        Arrays.fill(st,false);
        Arrays.fill(dist, INF);
        q.add(new PIIs(0,1));
        dist[1] = 0;

        while(!q.isEmpty())
        {
            PIIs p = q.poll();
            int t = p.second;
            int distance = p.first;

            if(st[t]) continue;
            st[t] = true;

            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                //若权值大于x则权值看成1
                if(w[i] > x)
                {
                    dist[j] = Math.min(dist[j], distance + 1);
                    q.add(new PIIs(dist[j],j));
                }
                //若权值小于等于x则权值看成0
                else
                {
                    dist[j] = Math.min(dist[j], distance);
                    q.add(new PIIs(dist[j],j));
                }
            }
        }

        if(dist[n] <= k) return true;
        return false;

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        k = Integer.parseInt(s1[2]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a,b,c);
            add(b,a,c);
        }
        int l = 0,r = 1000001;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        if(r == 1000001) System.out.println("-1");
        else System.out.println(r);
    }
}
class PIIs implements Comparable<PIIs>
{
    public int first;
    public int second;
    public PIIs(int first,int second)
    {
        this.first = first;
        this.second = second;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(first, o.first);
    }
}




活动打卡代码 AcWing 1135. 新年好

一念花开
5个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int N = 50010;
    static int M = 100010 * 2;
    static int m;
    static int n;
    static int INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[][] dist = new int[6][N];
    static int[] id = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans = INF;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void spfa(int start,int[] dist)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, INF);
        dist[start] = 0;
        q.add(start);
        st[start] = true;
        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
    //u表示已经走了多少个点,start表示当前点,distance表示已走路程
    static int dfs(int u,int start,int distance){

        if (u > 5) return distance;

        int res = INF;
        for (int i = 1; i <= 5; i ++ )
            if (!st[i])
            {
                int next = id[i];
                st[i] = true;
                res = Math.min(res, dfs(u + 1, i, distance + dist[start][next]));
                st[i] = false;
            }

        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        id[0] = 1;
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= 5;i ++) id[i] = Integer.parseInt(s2[i - 1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]);
            int b = Integer.parseInt(s3[1]);
            int c = Integer.parseInt(s3[2]);
            add(a,b,c);
            add(b,a,c);
        }

        for(int i = 0;i < 6;i ++)
        {
            spfa(id[i],dist[i]);
        }

       ans= dfs(1,0,0);
        System.out.println(ans);
    }
}



活动打卡代码 AcWing 154. 滑动窗口

一念花开
6个月前

[//]: # 用数组模拟栈的操作,这个是从前到后搜索的,因此比当前小的数,要么在栈里面,要么就没有。

#include <iostream>

using namespace std;

const int N=1e5+10;

int stk[N],tt;
int n;

int main(){


    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        //当栈为空或者栈顶的元素大于当前的元素的时候,就把栈里面的元素删除
        while(tt && stk[tt]>=x)tt--;
        if(!tt)printf("%d ",-1);
        else printf("%d ",stk[tt]);

        stk[++tt]=x;
    }

    return 0;
}


活动打卡代码 AcWing 791. 高精度加法

一念花开
6个月前

[//]: # 计算的时候,要以位数高的为基准,存储数据的时候,要把高位的从数组的地位开始存储,这样方便进位

#include <iostream>
#include <vector>

using namespace std;


vector<int> add(vector<int>&A,vector<int> &B){

    vector<int>C;

    if(A.size()<B.size())return add(B,A);

    int t=0;

    for(int i=0;i<A.size();i++){
        t+=A[i];
        if(i<B.size())t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)C.push_back(1);


    return C;

}

int main(){

    string a,b;
    vector<int>A,B;

    cin>>a>>b;

    for(int i=a.size()-1;i>=0;i--){
        A.push_back(a[i]-'0');
    }
    for(int i=b.size()-1;i>=0;i--){
        B.push_back(b[i]-'0');
    }

    auto c=add(A,B);

    for(int i=c.size()-1;i>=0;i--){
        cout<<c[i];
    }

    return 0;
}