hgoi#20190514

muronglin
muronglin 2019年05月14日
  • 在其它设备中阅读本文章

T1-Curriculum Vitae

给你一个长度为 n 的 01 序列 a,删去其中的几个数,使得序列中左边是连续的 0,右边是连续的 1,可以没有 0 或 1,求最多剩下几个数

解法

对于每个点看它左边几个 0,右边几个 1,弄个前缀和可以 O(n),虽然 n 方也能过 QAQ

ac 代码

#include<bits/stdc++.h> 
using namespace std;
int n,a[110],suml[110],sumr[110],ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)suml[i]=suml[i-1]+(a[i]==0);
    for(int i=n;i>=1;i--)sumr[i]=sumr[i+1]+(a[i]==1);
    for(int i=1;i<=n;i++)ans=max(ans,suml[i]+sumr[i]);
    printf("%dn",ans);
    return 0;
}

T2-Math Show

多鱼参加了一个数学节目。他被赋予 n 个任务,每个由 k 个子任务组成,编号为 1 到 k。这需要他用 t[i]分钟解决第 i 个子任务。多鱼可以按任何顺序解子任务。 通过解决任意人物的子任务,他得了一分。这样,任务的点数就等于其中解出的子任务的个数。此外,如果聚鱼完全解决了这个任务(解决了它所有的子任务),他会多得一分。这样,他所得到的任务完全解出的总点数为 k +1。 多鱼有 m 分钟的时间。他最多能挣多少分?

解法

本来想到背包,结果容量有 2e9,不太现实 n 和 k 很小,又因为每个子任务分值相同,设 dp[i]为做了 i 个完整的任务 (其余做的是单独子任务) 的最多分数 将 t 数组排序后暴力求解

ac 代码

#include<bits/stdc++.h> 
using namespace std;
int n,k,m,sum=0,ans=0,lim,s,a[50],dp[50];
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=k;i++)scanf("%d",&a[i]),sum+=a[i];
    sort(a+1,a+1+k);
    for(int i=0;i<=n;i++)
    {
        if(sum*i>m)break;
        dp[i]=ik+i,lim=n-i,s=sumi;
        for(int j=1;j<=k;j++)
        {
            for(int kk=1;kk<=lim;kk++)
                {s+=a[j];if(s>m)break;dp[i]++;}
            if(s>m)break;
        }
        ans=max(dp[i],ans);
    }
    printf("%dn",ans);
    return 0;
}

T3-Four Segments

给定长度为 n 的序列 a,求出三个点 i,j,k(0<=i<=j<=k<=n),使得 a[1]+...+a[i]-a[i+1]-...-a[j]+a[j+1]+...+a[k]-a[k+1]-...-a[n]最大

解法

如果暴力就是 n 的立方,无法接受啊 QAQ 想一想优化,对于每个点都可以 O(n)求出以它为 j 点的最优 i 点和 k 点,且 i 点和 k 点不相干 就可以优化成 n 方了

ac 代码

#include<bits/stdc++.h> 
using namespace std;
long long n,a[5010],l[5010],r[5010],sl,sr,suml,sumr,sum,ans=-23333333333333,res=0;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
    for(int i=0;i<=n;i++)
    {
        l[i]=0,r[i]=i;
        sl=0,sr=a[i];
        for(int j=1;j<=i;j++)
        {
            suml=a[j]-a[0],sumr=a[i]-a[j];
            if(suml-sumr>sl-sr)sl=suml,sr=sumr,l[i]=j;
        }
        sum=sl-sr;
        sl=0,sr=a[n]-a[i];
        for(int j=i+1;j<=n;j++)
        {
            suml=a[j]-a[i],sumr=a[n]-a[j];
            if(suml-sumr>sl-sr)sl=suml,sr=sumr,r[i]=j;
        }
        sum+=sl-sr;
        if(sum>ans)ans=sum,res=i;
    }
    printf("%lld %lld %lldn",l[res],res,r[res]);
    return 0;
}

T4-Monitor

有一个 n×m 的矩阵, 矩阵上的点会破碎,当有一个边长为 k 的正方形完全破碎时,整个矩阵就会破碎 现给出 q 个信息,x,y,t,表示 x 行 y 列会在 t 时破碎 求出整个矩阵什么时候会破碎,如果不会,输出 -1

解法

a[i][j] 表示 i 行 j 列破碎的时间,如果不会破碎,就是 inf 我们需要查询所有边长为 k 的正方形中最大值的最小值 暴力的话是 n^4,而可接受的是 n^3,想一想 可以预处理出 max[i][j]表示 i 行 j~j+k- 1 列中的最大值,就优化成 n^3 了

ac 代码

#include<bits/stdc++.h> 
using namespace std;
int n,m,k,q,x,y,t,s,ans=0x3f3f3f3f,a510,maxx510;
int main()
{
    memset(a,0x3f,sizeof(a)),memset(maxx,0,sizeof(maxx)),scanf("%d%d%d%d",&n,&m,&k,&q);
    for(int i=1;i<=q;i++)scanf("%d%d%d",&x,&y,&t),ax=t;
    for(int i=1;i<=n;i++)for(int j=1;j<=m-k+1;j++)
        for(int kk=0;kk<k;kk++)maxxi=max(maxxi,ai);
    for(int i=1;i<=n-k+1;i++)for(int j=1;j<=m-k+1;j++)
    {
        s=0;
        for(int kk=0;kk<k;kk++)s=max(s,maxxi+kk);
        ans=min(ans,s);
    }
    if(ans>1e9)puts("-1");
    else printf("%dn",ans);
    return 0;
}

T5-Chemistry in Berland

给定 2 个长度为 n 的序列 a,b,表示当前的材料数量和目标材料数量 给出 n - 1 组转换关系,Xi,Ki,表示 Ki 个 Xi 可以转换为 1 个 i 且 1 个 i 可以转换为 1 个 Xi 求是否能满足需求

解法

首先处理一下序列 a,b,让 a[i]-=b[i],目标就是使 a 序列变成非负序列 把转换关系看成代价为 k 的从 x 到 i 的边,然后就可以跑 dfs 了 QAQ 对于一个点,跑完了它的所有儿子之后,如果它已经满足,把多的给它爸 如果它不满足,就看它爸能不能转给他 优先转给它的一定是它儿子,因为它儿子转给它是 1 比 1,它爸转给它是 k 比 1 如果他爸不能转给它,就炸了 QWQ

tips: 乘起来会爆 long long(大雾

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define inf 23333333333333333
using namespace std;
struct node{ll to,next,w;}e[100010];
ll n,cnt=0,x,y,a[100010],head[100010];
double tmp;
void add(ll i){e[++cnt]={i,head[x],y},head[x]=cnt;}
void dfs(ll u,ll f,ll k)
{
    for(ll i=head[u];i;i=e[i].next)dfs(e[i].to,u,e[i].w);
    if(a[u]>=0)a[f]+=a[u];
    else
    {
        tmp=double(k)*double(a[u]);
        if(!f||tmp<-inf)puts("NO"),exit(0);
        a[f]+=k*a[u];
        if(a[f]<-inf)puts("NO"),exit(0);
    }
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++)scanf("%lld",&x),a[i]-=x;
    for(ll i=2;i<=n;i++)scanf("%lld%lld",&x,&y),add(i);
    dfs(1,0,0),puts("YES");
    return 0;
}

T6-Random Query

给定一个数列 A, 随机选取两个值 l,r(等概率, 可以相等), 进行以下操作: 1.if(l>r):swap(l,r) 2. 对数列 A 中 l,r 区间内的数去重得到数列 B 求数列 B 的期望大小。

解法

答案可以转化为总长度 / 序列总数 然后手推一下原始总长度的公式,n+2(2(n-1)+3(n-2)+...+n(n-(n-1))) 序列总数就是 n 方,之后看去重后的贡献,对于 a[i]和 a[j] (i<j),只有当它们相等时才有贡献 我们设定一个区间中去重时只留下最后一次出现的数,所以 a[i]会删去,a[j]会留下,而贡献是 i *(n-j+1),即左端点取在 i 左边,右端点取在 j 右边,此时 i 点已经不会对后面再出现的该数产生影响,所以只需要对最近的相等的数作处理即可

ac 代码

#include<bits/stdc++.h> 
using namespace std;
int n,a[1000010],last[1000010];
double ans,res;
int main()
{
    memset(last,0,sizeof(last)),scanf("%d",&n),ans=double(n),res=double(n)*double(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans+=double(n-i)double(i+1)2.0;
    for(int i=1;i<=n;i++)
        {if(last[a[i]])ans-=double(last[a[i]])double(n-i+1)2.0;last[a[i]]=i;}
    printf("%.6f",ans/res);
    return 0;
}