[CodeVS 1217]借教室

很容易想到线段树水过。

很可惜,这样估计也就70分。

然后这个问题是符合单调性的……可以二分答案哒。不过怎么判定?

不知道诸位还记得差分序列?记得就好,用差分序列的方法维护即可。

等等,我怎么感觉你这个做法是[tex]O(nlogn)[/tex]的,能过?

推荐一个行之有效的优化:注意一下每一次修改都是在之前的基础上反悔或前进几次,所以就可以直接在原基础上修改差分序列辣~这样效率是很高滴~

代码:

#include <cstdio>
const int maxn=1e6+5;
typedef long long ll;
ll A[maxn];
int l[maxn],r[maxn];
ll d[maxn];
ll C[maxn];
int n,m,last=0;
bool Check(int x){
    register int i,cnt=0;
    if(x>last)
        for(i=last+1;i<=x;i++){
            C[l[i]]+=d[i];
            C[r[i]+1]-=d[i];
        }
    if(x<last)
        for(i=x+1;i<=last;i++){
            C[l[i]]-=d[i];
            C[r[i]+1]+=d[i];
        }
    last=x;
    for(i=1;i<=n;i++){
        cnt+=C[i];
        if(cnt>A[i])
            return false;
    }
    return true;
}

int main(){
    register int i,L,M,R;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
    }
    for(i=1;i<=m;i++){
        scanf("%lld%d%d",&d[i],&l[i],&r[i]);
    }
    L=1;
    R=m+1;
    while(L<R){
        M=L+(R-L)/2;
        if(Check(M)){
            L=M+1;
        }else{
            R=M;
        }
    }
    if(L==m+1)
        puts("0");
    else
        printf("-1\n%d\n",L);
    return 0;
}

[BZOJ 4326]运输计划

很容易想到树剖直接搞一发的玩法。估计复杂度是[tex]O(nlog^2n)[/tex]的,有点吃不消,再加上会被卡常,咔嚓掉。

考虑二分答案。我们可以直接二分最终答案,那么如何验证?

假设验证谓词为[tex]C(t)[/tex],表示通过把一条边清零可以使得用时为[tex]t[/tex]。那么所有用时大于[tex]t[/tex]的计划都要被清掉一条边。可见我们需要清零的边是所有用时大于[tex]t[/tex]的计划的边的交集中的最大边。

那么如何求交集呢?可以考虑树上差分,对于每次计划[tex](u,v)[/tex],我们求出其最近公共祖先[tex]L[/tex],然后对[tex]d[u][/tex]和[tex]d[v][/tex]分别加一,对[tex]d[L][/tex]则减二。随后将d上标记上推,可以求出每个点连向父亲的边被几个计划经过。易求交集。

至此方向已明确:二分答案,树上差分验证,同时我们还要用到LCA。LCA建议使用总计[tex]O(n)[/tex]的TarjanLCA离线算法,倍增也可。

代码:

/**************************************************************
    Problem: 4326
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4756 ms
    Memory:62188 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=300001,maxm=300001*2;
const int BUFSIZE=10000001;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
 
int n;
namespace FastIO{
    char buf[BUFSIZE];
    int IO_tot=0;
    inline void InitFastIO(){
        fread(buf,sizeof(char),BUFSIZE-1,stdin);
    }
    inline char GetC(){
        return buf[IO_tot++];
    }
    inline int readint(){
        register int x=0;
        register char c=GetC();
        while(!isdigit(c))
            c=GetC();
        while(isdigit(c)){
            x=10*x+c-'0';
            c=GetC();
        }
        return x;
    }
    int bf[10];
    inline void putint(int x){
        register int siz=0,i;
        if(!x){
            bf[siz++]=0;
        }else{
            while(x){
                bf[siz++]=x%10;
                x/=10;
            }
        }
        for(i=siz-1;i>=0;i--)
            putchar(bf[i]+'0');
        putchar('\n');
    }
};
namespace Tree{
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void Add_Edge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    int d[maxn],father[maxn];
    vector<int> hx;
    void dfs_1(int x,int fa,int dis){
        d[x]=dis;
        father[x]=fa;
        int i;
        GRAPH_REP(i,x){
            if(to[i]!=fa)
                dfs_1(to[i],x,dis+dist[i]);
        }
        hx.push_back(x);
    }
    int lazy[maxn];
    inline void ClearLazy(){
        memset(lazy,0,sizeof(lazy));
    }
    inline int DealCheck(int x){
        register int i,v,ans=0;
        REP_B(i,n){
            v=hx[i-1];
            lazy[father[v]]+=lazy[v];
        }
        REP_B(i,n){
            if(lazy[i]==x){
                ans=max(ans,d[i]-d[father[i]]);
            }
        }
        return ans;
    }
     
    // Djoin Set
    int p[maxn];
    int find_set(int x){
        if(p[x]==x)
            return x;
        else
            return p[x]=find_set(p[x]);
    }
    inline void union_set(int x,int y){
        p[find_set(y)]=find_set(x);
    }
    inline void make_set(int x){
        p[x]=x;
    }
     
    // LCA
    struct Query{
        int u,v,b;
    };
    bool vis[maxn];
    vector<Query> qs;
    vector<int> querys[maxn];
    inline void Add_Query(int x,int y,int b){
        querys[x].push_back(qs.size());
        qs.push_back((Query){x,y,b});
    }
    int res[maxn][3];
    int n;
    void LCA(int u){
        make_set(u);
        vis[u]=true;
        int i,temp;
        REP(i,querys[u].size()){
            Query& tep=qs[querys[u][i]];
            if(vis[tep.v])
                res[tep.b][2]=find_set(tep.v);
        }
        for(i=first[u];i;i=next[i]){
            temp=to[i];
            if(!vis[temp]){
                LCA(temp);
                union_set(u,temp);
            }
        }
    }
};
 
using namespace FastIO;
struct Deal{
    int u,v,lca,d;
    bool operator <(const Deal& x) const{
        return d<x.d;
    }
};
vector<Deal> V;
int m;
inline bool Check(int x){
    register int i,ideal=0,yh=V[m-1].d;
    Tree::ClearLazy();
    for(i=m-1;i>=0;i--){
        int& u=V[i].u,v=V[i].v,lca=V[i].lca,d=V[i].d;
        if(d>x){
            ideal++;
            Tree::lazy[u]++;
            Tree::lazy[v]++;
            Tree::lazy[lca]-=2;
        }else{
            break;
        }
    }
    yh-=Tree::DealCheck(ideal);
    return yh<=x;
}
int main(){
    register int i,u,v,lca,d;
    FastIO::InitFastIO();
    n=readint();
    m=readint();
    REP(i,n-1){
        u=readint();
        v=readint();
        d=readint();
        Tree::Add_Edge(u,v,d);
        Tree::Add_Edge(v,u,d);
    }
    REP(i,m){
        u=readint();
        v=readint();
        Tree::Add_Query(u,v,i);
        Tree::Add_Query(v,u,i);
        Tree::res[i][0]=u;
        Tree::res[i][1]=v;
    }
    Tree::dfs_1(1,0,0);
    Tree::LCA(1);
    REP(i,m){
        u=Tree::res[i][0];
        v=Tree::res[i][1];
        lca=Tree::res[i][2];
        d=Tree::d[u]+Tree::d[v]-2*Tree::d[lca];
        V.push_back((Deal){u,v,lca,d});
    }
    sort(V.begin(),V.end());
    u=0;
    v=V[m-1].d+1;
    while(u<v){
        d=u+(v-u)/2;
        if(Check(d))
            v=d;
        else
            u=d+1;
    }
    putint(u);
    return 0;
}

[洛谷 P2679]子串

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}

[BZOJ 4325]斗地主

是的你没有看错!就是这道坑提!

这题基本是个半成品,歧义真的,真的,真的很大。

至于方法?我们注意到同样的牌能一起出就尽可能避免拆开。例如,四带二分成炸弹加两单点(对子)肯定不好。三带一或者三带二也如此。先考虑不出顺子的最优解,并据此进行深度限制,再考虑出顺子。

然后,DFS暴搜即可。

顺便讲一下坑点:

  1. 顺子可以有A。
  2. 三带一,三带二,四代二都可以有头。但是大小头要区别开。

代码:

/**************************************************************
    Problem: 4325
    User: danihao123
    Language: C++
    Result: Accepted
    Time:24 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int ans;
int cnt[5],hand[15];
void dfs(int x){
    if(x>ans)
        return;
    int i,j,rest=0;
    memset(cnt,0,sizeof(cnt));
    for(i=0;i<=14;i++){
        cnt[hand[i]]++;
    }
    while(cnt[4]>0){
        cnt[4]--;
        rest++;
        if(cnt[2]>=2)
            cnt[2]-=2;
        else
            if(cnt[1]>=2)
                cnt[1]-=2;
    }
    while(cnt[3]>0){
        cnt[3]--;
        rest++;
        if(cnt[2]>0)
            cnt[2]--;
        else
            if(cnt[1]>0)
                cnt[1]--;
    }
    if(hand[0] && hand[1] && cnt[1]>=2)
        rest--;
    ans=min(ans,cnt[1]+cnt[2]+rest+x);
    for(i=3;i<=10;i++){
        for(j=i;j<=14 && hand[j];j++){
            hand[j]--;
            if(j-i+1>=5)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]++;
    }
    for(i=3;i<=12;i++){
        for(j=i;j<=14 && hand[j]>=2;j++){
            hand[j]-=2;
            if(j-i+1>=3)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=2;
    }
    for(i=3;i<=13;i++){
        for(j=i;j<=14 && hand[j]>=3;j++){
            hand[j]-=3;
            if(j-i+1>=2)
                dfs(x+1);
        }
        while(j>i)
            hand[--j]+=3;
    }
}
int main(){
    int T,u,v;
    register int i;
    scanf("%d%d",&T,&n);
    while(T--){
        ans=n;
        memset(hand,0,sizeof(hand));
        for(i=1;i<=n;i++){
            scanf("%d%d",&u,&v);
            if(!u){
                if(v==2)
                    hand[1]++;
                else
                    hand[0]++;
            }else{
                if(u==1)
                    hand[14]++;
                else
                    hand[u]++;
            }
        }
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

[洛谷 P1967]货车运输

倍增LCA经典题……

这题的做法就是求最大生成树,然后用倍增LCA法求瓶颈路……

注意一下,两点不连通时输出-1(其实这个用并查集判断不就行了……)!!!

代码:

继续阅读