HLOJ-DAY 1/2

Posted on By 张, 高畅 HLOJ-DAY 1/2无评论

[一些闲话]

HL好大好喜欢
直到进入机房……
我才知道
原来这把不是复活赛，不是复健赛，是淘汰赛
一晚上就出了一题
非常好的HLOJ，使我的大脑旋转

[T1]

题目
不是这题目真的挺误导人的。
其实也可以这么理解

[S_{a_i},E_{a_i}] 与 [S_{a_j},E_{a_j}] 是否相交记为 flag1
[S_{b_i},E_{b_i}] 与 [S_{b_j},E_{b_j}] 是否相交记为 flag2
你只需要判断，对于所有 (i,j) (i<j) ，

是否都有 flag1+flag2 \neq 1

是则为 YES，不是则为 NO

接下来，您可以轻而易举的写出这样一个 O(n^2) 的暴力算法
其实就是模拟上面的过程

#include
using namespace std;
const int N=100005;
int n;
#define S first
#define E second
pairA[N],B[N];
int cross(int a,int b,int c,int d){return max(a,c)<=min(b,d);}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d%d",&A[i].S,&A[i].E,&B[i].S,&B[i].E);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(cross(A[i].S,A[i].E,A[j].S,A[j].E)+cross(B[i].S,B[i].E,B[j].S,B[j].E)==1)
            {
                puts("NO");
                return 0;
            }
        }
    }
    puts("YES");
    return 0;
}

但是很显然，时间复杂度并不符合题目的要求。
现在我们换一种思路来看这个问题。
我们把A会场的所有会议时间段都用类似差分的方法来看待。
然后把所有时间点进行排序。
在处理 $S_{ai}的时候，我们将[S{bi},E{bi}]$ 扔入 multiset 里面。
而在处理 $E{ai}+1的时候，我们将[S{bi},E{bi}]$ 从 multiset 中删除。
至于判断是否合法，只需要在插入前判断当前 $[S{bi},E{bi}]$ 区间与 multiset 内部的区间是否存在区间是不交的，如果不交，答案就是 NO。
然后 A 与 B 进行交换，再做一次上述操作就可以了。
接下来我们感性理解一下为什么判断合法的步骤是正确的。
我们定义： A区间 为 $[S{ai},E{ai}]$， B区间为 $[S{bj},E{bj}]$ ，A区间对应的B区间 即为 $[S{ai},E{ai}]对应的区间[S{bi},E{b_i}]$。
因为 multiset 里面存在的 任意一个B区间 所对应的A区间 一定是 与当前的A区间是相交的（因为我们已经保证每一个插入/删除的时间点是有序的），所以 如果出现当前的B区间 与 multiset 内部的区间 有不交的，那么就满足题目 NO 的条件。
很显然，用 multiset 查找维护需要 O(\log n) 的时间，进行循环需要 O(n) 的时间，排序也需要 O(n \log n) 的时间，所以总时间是 O(n\log n) 的。
还有一些小细节：
1.为了维护方便，事实上可以采用两个multiset 分别维护 S 与 E 。
2.multiset 自带的 S.find(...) 是 O(\log n) 的，但是 find(S.begin(),S.end(),...) 是 O(n) 的，这点在 OI-WIKI 上也有提过。
CODE:

#include
using namespace std;
const int N=100005;
typedef pair PII;
int n;
PII a[N],b[N];
#define S first
#define E second
int PP(paira[],pairb[])
{
    multisetStart,End;
    vector<pair >V;
    for(int i=1;i<=n;i++)
    {
        V.push_back({{a[i].S,1},{b[i].S,b[i].E,}});
        V.push_back({{a[i].E+1,-1},{b[i].S,b[i].E}});
    }
    sort(V.begin(),V.end());
    for(auto i:V)
    {
        PII s=i.first,t=i.second;
        if(s.second==1)
        {
            if(Start.size()&&End.size())
            {
                if(t.E<*--Start.end()||*End.begin()<t.S)return 0;
            }
            Start.insert(t.S);
            End.insert(t.E);
        }
        else
        {
            Start.erase(Start.find(t.S));
            End.erase(End.find(t.E));
        }
    }
    return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a[i].S,&a[i].E,&b[i].S,&b[i].E);
    }
    puts(PP(a,b)&&PP(b,a)?"YES":"NO");
    return 0;
}

[T2]

原题
这是一个字符串题（挠头
首先考虑若前 i 位都一样，但 s_{i+1} i+1 ，前 i 位所需的代价可以完全继承，再计算上面所述的就可以了。
需要注意的是移动时，整体的下标可能会+1，可以考虑用树状数组维护。
注意开启 long long
时间复杂度 O(n \log n)
CODE:

#include
using namespace std;
const int N=2e5+5;
typedef long long LL;
int n;
char s[N],t[N];
int tr[N];
int lowbit(int x){return x&(-x);}
void add(int x,int v){for(;x<=n;x+=lowbit(x))tr[x]+=v;}
int query(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))res+=tr[x];
    return res; 
}
int move(int x,int y)
{
    y=query(y);
    return y-x;
}
void work()
{
    memset(tr,0,sizeof tr);
    vectorpos[30];
    scanf("%d%s%s",&n,s+1,t+1);
    for(int i=1;i<=n;i++)
    {
        pos[s[i]-'a'].push_back(i);
        add(i,1);
    }
    for(int i=0;i<26;i++)reverse(pos[i].begin(),pos[i].end());
    LL res=1e18,ans=0;
    for(int i=1;i<=n;i++)
    {
        int P=n+1;
        for(int j=0;j<t[i]-'a';j++)
        {
            if(pos[j].size())P=min(P,pos[j].back());
        }
        if(P!=n+1)res=min(res,ans+query(P-1));
        if(!pos[t[i]-'a'].size())break;
        P=pos[t[i]-'a'].back(); 
        pos[t[i]-'a'].pop_back();
        ans+=query(P-1);
        add(P,-1);
    }
    printf("%lld\n",(res==1e18)?-1:res);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

[T5]

原题
以调的时间来说，这哪是生日礼物，明明是祭日礼物。
发现如果相邻的两个数符号是一样的，就可以合并。
最后会出现一个形如 +-+-+...-+ 的一个序列。
如果序列中 + 的个数小于等于 m ，显然答案就是所有正数之和。
但如果大于，我们就每次选择绝对值最小的，将其与旁边的合并（反悔贪心），并删除旁边的两个数。
这个东西使用优先队列+双向链表维护。
注意如果选出了 - ，要判断是否处于边界，若处于边界，直接舍弃。
时间复杂度 O(n \log n)
CODE:

#include
using namespace std;
const int N=1e5+5;
typedef long long LL;
typedef pair PII;
int n,m,cnt;
priority_queue<PII,vector,greater >q;
int pre[N],nex[N],st[N],tt=0;
int V[N],res;
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(!x)continue;
        if(!tt||1LL*V[tt]*x<0)V[++tt]=x;
        else V[tt]+=x;
    }
    for(int i=1;i0)
        {
            res+=V[i];
            cnt++;
        }
    }
}
void CUT(int u)
{
    int s=pre[u],t=nex[u];
    st[u]=1;
    nex[s]=t;
    pre[t]=s;
}
int main()
{
    init();
    while(cnt>m)
    {
        PII u=q.top();
        q.pop();
        int id=u.second;
        if(st[id])continue;
        if((!pre[id]||nex[id]==tt+1)&&V[id]<0)
        {
            CUT(id);
            continue;
        }
        res-=abs(V[id]);
        cnt--;
        V[id]+=V[pre[id]]+V[nex[id]];
        q.push({abs(V[id]),id});
        CUT(pre[id]);
        CUT(nex[id]);
    }
    printf("%lld",res);
    return 0;
}

[T6]

原题
罕见的做过的原题。
三个队列维护我至今记忆犹新。
注意数据加强之后好像不能使用 floor() 来向下取整。
CODE:

#include
using namespace std;
typedef long long LL;
const int N=100005,M=7*1e6+3,INF=1e9;
int n,m,add,pu,pv,ti;
LL q[4][M];
int hh[4]={0},tt[4]={0};
LL get_max()
{
    pairres={-1,-1};
    for(int i=1;ires.first))res={q[i][hh[i]],i};
        }
    }
    if(res.second==-1)return INF;
    if(hh[res.second]==M)hh[res.second]=0;
    hh[res.second]++;
    return res.first;
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&add,&pu,&pv,&ti);
    while(n--)
    {
        LL x;
        scanf("%lld",&x);
        q[1][tt[1]++]=x;
    }
    sort(q[1],q[1]+tt[1]);
    reverse(q[1],q[1]+tt[1]);
    for(int i=0;i<m;i++)
    {
        LL x=get_max()+i*add;
        if((i+1)%ti==0)printf("%lld ",x);
        LL FIR=pu*x/pv;
        LL SEC=x-FIR;
        if(tt[2]==M)tt[2]=0;
        if(tt[3]==M)tt[3]=0;
        q[2][tt[2]++]=FIR-(LL)(i+1)*(LL)add;
        q[3][tt[3]++]=SEC-(LL)(i+1)*(LL)add;
    }
    puts("");
    for(int cnt=1;;cnt++)
    {
        LL p=get_max();
        if(p==INF)break;
        if(cnt%ti==0)printf("%lld ",p+m*add);
    }
    return 0;
}

[最后的话]

最恐怖的是，写到这里发现还有5题没动，1题WA。
明天还有模拟赛。
非常好的HLOJ，使我身心俱疲。

训练日志

发表回复