Kalorona

P4093:「HEOI2016/TJOI2016」序列 – 题解

主要思路

大概就是要求一个子序列，使得在所有变化中始终长度最长。我们可以考虑分治，讨论变化的点的左右位置，然后用树状数组维护一下即可。

代码

// P4093.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, ai[MAX_N], mx[MAX_N], mn[MAX_N], dp[MAX_N], nodes[MAX_N], idx[MAX_N];

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

void update(int x, int d)
{
    for (; x <= n; x += lowbit(x))
        nodes[x] = max(nodes[x], d);
}

void clear(int x)
{
    for (; x <= n; x += lowbit(x))
        nodes[x] = 0;
}

int query(int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = max(ret, nodes[x]);
    return ret;
}

void solve(int l, int r)
{
    if (l == r)
        return (void)(dp[l] = max(dp[l], 1));
    int mid = (l + r) >> 1;
    solve(l, mid);
    for (int i = l; i <= r; i++)
        idx[i] = i;
    sort(idx + l, idx + mid + 1, [](const int &a, const int &b) { return mx[a] < mx[b]; });
    sort(idx + mid + 1, idx + r + 1, [](const int &a, const int &b) { return ai[a] < ai[b]; });
    for (int i = mid + 1, ptr = l; i <= r; i++)
    {
        while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
            update(ai[idx[ptr]], dp[idx[ptr]]), ptr++;
        dp[idx[i]] = max(dp[idx[i]], query(mn[idx[i]]) + 1);
    }
    for (int i = mid + 1, ptr = l; i <= r; i++)
        while (ptr <= mid && mx[idx[ptr]] <= ai[idx[i]])
            clear(ai[idx[ptr]]), ptr++;
    solve(mid + 1, r);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), mx[i] = mn[i] = ai[i];
    for (int i = 1, x, y; i <= n; i++)
        scanf("%d%d", &x, &y), mx[x] = max(mx[x], y), mn[x] = min(mn[x], y);
    solve(1, n);
    int ans = *max_element(dp + 1, dp + 1 + n);
    printf("%d\n", ans);
    return 0;
}

 

BZOJ2961:共点圆 – 题解

主要思路

这道题作为偏序题还是很有意思的，第一次碰到「二维偏序」。

先考虑偏序条件，设圆原点在 \((a, b)\)，现在有一个点 \((x, y)\)，如果这个点被覆盖：

\[ (x – a)^2 + (y – b)^2 \leq a^2 + b^2 \]

Continue reading →

LibreOJ#2353. 「NOI2007」 货币兑换 – 题解

主要思路

首先这题有个提示：

必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。

那么我们可以考虑直接算这个钱反复转手的最大值即可。设计状态 \(dp[i]\)，然后有转移：

\[ dp[i] = \max_{j \in [0, i)} \frac{(A_i Rate_j + B_i)f[j]}{A_j \times Rate_j + B_j} \]

Continue reading →

「Fortuna OJ」Aug 2nd – Group A 解题报告 / 集训队互测 2012 「李超」

A – Attack

这道题在 JZOJ 上面开 10s，遂 AC。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 60100;

struct point
{
    int x, y, prop, id;
    bool operator<(const point &pt) const { return prop < pt.prop; }
} nodes[MAX_N], *cur[MAX_N];

int n, m;
char opt[10];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &nodes[i].x, &nodes[i].y, &nodes[i].prop), nodes[i].id = i;
    sort(nodes + 1, nodes + 1 + n);
    for (int i = 1; i <= n; i++)
        cur[nodes[i].id] = &nodes[i];
    while (m--)
    {
        scanf("%s", opt + 1);
        int x, y, x_, y_, k;
        if (opt[1] == 'Q')
        {
            scanf("%d%d%d%d%d", &x, &y, &x_, &y_, &k);
            bool flag = false;
            for (int i = 1; i <= n; i++)
                if (nodes[i].x <= max(x, x_) && nodes[i].x >= min(x, x_) && nodes[i].y <= max(y, y_) && nodes[i].y >= min(y, y_))
                {
                    k--;
                    if (k == 0)
                    {
                        printf("%d\n", nodes[i].prop), flag = true;
                        break;
                    }
                }
            if (!flag)
                puts("It doesn't exist.");
        }
        else
        {
            scanf("%d%d", &x, &y), x++, y++;
            swap(cur[x]->x, cur[y]->x), swap(cur[x]->y, cur[y]->y);
            swap(cur[x]->id, cur[y]->id), swap(cur[x], cur[y]);
        }
    }
    return 0;
}

Continue reading →