声之形

KafuuChinocpp / 2023-05-05 / 原文

胡测9 (by gtm1514)

今天出发参加清北营，感觉自己已经完全丧失写暴力的能力，正解也从来不会打，所以……

清北营要保龄了！！！

然后是比赛前的标准题目。

T1 Heavenly Blast

这是平面最近点对问题的扩展。

假设当前三角形最小周长为 \(C\) ，考虑平面上一个边长为 \(\tfrac{\sqrt{2}}{6}C\) 的正方形，由于正方形内最远点对距离为 \(\tfrac{C}{3}\) ，因此正方形内最多存在 \(2\) 个点，考虑在集合内加入一个点，发现只有与这个点的距离小于 \(\tfrac{C}{2}\) 的店可以更新答案，根据上面的结论发现这样的点只有 \(O(1)\) 个，找到这些点后暴力更新即可。

具体的，将所有点按照 \(x\) 为第一关键字， \(y\) 为第二关键字排序，维护 multiset 并按照 \(y\) 为第一关键字， \(x\) 为第二关键字排序，首先考虑更新答案，找到与当前点在 \(y\) 坐标上相差 \(\tfrac{1}{2}\) 以内的所有点，如果这个点与当前点在 \(x\) 坐标上相差大于 \(\tfrac{1}{2}\) ，则从 multiset 中删除，否则用于更新答案，容易发现每个点会被插入并删除一次，并且更新答案的操作为 \(O(n)\) 次，总复杂度为 \(O(n\log n)\) 。

code

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
const int max1 = 1e6;
const double inf = 3e9, eps = 1e-6;
int n;
struct Point
{
    double x, y;
    Point () {}
    Point ( double __x, double __y )
        { x = __x, y = __y; }
    bool operator < ( const Point &A ) const
    {
        if ( y == A.y )
            return x < A.x;
        return y < A.y;
    }
}A[max1 + 5], B[max1 + 5];
int len;
multiset <Point> Set;
bool Cmp ( const Point &A, const Point &B )
{
    if ( A.x == B.x )
        return A.y < B.y;
    return A.x < B.x;
}
double ans;
double Get_Dis ( const Point &A, const Point B )
    { return sqrt(( A.x - B.x ) * ( A.x - B.x ) + ( A.y - B.y ) * ( A.y - B.y )); }
int main ()
{
    freopen("hb.in", "r", stdin);
    freopen("hb.out", "w", stdout);
    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%lf%lf", &A[i].x, &A[i].y);
    ans = inf;
    sort(A + 1, A + 1 + n, Cmp);
    Set.clear();
    for ( int i = 1; i <= n; i ++ )
    {
        len = 0;
        Point lim = Point(-inf, A[i].y - ans * 0.5 - eps);
        while ( true )
        {
            auto it = Set.lower_bound(lim);
            if ( it == Set.end() || ( it -> y ) - A[i].y > ans * 0.5 )
                break;
            if ( A[i].x - ( it -> x ) > ans * 0.5 )
                Set.erase(it);
            else
                B[++len] = *it, lim = Point(( it -> x ) + eps, it -> y);
        }
        for ( int j = 1; j <= len; j ++ )
            for ( int k = j + 1; k <= len; k ++ )
                ans = min(ans, Get_Dis(A[i], B[j]) + Get_Dis(A[i], B[k]) + Get_Dis(B[j], B[k]));
        Set.insert(A[i]);
    }
    printf("%.8lf\n", ans);
    return 0;
}

T2 QZKago Requiem

考虑二分答案，由于 \(f\) 单调递增，因此可以贪心的让前面的段尽可能长。

发现求解一个已知字符串的代价的最优复杂度为 \(O(|S|)\) ，因此求解一个尽可能长的字符串，我们可以先从小到大倍增，然后二分，容易发现求解代价时，字符串长度不超过最终长度的 \(2\) 倍，因此总复杂度为 \(O(n\log n\log w)\) 。

code

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <utility>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int n, k, f[max1 + 5];
char s[max1 + 5];
map < pair <int, int>, long long > Map;
struct Suffix_Automaton
{
    int trans[max1 * 2 + 5][2], link[max1 * 2 + 5], maxlen[max1 * 2 + 5], sum[max1 * 2 + 5], last, total;
    vector <int> edge[max1 * 2 + 5];
    void Clear ()
        { trans[0][0] = trans[0][1] = maxlen[0] = sum[0] = last = total = 0; link[0] = -1; return; }
    void Extend ( int id )
    {
        int now = ++total, p = last;
        trans[now][0] = trans[now][1] = 0;
        maxlen[now] = maxlen[p] + 1;
        sum[now] = 1;
        last = now;
        while ( p != -1 && !trans[p][s[id] - '0'] )
            trans[p][s[id] - '0'] = now, p = link[p];
        if ( p == -1 )
            link[now] = 0;
        else
        {
            int q = trans[p][s[id] - '0'];
            if ( maxlen[q] == maxlen[p] + 1 )
                link[now] = q;
            else
            {
                int clone = ++total;
                trans[clone][0] = trans[q][0];
                trans[clone][1] = trans[q][1];
                link[clone] = link[q];
                maxlen[clone] = maxlen[p] + 1;
                sum[clone] = 0;
                while ( p != -1 && trans[p][s[id] - '0'] == q )
                    trans[p][s[id] - '0'] = clone, p = link[p];
                link[q] = link[now] = clone;
            }
        }
        return;
    }
    void Build ( int L, int R )
    {
        Clear();
        for ( int i = L; i <= R; i ++ )
            Extend(i);
        for ( int i = 0; i <= total; i ++ )
            edge[i].clear();
        for ( int i = 1; i <= total; i ++ )
            edge[link[i]].push_back(i);
        return;
    }
    long long Dfs ( int now )
    {
        long long ans = 0;
        for ( auto v : edge[now] )
        {
            ans += Dfs(v);
            sum[now] += sum[v];
        }
        if ( now )
            ans += f[sum[now]] * ( maxlen[now] - maxlen[link[now]] );
        return ans;
    }
}SAM;
long long Solve ( int L, int R )
{
    if ( Map.find(make_pair(L, R)) != Map.end() )
        return Map[make_pair(L, R)];
    SAM.Build(L, R);
    return Map[make_pair(L, R)] = SAM.Dfs(0);
}
bool Check ( long long x )
{
    int ans = 0;
    for ( int L = 1, R; L <= n; L = R + 1 )
    {
        R = L - 1;
        for ( int len = 1; L + len - 1 <= n; len <<= 1 )
        {
            if ( Solve(L, L + len - 1) <= x )
                R = L + len - 1;
            else
                break;
        }
        if ( R == L - 1 )
            return false;
        int l = R, r = min(n, R + R - L + 1);
        while ( l <= r )
        {
            int mid = l + r >> 1;
            if ( Solve(L, mid) <= x )
                R = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        ++ans;
        if ( ans > k )
            return false;
    }
    return true;
}
int main ()
{
    freopen("qz.in", "r", stdin);
    freopen("qz.out", "w", stdout);

    scanf("%d%d%s", &n, &k, s + 1);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &f[i]);
    long long L, R, pos;
    L = 0, R = pos = Solve(1, n);
    while ( L <= R )
    {
        long long mid = L + R >> 1;
        if ( Check(mid) )
            pos = mid, R = mid - 1;
        else
            L = mid + 1;
    }
    printf("%lld\n", pos);
    return 0;
}

T3 TEmPTaTiON

设当前序列为 \(a\) ，询问为 \(x\) ，考虑到 \(a_i+x=\operatorname{not}(\operatorname{not}(a_i)-x)\) ，其中 \(\operatorname{not}\) 为按位取反操作，因此对 \(a_i\) 和 \(x\) 同时取反，最小操作次数不变，从高位向低位依次考虑，容易发现通过上述操作可以将 \(a\) 序列最高位全部变为 \(0\) ，如果此时 \(x\) 最高位为 \(0\) ，显然这一位可以不操作，如果 \(x\) 最高位为 \(1\) ，考虑找到一个最大的 \(a_i\) 并将其变为 \(2^{m-1}\) ，之后递归处理下一位。

考虑贪心选择的正确性，我们将变化体现在数轴上，一次操作实际上是将一个点向右移动 \(1\) 个单位长度，容易发现操作代价为当前值与目标值的距离，如果当前不操作最大的 \(a_i\) ，那么一定是因为 \(a_i\) 用于较低位的操作，设当前操作的为 \(a_j\) ，由于 \(a_j\le a_i\) ，因此两次操作一定存在交集，不难发现这一定不优。

考虑优化这个过程，考虑上述贪心的实质，如果 \(a_i\) 在当前位的异或和等于 \(x\) 在这一位的值，那么不进行操作，否则考虑操作一个 \(a_i\) ，如果操作的 \(a_i\) 在这一位为 \(0\) ，那么会产生 \(2^{m-1}-a_i\) 的代价，如果操作的 \(a_i\) 在这一位为 \(1\) ，那么会产生 \(a_i-(2^{m-1}-1)\) 的代价，容易发现可以预处理每一位每个数的代价并从小到大排序，查询时从高到低枚举每一位并贪心的选择较小的代价。由于考虑当前位时最多需要跳过 \(m\) 个之前选择的数，因此查询复杂度为 \(O(m^2)\) 。

code

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int max1 = 1e5, max2 = 60;
int n, m, q;
long long a[max1 + 5];
int sum[max2 + 5];
bool vis[max1 + 5];
struct Data
{
    long long val;
    int id;
    bool operator < ( const Data &A ) const
        { return val < A.val; }
}d[max2 + 5][max1 + 5];
int main ()
{
    freopen("mika.in", "r", stdin);
    freopen("mika.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &q);
    for ( int i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]);
    for ( int bit = 0; bit < m; bit ++ )
    {
        sum[bit] = 0;
        for ( int i = 1; i <= n; i ++ )
        {
            if ( a[i] >> bit & 1 )
                d[bit][i].val = ( a[i] & ( ( 1LL << bit + 1 ) - 1 ) ) - ( 1LL << bit ) + 1;
            else
                d[bit][i].val = ( 1LL << bit ) - ( a[i] & ( ( 1LL << bit + 1 ) - 1 ) );
            d[bit][i].id = i;
            sum[bit] ^= a[i] >> bit & 1;
        }
        sort(d[bit] + 1, d[bit] + 1 + n);
    }
    long long x, ans;
    while ( q -- )
    {
        scanf("%lld", &x);
        ans = 0;
        for ( int i = 0; i <= m - 1; i ++ )
            for ( int j = 1; j <= min(n, m); j ++ )
                vis[d[i][j].id] = false;
        for ( int bit = m - 1; bit >= 0; bit -- )
        {
            if ( ( x >> bit & 1 ) ^ sum[bit] )
            {
                int now = 1;
                while ( now <= n && vis[d[bit][now].id] )
                    ++now;
                if ( now == n + 1 )
                    ans += 1 << bit;
                else
                {
                    ans += d[bit][now].val;
                    vis[d[bit][now].id] = true;
                    if ( a[d[bit][now].id] >> bit & 1 )
                    {
                        x ^= a[d[bit][now].id];
                        x ^= ( 1LL << bit ) - 1;
                    }
                    else
                    {
                        x ^= a[d[bit][now].id];
                        x ^= 1 << bit;
                    }
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}