『模拟赛』CSP-S模拟5

17天前发布

Rank

一般

A. 光

胱！

妈的传奇题目控我两个小时想 $\mathcal{O(1)}$ 做法。

其实带下取整的四个四元一次方程根本解不了，考虑到这个题给的范围只有 $n\le 1500$，可以枚举两维剩下二分到一个小区间里去做，复杂度 $\mathcal{O(n^2\log n)}$，当然数据水卡卡枚举的边界 $\mathcal{O(n^3)}$ 也能过。

学的 K8He 的带 $4^4$ 常数的 $\mathcal{O(n)}$ 做法。考虑到以四为单位减小不会有浪费的亮度，因此这样贪心着耗电是很优的。我们枚举最后剩下需要的亮度，进而求出我们需要进行以四为单位贪心的数据，优先队列随便维护一下，然后处理一下以四为单位贪不了的和我们枚举的剩余局面，三者消耗之和即为答案。

想卡最优解来着，所以提前跑了一遍把剩余局面的所有消耗跑出来赋给数组了，结果还是比不过小常数选手们，拜谢！

注释掉的是跑剩余局面的代码，有需要的自行打开。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5 , M = 6000;
const int mod = 998244353;
int a, b, c, d;
int ans = 1e9;
int res[4][4][4][4]={0,1,2,3,1,2,2,3,2,2,3,4,3,3,4,4,1,2,2,3,2,2,2,3,3,3,3,4,4,4,4,4,2,2,
3,4,3,3,3,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,5,5,6,6,6,6,1,2,3,4,2,3,3,4,2,2,3,4,3,3,
4,4,2,3,3,4,3,3,3,4,3,3,4,4,4,4,4,4,2,2,3,4,3,3,4,4,4,4,4,4,5,5,5,5,3,3,4,4,4,4,4,4,5,5,
5,5,6,6,6,6,2,3,4,5,2,3,4,5,3,3,4,5,4,4,5,5,2,3,4,5,2,3,4,5,3,4,4,5,4,4,5,5,3,3,4,5,3,4,
4,5,4,4,4,5,5,5,5,6,4,4,5,5,4,4,5,5,5,5,5,6,6,6,6,6,3,4,5,6,3,4,5,6,4,4,5,6,4,4,5,6,3,4,
5,6,3,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,4,4,5,6,5,5,5,6,5,5,6,6,4,4,5,6,4,4,5,6,5,5,6,6,6,6,6,6};
priority_queue<pii, vector<pii >, less<pii > > q;
namespace Wisadel
{
    void Wfang(pii x, pii y)
    {
        if(x.se + y.se == 5) q.push({y.fi - 1, y.se});
        else q.push({y.fi - 2, y.se});
    }
    short main()
    {
        freopen("light.in", "r", stdin) , freopen("light.out", "w", stdout);
        a = qr, b = qr, c = qr, d = qr;
        fo(i1, 0, 3) fo(i2, 0, 3) fo(i3, 0, 3) fo(i4, 0, 3)
        {
            int A = a - i1, B = b - i2, C = c - i3, D = d - i4;
            q.push({A, 1}), q.push({B, 2}), q.push({C, 3}), q.push({D, 4});
            int tim = 0, cs;
            int ba, bb, bc, bd;
            while(q.top().fi >= 4)
            {
                pii aa = q.top(); q.pop();
                pii bb = q.top(); q.pop();
                pii cc = q.top(); q.pop();
                pii dd = q.top(); q.pop();
                q.push({aa.fi - 4, aa.se});
                Wfang(aa, bb), Wfang(aa, cc), Wfang(aa, dd);
                tim++;
            }
            A = max(q.top().fi, 0), ba = q.top().se, q.pop(), B = max(q.top().fi, 0), bb = q.top().se, q.pop(),
            C = max(q.top().fi, 0), bc = q.top().se, q.pop(), D = max(q.top().fi, 0), bd = q.top().se, q.pop();
            cs = A + B + C + D;
            if(ba + bd != 5) swap(B, D), swap(bb, bd);
            if(ba + bd != 5) swap(C, D), swap(bc, bd);
            fo(i, 0, A) fo(j, 0, B) fo(k, 0, C)
            {
                int l = -1;
                if(A - i - (j / 2) - (k / 2) >= 0) l = max(l, (A - i - (j / 2) - (k / 2)) * 4);
                if(B - j - (i / 2) - (k / 4) >= 0) l = max(l, (B - j - (i / 2) - (k / 4)) * 2);
                if(C - k - (i / 2) - (j / 4) >= 0) l = max(l, (C - k - (i / 2) - (j / 4)) * 2);
                if(D - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, D - (i / 4) - (j / 2) - (k / 2));
                if(l != -1) cs = min(cs, i + j + k + l);
            }
            // fo(i, 0, i1) fo(j, 0, i2) fo(k, 0, i3)
            // {
            //     int l = -1;
            //     if(i1 - i - (j / 2) - (k / 2) >= 0) l = max(l, (i1 - i - (j / 2) - (k / 2)) * 4);
            //     if(i2 - j - (i / 2) - (k / 4) >= 0) l = max(l, (i2 - j - (i / 2) - (k / 4)) * 2);
            //     if(i3 - k - (i / 2) - (j / 4) >= 0) l = max(l, (i3 - k - (i / 2) - (j / 4)) * 2);
            //     if(i4 - (i / 4) - (j / 2) - (k / 2) >= 0) l = max(l, i4 - (i / 4) - (j / 2) - (k / 2));
            //     if(l != -1) res = min(res, i + j + k + l);
            // }
            // cout<<res<<',';
            ans = min(ans, res[i1][i2][i3][i4] + tim * 4 + cs);
        }
        // cout<<endl;
        printf("%d\n", ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 爬

感觉最简单的一道，赛时 20min 就做出来了，不过因为 T1 耽误太久导致没细想复杂度，暴力找每一个点的所有贡献好像无论时间空间都是 $\mathcal{O(2^n)}$ 的，不过还是能拿到 80pts，但是我在求贡献的时候没取模导致爆 long long 了挂 20pts。

其实关键点在于想到每个点的贡献是独立的，只与它和它的子节点有关。一共只有 $n-1$ 个点可以移动，因此共有 $2^{n-1}$ 种方案。对于非根的节点来说，它对全局的贡献应该是它的总贡献乘上其它节点的总方案数，即若设它和它子节点的个数为 $tot$，应乘上 $2^{n-1-tot}$，因为根节点上的蚂蚁不会动，所以 $tot$ 要减一。

然后考虑怎么求每个点的贡献和。一种优化的思路是二进制拆分。对于二进制下数的每一位，只有出现的次数为奇异或起来才会有贡献，因此我们可以将每个数拆成二进制，在统计总贡献时先求出一点和它的子节点每一位上为 1 的数的个数，再逐位去求，那么有贡献的方案应该是 $C_{tot}^1 \ +\ C_{tot}^3\ +\cdots\ = 2^{tot-1} $，每次的贡献是 $1$<<$i$，记得算上该位为 0 的数的方案数，把各位上的贡献加起来就是该点的总贡献。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n;
int fa[N], a[N][31], num[N][31];
int hh[N], to[N], ne[N], cnt;
ll Ans;
namespace Wisadel
{
    void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wdfs(int u, int fa)
    {
        int tot = (u != 1);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            tot++;
            Wdfs(v, u);
            fo(j, 0, 30) num[u][j] += a[v][j];
        }
        ll res = 0;
        if(u != 1)
        {
            fo(i, 0, 30)
            {
                if(!num[u][i]) continue;
                res = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - num[u][i] + mod) % mod) % mod;
            }
        }
        else
        {
            fo(i, 0, 30)
            {
                if(a[u][i])
                {
                    if(!num[u][i])
                        res = (res + (1ll << i) * (Wqp(2, tot) - 1) % mod) % mod;
                    else
                        res = (res + (1ll << i) * (Wqp(2, num[u][i] - 1) * Wqp(2, tot - num[u][i]) % mod - 1 + mod) % mod) % mod;
                }
                else
                {
                    if(!num[u][i]) continue;
                    res = (res + (1ll << i) * Wqp(2, num[u][i] - 1) % mod * Wqp(2, tot - num[u][i]) % mod) %mod;
                }
            }
        }
        Ans = (Ans + res * Wqp(2, n - 1 - tot) % mod) % mod;
    }
    short main()
    {
        freopen("climb.in", "r", stdin) , freopen("climb.out", "w", stdout);
        n = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n)
        {
            int bb = qr, ttt = 0;
            while(bb) a[i][ttt] = bb & 1, bb >>= 1, ttt++;
            if(i != 1) fo(j, 0, ttt) num[i][j] = a[i][j];
        }
        fo(i, 2, n) fa[i] = qr, Wadd(fa[i], i);
        Wdfs(1, 0);
        printf("%lld\n",Ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 字符串

贪心唐氏大分讨。

感觉做到这如果有时间静下心来想应该很好得出结论：只有 $A$ 与 $B$ 紧密交替出现时每个字符的回报率是 1，其它情况均小于 1，因此能交替就交替是第一准则。称 1 个 $A$ 与 $c$ 个 $B$ 交替出现的串为紧密交替出现的串。

我们枚举交替串的数量，规定 $B$ 在前 $A$ 在后。对于剩下的 $A$，首先置于串首最优，回报率为 1；其次由于我们交替串数量固定了，不能在新加串，因此剩下的 $A$ 要插入到原来的 $A$ 串中，考虑到此时每个 $A$ 串长度为 $1$，因此每 $a$ 个 $A$ 可以提供 1 的贡献。再考虑剩下的 $B$，首先在末尾增加一个最优；其次考虑在原有的长度为 $c$ 的 $B$ 串中加入 $B$，先都将其补至长度为 $b$，剩下的每 $b$ 个还能产生 1 的贡献。然后就做完了。

头脑冷静，理清思路最重要。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, a, b, c;
int ans;
namespace Wisadel
{
    short main()
    {
        freopen("string.in", "r", stdin) , freopen("string.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr, a = qr, b = qr, c = qr;
            int sum = 0; ans = -1e9;
            fo(i, 0, m / c)
            {
                sum = i * 2 + (c - 1) / b * i;
                int _n = n - i, _m = m - i * c;
                if(_n < 0 || _m < 0) break;
                if(_m)
                {
                    _m--, sum++;
                    if(_m)
                    {
                        int w = min(i, _m / (b - (c - 1) % b));
                        sum += w + (_m - w * (b - (c - 1) % b)) / b;
                    }
                }
                if(_n)
                {
                    _n--,sum++;
                    if(_n) sum += _n / a;
                }
                ans = max(ans, sum);
            }
            printf("%d\n", ans);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

D. 奇怪的函数

赛时没时间了，5pts 暴力都没打完。

稍微手模一下就能发现这 $n$ 次操作本质上是一个分段函数，考虑如何实现动态维护这个函数。

容易想到线段树，以操作为维护对象，维护每个区间有实际意义值域对应的定义域范围，所有 1 操作的总和。由于可能存在上述定义域范围不存在的情况，而此时该函数实质上变为了一个定函数，即只有一个值，所以我们还需要维护这个值。

考虑两个问题：首先是边界问题。比较好得出取 min 操作是划定定义域的上界，取 max 划定下界。其他情况我们将范围赋成极大区间即可。定值由于是定值？无论取啥都一样。

第二是 pushup，考虑如何合并两个分段函数。1 操作的总和不用说，直接加就行。定义域，我们要取左区间的定义域在右区间上仍有意义的区间，思考一下，从左到右之间做了左区间的加操作，那么若一个数在定义域内，一定有 $x+sum_{ls} \ge L_{rs}$，转换过去就是 $x\ge L_{ls}- sum_{ls}$，由于我们取得是区间的交集，所以要取 $L$ 的最大值和 $R$ 的最小值。至于定值，我们可以看成是执行完左区间的操作后继续执行右区间的，如果右区间定义域不存在就取右区间的，否则视为求 $ans_{ls}$ 在右区间上的值，跟总函数一样如下：

\[F(x)=\begin{cases}R+sum\quad x\ge R\\ x+sum\quad L\lt x\lt R\\L+sum\quad x\le L\end{cases} \]

其中 $L,R$ 表示区间函数的定义域。

然后就做完了，比一般的线段树甚至好写。

点击查看代码

#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x) = (y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x) = (y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
	char ch = getchar();lx x = 0 , f = 1;
	for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;
	for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);
	return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int , int>
#define fi first
#define se second
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int op[N], v[N];
ll L[N << 2], R[N << 2], sum[N << 2], ans[N << 2];
namespace Wisadel
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    void Wpushup(int rt)
    {
        L[rt] = max(L[ls], L[rs] - sum[ls]), R[rt] = min(R[ls], R[rs] - sum[ls]);
        sum[rt] = sum[ls] + sum[rs];
        if(L[rs] > R[rs]) ans[rt] = ans[rs];
        else if(ans[ls] < L[rs]) ans[rt] = L[rs] + sum[rs];
        else if(ans[ls] > R[rs]) ans[rt] = R[rs] + sum[rs];
        else ans[rt] = ans[ls] + sum[rs];
    }
    void Wbuild(int rt, int l, int r)
    {
        L[rt] = -1e9, R[rt] = 1e9;
        if(l == r)
        {
            if(op[l] == 1) sum[rt] = v[l], ans[rt] = v[l];
            else if(op[l] == 2) R[rt] = v[l], ans[rt] = 0;
            else L[rt] = v[l], ans[rt] = v[l];
            return ;
        }
        Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
        Wpushup(rt);
    }
    void Wupd(int rt, int l, int r, int x, int k, int opp)
    {
        if(l == r)
        {
            if(opp == 1) L[rt] = -1e9, R[rt] = 1e9, ans[rt] = sum[rt] = k;
            else if(opp == 2) L[rt] = -1e9, R[rt] = k, ans[rt] = sum[rt] = 0;
            else ans[rt] = L[rt] = k, R[rt] = 1e9, sum[rt] = 0;
            return ;
        }
        if(x <= mid) Wupd(ls, l, mid, x, k, opp);
        else Wupd(rs, mid + 1, r, x, k, opp);
        Wpushup(rt);
    }
    ll Wq(int x)
    {
        if(L[1] > R[1]) return ans[1];
        if(x < L[1]) return 1ll * L[1] + sum[1];
        else if(x > R[1]) return 1ll * R[1] + sum[1];
        else return x + sum[1];
    }
    short main()
    {
        freopen("function.in", "r", stdin) , freopen("function.out", "w", stdout);
        n = qr;
        fo(i, 1, n) op[i] = qr, v[i] = qr;
        Wbuild(1, 1, n);
        m = qr;
        fo(i, 1, m)
        {
            int opp = qr, pos = qr, vv;
            if(opp == 4) printf("%lld\n", Wq(pos));
            else vv = qr, Wupd(1, 1, n, pos, vv, opp);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}