Mambacrose

ride or die

最近做的一些水题

| Comments

搞完省选后人都要虚脱了。

已经沦落到只能以刷水题为乐了= =

做了天,把做完了,补一发题解吧。

apio 2007

mobiles

首先,任意两个风铃的深度差必须小于,其次不存在两棵不相交的子树都包含深度不同的风铃。

处理答案的时候自底向上处理,如果左子树风铃的深度小,交换左子树和右子树即可。

backup

很水的贪心题。我们先在这个方案中选出权值最小的一个,然后将这个方案的值改为左面方案的值加右面方案的值减自己的值,并把这左边的方案和右边的方案删掉,取次即可得到答案。

zoo

首先我们考虑一条链的答案,由于每个小朋友都只能看到个围栏,所以我们可以想到状态压缩。

表示对于所有位置小于的小朋友,第个围栏的状态为时能使多少人高兴。

很容易得到转移方程

其中表示对于所有位置为的小朋友,第个围栏的状态为时能使多少人高兴。

转化成环也很简单,枚举前个围栏的状态即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define T(x) (1 << (x))
#define M 32
#define N 100100
using namespace std;
int f[N][40], g[N][6], h[N][40], n, m, i, j, k, t, ans;
vector<int> s[N]; 
void Getval()
{
    for (i = 1; i <= n; i++)
        for (j = 0; j < M; j++)
        {
            int sz = s[i].size();
            for (k = 0; k < sz; k++)
            {
                int x = s[i][k];
                for (t = 1; t <= 5; t++)
                    if ((j >> (5 - t)) & 1) 
                        if (g[x][t] == 1) {h[i][j]++; break;} else;
                    else
                        if (g[x][t] == 2) {h[i][j]++; break;}
            }
        }
}
void Work()
{
    for (i = 0; i <= 31; i++)
    {
        memset(f, 0, sizeof(f));
        f[1][i] = h[1][i];
        for (j = 2; j <= n - 4; j++)
            for (k = 0; k < M; k++)
                f[j][k] = max(f[j - 1][k >> 1], f[j - 1][(k >> 1) | T(4)]) + h[j][k];
        for (j = n - 3; j <= n; j++)
            for (k = 0; k < T(n - j + 1); k++)
            {
                t = (k << (j + 4 - n)) + (i >> (n - j + 1));
                f[j][t] = max(f[j - 1][t >> 1], f[j - 1][(t >> 1) | T(4)]) + h[j][t];
                if (j == n) ans = max(ans, f[n][t]);
            }
    }
    cout << ans << endl;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        int e, f, l, x, j; scanf("%d%d%d", &e, &f, &l);
        for (j = 1; j <= f; j++) {
            scanf("%d", &x);
            if (x < e) x = x + n - e; else x -= e;
            g[i][x + 1] = 2;
        }
        for (j = 1; j <= l; j++) {
            scanf("%d", &x);
            if (x < e) x = x + n - e; else x -= e;
            g[i][x + 1] = 1;
        }
        s[e].push_back(i);
    }
    Getval();
    Work();
    return 0;
}

apio 2008

beads

交互题再见

roads

又是一道大水题= =

题目明显就是要求是否存在有且仅有条边为的树。

首先将权值为的边添到图中,再把权值为的边添进去,这样我们就可以得到有哪些值为的边是必要的。

然后我们将图中仅保留必要的值为的边,再添入值为的边直到达到条,再添入值为的边即可。

dna

由于很大,我们不妨考虑怎么放数来组成

表示第位为,且是范氏

所以

apio2009

oil

脑补一下三个矩形可能的放法。

记录左上角,左下角,右上角,右下角的前缀最大值,分类讨论一下即可。

convention

题目就是要求有若干个区间,要取出尽可能多的区间,且在数量尽可能多的前提下,取出字典序最小的若干区间。

首先离散化,用表示区间中最多取出的区间个数。

然后我们考虑按字典序从小到大不断取出区间,那么我们能取出一个区间的条件是:

不与前面已经取出的区间相交。

个限制条件用线段树维护线段覆盖即可,那么我们就只要求出就可以了。

因为与编号没有任何关系,所以我们可以把存在包含关系的大区间删掉,这样留下的就是一堆没有包含关系的区间。

数组存放的是去重后且排了序的区间。

表示从端点出发,往右跳个互不相交区间后,最近的端点为数组中的第多少个区间的编号。

那么

然后我们就可用倍增一样的求法求即可。

ATM

对于一个环来说,上面的权值如果能取那么一定会全取完。

所以我们缩点,给每个点重新赋值,在得到的拓扑图上即可。

apio2010

commando

很容易得到方程:

其中

考虑两个决策,如果优那么

不妨设

那么当优。

因为递增,所以用个单调队列维护最优决策即可。

partrol

题目很明显是要求条最长链,对于的话,就是直径。

对于,首先求一遍直径,将直径上得边的权值标为,再求一边直径即可。

signaling

因为不存在四点共圆,那么考虑一个凸四边形对答案的贡献就是,一个凹四边形对答案的贡献就是。所以我们只要求出图中有多少个凸四边形和凹四边形。

对于一个凹四边形,它一定形如一个点加上一个覆盖它的三角形,我们枚举中间点,让其他点极角排序,那么能与这个点构成凹四边形的三个点两两极角之差一定小于度,容斥一下就变成了求三个点,最大的极角和最小的极角之差小于度。用单调性维护即可。

Comments

comments powered by Disqus