2021牛客OI赛前集训营-提高组（第四场）-（重现赛）赛后总结

注：买的去年的题，本地OI赛制，排名按当年的计算。

又双叒叕挂大分，T2离正解只差一步（但输出格式错了，10pts -> 0pts）,T3花了 1h 30min 打出了正解但由于线段树标记没开 long long 爆 55 了

A.最终测试

把 1 个人劈成 4 半，用树状数组维护区间人数和， $O(n\log n)O(n\backslash log\; n)$ 就可以过掉此题。

代码：

#include<bits/stdc++.h>
using namespace std;
 
#define lowbit(x) x&(-x)
const int MAXN=1e5+5;
const int MAXM=2e4+5;
int a[MAXN][2],sum[MAXM];
void add(int x,int val){++x;while(x<MAXM) sum[x]+=val,x+=lowbit(x);}
int ask(int x)
{
    ++x;
    int ret=0;
    while(x) ret+=sum[x],x-=lowbit(x);
    return ret;
}
int query(int x){return ask(MAXM-2)-ask(x);}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d %d",&a[i][0],&a[i][1]),add(0,1),add(a[i][0],1),add(a[i][1],1),add(a[i][0]+a[i][1],1);
    for(int i=1;i<=n;++i)
    {
        add(0,-1),add(a[i][0],-1),add(a[i][1],-1),add(a[i][0]+a[i][1],-1);
        double ans=(double)(query(0)+query(a[i][0])+query(a[i][1])+query(a[i][0]+a[i][1]))/16+1;
        printf("%.6lf\n",ans);
        add(0,1),add(a[i][0],1),add(a[i][1],1),add(a[i][0]+a[i][1],1);
    }
    return 0;
}

B.空间跳越

考场都看出来用角谷猜想逆推了，但没想到负数怎么处理，结果直接 0 分。

角谷猜想，对于任意一个正整数 n，进行如下变换：若为偶数则变为 n/2，否则变为 n*3+1

负数的话先用后两种操作降为 100 以内（此时它会出现循环），然后一直加 $dd$ 直到大于等于 $11$ 为止，然后再正着一遍角谷猜想即可得出答案。

代码：

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

vector<int>ans;
int main()
{
	int q,d,l;
	cin>>q>>d>>l;
	int x;
	while(q--)
	{
		scanf("%d",&x);
		if(x<1)
		{
			while(abs(x)>100)
			{
				ans.push_back(x);
				if(x%2==0) x/=2;
				else x=x*3+1;
			}
			while(x<1)
			{
				ans.push_back(x);
				x+=d;
			}
		}
		while(x!=1)
		{
			ans.push_back(x);
			if(x%2==0) x/=2;
			else x=x*3+1;
		}
		ans.push_back(1);
		reverse(ans.begin(),ans.end());
		printf("%ld",ans.size()-1);
		for(auto i:ans) printf(" %d",i);
		putchar('\n'),ans.clear();
	}
	return 0;
}

C.快速访问

WARNING：本题思维难度不大，但代码实现难度极高，提高组及以下 OIer 请在成年人的陪同下谨慎观看！

考虑暴力拆式子：

$A_{x}A\_x$

$=di{s}^2(x,0)+\sum di{s}^2(x,y)=dis^2(x,0)+\backslash sum\; dis^2(x,y)$

$=di{s}^2(x,0)+\sum (de{p}_x+de{p}_y-de{p}_{lca(x,y)}\times 2{)}^2=dis^2(x,0)+\backslash sum(dep\_x+dep\_y-dep\_\{lca(x,y)\}\backslash times\; 2)^2$

$=di{s}^2(x,0)+\sum ({de{p}_x}^2+{de{p}_y}^2+{de{p}_{lca(x,y)}}^2\times 4+de{p}_x\times de{p}_y\times 2-de{p}_x\times de{p}_{lca(x,y)}\times 4-de{p}_y\times de{p}_{lca(x,y)}\times 4)=dis^2(x,0)+\backslash sum(\{dep\_x\}^2+\{dep\_y\}^2+\{dep\_\{lca(x,y)\}\}^2\backslash times\; 4\; +dep\_x\backslash times\; dep\_y\; \backslash times\; 2-dep\_x\backslash times\; dep\_\{lca(x,y)\}\; \backslash times\; 4-dep\_y\backslash times\; dep\_\{lca(x,y)\}\; \backslash times\; 4)$

$=di{s}^2(x,0)+\sum {de{p}_x}^2+\sum {de{p}_y}^2+4\times \sum {de{p}_{lca(x,y)}}^2+2\times de{p}_x\times \sum de{p}_y-4\times de{p}_x\times \sum de{p}_{lca(x,y)}-4\times \sum de{p}_y\times de{p}_{lca(x,y)}=dis^2(x,0)+\backslash sum\; \{dep\_x\}^2+\backslash sum\{dep\_y\}^2+4\backslash times\backslash sum\; \{dep\_\{lca(x,y)\}\}^2+2\backslash times\; dep\_x\backslash times\backslash sum\; dep\_y-4\backslash times\; dep\_x\backslash times\backslash sum\; dep\_\{lca(x,y)\}-4\backslash times\backslash sum\; dep\_y\; \backslash times\; dep\_\{lca(x,y)\}$

第 $1,21,2$ 项（$di{s}^2(x,0)dis^2(x,0)$，$\sum {de{p}_x}^2\backslash sum\; \{dep\_x\}^2$）：这个应该不难 $\mathcal{O}(1)\backslash mathcal\{O\}(1)$ 求出。

第 $3,53,5$ 项（$\sum {de{p}_y}^2\backslash sum\{dep\_y\}^2$，$2\times de{p}_x\times \sum de{p}_{y}2\backslash times\; dep\_x\backslash times\backslash sum\; dep\_y$）：可以顺便维护前缀和，同样可以 $\mathcal{O}(1)\backslash mathcal\{O\}(1)$ 求出。

第 $66$ 项（$4\times de{p}_x\times \sum de{p}_{lca(x,y)}4\backslash times\; dep\_x\backslash times\backslash sum\; dep\_\{lca(x,y)\}$）：可以采用树剖，将 $yy$ 到 $00$ 的路径每一段边都加 $11$，查询出的 $xx$ 到 $00$ 路径上的权值和即为答案。

第 $77$ 项（$4\times \sum de{p}_y\times de{p}_{lca(x,y)}4\backslash times\backslash sum\; dep\_y\; \backslash times\; dep\_\{lca(x,y)\}$）：与第 $66$ 项同理，只不过边上的权值加的是 $de{p}_{y}dep\_y$。

第 $44$ 项（$4\times \sum {de{p}_{lca(x,y)}}^{2}4\backslash times\backslash sum\; \{dep\_\{lca(x,y)\}\}^2$）：这是最难的一项，不过仍然可以维护，考虑平方数列 $1,4,9,16,\mathrm{.}\mathrm{.}\mathrm{.}1,4,9,16,...$ 它的差分数组是 $1,3,5,7,\mathrm{.}\mathrm{.}\mathrm{.}1,3,5,7,...$ 因此只要维护区间加等差数列即可，由于每次都是修改到根结点的所以不存在链反向的情况。

总复杂度 $\mathcal{O}(n\log n)\backslash mathcal\{O\}(n\backslash log\; n)$。

代码：

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

typedef long long ll;
const int MAXN=2e5+5;
struct Segment_Tree
{
    #define ls(p) p<<1
    #define rs(p) p<<1|1
    struct NODE
    {
        #define sum1(p) tree[p].sum1
        #define sum2(p) tree[p].sum2
        #define sum3(p) tree[p].sum3
        #define tag1(p) tree[p].tag1
        #define tag2_a(p) tree[p].tag2_a
        #define tag2_d(p) tree[p].tag2_d
        #define tag3(p) tree[p].tag3
        int l,r;
        ll sum1,sum2,sum3;
        ll tag1,tag2_a,tag2_d,tag3;
        int len(){return r-l+1;}
    }tree[MAXN<<2];
    void update(int p,ll tag1,ll tag2_a,ll tag2_d,ll tag3)
    {
        sum1(p)+=(ll)tag1*tree[p].len();
        sum2(p)+=(ll)tree[p].len()*tag2_a-(ll)tree[p].len()*(tree[p].len()-1)/2*tag2_d;
        sum3(p)+=(ll)tag3*tree[p].len();
        tag1(p)+=tag1,tag2_a(p)+=tag2_a,tag2_d(p)+=tag2_d,tag3(p)+=tag3;
    }
    void push_up(int p)
    {
        sum1(p)=sum1(ls(p))+sum1(rs(p));
        sum2(p)=sum2(ls(p))+sum2(rs(p));
        sum3(p)=sum3(ls(p))+sum3(rs(p));
    }
    void push_down(int p)
    {
        if(tag1(p) || tag2_a(p) || tag2_d(p) || tag3(p))
        {
            update(ls(p),tag1(p),tag2_a(p)-tree[rs(p)].len()*tag2_d(p),tag2_d(p),tag3(p));
            update(rs(p),tag1(p),tag2_a(p),tag2_d(p),tag3(p));
            tag1(p)=tag2_a(p)=tag2_d(p)=tag3(p)=0;
        }
    }
    void build(int p,int l,int r)
    {
        tree[p].l=l,tree[p].r=r;
        if(l==r) return;
        int mid=(tree[p].l+tree[p].r)>>1;
        build(ls(p),l,mid),build(rs(p),mid+1,r);
    }
    void modify1(int p,int l,int r,int x)
    {
        if(l<=tree[p].l && tree[p].r<=r){update(p,x,0,0,0);return;}
        push_down(p);
        int mid=(tree[p].l+tree[p].r)>>1;
        if(l<=mid) modify1(ls(p),l,r,x);
        if(r>mid) modify1(rs(p),l,r,x);
        push_up(p);
    }
    void modify2(int p,int l,int r,int a,int d)
    {
        if(l<=tree[p].l && tree[p].r<=r){update(p,0,a,d,0);return;}
        push_down(p);
        int mid=(tree[p].l+tree[p].r)>>1;
        if(r<=mid) modify2(ls(p),l,r,a,d);
        else if(l>mid) modify2(rs(p),l,r,a,d);
        else modify2(ls(p),l,mid,a-(r-mid)*d,d),modify2(rs(p),mid+1,r,a,d);
        push_up(p);
    }
    void modify3(int p,int l,int r,int x)
    {
        if(l<=tree[p].l && tree[p].r<=r){update(p,0,0,0,x);return;}
        push_down(p);
        int mid=(tree[p].l+tree[p].r)>>1;
        if(l<=mid) modify3(ls(p),l,r,x);
        if(r>mid) modify3(rs(p),l,r,x);
        push_up(p);
    }
    ll query(int p,int l,int r,int opt)
    {
        if(l<=tree[p].l && tree[p].r<=r)
        {
            if(opt==1) return sum1(p);
            else if(opt==2) return sum2(p);
            else return sum3(p);
        }
        push_down(p);
        int mid=(tree[p].l+tree[p].r)>>1;
        ll ret=0;
        if(l<=mid) ret+=query(ls(p),l,r,opt);
        if(r>mid) ret+=query(rs(p),l,r,opt);
        return ret;
    }
}SGT;
vector<int>G[MAXN];
int dep[MAXN],fa[MAXN],son[MAXN],siz[MAXN],top[MAXN],dfn[MAXN],tim;
void dfs1(int x,int father)
{
    dep[x]=dep[father]+1,fa[x]=father,siz[x]=1;
    if(x==1) dep[x]=0;
    for(auto y:G[x])
    {
        if(y==father) continue;
        dfs1(y,x),siz[x]+=siz[y];
        if(siz[y]>siz[son[x]]) son[x]=y;
    }
}
void dfs2(int x,int root)
{
    top[x]=root,dfn[x]=++tim;
    if(!son[x]) return;
    dfs2(son[x],root);
    for(auto y:G[x]) if(y!=fa[x] && y!=son[x]) dfs2(y,y);
}
void add_chain1(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        SGT.modify1(1,dfn[top[x]],dfn[x],z),x=fa[top[x]];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    SGT.modify1(1,dfn[x],dfn[y],z);
}
void add_chain2(int x,int y,int z,int d)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        SGT.modify2(1,dfn[top[x]],dfn[x],z,d),z-=(dfn[x]-dfn[top[x]]+1)*d,x=fa[top[x]];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    SGT.modify2(1,dfn[x],dfn[y],z,d);
}
void add_chain3(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        SGT.modify3(1,dfn[top[x]],dfn[x],z),x=fa[top[x]];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    SGT.modify3(1,dfn[x],dfn[y],z);
}
ll query_chain(int x,int y,int opt)
{
    ll ret=0; 
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ret+=SGT.query(1,dfn[top[x]],dfn[x],opt),x=fa[top[x]];
    }
    if(dfn[x]>dfn[y]) swap(x,y);
    ret+=SGT.query(1,dfn[x],dfn[y],opt);
    ret-=SGT.query(1,dfn[1],dfn[1],opt);
    return ret;
}
void add(int x)
{
    add_chain1(1,x,1);
    add_chain2(1,x,dep[x]*2-1,2);
    add_chain3(1,x,dep[x]);
}
void del(int x)
{
    add_chain1(1,x,-1);
    add_chain2(1,x,-dep[x]*2+1,-2);
    add_chain3(1,x,-dep[x]);
}
int main()
{
    int n,k;
    cin>>n>>k;
    ++n;
    int u,v;
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v),++u,++v;
        G[u].push_back(v),G[v].push_back(u);
    }
    dfs1(1,0),dfs2(1,1),SGT.build(1,1,n);
    ll s=0,ss=0;
    int cnt=0;
    for(int i=2;i<=n;++i)
    {
        ll ans=(ll)dep[i]*dep[i];
        if(i-k-1>1) del(i-k-1),--cnt,s-=dep[i-k-1],ss-=(ll)dep[i-k-1]*dep[i-k-1];
        ans+=(ll)dep[i]*dep[i]*cnt;
        ans+=(ll)dep[i]*2*s;
        ans+=ss;
        ans-=(ll)4*dep[i]*query_chain(1,i,1);
        ans+=(ll)4*query_chain(1,i,2);
        ans-=(ll)4*query_chain(1,i,3);
        add(i),++cnt,s+=dep[i],ss+=(ll)dep[i]*dep[i];
        printf("%lld\n",ans);
    }
    return 0;
}

注意线段树的 tag 一定要开 long long，因为单次的累加不会爆但累加

D.门童

设 $d{p}_{i}dp\_i$ 为第 $ii$ 个时间如果牛牛还没下班，他的最大欢乐值。

转移方程不难，但要注意牛牛不能在接完所有人之后摸鱼，且必须接完所有人。

加上点小优化可以做到 $\mathcal{O}(n^2)\backslash mathcal\{O\}(n^2)$（跑不满），目前尚未弄懂如何用李超线段树优化。

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

typedef long long ll;
const int MAXN=1e5+5;
struct node
{
	int t,p,f;
	friend bool operator < (const node i,const node j){return i.t<j.t;}
	friend bool operator > (const node i,const node j){return i.t>j.t;}
}a[MAXN];
int x[2][2],tim[MAXN<<1];
ll dp[MAXN<<1];
int n,L;
int main()
{
	cin>>n>>L;
	cin>>x[0][0]>>x[0][1]>>x[1][0]>>x[1][1];
	for(int i=1;i<=n;++i) scanf("%d %d %d",&a[i].t,&a[i].p,&a[i].f);
	sort(a+1,a+n+1);
	int cnt=0;
	for(int i=1;i<=n;++i) tim[++cnt]=a[i].t,tim[++cnt]=a[i].t+a[i].p;
	sort(tim+1,tim+cnt+1);
	int len=unique(tim+1,tim+cnt+1)-tim-1;
	memset(dp,-0x3f,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=len;++i)
	{
		node tmp={tim[i],0,0};
		int pos=upper_bound(a+1,a+n+1,tmp)-a,r=pos;
		ll sum1=0,sum2=0;
		for(int j=i-1;j>=0;--j)
		{
			bool flag=0;
			while(pos>1 && a[pos-1].t>tim[j])
			{
				--pos;
				if(a[pos].t+a[pos].p<tim[i]){flag=1;break;}
				sum1+=(ll)a[pos].f*(a[pos].t+a[pos].p-tim[i]);
				sum2+=(ll)a[pos].f*a[pos].p;
			}
			if(flag) break;
			if(pos==r) continue;
			dp[i]=max(dp[i],dp[j]-(ll)x[0][0]*(tim[i]-tim[j])+sum2);
			if(tim[i]-tim[j]>=2*L) dp[i]=max(dp[i],dp[j]-(ll)(x[0][1]+x[1][0])*L+(ll)x[1][1]*(tim[i]-tim[j]-2*L)+sum1);
		}
	}
    ll ans=-1e18;
    int maxn=0;
    for(int i=1;i<=n;++i) maxn=max(maxn,a[i].t);
    for(int i=len;i>=1;--i)
    {
        if(tim[i]<maxn) break;
        ans=max(ans,dp[i]);
    }
	cout<<ans;
	return 0;

//后记&总结：本次考试时间分配极不合理， T1 其实就花了 10min ，本来是占很大优势的，T2离正解只差一步之遥，但却把大笔的时间押在了 T3 上，虽然最后也打出来了，却因为没开 long long 挂了 45 分，且因此没时间打 T4 的 dp。总而言之还是要调整好自己的状态，找好自己的节奏，这样才能发挥出真实的实力。

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