头像

莫能与之争


访客:2547

离线:10天前


分享 线性组合

对应整数数列𝐴_1,𝐴_2,…,𝐴_𝑛 是否存在𝑋_1,𝑋_2,…,𝑋_𝑛,使得𝐴_1 𝑋_1+𝐴_2 𝑋_2+…+𝐴_𝑛 𝑋_𝑛=𝐶,其中 gcd⁡(𝐴_1,𝐴_2,…,𝐴_𝑛)|𝐶(𝑛≥2) 。如请找出一组整数解(𝑥_1,𝑥_2,𝑥_3,𝑥_4)满足12𝑥_1+24𝑥_2+18𝑥_3+15𝑥_4=3 。

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

public class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        InputReader in = new InputReader(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }


    static class Solver {
        long[] ans = new long[10];
        long[] a = {-1, 12, 24, 28, 15};
        long[] g = new long[10];

        long gcd(long a, long b) {
            if (b == 0) return a;
            return gcd(b, a % b);
        }

        void exgcd(long a, long b, long[] d, long[] x, long[] y) {
            if (b == 0) {
                x[0] = 1;
                y[0] = 0;
                d[0] = a;
                return;
            }
            exgcd(b, a % b, d, y, x);
            y[0] -= a / b * x[0];
        }

        void solve(int i, long c) {
            long[] x = new long[2];
            long[] y = new long[2];
            long[] d =new long[2];
            exgcd(g[i - 1], a[i], d, x, y);
            y[0] = y[0] * (c / d[0]);
            x[0] = x[0] * (c / d[0]);
            ans[i] = y[0];
            if (i == 2) {
                ans[i - 1] = x[0];
            } else {
                solve(i - 1, c - a[i] * y[0]);
            }
        }
        public void solve(InputReader in, PrintWriter out) {
            long dd = a[1];
            for (int i = 1; i < 4; i++) {
                dd = gcd(dd, a[i]);
                g[i] = dd;
            }
            solve(4, 3);
            long s = 0;
            for (int i = 1; i <= 4; i++) {
                s += ans[i] * a[i];
                out.println(ans[i]);
            }
            out.println(s);
        }

    }

}


活动打卡代码 AcWing 244. 谜一样的牛

写的时候模拟出了思路,但复杂度是O(N^2)的,不知道如何快速求一个可以修改的数组的第k小
看了题解后懂得了将第k小问题转化成判定问题,用二分实现查找第k小

import java.util.*;
import java.io.*;
import java.util.StringTokenizer;
import java.util.concurrent.ExecutorService;


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        InputReader in = new InputReader(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {

        final int N = (int) (1e5) + 10;
        int n;
        int[] a = new int[N];
        int[] bit = new int[N];
        int[] ans = new int[N];

        int lowbit(int x) {
            return x & -x;
        }
        void add(int x, int v) {
            for (int i = x; i <= n; i += lowbit(i)) bit[i] += v;
        }
        int sum(int x) {
            int ret = 0;
            for (int i = x; i >= 1; i -= lowbit(i)) ret += bit[i];
            return ret;
        }
        public void solve(InputReader in, PrintWriter out) {
            n = in.nextInt();
            for (int i = 2; i <= n; i++) a[i] = in.nextInt();
            for (int i = n; i >= 1; i--) {
                int l = 1, r = n;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (mid - sum(mid) >= a[i] + 1) r = mid;
                    else l = mid + 1;
                }
                ans[i] = l;
                add(l, 1);
            }
            for (int i = 1; i <= n; i++) out.println(ans[i]);
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {
            return Long.parseLong(next());
        }
        Double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}



注意维护的前缀和数组可能溢出

import java.util.*;
import java.io.*;
import java.util.StringTokenizer;
import java.util.concurrent.ExecutorService;


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        InputReader in = new InputReader(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {

        final int N = (int) (1e5) + 10;
        long[][] bit = new long[2][N];

        int lowbit(int x) {
            return x & -x;
        }
        void add(int k, int x, long v) {
            for (int i = x; i < N; i += lowbit(i)) bit[k][i] += v;
        }
        long pre(int k, int x) {
            long ret = 0;
            for (int i = x; i >= 1; i -= lowbit(i)) ret += bit[k][i];
            return ret;
        }
        long getSum(int x) {
            return (x + 1) * pre(0, x) - pre(1, x);
        }
        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();
            int last = 0, now = 0;
            for (int i = 1; i <= n; i++) {
                now = in.nextInt();
                add(0, i, now - last);
                add(1, i, (long) i * (now - last));
                last = now;
            }
            char op;
            int l, r;
            long v;
            while (m-- > 0) {
                op = in.next().charAt(0);
                l = in.nextInt();
                r = in.nextInt();
                if (op == 'Q') {
                    out.println(getSum(r) - getSum(l - 1));
                } else {
                    v = in.nextInt();
                    add(0, l, v);
                    add(0, r + 1, -v);
                    add(1, l, l * v);
                    add(1, r + 1, -(r + 1) * v);
                }
            }
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {
            return Long.parseLong(next());
        }
        Double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}



import java.util.*;
import java.io.*;
import java.util.StringTokenizer;
import java.util.concurrent.ExecutorService;


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {

        final int N = (int) (1e5) + 10;
        int[] bit = new int[N];
        int[] a = new int[N];

        int lowbit(int x) {
            return x & -x;
        }
        int pre(int x) {
            int ret = 0;
            for (int i = x; i >= 1; i -= lowbit(i)) ret += bit[i];
            return ret;
        }
        void add(int x, int val) {
            for (int i = x; i < N; i += lowbit(i)) bit[i] += val;
        }

        public void solve(Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();

            for (int i = 1; i <= n; i++) a[i] = in.nextInt();

            char op;
            int le, ri, d;

            while (m-- > 0) {
                op = in.next().charAt(0);
                if (op == 'Q') {
                    d = in.nextInt();
                    out.println(pre(d) + a[d]);
                } else {
                    le = in.nextInt();
                    ri = in.nextInt();
                    d = in.nextInt();
                    add(le, d);
                    add(ri + 1, -d);
                }
            }
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 241. 楼兰图腾

import java.util.*;
import java.io.*;
import java.util.StringTokenizer;
import java.util.concurrent.ExecutorService;


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {

        final int N = (int) (2e5) + 10;
        int[] bit = new int[N];

        int lowbit(int x) {
            return x & -x;
        }
        int pre(int x) {
            int ret = 0;
            for (int i = x; i >= 1; i -= lowbit(i)) ret += bit[i];
            return ret;
        }
        void add(int x, int val) {
            for (int i = x; i < N; i += lowbit(i)) bit[i] += val;
        }

        public void solve(Scanner in, PrintWriter out) {
            long ans1 = 0, ans2 = 0;
            int n = in.nextInt();
            for (int i = 1; i <= n; i++) {
                int y = in.nextInt();
                long t1 = pre(y);
                int t2 = (i - 1 - pre(y));
                ans1 += t1 * (y - 1 - t1);
                ans2 += t2 * (n - y - t2);
                add(y, 1);
            }
            out.println(ans2 + " " + ans1);
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 1243. 糖果

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


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {


        final int N = 1 << 21;
        int n, m, k, t;
        int[] sta = new int[N];
        int[] dp = new int[N];

        public void solve(Scanner in, PrintWriter out) {
            n = in.nextInt();
            m = in.nextInt();
            k = in.nextInt();
            Arrays.fill(dp, Integer.MAX_VALUE);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= k; j++) {
                    t = in.nextInt();
                    sta[i] |= 1 << (t - 1);
                }
                dp[sta[i]] = 1;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j < (1 << m); j++) {
                    if (dp[j] != Integer.MAX_VALUE) {
                        dp[sta[i] | j] = Math.min(dp[sta[i]] + dp[j], dp[sta[i] | j]);
                    }
                }
            }
            out.println(dp[(1 << m) - 1] == Integer.MAX_VALUE ? 0 : dp[(1 << m) - 1]);
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 1225. 正则问题

递归题,有个类似题,将数字转成二进制下表示 比如 9 -> 2^(2^1 + 1) + 2^(0)

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


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {

        String str;
        int k = 0;

        int dfs() {
            int res = 0;
            while (k < str.length()) {
                char ch = str.charAt(k);
                if (ch == '(') {
                    k++;
                    res += dfs();
                    k++;
                } else if (ch == ')') {
                    break;
                } else if (ch == '|') {
                    k++;
                    res = Math.max(res, dfs());
                } else {
                    res++;
                    k++;
                }
            }
            return res;
        }

        public void solve(Scanner in, PrintWriter out) {
            str = in.next();
            out.println(dfs());
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 1296. 聪明的燕姿

这个题还是有一些想不明白的地方

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


class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {
        final int N = 2 * (int) (1e5) + 10;
        int[] primes = new int[N];
        int tot = 0;
        int cnt = 0;
        boolean[] notPrime = new boolean[N];
        int[] ans = new int[N];

        boolean chk(int x) {
            if (x < N) return !notPrime[x];
            int ed = (int) Math.sqrt(x);
            for (int i = 1; primes[i] <= ed; i++) {
                if (x % primes[i] == 0) return false;
            }
            return true;
        }

        void makePrimes() {
            for (int i = 2; i < N; i++) {
                if (!notPrime[i]) primes[++tot] = i;
                for (int j = 1; j <= tot; j++) {
                    if (i * primes[j] >= N) break;
                    notPrime[i * primes[j]] = true;
                    if (i % primes[j] == 0) break;
                }
            }
        }

        void dfs(int lastp, int prod, int remain) {
            if (remain == 1) {
                ans[++cnt] = prod;
                return;
            }
            int ed = (int) Math.sqrt(remain);
            if ((remain - 1) > (lastp == 0 ? 1 : primes[lastp]) && chk(remain - 1)) ans[++cnt] = prod * (remain - 1);
            for (int i = lastp + 1; primes[i] <= ed; i++) {
                int p = primes[i];
                for (int sum = p + 1, tmp = p; sum <= remain; tmp *= p, sum += tmp) {
                    if (remain % sum == 0) dfs(i, prod * tmp, remain / sum);
                }
            }
        }

        public void solve(Scanner in, PrintWriter out) {
            makePrimes();
            while (in.hasNextInt()) {
                int n = in.nextInt();
                cnt = 0;
                dfs(0, 1, n);
                out.println(cnt);
                if (cnt != 0) Arrays.sort(ans, 1, cnt + 1);
                for (int i = 1; i <= cnt; i++) out.print("" + ans[i] + (i != cnt ? ' ' : '\n'));
            }
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 1295. X的因子链

import java.io.*;
import java.util.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        Scanner in = new Scanner(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {
        final int N = (1 << 20) + 10;
        int tot = 0;
        int[] primes = new int[N];
        int[] minp = new int[N];
        boolean[] not_prime = new boolean[N];
        int[] cnt = new int[20000];
        long[] factorial = new long[40];

        void getPrimes() {
            for (int i = 2; i < N; i++) {
                if (!not_prime[i]) {
                    primes[++tot] = i;
                    minp[i] = i;
                }
                for (int j = 1; j <= tot; j++) {
                    if (primes[j] * i >= N) break;
                    not_prime[primes[j] * i] = true;
                    minp[primes[j] * i] = primes[j];
                    if (i % primes[j] == 0) break;
                }
            }
        }
        public void solve(Scanner in, PrintWriter out) {

            getPrimes();
            factorial[1] = 1;
            for (int i = 2; i <= 30; i++) factorial[i] = factorial[i - 1] * i;

            while (in.hasNextInt()) {
                int n = in.nextInt();
                int tot = 0, sum = 0;
                while (n > 1) {
                    int mp = minp[n];
                    cnt[++tot] = 0;
                    while (n % mp == 0) {
                        cnt[tot]++;
                        n /= mp;
                    }
                    sum += cnt[tot];
                }
                long ans = factorial[sum], tmp = 1;
                for (int i = 1; i <= tot; i++) {
                    tmp *= factorial[cnt[i]];
                }
                out.println(sum + " " + ans / tmp);
            }
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}


活动打卡代码 AcWing 1246. 等差数列

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) {
        InputStream is = System.in;
        OutputStream os = System.out;
        InputReader in = new InputReader(is);
        PrintWriter out = new PrintWriter(os);

        Solver solver = new Solver();

        solver.solve(in, out);

        out.close();

    }

    static class Solver {
        final int N = 1010;
        BigInteger[] fib = new BigInteger[N];

        int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }

        public void solve(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int[] a = new int[n + 1];
            for (int i = 1; i <= n; i++) a[i] = in.nextInt();
            Arrays.sort(a, 1, n + 1);
            int d = a[2] - a[1];
            for (int i = 3; i <= n; i++) {
                d = gcd(d, a[i] - a[i - 1]);
            }
            if (a[n] - a[1] == 0) out.println(n);
            else out.println((a[n] - a[1]) / d + 1);
        }
    }

    static class InputReader {
        BufferedReader br = null;
        StringTokenizer st = null;
        InputReader(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }
        String nextLine() {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        Integer nextInt() {
            return Integer.parseInt(next());
        }
        Long nextLong() {return Long.parseLong(next());}
    }
}