跳转至

ABC340(A-F)

A - Arithmetic Progression

题目大意

有一个首项为 \(A\)，末项为 \(B\)，公差为 \(D\) 的等差数列，输出这个数列的所有项。

参考代码 
#include <iostream>

using namespace std;

int main()
{
    int a, b, d;
    cin >> a >> b >> d;
    do {
        cout << a << ' ';
        a += d;
    }while(a <= b);
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int d = in.nextInt();
        do {
            System.out.printf("%d ", a);
            a += d;
        } while (a <= b);
        in.close();
    }
}

B - Append

题目大意

维护一个数列，有 \(Q\) 个询问，询问有两种类型：

1 x：在数列末尾添加一个数字 \(x\)。

2 k：输出末尾倒数第 \(k\) 个数字。

参考代码 
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int q, op, x;
    cin >> q;
    vector<int> a;
    while(q--)
    {
        cin >> op >> x;
        if(op == 1)
            a.push_back(x);
        else
            cout << a[a.size() - x] << endl;
    }
    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q, op, x;
        q = in.nextInt();
        ArrayList<Integer> a = new ArrayList<>();
        while (q-- > 0) {
            op = in.nextInt();
            x = in.nextInt();
            if (op == 1)
                a.add(x);
            else
                System.out.println(a.get(a.size() - x));
        }
        in.close();
    }
}

C - Divide and Divide

题目大意

给你一个整数 \(N(2 \le N \le 10^{17})\)，初始时只有 \(N\) 一个数字，一直重复以下操作：

  • 选择一个不小于 \(2\) 的数字，假设选定的数字是 \(x\)，然后花费 \(x\) 元将这个数字分裂成 \(\lfloor\frac{x}{2}\rfloor\) 和 \(\lceil\frac{x}{2}\rceil\)

问：一直执行操作，直到无法执行任何操作，需要花费多少元？

解题思路

定义 \(dp[i]\) 表示选中数字 \(i\)，同时将 \(i\) 后续分裂的所有数字都递归执行操作，直到无法执行任何操作所需要的花费。

则有：

\[ dp[i] = \left\{ \begin{matrix} 0, & i = 1\\ i + dp[\frac{i}{2}] + dp[\frac{i+1}{2}], & i \ge 2 \end{matrix} \right. \]

考虑到 \(N \le 10^{17}\) 显然不能从前往后算，注意到计算某个 \(dp[i]\) 的值实际上不会遍历所有点，所以记忆化搜索即可。

参考代码 
#include <iostream>
#include <unordered_map>

using namespace std;

typedef long long LL;
unordered_map<LL, LL> dp;
LL DP(LL x)
{
    if(dp.count(x))
        return dp[x];
    LL ans = DP(x/2) + DP((x+1)/2) + x;
    dp[x] = ans;
    return ans;
}

int main()
{
    LL n;
    cin >> n;
    dp[1] = 0;
    cout << DP(n);
    return 0;
}

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    private static HashMap<Long, Long> dp = new HashMap<>();

    private static long DP(long x) {
        if (dp.containsKey(x))
            return dp.get(x);
        long ans = DP(x / 2) + DP((x + 1) / 2) + x;
        dp.put(x, ans);
        return ans;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        dp.put(1l, 0l);
        System.out.println(DP(n));
        in.close();
    }
}

D - Super Takahashi Bros.

题目大意

给你 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个点，初始的时候你在点 \(1\)。当你在点 \(i(1 \le i < N)\) 时，可以花费 \(A_i(1 \le A_i \le 10^9)\) 元移动到点 \(i+1\)，也可以花费 \(B_i(1 \le B_i \le 10^9)\) 移动到点 \(X_i(1 \le X_i \le N)\)。问：从点 \(1\) 移动到点 \(N\) 最少要花费多少元？

解题思路

最短路模板。

参考代码 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
const int maxm = 2 * maxn;
int head[maxn], edge[maxm], ne[maxm], cost[maxm], idx = 1;
void add(int u, int v, int w)
{
    edge[idx] = v;
    ne[idx] = head[u];
    cost[idx] = w;
    head[u] = idx++;
}

struct Node {
    int u;
    LL d;
    Node(int _u, LL _d) : u(_u), d(_d) {}
    bool operator > (const Node &y) const
    {return d > y.d;}
};

int n;

LL dijkstra()
{
    LL dis[maxn];
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<Node, vector<Node>, greater<Node>> heap;
    heap.push(Node(1, 0));
    while(!heap.empty())
    {
        Node p = heap.top();
        heap.pop();
        int u = p.u;
        LL d = p.d;
        if(d > dis[u])
            continue;
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            LL nd = d + cost[i];
            if(nd < dis[v])
            {
                dis[v] = nd;
                heap.push(Node(v, nd));
            }
        }
    }
    return dis[n];
} 

int main()
{
    cin >> n;
    for(int i = 1, a, b, x; i < n; i++)
    {
        scanf("%d %d %d", &a, &b, &x);
        add(i, i+1, a);
        add(i, x, b);
    }
    cout << dijkstra() << endl;
    return 0;
}

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Node {
    int u;
    long d;

    public Node(int _u, long _d) {
        u = _u;
        d = _d;
    }
}

public class Main {
    private static int n;
    private static int[] head, edge, ne, cost;
    private static long[] dis;
    private static int idx;

    private static void graph_init(int n, int m) {
        idx = 1;
        head = new int[n];
        dis = new long[n];
        edge = new int[m];
        ne = new int[m];
        cost = new int[m];
    }

    private static void add(int u, int v, int w) {
        edge[idx] = v;
        cost[idx] = w;
        ne[idx] = head[u];
        head[u] = idx++;
    }

    private static long dijkstra() {
        Arrays.fill(dis, 0x3f3f3f3f3f3f3f3fl);
        dis[1] = 0;
        PriorityQueue<Node> heap = new PriorityQueue<>((x, y) -> Long.compare(x.d, y.d));
        heap.add(new Node(1, 0));
        while (!heap.isEmpty()) {
            Node p = heap.remove();
            int u = p.u;
            long d = p.d;
            if (d > dis[u])
                continue;
            for (int i = head[u]; i > 0; i = ne[i]) {
                int v = edge[i];
                long nd = d + cost[i];
                if (nd < dis[v]) {
                    dis[v] = nd;
                    heap.add(new Node(v, nd));
                }
            }
        }
        return dis[n];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        graph_init(n + 1, 2 * n);
        for (int i = 1, a, b, x; i < n; i++) {
            a = in.nextInt();
            b = in.nextInt();
            x = in.nextInt();
            add(i, i + 1, a);
            add(i, x, b);
        }
        System.out.println(dijkstra());
        in.close();
    }
}

E - Mancala 2

题目大意

有 \(N(1 \le N \le 2 \times 10^5)\) 个盒子，初始的时候第 \(i\) 个盒子有 \(A_i(0 \le A_i \le 10^9)\) 个球，\(N\) 个盒子的编号为 \(0\) 到 \(N-1\)，第 \(i\) 个盒子的下一个盒子是 \((i+1) \bmod N\)，你需要执行 \(M(1 \le M \le 2 \times 10^5)\) 次操作，每次操作给你一个整数 \(B_i\)，流程为：

  • 首先，将编号为 \(B_i\) 的盒子的所有球拿在手中。
  • 然后，从 \(B_i\) 的下一个盒子开始，依次给这些盒子放入一个小球，直到手中没有小球。

问：在 \(M\) 次操作之后，每个盒子有多少小球？

解题思路

对于一次操作，假设 \(B_i\) 盒子有 \(X\) 个球，首先将 \(B_i\) 盒子置 \(0\)，然后令 \(k = \lfloor\frac{X}{N}\rfloor\)，\(r = X \bmod N\)，则相当于给= \([0, N-1]\) 上的点都加上 \(k\)，剩下 \(r\) 个球，拆成 \([x, N-1]\) 和 \([0, y]\) 两个区间加 \(1\) 的操作即可。涉及到单点查，区间改，线段树和树状数组都可以。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
int n, m, a[maxn];
LL t[maxn];

int lowbit(int x)
{return x & -x;}

void update(int x, LL k)
{
    for(; x <= n; x += lowbit(x))
        t[x] += k;
}

void add(int l, int r, LL k)
{
    ++l, ++r;
    update(l, k);
    update(r+1, -k);
}

LL ask(int x)
{
    LL sum = 0;
    for(; x; x -= lowbit(x))
        sum += t[x];
    return sum;
}

LL query(int x)
{
    ++x;
    return ask(x) + a[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int x;
    while(m--)
    {
        scanf("%d", &x);
        LL y = query(x);
        if(!y)
            continue;
        add(x, x, -y);
        if(x + 1 < n)
        {
            int r = min(n-1ll, x + y);
            y -= r - x;
            add(x+1, r, 1);
        }
        if(!y)
            continue;
        add(0, n-1, y/n);
        y %= n;
        if(!y)
            continue;
        add(0, y-1, 1);
    }
    for(int i = 0; i < n; i++)
        printf("%lld ", query(i));
    return 0;
}

import java.util.Scanner;

public class Main {
    private static int n, m;
    private static int[] a;
    private static long[] t;

    private static int lowbit(int x) {
        return x & -x;
    }

    private static void update(int x, long k) {
        for (; x <= n; x += lowbit(x))
            t[x] += k;
    }

    private static void add(int l, int r, long k) {
        l++;
        r++;
        update(l, k);
        update(r + 1, -k);
    }

    private static long ask(int x) {
        long sum = 0;
        for (; x > 0; x -= lowbit(x))
            sum += t[x];
        return sum;
    }

    private static long query(int x) {
        ++x;
        return ask(x) + a[x];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        a = new int[n + 1];
        t = new long[n + 1];
        for (int i = 1; i <= n; i++)
            a[i] = in.nextInt();
        int x;
        while (m-- > 0) {
            x = in.nextInt();
            long y = query(x);
            if (y == 0)
                continue;
            add(x, x, -y);
            if (x + 1 < n) {
                int r = (int) Math.min(n - 1l, x + y);
                y -= r - x;
                add(x + 1, r, 1);
            }
            if (y == 0)
                continue;
            add(0, n - 1, y / n);
            y %= n;
            if (y == 0)
                continue;
            add(0, (int) y - 1, 1l);
        }
        for (int i = 0; i < n; i++)
            System.out.printf("%d ", query(i));
        in.close();
    }
}

F - S = 1

题目大意

在平面上给你一个点 \((X, Y)\)，其中 \((X, Y) \neq (0, 0)\)，问：是否存在另一个点 \((A, B)\) 满足以下条件：

  • \(-10^{18} \le A, B \le 10^{18}\)​
  • \((0, 0)\)，\((X, Y)\) 和 \((A, B)\) 三个点组成的三角形的面积为 \(1\)。

如果存在这样的点，输出这个点的坐标，否则输出 -1。

解题思路

原点到点 \((X, Y)\) 的直线为 \(Yx - Xy = 0\)，设 \((A, B)\) 到这条直线的距离为 \(d\)，则有：

\[ d = \frac{|YA-XB|}{\sqrt{X^2+Y^2}} \]

又因为 \(\sqrt{X^2+Y^2}\) 表示原点到 \((X, Y)\) 的距离，即 \(d\sqrt{X^2+Y^2} = 2\)。

问题转化为 \(|YA-XB|=2\) 在 \(-10^{18} \le A, B \le 10^{18}\) 上是否有解。

不失一般性，考虑 \(YA-XB=2\) 是否有解，令 \(P = |Y|\)，\(Q = |-X|\)，即求不定方程 \(Pa+Qb = 2\) 是否有解。

拓展欧几里得算法可以求出形如这样的 \(Pa+Qb = \gcd(P, Q)\) 的一组解，显然，本题的条件下首先需要满足 \(\gcd(P, Q)\) 等于 \(1\) 或者 \(2\)，否则无解。

使用拓展欧几里得算法求出一组解（如果 \(\gcd(P, Q) = 1\)，还需要将得到的解乘 \(2\) ），判断是否满足 \(-10^{18} \le A, B \le 10^{18}\)，然后再将正负关系映射回去即可。

参考代码 
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main()
{
    LL a, b, x, y;
    cin >> a >> b;
    LL g = exgcd(abs(b), abs(a), x, y);
    if(g > 2)
        puts("-1");
    else
    {
        if(g == 1)
            x *= 2, y *= 2;
        if(abs(x) > 1E17 || abs(y) > 1E17)
            puts("-1");
        if(b < 0)
            x *= -1;
        if(a > 0)
            y *= -1;
        printf("%lld %lld", x, y);
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static long[] exgcd(long a, long b) {
        if (b == 0) {
            return new long[] { 1, 0, a };
        }
        long[] xy = exgcd(b, a % b);
        long x = xy[0], y = xy[1];
        xy[0] = y;
        xy[1] = x - a / b * y;
        return xy;
    }

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

        long a, b;
        a = in.nextLong();
        b = in.nextLong();
        long[] res = exgcd(Math.abs(b), Math.abs(a));
        long x = res[0], y = res[1], g = res[2];
        if (g > 2)
            System.out.println(-1);
        else {
            if (g == 1) {
                x *= 2;
                y *= 2;
            }
            if (Math.abs(x) > 1E17 || Math.abs(y) > 1E17)
                System.out.println(-1);
            if (b < 0)
                x *= -1;
            if (a > 0)
                y *= -1;
            System.out.printf("%d %d", x, y);
        }
        in.close();
    }
}
最后更新: 2024-03-24
创建日期: 2024-03-16