[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查

这个是一道题啊……不过都是挺经典的问题……

建图是这样的:支持0的从[tex]S[/tex]向此点连一条容量为1的边,支持1的就向[tex]T[/tex]连一条长度为1的边,朋友之间连一条长度为1的边。跑一遍最小割即可。

这个的解释?最优情况下任何人违背自己的意见都是因为怕和朋友冲突,和朋友冲突则是因为没有违背自己的意见(废话)。所以拆了最小割就解决掉了所有冲突问题。

代码:

/**************************************************************
    Problem: 2768
    User: danihao123
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:7668 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
    struct Edge{
        int u,v,cap,flow;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int s,t;
    int m;
    inline void AddEdge(int u,int v,int cap){
        edges.push_back((Edge){u,v,cap,0});
        edges.push_back((Edge){v,u,0,0});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    bool vis[maxn];
    int cur[maxn],d[maxn];
    bool bfs(){
        register int i,u;
        queue<int> Q;
        memset(vis,0,sizeof(vis));
        Q.push(s);
        d[s]=0;
        vis[s]=true;
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(!vis[e.v] && e.cap>e.flow){
                    d[e.v]=d[u]+1;
                    Q.push(e.v);
                    vis[e.v]=true;
                }
            }
        }
        return vis[t];
    }
    int dfs(int x,int a){
        if(x==t || a==0)
            return a;
        int f,flow=0;
        for(int& i=cur[x];i<G[x].size();i++){
            Edge& e=edges[G[x][i]];
            if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
                flow+=f;
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }
    int MinCut(int S,int T){
        register int ans=0;
        s=S;
        t=T;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            ans+=dfs(s,0x7fffffff);
        }
        return ans;
    }
};
int main(){
    int n,m;
    int u,v;
    register int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&u);
        if(!u){
            Dinic::AddEdge(0,i,1);
        }else{
            Dinic::AddEdge(i,n+1,1);
        }
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        Dinic::AddEdge(u,v,1);
        Dinic::AddEdge(v,u,1);
    }
    printf("%d\n",Dinic::MinCut(0,n+1));
    return 0;
}

[BZOJ 3531]旅行

发现自己好久没写树链剖分了……唉……

言归正传,这道题很容易想到的做法就是每种宗教开一个线段树,到各个宗教的线段树里面操作即可。

很可惜,直接开线段树的话肯定会MLE。我们可以考虑动态开点,对于不需要的点一律不开。这样内存消耗量就大减了。

注意一些细节:

  1. 查询时判断当前结点是不是NULL。
  2. 删除前最好判断一下这个结点是不是NULL吧,以防万一。
  3. 删除操作时,如果结点没有用了,就删。但是注意,记得delete前要把原指针设为NULL,直接delete会引起悬垂指针问题导致爆炸!

代码:

/**************************************************************
    Problem: 3531
    User: danihao123
    Language: C++
    Result: Accepted
    Time:10404 ms
    Memory:34872 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n;
namespace SegmentTree{
    struct Node{
        int sumv,maxv;
        Node *lc,*rc;
        Node(){
            sumv=maxv=0;
            lc=rc=NULL;
        }
        void maintain(){
            if(lc!=NULL){
                if(rc!=NULL){
                    sumv=lc->sumv+rc->sumv;
                    maxv=max(lc->maxv,rc->maxv);
                }else{
                    sumv=lc->sumv;
                    maxv=lc->maxv;
                }
            }else{
                if(rc!=NULL){
                    sumv=rc->sumv;
                    maxv=rc->maxv;
                }
            }
        }
    };
    Node* T[maxn];
    int p,v;
    void _Delete(Node* &o,int L,int R){
        if(o==NULL)
            return;
        if(L==R){
            Node *temp=o;
            o=NULL;
            delete temp;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Delete(o->lc,L,M);
            else
                _Delete(o->rc,M+1,R);
            if(o->lc==NULL && o->rc==NULL){
                Node *temp=o;
                o=NULL;
                delete temp;
            }else{
                o->maintain();
            }
        }
    }
    inline void Delete(int c,int pos){
        p=pos;
        _Delete(T[c],1,n);
    }
    void _Insert(Node* &o,int L,int R){
        if(o==NULL)
            o=new Node();
        if(L==R){
            o->sumv=o->maxv=v;
        }else{
            int M=L+(R-L)/2;
            if(p<=M)
                _Insert(o->lc,L,M);
            else
                _Insert(o->rc,M+1,R);
        }
        o->maintain();
    }
    inline void Insert(int c,int pos,int value){
        p=pos;
        v=value;
        _Insert(T[c],1,n);
    }
    int ql,qr;
    int _query_max(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->maxv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans=max(ans,_query_max(o->lc,L,M));
        if(qr>M)
            ans=max(ans,_query_max(o->rc,M+1,R));
        return ans;
    }
    inline int query_max(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_max(T[c],1,n);
    }
    int _query_sum(Node *o,int L,int R){
        if(o==NULL)
            return 0;
        if(ql<=L && R<=qr)
            return o->sumv;
        int M=L+(R-L)/2,ans=0;
        if(ql<=M)
            ans+=_query_sum(o->lc,L,M);
        if(qr>M)
            ans+=_query_sum(o->rc,M+1,R);
        return ans;
    }
    inline int query_sum(int c,int l,int r){
        ql=l;
        qr=r;
        return _query_sum(T[c],1,n);
    }
};
#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])
int first[maxn];
int next[maxn*2],to[maxn*2];
int graph_tot=0;
inline void AddEdge(int u,int v){
    graph_tot++;
    next[graph_tot]=first[u];
    first[u]=graph_tot;
    to[graph_tot]=v;
}
 
int dep[maxn],fa[maxn],son[maxn],siz[maxn];
bool vis[maxn];
void dfs_1(int x,int father,int depth){
    vis[x]=true;
    fa[x]=father;
    dep[x]=depth;
    siz[x]=1;
    int i,temp,max_siz=0;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_1(temp,x,depth+1);
            siz[x]+=siz[temp];
            if(siz[temp]>max_siz){
                son[x]=temp;
                max_siz=siz[temp];
            }
        }
    }
}
int hld_cnt=0;
int rlg[maxn];
int d[maxn];
int tid[maxn],top[maxn];
void dfs_2(int x,int a){
    vis[x]=true;
    top[x]=a;
    tid[x]=++hld_cnt;
    SegmentTree::Insert(rlg[x],hld_cnt,d[x]);
    if(son[x])
        dfs_2(son[x],a);
    else
        return;
    int i,temp;
    GRAPH_REP(i,x){
        temp=to[i];
        if(!vis[temp]){
            dfs_2(temp,temp);
        }
    }
}
int query_max(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_max(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return max(SegmentTree::query_max(c,tid[top[x]],tid[x]),query_max(c,fa[top[x]],y));
}
int query_sum(int c,int x,int y){
    if(top[x]==top[y]){
        if(tid[x]>tid[y])
            swap(x,y);
        return SegmentTree::query_sum(c,tid[x],tid[y]);
    }
    if(dep[top[x]]<dep[top[y]])
        swap(x,y);
    return SegmentTree::query_sum(c,tid[top[x]],tid[x])+query_sum(c,fa[top[x]],y);
}
inline void Replace(int pos,int direction){
    int c=rlg[pos];
    SegmentTree::Delete(c,tid[pos]);
    SegmentTree::Insert(direction,tid[pos],d[pos]);
    rlg[pos]=direction;
}
inline void Update(int pos,int v){
    d[pos]=v;
    SegmentTree::Insert(rlg[pos],tid[pos],v);
}
 
int main(){
    register int i;
    int q,u,v;
    char buf[5];
    scanf("%d%d",&n,&q);
    REP_B(i,n){
        scanf("%d%d",&d[i],&rlg[i]);
    }
    REP_B(i,n-1){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs_1(1,0,1);
    memset(vis,0,sizeof(vis));
    dfs_2(1,1);
    while(q--){
        memset(buf,0,sizeof(buf));
        scanf("%s%d%d",buf,&u,&v);
        if(buf[0]=='C'){
            if(buf[1]=='W'){
                Update(u,v);
            }else{
                Replace(u,v);
            }
        }else{
            if(buf[1]=='M'){
                printf("%d\n",query_max(rlg[u],u,v));
            }else{
                printf("%d\n",query_sum(rlg[u],u,v));
            }
        }
    }
    return 0;
}

[BZOJ 2330]糖果

比较裸一些的差分约束系统题……话说好像第一次写SPFA最长路啊TAT

这个题1,3,5条件直接搞就可以。2,4条件要转化成有等于号的版本。

顺便说一些这题的坑点:

  1. 有一个点是一个十万个点的链。在从源点连的时候,如果正序连就会炸。倒着连就不会T。
  2. 有的点的2,4条件出现了[tex]a=b[/tex]的情况,要特判……
  3. 要开long long!

代码:

/**************************************************************
    Problem: 2330
    User: danihao123
    Language: C++
    Result: Accepted
    Time:356 ms
    Memory:7592 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(i=1;i<=(n);i++)
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
#define CL_ARR(i,x) memset(i,x,sizeof(i))
const int maxn=100005,maxm=300005;
 
typedef long long ll;
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v,ll d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int n;
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
ll SPFA(){
    register int i,u;
    register ll ans=0;
    queue<int> Q;
    CL_ARR(d,-1);
    d[0]=0;
    Q.push(0);
    inQueue[0]=true;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        inQueue[u]=false;
        GRAPH_REP(i,u){
            if(d[u]>-1 && d[to[i]]<d[u]+dist[i]){
                d[to[i]]=d[u]+dist[i];
                if(!inQueue[to[i]]){
                    Q.push(to[i]);
                    inQueue[to[i]]=true;
                    if((++cnt[to[i]])>(n+1))
                        return -1;
                }
            }
        }
    }
    REP(i,n){
        ans+=d[i];
    }
    return ans;
}
 
int main(){
    register int i;
    int opt,u,v;
    int k;
    scanf("%d%d",&n,&k);
    REP(i,k){
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1){
            AddEdge(u,v,0);
            AddEdge(v,u,0);
        }else{
            if(opt==2){
                if(u==v){
                    puts("-1");
                    return 0;
                }
                AddEdge(u,v,1);
            }else{
                if(opt==3){
                    AddEdge(v,u,0);
                }else{
                    if(opt==4){
                        if(u==v){
                            puts("-1");
                        }
                        AddEdge(v,u,1);
                    }else{
                        AddEdge(u,v,0);
                    }
                }
            }
        }
    }
    for(i=n;i>=1;i--){
        AddEdge(0,i,1);
    }
    printf("%lld\n",SPFA());
    return 0;
}


[BZOJ 1013]球型空间产生器

不行不能颓了……线代其实刚起步……

注意每个点到球心的距离相同,距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex],那么我们先可以列出两个方程(假设[tex]n=2[/tex],不过此时事实上可以列三个,但出于方便讨论的目的便只列两个):

[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]

[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]

两方程作差,得:

[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]

整理,得:

[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]

对这种方法加以推广,便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。

代码:

/**************************************************************
    Problem: 1013
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1296 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
    register int i,j,k,r;
    register double f;
    for(i=1;i<=n;i++){
        r=i;
        for(j=i+1;j<=n;j++)
            if(fabs(A[j][i])>fabs(A[r][i]))
                r=j;
        if(r!=i)
            for(j=1;j<=(n+1);j++)
                swap(A[r][j],A[i][j]);
        for(k=i+1;k<=n;k++){
            f=A[k][i]/A[i][i];
            for(j=i;j<=n+1;j++)
                A[k][j]-=f*A[i][j];
        }
    }
    for(i=n;i>=1;i--){
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[j][n+1]*A[i][j];
        A[i][n+1]/=A[i][i];
    }
}
int main(){
    register int i,j;
    bool flag=false;
    cin>>n;
    for(i=1;i<=(n+1);i++)
        for(j=1;j<=n;j++)
            cin>>M[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=(n+1);j++)
            A[i][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            A[i][j]=2*(M[i+1][j]-M[i][j]);
            A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
        }
    }
    Gause();
    for(i=1;i<=n;i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%.3f",A[i][n+1]);
    }
    putchar('\n');
    return 0;
}

[BZOJ 1196]公路修建问题

挺简单的二分答案题……然而到现在才A

思路很明显,直接二分最终答案。那么判定如何做呢?

假设判定谓词为[tex]C(x)[/tex],那么我们首先考虑选白边。贪心加入边权小于[tex]x[/tex]的边(当然是否有必要就要用并查集判定了。并且这样就算加的超过了[tex]k[/tex]条也不会对答案造成影响)。然后白边加的不够[tex]k[/tex]谓词就是假了。

然后再考虑黑边,接下来的事情就很简单了。

代码:

/**************************************************************
    Problem: 1196
    User: danihao123
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:1212 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i,n) for(i=0;i<(n);i++)
#define RAP(i,n) for(i=1;i<=(n);i++)
const int maxn=10001,maxm=20001;
 
struct Edge{
    int u,v,d1,d2;
};
bool cmp1(const Edge& x,const Edge& y){
    return x.d1<y.d1;
}
bool cmp2(const Edge& x,const Edge& y){
    return x.d2<y.d2;
}
 
int n;
int p[maxn],rank[maxn];
int find_set(int x){
    if(p[x]==x)
        return x;
    else
        return p[x]=find_set(p[x]);
}
inline void link_set(int x,int y){
    if(rank[x]>rank[y]){
        p[y]=x;
    }else{
        p[x]=y;
        if(rank[x]==rank[y])
            rank[y]++;
    }
}
inline void union_set(int x,int y){
    link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
    return find_set(x)==find_set(y);
}
inline void init_set(){
    register int i;
    for(i=1;i<=n;i++)
        p[i]=i;
    memset(rank,0,sizeof(rank));
}
 
int k,m;
Edge E[maxm];
inline bool check(int x){
    register int i,first_cnt=0,cnt=0;
    init_set();
    sort(E,E+m,cmp1);
    REP(i,m){
        if(E[i].d1>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                first_cnt++;
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1){
            return true;
        }
    }
    if(first_cnt<k)
        return false;
    sort(E,E+m,cmp2);
    REP(i,m){
        if(E[i].d2>x){
            break;
        }else{
            if(!is_same(E[i].u,E[i].v)){
                cnt++;
                union_set(E[i].u,E[i].v);
            }
        }
        if(cnt==n-1)
            return true;
    }
    return false;
}
int main(){
    register int i,L=1,M,R=0;
    scanf("%d%d%d",&n,&k,&m);
    m--;
    REP(i,m){
        scanf("%d%d%d%d",&E[i].u,&E[i].v,&E[i].d1,&E[i].d2);
        R=max(R,E[i].d1);
    }
    R++;
    while(L<R){
        M=L+(R-L)/2;
        if(check(M))
            R=M;
        else
            L=M+1;
    }
    printf("%d\n",L);
    return 0;
}

 

[BZOJ 1787]紧急集合

这个题需要一些脑洞。

给出任意三点,如果我们两两求LCA,肯定有两组相同,剩下那一组就是最优集合点了。为啥?画图理解一下吧……

代码:

/**************************************************************
    Problem: 1787
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4068 ms
    Memory:80900 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#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 TWO_POW(n) (1<<(n))
 
const int maxn=500001,maxm=1000001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
inline void Add_Edge(int u,int v,int d){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
    dist[graph_cnt]=d;
}
 
int d[maxn];
int dep[maxn];
int anc[maxn][32];
void dfs(int x,int father,int depth,int dis){
    d[x]=dis;
    anc[x][0]=father;
    dep[x]=depth;
    int i;
    GRAPH_REP(i,x){
        if(to[i]!=father)
            dfs(to[i],x,depth+1,dis+dist[i]);
    }
}
 
int n;
inline void InitLCA(){
    register int i,j;
    for(j=1;TWO_POW(j)<n;j++){
        REP_B(i,n){
            if(anc[i][j-1]!=-1){
                anc[i][j]=anc[anc[i][j-1]][j-1];
            }
        }
    }
}
 
int QueryLCA(int x,int y){
    register int j,log;
    if(dep[x]<dep[y])
        swap(x,y);
    for(log=1;TWO_POW(log)<=dep[x];log++);
    log--;
    for(j=log;j>=0;j--)
        if(dep[x]-TWO_POW(j)>=dep[y])
            x=anc[x][j];
    if(x==y)
        return y;
    for(j=log;j>=0;j--){
        if(anc[x][j]!=-1 && anc[x][j]!=anc[y][j]){
            x=anc[x][j];
            y=anc[y][j];
        }
    }
    return anc[x][0];
}
inline int make_dis(int x,int y){
    return d[x]+d[y]-2*d[QueryLCA(x,y)];
}
 
int main(){
    int u,v,D;
    int x,y,z,QinDing;
    int m;
    register int i,j;
    scanf("%d%d",&n,&m);
    REP(i,n-1){
        scanf("%d%d",&u,&v);
        Add_Edge(u,v,1);
        Add_Edge(v,u,1);
    }
    memset(anc,-1,sizeof(anc));
    dfs(1,-1,0,0);
    InitLCA();
    REP(i,m){
        scanf("%d%d%d",&u,&v,&D);
        x=QueryLCA(u,v);
        y=QueryLCA(u,D);
        z=QueryLCA(v,D);
        if(x==y){
            QinDing=z;
        }else{
            if(x==z){
                QinDing=y;
            }else{
                QinDing=x;
            }
        }
        printf("%d %d\n",QinDing,make_dis(QinDing,u)+make_dis(QinDing,v)+make_dis(QinDing,D));
    }
    return 0;
}

[BZOJ 1029]建筑抢修

废了。

我彻底废了。

就一个贪心水体。按截止时间排序然后遍历,当前花时间能干完就干,不能的话看能不能把更劣的选择换。仅此而已。

代码:

/**************************************************************
    Problem: 1029
    User: danihao123
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:2764 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
    int a,b;
    bool operator <(const Node& x) const{
        return b<x.b;
    }
    bool operator >(const Node& x) const{
        return b>x.b;
    }
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
    int n;
    register int i,ans=0;
    register ll cur=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&T[i].a,&T[i].b);
    sort(T+1,T+1+n);
    for(i=1;i<=n;i++){
        if(cur+T[i].a<=T[i].b){
            cur+=T[i].a;
            Q.push(T[i].a);
        }else{
            if(Q.size() && Q.top()>T[i].a){
                cur-=Q.top();
                Q.pop();
                cur+=T[i].a;
                Q.push(T[i].a);
            }
        }
    }
    printf("%d\n",Q.size());
    return 0;
}

[BZOJ 1034]泡泡堂

这题其实就是一个田忌赛马类问题。贪心即可。

如果你不知道田忌赛马怎么贪,可以看《骗分导论》相关介绍(然而那个贪心不是骗分算法哦)。

代码:

/**************************************************************
    Problem: 1034
    User: danihao123
    Language: C++
    Result: Accepted
    Time:256 ms
    Memory:1604 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
    register int L1=1,R1=n,L2=1,R2=n,ans=0;
    while(L1<=R1 && L2<=R2){
        if(A[L1]>B[L2]){
            ans+=2;
            L1++;
            L2++;
        }else{
            if(A[R1]>B[R2]){
                ans+=2;
                R1--;
                R2--;
            }else{
                if(A[L1]==B[R2])
                    ans++;
                L1++;
                R2--;
            }
        }
    }
    return ans;
}
int main(){
    register int i,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    printf("%d %d\n",solve(a,b),2*n-solve(b,a));
    return 0;
}

[BZOJ 1022]小约翰的游戏

这个题是比较特殊的游戏。因为扩展出最后一个状态的人会输。这种游戏称为Anti-SG游戏。

解决这种题,需要SJ定理:先手必胜当且仅当游戏的SG函数为0而存在一个单一游戏的SG函数大于1,或整个游戏的SG函数不为0且没有任何单一游戏的SG函数大于1。问题迎刃而解。

代码:

/**************************************************************
    Problem: 1022
    User: danihao123
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    register int i,last;
    int n,temp,T;
    bool obey_1;
    scanf("%d",&T);
    while(T--){
        obey_1=false;
        last=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&temp);
            if(temp>1){
                obey_1=true;
            }
            last=last^temp;
        }
        if((last!=0 && obey_1) || (last==0 && !obey_1)){
            puts("John");
        }else{
            puts("Brother");
        }
    }
    return 0;
}

[BZOJ 1878]HH的项链

扫描线处女作TAT

直接离线,按左端点排序扫描。每个点要保存后继相同节点,每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。

代码:

/**************************************************************
    Problem: 1878
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1344 ms
    Memory:8444 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int p,int v){
    while(p<=n){
        T[p]+=v;
        p+=lowbit(p);
    }
}
inline int query(int p){
    register int ans=0;
    while(p>0){
        ans+=T[p];
        p-=lowbit(p);
    }
    return ans;
}
 
struct Query{
    int l,r;
    int id;
    int ans;
    bool operator <(const Query& x) const{
        return l==x.l?r<x.r:l<x.l;
    }
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
    return a.id<b.id;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
 
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
    int m,maxA=0;
    register int i,j;
    n=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        maxA=max(maxA,A[i]);
    }
    for(i=n;i;i--){
        next[i]=pos[A[i]];
        pos[A[i]]=i;
    }
    for(i=1;i<=maxA;i++)
        if(pos[i])
            update(pos[i],1);
    m=readint();
    for(i=1;i<=m;i++){
        Q[i].l=readint();
        Q[i].r=readint();
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    register int tot=1;
    for(i=1;i<=m;i++){
        while(tot<Q[i].l){
            if(next[tot])
                update(next[tot],1);
            tot++;
        }
        Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
    }
    sort(Q+1,Q+1+m,cmp2);
    for(i=1;i<=m;i++){
        writeint(Q[i].ans);
        putchar('\n');
    }
    return 0;
}