Educational Codeforces Round 112 (Rated for Div. 2)

A.PizzaForces

Difficulty\mathtt{Difficulty}=900\mathtt{900}
首先我们来枚举一下，得知：66 及以上的偶数都会刚好分完
而且每个披萨的性价比是一样的
那么，我们可以这样考虑：

  • 如果人数不多于 66 人，那么也要 1515 分钟
  • 如果人数多于 66 人且为偶数，那么肯定可以刚好吃完，没有多余
  • 如果人数多于 66 人且为奇数，那么一定会剩下一个人的量
    然后就不难写出代码了
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(void)
{
    register int Case;cin>>Case;while(Case--)
    {
        register int N;cin>>N;
        if(N<=6)cout<<15<<endl;
        else if(N&1)cout<<(N+1)/2*5<<endl;
        else cout<<N/2*5<<endl;
    }
    return 0;
}

B.Two Tables

Difficulty\mathtt{Difficulty}=1300\mathtt{1300}
肯定是横着平移或者竖着平移才有可能作为最短距离
不难发现，我们一定只能把它移到边界上
那么我们不妨枚举 44 条边，然后依次判是否可行
最后再取一下答案即可
然后就不难写出代码了

#include<bits/stdc++.h>
using namespace std;
int N,M,A,B,C,D,E,F,P,Q;
signed main(void)
{
    register int Case;cin>>Case;while(Case--)
    {
        cin>>N>>M>>A>>B>>C>>D>>E>>F;
        register int Ans=1000000000;
        P=abs(A-C),Q=abs(B-D);
        if(P+E<=N)Ans=min(Ans,min(max(0,E-N+max(A,C)),max(0,E-min(A,C))));
        if(Q+F<=M)Ans=min(Ans,min(max(0,F-M+max(B,D)),max(0,F-min(B,D))));
        if(Ans>=99999999)cout<<-1<<endl;
        else cout<<Ans<<".000000"<<endl;
    }
    return 0;
}

C.Coin Rows

Difficulty\mathtt{Difficulty}=1300\mathtt{1300}
看懂题目之后，我们来观察样例
我们提出一个猜想：Bob 只能先一直往右，再一直往下或是先一直往下，再一直往右
然后我们考虑分别用前缀和维护一下，不然会 TLE\texttt{TLE}
维护完之后，暴力枚举 Alice 的路线即可
然后就不难写出代码了

#include<bits/stdc++.h>
using namespace std;
#define int long long
int N;
int Dp1[100001],Dp2[100001];
signed main(void)
{
    register int Case;cin>>Case;while(Case--)
    {
        register int i;cin>>N;
        for(i=1;i<=N;i++)Dp1[i]=Dp2[i]=0;
        for(i=1;i<=N;i++){register int X;cin>>X;Dp1[i]=Dp1[i-1]+X;}
        for(i=1;i<=N;i++){register int X;cin>>X;Dp2[i]=Dp2[i-1]+X;}
        register int Ans;
        Ans=min(Dp1[N]-Dp1[1],Dp2[N-1]);
        for(i=2;i<N;i++)Ans=min(Ans,max(Dp1[N]-Dp1[i],Dp2[i-1]));
        if(N==1)Ans=0;
        cout<<Ans<<endl;
    }
    return 0;
}

D.Say No to Palindromes

Difficulty\mathtt{Difficulty}=1600\mathtt{1600}
这道题放在第四道，差评！
实际上，看懂题目之后，我们不难想到一个结论：

该字符串一定是 a,b,ca,b,c 的一个排列不断重复

然后我们干脆暴力枚举 66 种情况，但是我们会发现自己 TLE\texttt{TLE} 了
于是我们考虑加上一个前缀和维护，然后差分一把答案即可
然后就不难写出代码了

#include<bits/stdc++.h>
using namespace std;
int N,M;
string S,S0[7]={"","abc","acb","bac","bca","cab","cba"};
int Prefix[7][200011];
int main(void)
{
    register int i,j;cin>>N>>M;cin>>S;S="@"+S;
    for(i=1;i<=6;i++)
    {
        for(j=1;j<=N;j++)if(S0[i][(j-1)%3]!=S[j])Prefix[i][j]=Prefix[i][j-1]+1;
                         else Prefix[i][j]=Prefix[i][j-1];
    }
    while(M--)
    {
        register int Left,Right;cin>>Left>>Right;
        register int Ans=Right-Left+1;
        for(i=1;i<=6;i++)Ans=min(Ans,Prefix[i][Right]-Prefix[i][Left-1]);
        cout<<Ans<<endl;
    }
    return 0;
}

E.Boring Segments

Difficulty\mathtt{Difficulty}=2100\mathtt{2100}
题意是最小化最大值和最小值的差，不难想到 two-pointer\texttt{two-pointer}
枚举左端点，然后把上次的右端点继续向右移动即可
我们不妨使用线段树来维护这个区间
插入、删除就是在线段树 [l,r−1][l,r-1] 上加减，维护区间
时间复杂度 O(nlog⁡m)\mathcal{O(n\log m)}，想必是正解吧

#include<bits/stdc++.h>
using namespace std;
struct Struct
{
    int Left,Right,Value;
    inline bool operator <(const Struct &Compare)const
    {
        return Value<Compare.Value;
    }
};
struct Node
{
    int Tmp,Tag;
};
int N,M;
Struct S[1000010];
Node C[4000040];
inline void Pd(int Rt)
{
    if(C[Rt].Tag)
    {
        C[Rt*2].Tag+=C[Rt].Tag;
        C[Rt*2+1].Tag+=C[Rt].Tag;
        C[Rt*2].Tmp+=C[Rt].Tag;
        C[Rt*2+1].Tmp+=C[Rt].Tag;
    }
    C[Rt].Tag=0;
}
inline void Pu(int Rt)
{
    C[Rt].Tmp=min(C[Rt*2].Tmp,C[Rt*2+1].Tmp);
}
inline void Add(int Rt,int L,int R,int LL,int RR,int VV)
{
    if(L>=LL&&R<=RR){C[Rt].Tag+=VV,C[Rt].Tmp+=VV;return;}
    Pd(Rt);
    if((L+R>>1)>=LL)Add(Rt*2,L,(L+R>>1),LL,RR,VV);
    if((L+R>>1)<RR)Add(Rt*2+1,(L+R>>1)+1,R,LL,RR,VV);
    Pu(Rt);
}
int main(void)
{
    register int i,Cnt=0,Ans=INT_MAX,T=0;
    cin>>N>>M,M--;
    for(i=1;i<=N;i++)cin>>S[i].Left>>S[i].Right>>S[i].Value,S[i].Right--;
    sort(S+1,S+N+1);
    while(!C[1].Tmp)Cnt++,Add(1,1,M,S[Cnt].Left,S[Cnt].Right,1);
    Add(1,1,M,S[Cnt].Left,S[Cnt].Right,-1);
    for(i=Cnt;i<=N;i++)
    {
        Add(1,1,M,S[i].Left,S[i].Right,1);
        while(C[1].Tmp)T++,Add(1,1,M,S[T].Left,S[T].Right,-1);
        Add(1,1,M,S[T].Left,S[T].Right,1);
        Ans=min(Ans,S[i].Value-S[T].Value),T--;
    }
    cout<<Ans<<endl;
    return 0;
}