慕容琳的后花园
慕容琳的后花园
hgoi#20191103

T1-繁繁的数字

问将一个数分解成多个 2 的幂次相加的形式有多少种方案

解法

简单dp,依次用1,2,4,8…去转移即可
复杂度是 n \log n

ac代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n,f[1000010];
int main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    scanf("%d",&n),f[0]=1;
    for(int i=0;;i++)
    {
        int k=(1<<i);
        if(k>n)break;
        for(int j=k;j<=n;j++)
            (f[j]+=f[j-k])%=mod;
    }
    printf("%d\n",f[n]);
    return 0;
}

T2-繁繁的游戏

你有一个简单的差分约束系统
在一幅无向图中要求每条边两端的点的权值差不超过d
问权值最大和权值最小的点的权值差是多少

解法

显然,最优的情况就是对于每个点跑最短路
找它最远的点,所有这些最远的点中距离最远的就是答案

ac代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
using namespace std;
vector<int>e[100];
queue<int>q;
int T,n,d,ans,dis[100];
char opt;
int main()
{
    freopen("bridge.in","r",stdin);
    freopen("bridge.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&d),ans=0;
        for(int i=1;i<=n;i++)
        {
            vector<int>().swap(e[i]);
            for(int j=1;j<=n;j++)
            {
                for(opt=getchar();opt!='N'&&opt!='Y';opt=getchar());
                if(opt=='Y')e[i].pb(j);
            }
        }
        for(int i=1;i<=n;i++)
        {
            memset(dis,0x3f,sizeof(dis));
            dis[i]=0,q.push(i);
            while(!q.empty())
            {
                int u=q.front();q.pop();
                for(auto v:e[u])
                    if(dis[v]==inf)
                        dis[v]=dis[u]+1,q.push(v);
            }
            for(int j=1;j<=n;j++)
                ans=max(ans,dis[j]);
        }
        if(ans==inf)puts("-1");
        else printf("%d\n",ans*d);
    }
    return 0;
}

T3-繁繁的队列

你有一个n的排列,每次你可以取一个数放到队首或队尾,问最少多少次操作可以将其变成升序

解法

我是不是在打假赛,这道题代码比T1还短emm
显然我们不用动的只有一个值连续的上升子序列
那么我们找出最长的值连续的上升子序列,其他的点都要进行一次操作

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,x,ans,f[50010];
int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&x),
        f[x]=f[x-1]+1,
        ans=max(ans,f[x]);
    printf("%d\n",n-ans);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191103
T1-繁繁的数字 问将一个数分解成多个 $ 2 $ 的幂次相加的形式有多少种方案 解法 简单dp,依次用1,2,4,8...去转移即可 复杂度是 $ n \log n $ 的 ac代码 #include<bits/stdc++.h&g…
扫描二维码继续阅读
2019-11-03
功能