今天的考试题改自闭了……所以滚来写陈年题解。

A.贪婪

RT，出题人告诉我们这题要贪心。

最优的策略一定是拖到必须断的时候再断开(虽然并不知道为什么)。

如果一段序列满足题目中的性质，那么一定有$gcd(a_i-a_{i-1},a_{i+1}-a_i,...)$不为1且$a_i,a_{i+1},...$各不相同。所以维护每段的相邻两项差值的gcd，遇到不符合或者重复的元素就ans++。set写起来比较方便。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<set>

#include<cmath>

using namespace std;

const int N=;

int n,a[N],ans=;

set<int> b;

int gcd(int x,int y)

{

    if(!y)return x;

    return gcd(y,x%y);

}

int now;

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    b.insert(a[]);

    for(int i=;i<=n;i++)

    {

        now=gcd(now,abs(a[i]-a[i-]));

        if(now==||b.count(a[i]))

        {

            ans++;

            now=;

            b.clear();b.insert(a[i]);

        }

        else b.insert(a[i]);

    }

    cout<<ans<<endl;

    return ;

}

B.见证*****

RT,出题人让我们见证$n^2$过500000。

没有打std中的离线dfs序解法，直接用有向边代表包含关系，每次询问暴力dfs统计答案即可。注意K=1要特判建双向边。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

int n,m,cnt;

const int N=;//change it!

int head[N],nxt[N],to[N],tot,vis[N];

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

    while(isdigit(ch))x=x*+ch-'',ch=getchar();

    return x*f;

}

bool dfs(int x,int f,int aim)

{

    if(x==aim)return ;

    for(int i=head[x];i;i=nxt[i])

    {

        if(to[i]!=f)

            if(dfs(to[i],x,aim))return ;

    }

    return ;

}

int main()

{

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

    while(m--)

    {

        int opt=read();

        if(!opt)

        {

            int op=read(),K=read(),now=++cnt;

            if(K==)

            {

                int tmp=read();

                add(now,tmp);add(tmp,now);

            }

            else if(op==)

            {

                for(int i=;i<=K;i++)

                    add(now,read());

            }

            else if(op==)

            {

                for(int i=;i<=K;i++)

                    add(read(),now);

            }

        }

        else if(opt==)

        {

            int x=read(),y=read();

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

        }

    }

    return ;

}

C.堆积****

RT，出题人告诉我们要用到堆。

暴力dp的方程可以一眼切掉：$dp[i]=\min \limits _{j=max(0,i-K)}^{i-1} dp[j]+max(sum[i]-sum[j],b[j])$

对于所有j，$dp[j]+b[j]$和$dp[j]-sum[j]$都是定值

所以用两个堆，分别维护二者。要求的$dp[i]=min(heap1.top,heap2.top+sum[i])$

首先检查第一个栈，如果取出的j比i-K小，pop掉继续取。如果取出的比$dp[j]-sum[j]+sum[i]$小，把它加进第二个堆里，pop掉。

就这样取到合法的为止，第二个堆也是一样。

时间复杂度$O(nlogn)$

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

typedef long long ll;

#define pa pair<ll,int>

int n,K;

const int N=;

int a[N],b[N];

ll sum[N],dp[N];

priority_queue<pa,vector<pa>,greater<pa> >q1,q2;

int main()

{

    scanf("%d%d",&n,&K);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]),sum[i]=sum[i-]+1LL*a[i];

    for(int i=;i<n;i++)

        scanf("%d",&b[i]);

    memset(dp,0x3f,sizeof(dp));

    dp[]=;

    q1.push(make_pair(dp[]+1LL*b[],));

    for(int i=;i<=n;i++)

    {

        ll val1=0x7ffffffffff,val2=0x7ffffffffff;

        while(!q1.empty())

        {

            ll val=q1.top().first;int id=q1.top().second;

            if(id<i-K)

            {

                q1.pop();continue;

            }

            if(val<dp[id]-sum[id]+sum[i])

            {

                q2.push(make_pair(dp[id]-sum[id],id));q1.pop();

                continue;

            }

            val1=min(val1,val);

            break;

        }

        while(!q2.empty())

        {

            ll val=q2.top().first;

            int id=q2.top().second;

            if(id<i-K)

            {

                q2.pop();continue;

            }

            val2=min(val2,val);

            break;

        }

        dp[i]=min(val1,val2+sum[i]);

        //cout<<i<<' '<<dp[i]<<endl;

        q1.push(make_pair(dp[i]+b[i],i));

    }

    cout<<dp[n]<<endl;

    return ;

}

巴特西

[NOIP模拟26]题解

A.贪婪

B.见证*****

C.堆积****

最新文章

热门文章

巴特西

[NOIP模拟26]题解

A.*****贪婪*****

B.**见证*******

C.**堆积******

最新文章

热门文章

A.贪婪

B.见证*****

C.堆积****