HLOJ-DAY 3

Posted on By 张, 高畅 HLOJ-DAY 3无评论

[一些前摇]

很好今天淘汰赛挂了

很好明天还有一场

[T1]

[题面]

给定一棵 𝑛 个点的树，求出满足以下条件的点集 S 的个数。

S 的导出子图中恰有一个点 𝑢 满足 deg_u \geq 3，其中 deg_u 表示 𝑢 的度数。

对 998244353 取模。

满足 1 \leq n \leq 5\times 10^3 。

最后悔的事情就是只打了特殊性质就跑了。

后面的题目一个比一个难。

[正解]

事实上我们只要找出 deg_u \geq 3 的点，
然后将其相连的子树大小算出来。

很显然答案最初是 \prod_v (Size_v+1)。

但是还要扣除删除只剩 0/1/2 相连的情况。

0的答案显然是 1，1的答案显然是 \sum Size_v，2的答案使用后缀和进行计算就可以了。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
typedef long long LL;
const LL mod=998244353;
int n,Size[N],d[N],par[N];
LL res=0;
vector<int>G[N];
void dfs(int u,int father)
{
    par[u]=father;
    Size[u]=1;
    for(auto j:G[u])
    {
        if(j==father)continue;
        dfs(j,u);
        Size[u]+=Size[j];
    }
}
void work(int u)
{
    vector<int>V;
    for(auto j:G[u])
    {
        if(j==par[u])V.push_back(n-Size[u]);
        else V.push_back(Size[j]);
    }
    LL ans=1LL;
    for(auto it:V)ans=1LL*ans*(it+1)%mod;
    res=(res+ans)%mod;
    res=(res+mod-1)%mod;//0
    ans=0LL;
    for(int i=V.size()-1;~i;i--)
    {
        res=(res+mod-V[i])%mod;//1
        res=(res+mod-(1LL*ans*V[i])%mod)%mod;//2
        ans=(ans+V[i])%mod;
    }
}
int main()
{
    freopen("star.in","r",stdin);
    freopen("star.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        d[a]++,d[b]++;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)
    {
        if(d[i]>=3)work(i);
    }
    printf("%lld",res);
    return 0;
}

很好不会改了

回到昨天继续吧。

[T3]

原题

令人感伤的红温

第一眼，这什么式子。

第二眼，还是不会分析。

显然 A(l,r) 其实就是数组中区间 [l,r] 内的最大值位置，相同的取靠右的。

而 Ω(l,r) = \max(0,l-A(1,r))

由于修改操作只在前缀添加非负数，所以我们发现一旦存在 a[x]>a[x+1] ，那么 a[x+1] 对答案一定是没有贡献的。

因此我们用并查集把没有贡献的合并到离它最近的有贡献的数上，并使用链表进行维护。

由于每一个数最多被删除一次，而且带路径压缩的并查集约可以看成是 O(1) 的，因此最终复杂度约为 O(n)。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=6e6+5;
int n,m;
int a[N],C[N],ne[N];
int par[N];
int find(int x)
{
    if(par[x]==x)return x;
    else return par[x]=find(par[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        par[i]=i;
        ne[i]=i+1;
    }
    for(int i=1;i<=n;i++)
    {
        int j=i+1;
        while(j<=n&&a[i]>a[j])
        {
            par[j]=i;
            j++;
        }
        ne[i]=j;
        C[i]=a[j]-a[i];
        i=j-1;
    }
    while(m--)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op==1)
        {
            int t=find(x);
            int tt=t;
            int sub=C[t];
            for(t=ne[t];t<=n&&sub<y;t=ne[t])
            {
                par[t]=tt;
                sub+=C[t];
            }
            ne[tt]=t;
            C[tt]=sub-y;
        }
        else printf("%d\n",max(0,x-find(y)));
    }
    return 0;
}

[T7]

原题

为什么感觉与蚯蚓异曲同工之妙

通过分析我们可以知道，游戏的模拟分为两个阶段：

  1. 阶段一：所有最强蛇进食后都不是最弱的蛇，放心吃。
  2. 阶段二：所有最强蛇进食后都是最弱的蛇，直到有一条蛇可以放心吃为止。

维护时，我们采用两个双端队列维护。

其中一个用来存本来的序列，另一个存吃完之后的序列。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef pair<int,int> PII;
int n,a[N];
void work()
{
    deque<PII>QY,QM;
    int res=0;
    for(int i=1;i<=n;i++)QY.push_back({a[i],i});
    while(1)
    {
        if(QY.size()+QM.size()==2)
        {
            res=1;
            break;
        }
        int Rx=QY.front().first;
        QY.pop_front();
        PII u;
        if(QM.empty()||(!QY.empty()&&QY.back()>QM.back()))
        {
            u=QY.back();
            QY.pop_back();
        }
        else
        {
            u=QM.back();
            QM.pop_back();
        }
        u.first-=Rx;
        if(QY.empty()||u<QY.front())
        {
            res=QY.size()+QM.size()+2;
            int cnt=0;
            while(1)
            {
                cnt++;
                if(QY.size()+QM.size()==1)
                {
                    res-=(!(cnt&1));
                    break;
                }
                PII Qt;
                if(QM.empty()||(!QY.empty()&&QY.back()>QM.back()))
                {
                    Qt=QY.back();
                    QY.pop_back();  
                }
                else 
                {
                    Qt=QM.back();
                    QM.pop_back();
                }
                u={Qt.first-u.first,Qt.second};
                if((QY.empty()||u<QY.front())&&(QM.empty()||u<QM.front()));
                else
                {
                    res-=(!(cnt&1));
                    break;
                }
            }
            break;
        }
        else QM.push_front(u);
    }
    printf("%d\n",res);
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int C=1;C<=T;C++)
    {
        if(C==1)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        }
        else
        {
            int k=0;
            scanf("%d",&k);
            while(k--)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                a[x]=y;
            }
        }
        work();
    }
    return 0;
}

[T8]

原题

我不是算数天才
你也不要找我算数

一个序列是不好维护的，因此我们只能通过维护一些关键的东西来推出是等差数列。

具体要判断以下三个东西：

  1. 首先 \max -\min=(r-l)\times k
  2. 其次相邻两数差的绝对值的 gcd 是 k
  3. 区间 [l,r] 内的数不重复

对于1/2，我们可以使用线段树。

对于3，我们使用 map 套 set 维护位置。

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int INF=1e9;
int n,m,a[N],c[N],pre[N];
struct node
{
    int Max,Min,pre;    
}tr[N<<2];
int G[N<<2];
void pushup_tr(int u)
{
    tr[u].Max=max(tr[u<<1].Max,tr[u<<1|1].Max);
    tr[u].Min=min(tr[u<<1].Min,tr[u<<1|1].Min);
    tr[u].pre=max(tr[u<<1].pre,tr[u<<1|1].pre);
}
void build_tr(int u,int l,int r)
{
    if(l==r)
    {
        tr[u].Max=tr[u].Min=a[l];
        tr[u].pre=pre[l];
        return;
    }
    int mid=l+r>>1;
    build_tr(u<<1,l,mid);
    build_tr(u<<1|1,mid+1,r);
    pushup_tr(u);
}
void modify_tr(int u,int l,int r,int x,int v)
{
    if(l==r)
    {
        tr[u].Max=tr[u].Min=v;
        tr[u].pre=pre[l];
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify_tr(u<<1,l,mid,x,v);
    else modify_tr(u<<1|1,mid+1,r,x,v);
    pushup_tr(u);
}
node query_tr(int u,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)return tr[u];
    node res={-INF,INF,-INF};
    int mid=l+r>>1;
    if(L<=mid)
    {
        node tp=query_tr(u<<1,l,mid,L,R);
        res={max(res.Max,tp.Max),min(res.Min,tp.Min),max(res.pre,tp.pre)};
    }
    if(mid<R)
    {
        node tp=query_tr(u<<1|1,mid+1,r,L,R);
        res={max(res.Max,tp.Max),min(res.Min,tp.Min),max(res.pre,tp.pre)};
    }
    return res;
}
//------
void pushup_G(int u)
{
    if(G[u<<1]&&G[u<<1|1])G[u]=__gcd(G[u<<1],G[u<<1|1]);
    else G[u]=0;
}
void build_G(int u,int l,int r)
{
    if(l==r)
    {
        G[u]=c[l];
        return;
    }
    int mid=l+r>>1;
    build_G(u<<1,l,mid);
    build_G(u<<1|1,mid+1,r);
    pushup_G(u);
}
void modify_G(int u,int l,int r,int x)
{
    if(l==r)
    {
        G[u]=c[l];
        return;
    }
    int mid=l+r>>1;
    if(x<=mid)modify_G(u<<1,l,mid,x);
    else modify_G(u<<1|1,mid+1,r,x);
    pushup_G(u);
}
int query_G(int u,int l,int r,int L,int R)
{
    if(l==r)return G[u];
    int mid=l+r>>1;
    int res=0;
    if(L<=mid)res=__gcd(res,query_G(u<<1,l,mid,L,R));
    if(mid<R)res=__gcd(res,query_G(u<<1|1,mid+1,r,L,R));
    return res;
}
int work(int l,int r,int k)
{
    if(l==r)return 1;
    node Q=query_tr(1,1,n,l,r);
    return (Q.Max-Q.Min==1LL*(r-l)*k)&&(!k||Q.pre<l)&&(query_G(1,1,n-1,l,r-1)==k);
}
map<int,set<int> >mp;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i>=2)c[i-1]=abs(a[i]-a[i-1]);
        if(!mp[a[i]].size())pre[i]=-1;
        else pre[i]=*(--mp[a[i]].end());
        mp[a[i]].insert(i);
    }
    build_tr(1,1,n);
    build_G(1,1,n-1);
    int cnt=0;
    while(m--)
    {
        int op,x,y,k;
        scanf("%d%d%d",&op,&x,&y);
        x^=cnt;
        y^=cnt;
        if(op==1)
        {
            auto it=mp[a[x]].find(x);
            if(it!=mp[a[x]].end())
            {
                it++;
                pre[*it]=pre[x];
                modify_tr(1,1,n,*it,a[*it]);
            }
            mp[a[x]].erase(x);
            a[x]=y;
            it=mp[a[x]].lower_bound(x);
            if(it!=mp[a[x]].end())
            {
                pre[*it]=x;
                modify_tr(1,1,n,*it,a[*it]);
            }
            if(it==mp[a[x]].begin())pre[x]=-1;
            else
            {
                it--;
                pre[x]=*it;
            }
            mp[a[x]].insert(x);
            c[x]=abs(a[x+1]-a[x]);
            c[x-1]=abs(a[x]-a[x-1]);
            modify_tr(1,1,n,x,y);
            if(x<=n-1)modify_G(1,1,n-1,x);
            if(x-1)modify_G(1,1,n-1,x-1);
        }
        else if(op==2)
        {
            scanf("%d",&k);
            k^=cnt;
            if(work(x,y,k))
            {
                puts("Yes");
                cnt++;
            }
            else puts("No");
        }
    }
    return 0;
}

[T4]

原题

看样例我们猜答案似乎是2的整数次幂。

事实上也是。

事实上我们可以将二元组 (i,j) 视作一个点，然后用并查集进行合并。如果(i,j) 与 (j,i) 合并在了一起，就不合法。

至于答案，如果最后二元组被分为 k 个集合，答案就是 2^k。
CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=405;
typedef long long LL;
const LL mod=1e9+7;
LL res=1LL;
int n,m,st[N][N],par[N*N];
inline int get(int a,int b){return (a-1)*n+b;}
int find(int x)
{
    if(par[x]==x)return x;
    else return par[x]=find(par[x]);
}
void unite(int a,int b)
{
    a=find(a);
    b=find(b);
    if(a!=b)par[a]=b;
}
int main()
{
    scanf("%d",&n);
    m=n*(n-1)>>1;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        st[a][b]=st[b][a]=i;
    }
    for(int i=1;i<=n*n;i++)par[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                if(st[i][j]>st[i][k]&&st[i][j]>st[j][k])
                {
                    unite(get(i,k),get(j,k));
                    unite(get(k,i),get(k,j));
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(find(get(i,j))==find(get(j,i)))
            {
                puts("0");
                return 0;
            }
        }
    }
    set<int>S;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            int x=find(get(i,j)),y=find(get(j,i));
            if(S.find(x)==S.end())
            {
                S.insert(x);
                S.insert(y);
                res=(res<<1)%mod;
            }
        }
    }
    printf("%lld",res);
    return 0;
}
训练日志

发表回复