• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2020沈阳区域赛补题&总结

admin

11月 28, 2021

7月18号的比赛,一直拖着没补。想想就这样放着不太行,还是开个坑慢慢填吧

考前一个月备战期末没摸acm,最后rank85/265,罚时卡出ag线,大概就是报应吧。

D. Journey to Un’Goro

传送门

构造。

很关键的一个想法:令(p_i)表示从(1)(i)位置中(r)数量的奇偶性,(i)(j)(r)的数量为奇数的条件便是(p_{i-1},p_j)不同。(特别地,(p_0)为偶)

那么对于(n)的一种构造方式,考虑有(x)个奇数点,(n+1-x)个偶数点,那么题中要求的((i,j))对数就是(x*(n-x+1))。均值不等式,想要最大化合法对数就是使得奇偶点数为(lceilfrac{n+1}{2}ceil)(lfloorfrac{n+1}{2}floor)(谁大谁小都行),然后就排列就是了。由于从第(0)位开始且该位确定是偶,所以排列确定,你的(br)序列也就定了。排列中当前位与前一位不同,这一位就是(r),反之是(b)

那么dfs就行了,贪心从前往后做一位一位的做,在满足奇偶点的数量约束的前提下((lceilfrac{n+1}{2}ceil)),优先保证当前位与前一位奇偶相同(也就是填(b)),搜到了100个答案就直接终止。

#include<bits/stdc++.h>
using namespace std;
int n,tot=0;
int ans[100005],num[2];
void dfs(int len)
{
    if(tot>=100)
        return;
    if(len>n)
    {
        for(int i=1;i<=n;i++)
        {
            if(ans[i]==ans[i-1])
                printf("b");
            else
                printf("r");
        }
        tot++;
        if(tot>=100)
            exit(0);
        printf("
");
        return;
    }
    int p=ans[len-1];
    if(num[p]<n/2+1)
    {
        num[p]++;
        ans[len]=p;
        dfs(len+1);
        num[p]--;
    }
    p=p^1;
    if(num[p]<n/2+1)
    {
        num[p]++;
        ans[len]=p;
        dfs(len+1);
        num[p]--;
    }
}
int main()
{
    scanf("%d",&n);
    long long p=n;
    ans[0]=0;
    num[0]=1;
    num[1]=0;
    printf("%lld
",(p+1ll)/2ll*(p/2ll+1ll));
    dfs(1);
    return 0;
}

H. The Boomsday Project

传送门
先考虑怎么暴力

显然你一定是把一张优惠卡用到不能用了(时间限制或次数限制)

将每次租车按时间排序,(dp[i])表示恰好处理完前(i)次租车的最小花费,(f[i][j])表示在第(i)次用第(j)张卡,能覆盖到的最后租车是那次,(f)数组可以二分查找来得出

转移:

[dp[i+f[i+1][j]]=max(dp[i]+c,dp[i+f[i+1][j]])
]

[dp[i+1]=max(dp[i+1],dp[i]+r)
]

再考虑怎么优化掉这个(log)

注意到(f)数组具有单调性:

[f[i+1][j]>=f[i][j]
]

事实上我们每次算(f[i][j])时,只需要从(f[i-1][j])开始递推,一个一个地往后挪即可

特别地,为了防止MLE,f数组需要使用滚动数组

#include<bits/stdc++.h>
using namespace std;
int n,m,r,p,q,cnt=0;
int d[505],k[505],c[505],rt[300005],f[2][505];
long long dp[300005];
int main()
{
    memset(f,0,sizeof(f));
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&d[i],&k[i],&c[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&p,&q);
        for(int j=cnt+1;j<=cnt+q;j++)
        {
            rt[j]=p;
            dp[j]=1e18;
        }
        cnt+=q;
    }
    sort(rt+1,rt+1+cnt);
    dp[0]=0;
    rt[0]=0;
    for(int i=0;i<=cnt-1;i++)
    {
        dp[i+1]=min(dp[i+1],dp[i]+1ll*r);
        for(int j=1;j<=n;j++)
        {
            for(int l=f[0][j];l<=cnt;l++)
            {
                if(l-i<=k[j]&&rt[l]-rt[i+1]<=d[j]-1)
                    f[1][j]=l;
                else
                    break;
            }
            f[0][j]=f[1][j];
            dp[f[0][j]]=min(dp[i]+1ll*c[j],dp[f[0][j]]);
            //printf("%d %d %d %lld %lld
",i,j,f[0][j],dp[i],dp[i+f[0][j]]);
        }
    }
    printf("%lld",dp[cnt]);
    return 0;
}
小鳥の翼がついに大きくなって ,
旅立ちの日だよ ,
遠くへと広がる海の色暖かく ,
夢の中で描いた絵のようなんだ ,
切なくて時をまきもどしてみるかい ?
No no no いまが最高!
だってだって、いまが最高!

发表回复

您的电子邮箱地址不会被公开。