【比赛】51nod 爆炸 noip 模拟赛 ——quhengyi11

noip 难度的比赛被我打成了省选的分数我要退役了。

模拟赛经验不足 QAQ

所以在这里写一篇总结 QAQ

T1：Anan 的派对

Anan 想举办一个派对。

Anan 的朋友总共有 n 人。第 i 个人如果参加派对会得到 ci 的快乐值，除他自己外每多一个人参加他会减少 di 的快乐值。

Anan 想让这个派对的总快乐值尽可能大，在这个基础上，能来的人越多越好。

Anan 想知道最佳的邀请方案的快乐值与参加人数。

$n\leq 1000$

傻子题，直接枚举天数，然后贪心算当前的最优快乐值，判一下更新 ans 就行，所以现场我就 A 了这一道题（

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 1005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
ll n, m, ans, sumd, q[N], tot, tmp;
struct node{
    ll c, d;
    inline friend bool operator < (node x, node y)
    {
        return x.c > y.c;
    }
}t[N];
int main ()
{
    scanf("%lld", &n);
    fo (i, 1, n)
        scanf("%lld", &t[i].c);
    fo (i, 1, n)
        scanf("%lld", &t[i].d);
    ans = -inf;
    fo (i, 1, n)
    {
        ans = std::max(ans, t[i].c);
    }
    tot = 1;
    fo (i, 2, n)
    {
        fo (j, 1, n)
            t[j].c -= t[j].d;
        std::sort(t + 1, t + n + 1);
        tmp = 0;
        fo (j, 1, i)
            tmp += t[j].c;
        if (tmp >= ans)
        {
            ans = tmp;
            tot = i;
        }
    }
    printf("%lld\n%lld\n", ans, tot);
    return 0;
}

T2：XYG 的蛋糕

题意，给你个 $n\times m$ 的蛋糕，让你将它们所有都切成 $1\times 1$ 的小蛋糕，求本质不同的切法，两个切法不同当且仅当其中一个切法中存在一条刀痕，在另一个切法中不存在，一种切法对应一种不交线段的方案。 $n,m\leq 300$

我在考场上的时候想了半天每个交点是被横切还是纵切然后来统计方案，后来发现那样弄出来的 01 序列光是判断是否是一个合法方案就已经很烦了，计数就更 gg 了。

首先介绍如何暴力：

对于每一个切，我们可以发现把一块蛋糕切成了两份（废话），能不能递归一下两个蛋糕的切法，然后将它们的方案乘起来就是当前这刀在多少种方案中出现过吗？

显然这种方法是不行的，我们很容易找到会有重复，比如说在先后在 1 位置纵切，2 位置纵切，显然 2 位置纵切后 1 位置纵切这种情况也被算了一次，可是这与前面那种方案是本质相同的。所以咕咕咕。

处理的方法也很简单（我可能是傻了我比赛时候没想到），规定一个扫描顺序，必须从左往右纵切，从上往下横切，那样就不会重复算了（比如在 2 位置纵切，则 2 左边的位置的第一刀是不允许被纵切的）

这个暴力的改进也很简单，弄成记忆化搜索就行了（说白了就是 dp）

$f[i][j][s]$ 表示 $i\times j$ 的蛋糕下一道 $s$ 切法的方案数， $s=1$ 为横切， $s=2$ 为纵切， $s=0$ 为横纵切都行。

我们由上面的搜索过程可以很容易写出下面的方程：

$f[i][j][2]=\sum_{1\leq k<j} f[i][k][1] \times f[i][j-k][0]$

$f[i][j][1]=\sum_{1\leq k<i} f[k][j][2] \times f[i-k][j][0]$

$f[i][j][0]=f[i][j][1]+f[i][j][2]$

然后就乐滋滋的打代码：

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 305
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
ll n, m, ans, sumd, q[N], tot, tmp, f[N][N][3];
int main ()
{
    scanf("%lld %lld", &n, &m);
    f[1][1][0] = 1;
    fo (i, 2, n)
        f[i][1][0] = f[i][1][1] = 1;
    fo (j, 2, m)
        f[1][j][0] = f[1][j][2] = 1;
    fo (i, 2, n)
        fo (j, 2, m)
        {
            fo (k, 1, j - 1)
                f[i][j][2] = (f[i][j][2] + 1ll * f[i][k][1] * f[i][j - k][0]) % mod;
            fo (k, 1, i - 1)
                f[i][j][1] = (f[i][j][1] + 1ll * f[k][j][2] * f[i - k][j][0]) % mod;
            f[i][j][0] = (f[i][j][1] + f[i][j][2]) % mod;
        }
    printf("%lld", f[n][m][0]);
    return 0;
}

T3：WZD 的洞洞

WZD 有一个形状为直角三角形的洞洞。

平面上有 n 个物品，每个物品有坐标 xi,yi 和价值 wi，WZD 希望用洞洞包含住价值尽可能高的物品。

由于洞洞的构造，其两条边必须平行于坐标轴，且直角在左下方（也就是说，洞洞只能平行移动），并且要求直角必须恰好落在一个物品上。a 为平行于 x 轴的直角边的长度，b 为平行 y 轴的直角边的长度

求洞洞能包含住最大价值为多少的物品。

$n\leq 10^5, x,y \leq 10^4, -10^4 \leq w \leq 10^4$

第二题弃疗之后已经没多少时间想第三题了，在比赛快结束的时候口胡了一个题解。

每个点弄个 $(x,y,z)$ 的三元组，然后令 $z=-bx+ay$ ，一个点 c 为直角顶点形成的三角形，点 d 在里面当且仅当 $c(x,y,z+a\times b) \leq d(x,y,z)$ ，然后就用 cdq 分治搞一把三维偏序就行了，复杂度 $O(nlog^2n)$

赛后跟出题人一讲，发现标程是 $O(nlogn)$ 的，眼神渐渐复杂。

其实题解超简单（

首先我们把 z 滑动窗口一下，确定一个矩形区域出来。

然后我们只需要将矩形区域里所有的点的权值-x 小于直角顶点 x 的所有点权值-y 小于直角顶点 y 的所有点权值就是当前三角形里的权值了。

看图就明白了

减去阴影部分就是三角了w

用树状数组维护一下下就行啦 QAQ

代码：

#include<bits/stdc++.h> 
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
ll n, m, ans, a, b, dis, t1[N], t2[N], q[N], r, sum;
inline void add1 (ll x, ll val) {for (int i = x; i <= up; i += lowbit(i)) t1[i] += val;}
inline ll query1 (ll x) {ll ret = 0; for (int i = x; i; i -= lowbit(i)) ret += t1[i]; return ret;}
inline void add2 (ll x, ll val) {for (int i = x; i <= up; i += lowbit(i)) t2[i] += val;}
inline ll query2 (ll x) {ll ret = 0; for (int i = x; i; i -= lowbit(i)) ret += t2[i]; return ret;}
struct node{
    ll x, y, z, w;
    inline friend bool operator < (node a, node b)
    {
        return a.z < b.z;
    }
}t[N];
int main ()
{
    scanf("%lld %lld %lld", &n, &a, &b);
    fo (i, 1, n)
    {
        scanf("%lld %lld %lld", &t[i].x, &t[i].y, &t[i].w);
        t[i].z = 1ll * b * t[i].x + 1ll * a * t[i].y;
    }
    std::sort(t + 1, t + n + 1);
    dis = 1ll * a * b;
    r = 1;
    ans = -inf;
    fo (l, 1, n)
    {
        while (r <= n && t[l].z + dis >= t[r].z) 
        {
            sum += t[r].w;
            add1(t[r].x, t[r].w);
            add2(t[r].y, t[r].w);
            ++r;
        }
        ans = std::max(ans, sum - query1(t[l].x - 1) - query2(t[l].y - 1));
        sum -= t[l].w;
        add1(t[l].x, -t[l].w);
        add2(t[l].y, -t[l].w);
    }
    printf("%lld", ans);
    return 0;
}