UOJ Logo xyleo的博客

博客

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

2018-10-29 14:11:33 By xyleo

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???

完结撒花!

评论

harryhe
前排膜拜rank1大佬xyleo
  • 2018-10-29 14:24:21
nickluo
我什么时候说过这些话了?!!!!!
  • 2018-10-29 14:27:36
RainAir
精神AK怕不是在嘲讽蒟蒻/kel /dk “只要dfs就好啦 似乎巨佬都成功避开了这种写法?”为什么是dfs啊qaq
  • 2018-10-29 14:43:33
siyuan
后排膜拜 rank 1 掉分大佬!
  • 2018-10-29 14:53:31
wph
xy稳啊xy阿克啊xy飞科啊xy集训队啊%%%%%%%%%%快快快快和我一起膜死她
  • 2018-10-29 16:06:41
lioutao
中排膜拜rank1大佬xyleo
  • 2018-10-31 13:09:33
harryhe
xyleoℵ 和 xyleo 分明是两个人!
  • 2018-11-07 19:21:20
Alpha
Orz xyleo!(自动一级标题)
  • 2019-04-20 19:55:05