3001 字
15 分钟
UR17 题解
2018-03-19
题解
DP

A. 【UR #17】滑稽树上滑稽果#

“滑稽树上滑稽果，滑稽树下你和我” 听到这熟悉的句子，他猛然忆起年少时最喜欢的节目，彼时单纯而简单的生活，以及那幼稚而天真的苦恼。 幼年的他常常苦恼这么一个问题： 他有 nn 个滑稽果，第 ii 个滑稽果的大小为 aia_i。 他现在想把它们构成一棵任意形态的有根树，每个点的滑稽度为它的大小和它父亲的滑稽度的 andand，其中 andand 表示按位与运算，例如 2 and 3=2,1 and 0=0, 1 and 1=12\ and\ 3=2,1\ and\ 0=0,\ 1\ and\ 1=1。特别地，根的滑稽度等于他的大小。 为了世界的和平，他希望能最小化这棵树上所有滑稽果的滑稽度之和。请问你能帮他解决这个问题吗？

006fbYi5gw1f9djtje2mdj30hs0dcwfe.jpg

输入格式#

第一行一个正整数 nn。 接下来一行有 nn 个正整数 aia_i, 表示 ii 个滑稽果的大小。

输出格式#

一行一个整数，表示最小的滑稽度之和。

样例一#

input#

5
12 9 14 17 15

output#

10

样例二#

input#

10
42256 116359 103553 58560 49680 99204 37408 57353 110732 33797

output#

328709
子任务分值$n$的规模$a_i$的规模特殊性质
15$n \leq 9$$1 \leq a_i \leq 2 \times 10^5$无
210$n \leq 12$保证存在合法的最优解是一条链
310$n \leq 100$保证存在合法的最优解是一条链。并且从根开始的每个滑稽值构成了一个序列，保证解的这个序列的字典序，在所有链对应的序列中最小
415$n \leq 10^5$
530$n \leq 100$无
630$n \leq 10^5$

A. 题解#

这题面有毒吧。。。

对于第一个Subtask可以直接枚举父节点时间复杂度O(nn)O(n^n)
然后是第二个Subtask据说可以用n!n!的时间复杂度枚举，但不知道为什么过不去。。。
第三四的Subtask保证了字典序最小，我们可以暴力跑一下O(n2)O(n^2)过掉n<=100n<=100的数据， 而对于n<=105n<=10^5的数据我们可以Sort一下O(nlog2(n))O(nlog^2(n))跑过去 核心代码在下面

for (int i = 1; i <= n; i++) a[i] = read();
Now = 0x7fffffffffffffffll;
long long ans = 0;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
    ans += (Now & a[i]);
    if ((Now & a[i]) != Now)
    {
        Now = (Now & a[i]);
        sort(a + i + 1, a + n + 1, cmp);
    }
}
printf ("%lld\n", ans);

bool cmp(long long c, long long d)
{
    if ((Now & c) == (Now & d)) return c > d;
    return (Now & c) < (Now & d);
}

剩下的就是正解了
把相同的位拿出来，这些位要么一定是每次没贡献，要么一定是每次有贡献。
所以我们一样先把每个数都一样的那些位拿出来，剩下的位我们等于是希望尽快把他们变成0。
用一个DP
f[S]f[S]表示当SS集合的值为11时将他消为00的最小代价
转移的时候枚举a[i]a[i]，令F[S] = F[S \\& a[i]] + (S \\& a[i])
这样是O(na)O(na)的配合上前面的部分分，可以有70分了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN = 1e5 + 5;
long long a[MAXN], C[MAXN];
int n;
bool rm[10];
int Count[10];
inline void Trans(int x, long long *c)
{
    int cnt = 0;
    for (int i = 1; i <= n - 2; i++) c[i] = 0;
    while (x) c[++cnt] = x % n, x = x / n;
    for (int i = 1; i <= n - 2; i++) c[i]++;
}
struct edge
{
    int END, next;
}v[20];
int first[10], p;
bool flag[100005];
void add(int a, int b)
{
    v[p].END = b;
    v[p].next = first[a];
    first[a] = p++;
}
int Sum;
void DFS(int rt, int fa)
{
    if (fa != 0) C[rt] = (C[fa] & a[rt]);
    Sum += C[rt];
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
        if (v[i].END == fa) continue;
        DFS(v[i].END, rt);
    }
}
long long Now;
bool cmp(long long c, long long d)
{
    if ((Now & c) == (Now & d)) return c > d;
    return (Now & c) < (Now & d);
}
long long f[(1 << 18) + 1], S[(1 << 18) + 1];
int main()
{
    n = read();
    if (n <= 100)
    {
        long long SAME = 0x7fffffffffffffffll;
        for (int i = 1; i <= n; i++) a[i] = read(), SAME = (SAME & a[i]);
        int N = (1 << 18) - 1;
        int cnt = 0;
        for (int i = 1; i <= N; i++)
            S[++cnt] = (i | SAME) ^ SAME;
        memset (f, 0x3f, sizeof (f));
        f[0] = 0;
        sort(S + 1, S + cnt + 1);
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= n; j++)
                f[S[i]] = min(f[S[i]], f[S[i] & a[j]] + (S[i] & a[j]));
        printf ("%lld\n", 1ll * SAME * n + f[S[cnt]]);
    }
    else
    {
        for (int i = 1; i <= n; i++) a[i] = read();
        Now = 0x7fffffffffffffffll;
        long long ans = 0;
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; i++)
        {
            ans += (Now & a[i]);
            if ((Now & a[i]) != Now)
            {
                Now = (Now & a[i]);
                sort(a + i + 1, a + n + 1, cmp);
            }
        }
        printf ("%lld\n", ans);
    }
    // while (1);
}

对于满分做法 我们可以每次不枚举一个a[i]a[i]，而是枚举一个子集TT，强制把这个子集TT变成00。
我们需要知道哪些TT可以变为00
可以用枚举子集的方法，(但是因为太暴力被Hack了 2333) 转移是相似的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int MAXN = 1e5 + 5;
long long a[MAXN], C[MAXN];
int n;
long long Now;
bool cmp(long long c, long long d)
{
    if ((Now & c) == (Now & d)) return c > d;
    return (Now & c) < (Now & d);
}
long long f[(1 << 18) + 1], S[(1 << 18) + 1];
int cnt[(1 << 18) + 1];
int main()
{
    n = read();
    if (n <= 100000)
    {
        long long SAME = (1 << 18) - 1;
        for (int i = 1; i <= n; i++) a[i] = read(), SAME = (SAME & a[i]);
        int N = (1 << 18) - 1;
        for (int i = 1; i <= n; i++) a[i] ^= SAME;
        for (int i = 1; i <= n; i++)
        {
            long long t = N ^ a[i];
            for (int j = t; j; j = (j - 1) & t)
                cnt[j] = 1;
        }
        memset (f, 0x3f, sizeof (f));
        for (int i = 1; i <= n; i++) f[a[i]] = a[i];
        for (int i = N; i >= 1; i--) 
            if (f[i] < 0x3f3f3f3f3f3f3f3f)
                for (int j = i; j > 0; j = (j - 1) & i)
                    if (cnt[j])
                        f[i ^ j] = min(f[i ^ j], f[i] + (i ^ j));
        printf ("%lld\n", 1ll * SAME * n + f[0]);
    }
    else
    {
        for (int i = 1; i <= n; i++) a[i] = read();
        Now = 0x7fffffffffffffffll;
        long long ans = 0;
        sort(a + 1, a + n + 1, cmp);
        for (int i = 1; i <= n; i++)
        {
            ans += (Now & a[i]);
            if ((Now & a[i]) != Now)
            {
                Now = (Now & a[i]);
                sort(a + i + 1, a + n + 1, cmp);
            }
        }
        printf ("%lld\n", ans);
    }
    // while (1);
}

B. 【UR #17】滑稽树下你和我#

我，年幼的人赢，总是和我的同桌一起在滑稽树下讨论问题。
我的滑稽树是一棵长在平面上的，有 nn 个点的树。点从 11 到 nn 标号。这 nn 个点满足任意三点互不共线，并且树的边不相交。
现在我都和我的同桌一起在滑稽树上每人各控制一个点。我的点最开始在 stx\mathrm{stx}，我的同桌的点最开始在 sty\mathrm{sty}。我们可以任意沿着树的边移动各自的点。当两个点都在树上的某个叶子的时候游戏就结束了。
现在，我想要最小化任意时刻我们两个所控制的点之间距离的最大值。请问你能帮我解决这个问题吗？注意某个时刻两个点可能都在某一条边上，这时候的距离也要统计入答案。
一句话题意：给定一棵平面上的树，两个点在树上任意移动，最小化从开始到两个点都到达叶子的任意时刻两个点直线距离的最大值。

输入格式

第一行三个正整数 $n,\mathrm{stx},\mathrm{sty}$。 接下来 $n$ 行有 $2$ 个整数 $x_i,y_i$，表示第 $i$ 号节点的坐标。 接下来 $n-1$ 行有 $2$ 个整数 $a_i,b_i$，表示树上的一条边。

输出格式

输出一行，包含一个实数，表示最小的任意时刻我们两个所控制的点之间距离的最大值。 你的答案与参考答案的绝对误差或相对误差不超过 $10^{−6}$ 时被认为是正确的。

样例一

input

4 2 3
0 1
1 1
1 0
0 0
1 2
2 3
3 4

output

1.0000000000

样例二

input

4 2 4
0 0
51 49
100 100
100 0
1 2
2 3
3 4

output

69.2964645563

限制与约定

对于全部数据，$3\le n\le 1000$，$0\le x_i,y_i \le 10^6$。
子任务分值$n$特殊性质
15$\le 10$$\mathrm{stx}$ 和 $\mathrm{sty}$ 均为叶子
225无
325$\le 200$无
415$\le 1000$保证存在最优方案，在任意时刻至少有一端点位于树的某结点上
530无

B. 题解#

第一个Subtask可以直接输出两点距离
对于保证存在最优方案，在任意时刻至少有一端点位于树的某结点上的部分
先二分答案
定义f[i][j]f[i][j]表示两个点为i,ji, j是否可行, 按照定义枚举转移


bool Judge(double mid)
{
    memset (f, 0, sizeof (f));
    f[stx][sty] = f[sty][stx] = 1;
    queue<pair<int, int> > Q;
    Q.push(pair<int, int>(stx, sty));
    while (!Q.empty())
    {
        pair<int, int> k = Q.front(); Q.pop();
        int x = k.first, y = k.second;
        if (x == y || (du[x] == 1 && du[y] == 1)) return 1;
        for (int i = first[x]; i != -1; i = v[i].next)
        {
            if (!f[v[i].END][y] && dis(a[v[i].END], a[y]) <= mid)
            {
                f[v[i].END][y] = f[y][v[i].END] = 1;
                Q.push(pair<int, int>(v[i].END, y));
            }
        }
        for (int i = first[y]; i != -1; i = v[i].next)
        {
            if (!f[x][v[i].END] && dis(a[v[i].END], a[x]) <= mid)
            {
                f[v[i].END][x] = f[x][v[i].END] = 1;
                Q.push(pair<int, int>(x, v[i].END));
            }
        }
    }
    return 0;
}

之后就是正解了
与20分的相似， 还是先二分答案
定义f[i][j]f[i][j]为一个点在点ii,一个点在边jj上距离点ii最近的那个点上是否可行
然后f[i][j]<=1f[i][j]<=1要求ii到jj的最小距离小于二分的答案, 且存在某个f[k][x]f[k][x]为11,其中kk是jj的某个端点,xx是某个以ii为端点的边，或存在某个f[t][j]f[t][j]为11，其中tt与ii有边相连， BFSBFS转移。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Point
{
    double x, y;
    Point(double _x = 0, double _y = 0): x(_x), y(_y) {}
    Point operator - (const Point &a)
    {
        return Point(x - a.x, y - a.y);
    }
    double operator * (const Point &a)
    {
        return x * a.x + y * a.y;
    }
    double operator ^ (const Point &a)
    {
        return x * a.y - y * a.x;
    }
}a[1005];
int du[1005];
struct edge
{
    int S, END, next, id;
}v[2005];
int first[1005], p;
void add(int c, int b, int id)
{
    v[p].S = c;
    v[p].END = b;
    v[p].next = first[c];
    v[p].id = id;
    first[c] = p++;
}
double dis(const Point &x, const Point &y)
{
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
struct line
{
    Point a, b, c;
    double k;
    line() {}
    line(Point x, Point y) 
    {
        a = x, b = y;
        c = a - b;
        k = atan2(b.y - a.y, b.x - a.x);
    }
}l[1005];
double dis(Point &x, line &y)
{
    if ((y.c * (y.a - x)) * (y.c * (y.b - x)) <= 0)
        return abs((y.a - x) ^ (y.b - x)) / dis(y.a, y.b);
    return min(dis(y.a, x), dis(y.b, x));
}
bool f[1005][1005];
int n, stx, sty;
bool Judge(double mid)
{
    memset (f, 0, sizeof (f));
    queue<pair<int, int> > Q;
    for (int i = first[stx]; i != -1; i = v[i].next)
        f[sty][v[i].id] = 1, Q.push(pair<int, int>(sty, v[i].id));
    for (int i = first[sty]; i != -1; i = v[i].next)
        f[stx][v[i].id] = 1, Q.push(pair<int, int>(stx, v[i].id));
    while (!Q.empty())
    {
        pair<int, int> k = Q.front(); Q.pop();
        int x = k.first, y = k.second;
        for (int i = first[x]; i != -1; i = v[i].next)
        {
            if (!f[v[i].END][y] && dis(a[v[i].END], l[y]) <= mid)
            {
                f[v[i].END][y] = 1;
                Q.push(pair<int, int>(v[i].END, y));
            }
            if (!f[v[(y - 1) << 1].S][v[i].id] && dis(a[v[(y - 1) << 1].S], l[v[i].id]) <= mid)
            {
                f[v[(y - 1) << 1].S][v[i].id] = 1;
                Q.push(pair<int, int>(v[(y - 1) << 1].S, v[i].id));
            }
            if (!f[v[(y - 1) << 1].END][v[i].id] && dis(a[v[(y - 1) << 1].END], l[v[i].id]) <= mid)
            {
                f[v[(y - 1) << 1].END][v[i].id] = 1;
                Q.push(pair<int, int>(v[(y - 1) << 1].END, v[i].id));
            }
        }
    }
    for (int i = 1; i <= n; i++) if (du[i] == 1)
        for (int j = 1; j <= n; j++) if (du[j] == 1)
            if (f[i][v[first[j]].id] && dis(a[i], a[j]) <= mid)
                return 1;
    return 0;
}
int main()
{
    memset (first, -1, sizeof (first));
    n = read(), stx = read(), sty = read();
    for (int i = 1; i <= n; i++)
        a[i].x = read(), a[i].y = read();
    for (int i = 1; i < n; i++)
    {
        int b = read(), c = read();
        du[b]++, du[c]++;
        add(b, c, i);
        add(c, b, i);
        l[i] = line(a[b], a[c]);
    }
    double l = dis(a[stx], a[sty]), r = 1e9;
    while (abs(r - l) >= 1e-8)
    {
        double mid = (l + r) / 2;
        if (Judge(mid)) r = mid;
        else l = mid;
    }
    printf ("%.10f", l);
    // while (1);
}

C题先坑着，还不会做呢， 过一段时间在填。

UR17 题解
https://www.nekomio.com/posts/137/
作者
NekoMio
发布于
2018-03-19
许可协议
CC BY-NC-SA 4.0
省选集训日记
BZOJ1038 [ZJOI2008]瞭望塔