头像

firstchoice




在线 


最近来访(44)
用户头像
耶耶
用户头像
wo怎么什么都不会
用户头像
辣鸡号航母
用户头像
雷鹤南
用户头像
dp咋学啊
用户头像
汪汪队立大功
用户头像
仙辞
用户头像
风华正茂_1
用户头像
-dzk-
用户头像
gky
用户头像
୧ꇴ૭
用户头像
n8sPxD
用户头像
wanglne
用户头像
未央灬
用户头像
进击的橡皮熊
用户头像
Epiphany_42
用户头像
Dinosaur.
用户头像
krio
用户头像
Faker丶
用户头像
寒酥遇雪

活动打卡代码 AcWing 826. 单链表

firstchoice
27分钟前

C++

#include<iostream>

using namespace std;

const int N = 100010;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
    idx = 0;
}

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++;
}

int main()
{
    int m;
    cin >> m;

    init();

    while(m--)
    {
        int k, x;
        char op;

        cin >> op;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }else if(op == 'D')
        {
            cin >> k;
            if(!k) head = ne[head];
            else remove(k - 1);
        }else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for(int i = head; i != -1; i = ne[i]) 
        cout << e[i] << ' ';

    cout << endl;
    return 0;
}


新鲜事 原文

firstchoice
13小时前
AcWing《蓝桥杯集训·每日一题》拼团优惠!https://www.acwing.com/activity/content/introduction/2869/group_buy/120225/


活动打卡代码 AcWing 802. 区间和

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

public class Main{
    static final int N = 300010;
    static int[] a = new int[N];
    static int[] s = new int[N];

    //去重(只要符合是第一个数或者后面一个数不等于前面一个数就是不重复的数)
    public static int unique(List<Integer> alls){
        int j = 0;
        for(int i = 0; i <= alls.size() - 1; i++){
            if(i == 0 || alls.get(i) != alls.get(i - 1)){
                alls.set(j, alls.get(i));
                j++;
            }
        }

        return j;
    }

    //二分查找(在集合中查找你现在的下标是在什么位置,因为需要符合我们要用的前缀和公式,
    //要让下标不是从0输出,最低的下标是1,符合前缀和的从1开始,所以输出的值加1)
    public static int find(int x, List<Integer> alls){
        int l = 0, r = alls.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(alls.get(mid) >= x) r = mid;
            else l = mid + 1;
        }

        return l + 1;
    }

    static class PII{
        int first, second;
        public PII(int x, int c){
            this.first = x;
            this.second = c;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);

        List<Integer> alls = new ArrayList<>();
        List<PII> add = new ArrayList<>();
        List<PII> query = new ArrayList<>();

        for(int i = 0; i < n; i++){
            String[] str1 = br.readLine().split(" ");
            int x = Integer.parseInt(str1[0]);
            int c = Integer.parseInt(str1[1]);
            add.add(new PII(x, c));

            alls.add(x);
        }

        for(int i = 0; i < m; i++){
            String[] str2 = br.readLine().split(" ");
            int l = Integer.parseInt(str2[0]);
            int r = Integer.parseInt(str2[1]);
            query.add(new PII(l, r));

            alls.add(l);
            alls.add(r);
        }

        // 去重
        Collections.sort(alls);
        int unique = unique(alls);
        alls = alls.subList(0, unique);

        // 处理查询
        for(PII item: add){
            int x = find(item.first, alls);
            a[x] += item.second;
        }

        // 预处理前缀和
        for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

        // 处理询问
        for(PII item: query){
            int l = find(item.first, alls), r = find(item.second, alls);
            System.out.println(s[r] - s[l - 1]);
        }
    }
}


活动打卡代码 AcWing 803. 区间合并

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

public class Main{
    public static int merge(List<PIIs> segs){
        List<PIIs> res = new ArrayList<>();

        Collections.sort(segs);

        int st = (int) -2e9, ed = (int) -2e9;
        for(PIIs seg: segs)
            if(ed < seg.first){
                if(st != (int) -2e9) res.add(new PIIs(st, ed));
                st = seg.first; ed = seg.second;
            }
            else
                ed = Math.max(ed, seg.second);

        if(st != (int) -2e9) res.add(new PIIs(st, ed));

        return res.size();
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<PIIs> segs = new ArrayList<>();
        for(int i = 0; i < n; i++){
            String[] str = br.readLine().split(" ");
            int l = Integer.parseInt(str[0]);
            int r = Integer.parseInt(str[1]);
            segs.add(new PIIs(l, r));
        }

        int res = merge(segs);
        System.out.println(res);
    }

    static class PIIs implements Comparable<PIIs>{
        int first,second;
        public PIIs(int first,int second){
            this.first = first;
            this.second = second;
        }
        public int compareTo(PIIs o){
            return Integer.compare(first, o.first);
        }
    }
}



import java.util.*;

public class Main{
    public static int lowbit(int x){
        return x & -x;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-- > 0){
            int x = sc.nextInt();

            int res = 0;
            while(x != 0){
                x -= lowbit(x);
                res++;
            }

            System.out.print(res + " ");
        }
    }
}



import java.util.Scanner;

public class Main{
    static final int N = 100010;
    static int[] q = new int[N];
    static int[] s = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i < n; i++) q[i] = sc.nextInt();

        int res = 0;
        for(int i = 0, j = 0; i < n; i++){
            s[q[i]]++;
            while(j < i && s[q[i]] > 1) s[q[j++]]--;
            res = Math.max(res, i - j + 1);
        }

        System.out.println(res);
    }
}


活动打卡代码 AcWing 790. 数的三次方根

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble();

        double l = -10000, r = 10000;
        while(r - l > 1e-8){
            double mid = (l + r) / 2;
            if(mid * mid * mid >= n) r = mid;
            else l = mid;
        }

        System.out.printf("%.6f\n", l);
    }
}


活动打卡代码 AcWing 788. 逆序对的数量

import java.io.*;

public class Main{
    static final int N = 100010;
    static int[] q = new int[N];
    static int[] tmp = new int[N];

    public static long mergeQuick(int l, int r){
        if(l == r) return 0;

        int mid = l + r >> 1;

        long res = mergeQuick(l, mid) + mergeQuick(mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
            if(q[i] <= q[j]) tmp[k++] = q[i++];
            else{
                tmp[k++] = q[j++];
                res += mid - i + 1;
            }

        while (i <= mid) tmp[k++] = q[i++];
        while (j <= r) tmp[k++] = q[j++];

        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];

        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        String[] str = br.readLine().split(" ");
        for(int i = 0; i < n; i++)  q[i] = Integer.parseInt(str[i]);

        System.out.println(mergeQuick(0, n - 1));
    }
}


新鲜事 原文

AcWing《考研算法辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/48/group_buy/119388/


活动打卡代码 AcWing 798. 差分矩阵

import java.io.*;

public class Main{
    static final int N = 1010;
    static int[][] a = new int[N][N];
    static int[][] b = new int[N][N];

    public static void insert(int x1, int y1, int x2, int y2, int c){
        b[x1][y1] += c;
        b[x1][y2 + 1] -= c;
        b[x2 + 1][y1] -= c;
        b[x2 + 1][y2 + 1] += c;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int q = Integer.parseInt(str[2]);

        for(int i = 1; i <= n; i++){
            String[] str1 = br.readLine().split(" ");
            for(int j = 1; j <= m; j++){
                a[i][j] = Integer.parseInt(str1[j - 1]);
            }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                insert(i, j, i, j, a[i][j]);

        while(q-- > 0){
            String[] str2 = br.readLine().split(" ");
            int x1 = Integer.parseInt(str2[0]);
            int y1 = Integer.parseInt(str2[1]);
            int x2 = Integer.parseInt(str2[2]);
            int y2 = Integer.parseInt(str2[3]);
            int c = Integer.parseInt(str2[4]);
            insert(x1, y1, x2, y2, c);
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                System.out.print(b[i][j] + " ");
            }
            System.out.println();
        }
    }
}