正睿OI联赛停课训练day11翻车记

day11真难难啊但楼下那位精神ak了

线段树什么的最讨厌了

T1 打暴力发现每翻上一层有4种情况 [l,r+len],[l-len,r],[l-len-1,r],[l,r+len-1]

暴力开心O(4^logn)感觉凉凉了？没事我们还可以瞎剪枝

注意区间越小复杂度越大，[x,x]会TLE要特判蒟蒻当场竟然以为长度最小的是[x,x+1]

所幸，正睿良心，给小蒟蒻70分的好成绩！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ans,lim;
void dfs(ll l,ll r)
{
    if(r>lim||r>ans)return;
    if(l==0){ans=r;return;}
    int len=r-l+1;
    if(r+len<=lim&&l>=2*len)dfs(l,r+len);
    if(l==len||l-len>=2*len)dfs(l-len,r);
    if(r+len+1<=lim&&l>=2*len-1)dfs(l,r+len-1);
    if(l-len-1==0||l-len-1>=2*len+1)dfs(l-len-1,r);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        ll l,r;scanf("%lld%lld%lld",&l,&r,&lim);ans=1e12;
        if(l==r){printf("%d\n",r);continue;}
        dfs(l,r);
        if(ans>lim)puts("-1");else printf("%d\n",ans);
    }
    return 0;
}

已经没有什么好害怕的了

考虑到合法的括号序列[l,r]会对这个区间的每一个的贡献增加1，似乎差分一下就可以了？

因为以前见过就直接瞎码的蒟蒻膜死了RainAir的blog，嗯真香

码着的时候发现此题取模有点怪？似乎可以坑死一波大佬

要不要在群里吐槽呢？算了吧(不然rank1就没了，然后成功直播掉分)

其实有另一种简单好想的思路需要注意到括号序列的树形结构

合法子串要么是同级要么是父亲的合法子串

ansx=ansfax+lxrx (lx表示同级在左边的数目，rx表示同级在右边的数目）

只要dfs就好啦似乎巨佬都成功避开了这种写法？

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e6+10;
const LL mod=1e9+7;
int n,a[N],l[N],r[N],stk[N],rr[N],ll[N];
char ch[N];
LL ans[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%s",ch+1);n=strlen(ch+1);
        memset(stk,0,sizeof(stk));memset(ll,0,sizeof(ll));memset(rr,0,sizeof(rr));
        memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(ans,0,sizeof(ans));
        int top=0;LL res=0;
        for(int i=1;i<=n;i++)if(ch[i]=='(')stk[++top]=i;else if(top)rr[stk[top]]=i+1,ll[i+1]=stk[top--];
        for(int i=n+1;i>=1;i--){r[i]++;r[ll[i]]+=r[i];}
        for(int i=1;i<=n;i++){l[i]--;l[rr[i]]+=l[i];}
        for(int i=1;i<=n;i++)ans[i]=ans[i-1]+r[i]+l[i];
        for(int i=1;i<=n;i++)res+=1ll*i*ans[i]%mod;
        printf("%lld\n",res);
    }
    return 0;
}

我才不是萝莉控呢

O($n^2$)的dp好像是送的啊

为了小常数，发现达不到(1,1)的状态都无用

考虑反过来dp，只会用到有影响的状态？

但实际上反过来后，容易发现dp在做一下这种事：

1.用掉当前的一个空间

2.在下一层开双倍大小的空间

最后要最小化所有点权值和深度乘积的总和

发现所求的好像和哈夫曼树很像开双倍大小的空间就可以理解为二叉树了

最后一个问题：为什么开2x大小的空间，不开2x-1大小的空间呢

似乎挺简单的手画一下脑补一下那不是最优解就好啦！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,a[N];
priority_queue<ll>q;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        while(!q.empty())q.pop();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),q.push(-a[i]);
        ll ans=0;
        for(int i=1;i<n;i++)
        {
            ll a=q.top();q.pop();
            ll b=q.top();q.pop();
            q.push(a+b);ans-=a+b;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

代码总行数77行，给不毒瘤的正睿点赞！

被懒得打的nickluo神犇嘲讽了：77行你还写了2.5h???

完结撒花！

xyleo的博客

博客

评论