2022牛客OI赛前集训营-提高组（第一场） 赛后总结

A.光

既然放在第一题那就应该不会太难，无脑暴力 $O(n^4)O(n^4)$ 能拿30pts，稍微加一个二分答案就能拿下70pts。

这里只讲正解：

令 $a,b,c,da,b,c,d$ 分别为左上角，右上角，左下角，右下角四盏灯的耗电量，$x_1,x_2,x_3,x_{4}x\_1,x\_2,x\_3,x\_4$ 分别为左上角，右上角，左下角，右下角四盏灯要求的亮度之和，那么一定满足下列式子：

设 $a=k\times 4+tmp\mathrm{，}maxn=a+b+c+da=k\backslash times4+tmp，maxn=a+b+c+d$，得：

$\{\begin{array}{c}a+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{d}{4}}\rfloor \le x_1\\ b+\lfloor {\displaystyle \frac{a}{2}}\rfloor +\lfloor {\displaystyle \frac{d}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{4}}\rfloor \le x_2\\ c+\lfloor {\displaystyle \frac{a}{2}}\rfloor +\lfloor {\displaystyle \frac{d}{2}}\rfloor +\lfloor {\displaystyle \frac{b}{4}}\rfloor \le x_3\\ d+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{a}{4}}\rfloor \le x_4\end{array}\backslash begin\{cases\}a+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{d\}\{4\}\backslash rfloor\backslash le\; x\_1\backslash \backslash b+\backslash lfloor\backslash dfrac\{a\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{d\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{4\}\backslash rfloor\backslash le\; x\_2\backslash \backslash c+\backslash lfloor\backslash dfrac\{a\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{d\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{b\}\{4\}\backslash rfloor\backslash le\; x\_3\backslash \backslash d+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{a\}\{4\}\backslash rfloor\backslash le\; x\_4\backslash end\{cases\}$

$\Rrightarrow \backslash Rrightarrow$ $\{\begin{array}{c}k\times 4+tmp+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-k\times 4-tmp-b-c}{4}}\rfloor =k\times 3+tmp+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-tmp-b-c}{4}}\rfloor \le x_1\\ b+\lfloor {\displaystyle \frac{k\times 4+tmp}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-k\times 4-tmp-b-c}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{4}}\rfloor =b+\lfloor {\displaystyle \frac{tmp}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-k-tmp-b-c}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{4}}\rfloor \le x_2\\ c+\lfloor {\displaystyle \frac{k\times 4+tmp}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-k\times 4-tmp-b-c}{2}}\rfloor +\lfloor {\displaystyle \frac{b}{4}}\rfloor =c+\lfloor {\displaystyle \frac{tmp}{2}}\rfloor +\lfloor {\displaystyle \frac{maxn-k-tmp-b-c}{2}}\rfloor +\lfloor {\displaystyle \frac{b}{4}}\rfloor \le x_3\\ maxn-k\times 4-tmp-b-c+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{k\times 4+tmp}{4}}\rfloor =maxn-k\times 3-tmp-b-c+\lfloor {\displaystyle \frac{b}{2}}\rfloor +\lfloor {\displaystyle \frac{c}{2}}\rfloor +\lfloor {\displaystyle \frac{tmp}{4}}\rfloor \le x_4\end{array}\backslash begin\{cases\}k\backslash times4+tmp+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-k\backslash times4-tmp-b-c\}\{4\}\backslash rfloor=k\backslash times3+tmp+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-tmp-b-c\}\{4\}\backslash rfloor\backslash le\; x\_1\backslash \backslash b+\backslash lfloor\backslash dfrac\{k\backslash times4+tmp\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-k\backslash times4-tmp-b-c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{4\}\backslash rfloor=b+\backslash lfloor\backslash dfrac\{tmp\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-k-tmp-b-c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{4\}\backslash rfloor\backslash le\; x\_2\backslash \backslash c+\backslash lfloor\backslash dfrac\{k\backslash times4+tmp\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-k\backslash times4-tmp-b-c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{b\}\{4\}\backslash rfloor=c+\backslash lfloor\backslash dfrac\{tmp\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{maxn-k-tmp-b-c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{b\}\{4\}\backslash rfloor\backslash le\; x\_3\backslash \backslash maxn-k\backslash times4-tmp-b-c+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{k\backslash times4+tmp\}\{4\}\backslash rfloor=maxn-k\backslash times3-tmp-b-c+\backslash lfloor\backslash dfrac\{b\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{c\}\{2\}\backslash rfloor+\backslash lfloor\backslash dfrac\{tmp\}\{4\}\backslash rfloor\backslash le\; x\_4\backslash end\{cases\}$

好丑的式子……

那么接下来只要二分 $maxnmaxn$ ，枚举 $b,c,tmpb,c,tmp$ 即可。

对于中间两个式子直接判合法性，对于上下两个化简后可以得出 $kk$ 的范围 $[l,r][l,r]$ （若 ， ， 均为不合法）。

时间复杂度 $O(n^{2}logn)O(n^2logn)$ 。

贴下代码吧：

#include<bits/stdc++.h>
using namespace std;

int x[5];
bool check(int maxn)
{
    for(int b=maxn;~b;--b)
        for(int c=maxn-b;~c;--c)
            for(int tmp=0;tmp<=min(3,maxn-b-c);++tmp)
            {
                if(b+tmp/2+(maxn-b-c-tmp)/2+c/4<x[2]) continue;
                if(c+tmp/2+(maxn-b-c-tmp)/2+b/4<x[3]) continue;
                int now=max(0,x[1]-tmp-b/2-c/2-(maxn-b-c-tmp)/4);
                int l=(now%3)?(now/3+1):(now/3);
                now=maxn-tmp-b-c+tmp/4+b/2+c/2-x[4];
                if(now<0) continue;
                int r=now/3;
                if(maxn-l*4-tmp-b-c<0) continue;
                if(r<l || r<0) continue;
                return 1;
            }
    return 0;
}
int main()
{
    int ans=0;
    for(int i=1;i<=4;++i) scanf("%d",&x[i]),ans+=x[i];
    int l=0,r=ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

B.爬

考虑按位拆数，对于每一位只需考虑当前节点及其儿子中该位为 $11$ 的数。

合法方案数 $2^{cnt-1}2^\{cnt-1\}$ ，其他位置随便选有 $2^{n-cnt}2^\{n-cnt\}$ 种情况。

于是当前块对答案的贡献 ${\sum }_{i=0}^{29}(num[i]>0)\times 2^i\times 2^{cnt-1}\times 2^{n-cnt}\backslash sum\_\{i=0\}^\{29\}\; (num[i]>0)\backslash times2^i\backslash times2^\{cnt-1\}\backslash times2^\{n-cnt\}$ 。

当然还要减去只有一只蚂蚁的贡献，还有根节点有一些恶心的特判。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int MOD=1e9+7;
vector<int>G[MAXN];
int a[MAXN],two[MAXN];
int n,ans;
void add(int x,int *num)
{
    for(int i=0;i<30;++i) if(x&(1<<i)) ++num[i];
}
void dfs(int x)
{
    int num[30],cnt=0;
    memset(num,0,sizeof(num));
    add(a[x],num),++cnt;
    for(auto y:G[x]) dfs(y),add(a[y],num),++cnt;
    if(cnt==1) return;
    int now=(x==1?two[cnt-2]:two[cnt-1]),all=(x==1?two[n-cnt]:two[n-cnt-1]);
    for(int i=0;i<30;++i)
    {
        if(!num[i]) continue;
        int tmp=now;
        if(x==1 && a[x]&(1<<i) && num[i]==1) (tmp<<=1)%=MOD;
        (ans+=(1ll<<i)*tmp%MOD*all%MOD)%=MOD;
    }
    (ans-=(long long)a[x]*all%MOD-MOD)%=MOD;
    if(x!=1) for(auto y:G[x]) (ans-=(long long)a[y]*all%MOD-MOD)%=MOD;
}
int main()
{
    cin>>n;
    two[0]=1;
    for(int i=1;i<=n;++i) two[i]=(two[i-1]<<1)%MOD;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    int x;
    for(int i=2;i<=n;++i) scanf("%d",&x),G[x].push_back(i);
    dfs(1);
    cout<<ans;
    return 0;
}

C.字符串

考场打了个 $O(n^4)O(n^4)$ 的dp，还过了50pts……

说实话OI赛制真的不是特别敢打贪心（尤其是放在T3的情况下）。

贪心构造的话就是先让尽量多的AB交错排，然后多的再凑上长度为 $a\mathrm{/}ba/b$ 的 $A\mathrm{/}BA/B$ 串。

代码（贴了些题解没有的注释）：

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin>>T;
    int n,m,a,b,c;
    while(T--)
    {
        scanf("%d %d %d %d %d",&n,&m,&a,&b,&c);
        int ans=(n-1)/a+(m-1)/b+2,tmp=min(n,m/c);  //先全A后全B的情况
        for(int i=1;i<=tmp;++i)
        {
            int sum=i*2; //间隔有i*2个（包括第1个与第0个）
            if(c>b) sum+=(c-1)/b*i;  //在构造长度为c的串时顺便贡献的答案
            if(n-i>=1) ++sum,sum+=(n-i-1)/a;  //前面是ABBBABBB的串，结尾全放A
            if(m-c*i>=1)   //前面是BBBABBBA的串，结尾全放B
            {
                ++sum;  //末尾扔一个B
                int lst=m-c*i-1;
                if(c<=b)                          //把前面长度为c的串凑整
                {
                    int tmp=min(i,lst/(b+1-c));
                    lst-=tmp*(b+1-c),sum+=tmp;
                }
                else
                {
                    int tmp=min(i,lst/(b-(c-1)%b));
                    lst-=tmp*(b-(c-1)%b),sum+=tmp;
                }
                sum+=lst/b;  //剩下的全扔到末尾
            }
            ans=max(ans,sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

D.奇怪的函数

本题数据太弱纯暴力能拿30pts，考场为了过特殊性质2的点加了些奇怪的优化然后写挂了剩下5pts……（OI赛制的魅力）

可以看出它是一个分段函数，min和max是限制初始值的，用线段树维护初始值的限制范围以及总共加了多少即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define ls(p) p<<1
#define rs(p) p<<1|1
const int MAXN=1e5+5;
const int INF=1e9;
struct Segment_Tree
{
    int l,r,L=-INF,R=INF,sum=0;
}tree[MAXN<<2];
void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(p),l,mid),build(rs(p),mid+1,r);
}
void push_up(int p)
{
    tree[p].L=max(min(tree[ls(p)].L,tree[rs(p)].R-tree[ls(p)].sum),tree[rs(p)].L-tree[ls(p)].sum);
    tree[p].R=max(min(tree[ls(p)].R,tree[rs(p)].R-tree[ls(p)].sum),tree[rs(p)].L-tree[ls(p)].sum);
    tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
}
void modify(int p,int pos,int opt,int val)
{
    if(tree[p].l==tree[p].r)
    {
        switch(opt)
        {
            case 1: tree[p]=(Segment_Tree){tree[p].l,tree[p].r,-INF,INF,val}; break;
            case 2: tree[p]=(Segment_Tree){tree[p].l,tree[p].r,-INF,val,0}; break;
            case 3: tree[p]=(Segment_Tree){tree[p].l,tree[p].r,val,INF,0}; break;
        }
        return;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(pos<=mid) modify(ls(p),pos,opt,val);
    else modify(rs(p),pos,opt,val);
    push_up(p);
}
int main()
{
    int n;
    cin>>n;
    build(1,1,n);
    int pos,opt,val;
    for(int i=1;i<=n;++i) scanf("%d %d",&opt,&val),modify(1,i,opt,val);
    int q;
    cin>>q;
    while(q--)
    {
        scanf("%d",&opt);
        if(opt!=4) scanf("%d %d",&pos,&val),modify(1,pos,opt,val);
        else scanf("%d",&val),printf("%d\n",max(min(val,tree[1].R),tree[1].L)+tree[1].sum);
    }
    return 0;
}

后记：这是第一次打牛客OI集训营，题目难度大概有CSP-S级别，不过感觉部分分设计的不太合理，导致分差拉的很大。

笔者能力有限，有未述详尽或有误之处，欢迎指正。