原题链接

前言

重庆一位金牌大佬出的。

感受：

除了最后一题，感觉难度不如 C 组，甚至没之前 D 组题难？

T1 浪费 2.5 h，最后还是打表秒了。

T2 想出正解，但发现是数据结构题，最后 40 min 怒打 100 行，差点打出正解。

T3 花 20 min 打出 20 分部分分，赛后发现 XD 秒了（tql）。

T4 看题浪费 5 min，发现不敢惹。

挂分情况：

T1 没特判，-10。

T1 串

打表找规律题，没啥好说的，过。

简单说下规律。

首先答案对于每个 \(n\)，答案是固定的。

\(\begin{cases} ans=(\frac{n}{2}+1)\cdot(\frac{n}{2}+1)\ \ \ \ \ (n \bmod 2=1) \\ ans=(\frac{n}{2})\cdot(\frac{n}{2}+1)\ \ \ \ \ \ \ \ \ \ \ \ (n \bmod 2=0) \end{cases}\)

第一个 \(1\) 的位置在 \(\frac{n}{2}+(n \& 1)\)。

然后不断从第一位添加 \(1\)，每添加奇数次 \(1\) 就把第一个 \(1\) 的位置往后调 \(1\)。

注意 \(k=0\) 的情况。

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

int main()
{
    int n,k;cin>>n>>k;
    if(!k) {cout<<0;for(int i=1;i<=n;i++) cout<<0<<' ';return 0;}
    if(n&1) cout<<1ll*(n/2+1)*(n/2+1)<<'\n';
    else cout<<1ll*n/2*(n/2+1)<<'\n';
    int now=n/2+(n&1)+k/2;k--;
    for(int i=1;i<=n;i++)
    {
        if(k-->0||i==now) cout<<1<<' ';
        else cout<<0<<' ';
    }
}

T2 艺术家

对于我这种爱好数据结构的人，一眼看出是到线段树合并的题（当然也可以用启发式合并）。

考虑用线段树维护区间的颜色情况。

注意到各区间不相交，且只有包含关系，很容易想到树形结构。

• 考虑建树，从叶子结点开始操作，如果当前结点符合要求，就往上合并。

• 具体地，把区间按大小排序，用一棵线段树维护每个位置的所属区间，即可建树。合并时也要注意维护所属区间，保证一次修改只会更改一棵（要合并的）线段树上的信息。

• 对于判断是否合法，记一下当前区间出现的颜色数量和最大颜色数量即可。

分析下复杂度

每次只会修改当前位置所属区间的线段树，也只会往上合并 \(n\) 次。

所以时间复杂度 \(O(n\log n)\)。

由于建树，初始化，合并都是 \(\log\) 的，又都是线段树维护，实际常数极大。

其实这题空间限制是 256 MB，而我代码是 261 MB，理论上是 MLE 了。

但这 \(5e5\) 的数据结构题空间限制是否太严谨？于是 oj 很人性化的没让我 MLE。（

回到正题，线段树合并空间复杂度只与 update 操作有关，空间复杂度 \(O(n\log(n+q))\)，大概要开 \(N\cdot 40\)。

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

const int N=5e5+5;
int n,m,q,tot,ans,a[N],fa[N],vis[N],rt[N];
int lc[N*40],rc[N*40],mx[N*40],cnt[N*40];
struct node{int l,r,id;}p[N];
struct SegmentTree{// 维护每个位置的所属区间的线段树
    #define mid (l+r>>1)
    int bel[N<<2],tag[N<<2];
    inline void pushdown(int k)
    {
        if(!tag[k]) return;
        bel[k<<1]=bel[k<<1|1]=tag[k];
        tag[k<<1]=tag[k<<1|1]=tag[k];
        tag[k]=0;
    }
    void upd(int x,int y,int v,int k=1,int l=1,int r=n)
    {
        if(l>=x&&r<=y) return bel[k]=tag[k]=v,void();
        pushdown(k);
        if(x<=mid) upd(x,y,v,k<<1,l,mid);
        if(mid<y) upd(x,y,v,k<<1|1,mid+1,r);
    }
    int query(int x,int k=1,int l=1,int r=n)
    {
        if(l==r) return bel[k];
        pushdown(k);
        return x<=mid?query(x,k<<1,l,mid):query(x,k<<1|1,mid+1,r);
    }
}T;
//线段树合并
inline void pushup(int k) {mx[k]=max(mx[lc[k]],mx[rc[k]]);cnt[k]=cnt[lc[k]]+cnt[rc[k]];}
void update(int &k,int x,int v,int l=1,int r=n)
{
    if(!k) k=++tot;
    if(l==r) {cnt[k]+=v;mx[k]=cnt[k];return;}
    x<=mid?update(lc[k],x,v,l,mid):update(rc[k],x,v,mid+1,r);
    pushup(k);
}

void merge(int &p,int q,int l=1,int r=n)
{
    if(!p||!q) {p=p+q;return;}
    if(l==r) {cnt[p]+=cnt[q];mx[p]=cnt[p];return;}
    merge(lc[p],lc[q],l,mid),merge(rc[p],rc[q],mid+1,r);
    pushup(p);
}

void work(int u,int i)
{
    while(u&&mx[rt[u]]==1&&cnt[rt[u]]==p[u].r-p[u].l+1)
    {
        ans^=i,vis[p[u].id]=1;
        T.upd(p[u].l,p[u].r,fa[u]);//注意维护所属区间
        merge(rt[fa[u]],rt[u]);
        u=fa[u];
    }
}

inline int rd()
{
    int x=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x;
}

int main()
{
    n=rd(),m=rd(),q=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=m;i++) p[i]={rd(),rd(),i};
    sort(p+1,p+1+m,[&](node a,node b) {return a.r-a.l>b.r-b.l;});
    for(int i=1;i<=m;i++) fa[i]=T.query(p[i].l),T.upd(p[i].l,p[i].r,i);//建树
    for(int i=1;i<=n;i++)
    {
        int u=T.query(i);
        update(rt[u],a[i],1);
        work(u,0);
    }
    for(int i=1;i<=q;i++)
    {
        int x=rd(),y=rd(),u=T.query(x);
        update(rt[u],a[x],-1);a[x]=y;
        update(rt[u],a[x],1);
        work(u,i);
    }
    for(int i=1;i<=m;i++) if(!vis[i]) ans^=m+i;
    cout<<ans<<'\n';
}

T3 黑白树

改题感觉不是很难（with six-floor-split-liu's help) 。

考虑树上每个点距其最远的点是直径一端点。

求出直径，枚举当前答案长度 \(d\)，再讨论情况数，就 van ♂ 了。

设直径为 \(p,q\)。

先考虑 \(p,q\) 同色，对答案的贡献为 \(2^{n-2}\cdot dis \cdot 2\)，\(dis\) 为直径长度。

再考虑 \(p,q\) 异色。为方便，钦定 \(p\) 为黑，\(q\) 为白，最后再反转所有颜色则又是一种方案，且本质不变。

设除直径的点距直径端点距离分别为 \(x_i,y_i\)，不妨设 \(x_i \geq y_i\)。

那么对当前点染两种不同颜色会分别取到 \(x_i\) 和 \(y_i\)。

显然 \(d_{min}=max\{y_i\}\)。

把点按 \(x_i\) 从小到大排序，再遍历。那么 \(i+1 \sim n-2\) 的点都必须选择取到 \(y\) 的颜色，当前点选择取到 \(x\) 的颜色，其余 \(i-1\) 个点则随便选。可以发现，每遍历一个点，当前点的染色方案就从选择取到 \(y\) 的颜色变为取到 \(x\) 的颜色。所以是不重不漏的。

而对于 \(x_i<d_{min}\) 的点，它的长度贡献实际就是 \(d_{min}\)。

\(p,q\) 异色贡献：\(2\cdot (\sum\limits_{i=1}^{n-2} 2^{i-1}\cdot \max(x_i,d_{min}))+2 \cdot d_{min}\)。

\(i=0\) 的情况有一种方案，就单独加在后面了。注意之前钦定了 \(p,q\) 颜色，所以还要再乘 2。

最终答案：\(2^{n-1}\cdot dis+2\cdot d_{min}+\sum\limits_{i=1}^{n-2}2^{i-1}\cdot \max(x_i,d_{min})\)。

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

const int N=1e6+5,mod=1e9+7;
int n,p,q,ans,mi,x[N],dp[N],dq[N],pw[N]={1};
vector<int> G[N];

void dfs(int u,int f,int w,int &p,int *d)
{
    d[u]=w;if(d[u]>d[p]) p=u;
    for(int v:G[u]) if(v!=f) dfs(v,u,w+1,p,d);
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
    for(int i=1,u,v;i<n;i++) scanf("%lld%lld",&u,&v),G[u].push_back(v),G[v].push_back(u);
    dfs(1,0,0,p,dp);memset(dp,0,sizeof(dp));dfs(p,0,0,q,dp);dfs(q,0,0,p,dq);//求直径，距离
    for(int i=1;i<=n;i++) x[i]=max(dp[i],dq[i]),mi=max(mi,min(dp[i],dq[i]));
    sort(x+1,x+1+n);ans=(dp[q]*pw[n-1]+mi*2)%mod;
    for(int i=1;i<=n-2;i++) ans=(ans+pw[i]*max(mi,a[i].mx)%mod)%mod;
    cout<<ans;
}

T4 敢览求

咕咕咕。