8.19 NOIP模拟测试26(B) 嚎叫响彻在贪婪的厂房+主仆见证了 Hobo 的离别+征途堆积出友情的永恒

T1 嚎叫响彻在贪婪的厂房

以前做过一个等比数列的题「序列」，这个类似

是等差数列且公差不为1的条件就是各项差的绝对值的$gcd！=1$，每次拿出序列前两个数，求出差值，插入到set里，每次向后扩展，如果该数出现过或与前面的公差的$gcd==1$，更新答案和序列起点，进行下一轮;否则插入到$set$中，记得清空

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<cmath>

#define ll long long

using namespace std;

ll n,a[],st,ans;

set<ll>s;

ll read()

{

    ll aa=,bb=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}

    while(cc>=''&&cc<=''){aa=(aa<<)+(aa<<)+(cc^'');cc=getchar();}

    return aa*bb;

}

ll gcd(ll a,ll b)

{

    if(b==) return a;

    return gcd(b,a%b);

}

int main()

{

    n=read();

    for(ll i=;i<=n;i++) a[i]=read();

    ll st=;

    while(st<=n){

        if(st==n){

            ans++;

            break;

        }

        ll d=abs(a[st+]-a[st]);

        if(d==||d==){

            ans++;

            st++;

            continue;

        }

        s.insert(a[st]);s.insert(a[st+]);

        ll i;

        for(i=st+;i<=n;i++){

            if(s.find(a[i])!=s.end()) break;

            d=gcd(d,abs(a[i]-*s.begin()));

            if(d==) break;

            s.insert(a[i]);

        }

        st=i;

        ans++;

        s.clear();

    }

    printf("%lld\n",ans);

    return ;

}

嚎叫响彻在贪婪的厂房

T2 主仆见证了 Hobo 的离别

建边，数据较水，暴力跑$dfs$就能过

如果是交集，就将合并的点向新点连边，并集就将新点向合并的点连边，$k==1$的情况交集和并集是一样的，所以建双向边。

最后的查询就是问$x$是否是$y$的一个子集，也就是从$y$出发能否找到$x$，这样建边就保证了从当前点出发，能到达的点都是自己能包含的

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

struct node

{

    int to,nxt;

}h[];

int n,m,nn,num,a[],tot,nxt[],son;

int read()

{

    int aa=,bb=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}

    while(cc>=''&&cc<=''){aa=(aa<<)+(aa<<)+(cc^'');cc=getchar();}

    return aa*bb;

}

void add(int x,int y)

{

    h[++tot].to=y;

    h[tot].nxt=nxt[x];

    nxt[x]=tot;

}

bool dfs(int x,int fa)

{

    if(x==son) return true;

    for(int i=nxt[x];i;i=h[i].nxt){

        int y=h[i].to;

        if(y==fa) continue;

        if(dfs(y,x)) return true;

    }

    return false;

}

int main()

{

    n=read();m=read();nn=n;

    int tpy,op,k,a,x,y;

    for(int i=;i<=m;i++){

        tpy=read();

        if(!tpy){

            op=read();k=read();nn++;

            if(!op){

                for(int i=;i<=k;i++){

                    x=read();

                    add(x,nn);

                    if(k==) add(nn,x);

                }

            }

            else{

                for(int i=;i<=k;i++){

                    x=read();

                    add(nn,x);

                    if(k==) add(x,nn);

                }

            }

        }

        else{

            son=read();y=read();

            printf("%d\n",dfs(y,));

        }

    }

    return ;

}

主仆见证了 Hobo 的离别

T3 征途堆积出友情的永恒

暴力建边跑$spfa$可以得到50分，加一手特判就能拿到80分的好成绩。

$f[i]$表示到i点的最小费用，$s[i]$表示$a[i]$的前缀和，转移很简单 $f[i]=min{f[j]+max(b[j],s[i]-s[j])}$ 复杂度n²显然抗不住

考虑优化，发现$f[j]+s[i]-s[j]$是单调递增的，$f[j]+b[j]$是一个定值，每次找可行范围内的最小值就行，考虑用两个小根堆维护

一个维护$f[j]+b[j]$，一个维护$f[j]-s[j]$

每次更新$f[i]$的时候找到距离不超过k的且最小的，$f[i]=min(第一个堆的堆顶，第二个堆的堆顶+s[i])$

距离不超过$k$就每次取堆顶，如果$id<i-k$就把他$pop$出去，直到找到合法的

如果第一个堆的堆顶$<f[j]+s[i]-s[j]$（答案不会是他，因为费用是要找路费和税中较大的）就$pop$出来，并把j插入到第二个堆里（税已经小于当前路程了，那么这个点以后对答案的贡献只可能是路径费用而不是税）

每次都将走过的点$i$的$f[i]+b[i]$插入到第一个堆里

注意最大值要开大一点。。。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define ll long long

using namespace std;

ll n,m,a[],b[],s[],f[];

priority_queue< pair<ll,ll> ,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q,qq;

ll read()

{

    ll aa=,bb=;char cc=getchar();

    while(cc>''||cc<''){if(cc=='-') bb=-;cc=getchar();}

    while(cc>=''&&cc<=''){aa=(aa<<)+(aa<<)+(cc^'');cc=getchar();}

    return aa*bb;

}

int main()

{

    n=read();m=read();

    for(ll i=;i<=n;i++) a[i]=read(),s[i]=s[i-]+a[i];

    for(ll i=;i<n;i++) b[i]=read();

    f[]=;

    for(ll i=;i<=n;i++){

        q.push(make_pair(f[i-]+b[i-],i-));

        ll ans=0x7fffffffffffff;

        while(q.size()&&q.top().second<i-m) q.pop();

        while(qq.size()&&qq.top().second<i-m) qq.pop();

        while(q.size()&&q.top().first<f[q.top().second]+s[i]-s[q.top().second]){

            qq.push(make_pair(f[q.top().second]-s[q.top().second],q.top().second));

            q.pop();

        }

        while(q.size()&&q.top().second<i-m) q.pop();

        while(qq.size()&&qq.top().second<i-m) qq.pop();

        if(q.size()) ans=min(ans,q.top().first);

        if(qq.size()) ans=min(ans,qq.top().first+s[i]);

        f[i]=ans;

    }

    printf("%lld\n",f[n]);

    return ;

}

征途堆积出友情的永恒

巴特西

8.19 NOIP模拟测试26(B) 嚎叫响彻在贪婪的厂房+主仆见证了 Hobo 的离别+征途堆积出友情的永恒

最新文章

热门文章