danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

29173

[BZOJ 3155]Preprefix sum

2016年10月22日 20:37 | Comments(0) | Category:题解 | Tags:

蛮有意思的一题……

考虑询问[tex]SS_i[/tex],[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex],然后式子就可以变成这样:

[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]

[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]

这样问题就简单多了,开两个树状数组乱搞搞即可。

代码:

/**************************************************************
    Problem: 3155
    User: danihao123
    Language: C++
    Result: Accepted
    Time:464 ms
    Memory:3164 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p,ll v){
    while(p<=n){
        C_1[p]+=v;
        p+=lowbit(p);
    }
}
inline ll sum(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_1[p];
        p-=lowbit(p);
    }
    return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
    register int pos=p;
    while(pos<=n){
        C_2[pos]+=((ll)p)*v;
        pos+=lowbit(pos);
    }
}
inline ll sum_2(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_2[p];
        p-=lowbit(p);
    }
    return ans;
}
 
int main(){
    int m,p;
    ll v;
    register int i;
    char *buf=(char*)calloc(10,1);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        add(i,A[i]);
        add_2(i,A[i]);
    }
    while(m--){
        scanf("%s%d",buf,&p);
        if(buf[0]=='Q'){
            printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
        }else{
            scanf("%lld",&v);
            add(p,v-A[p]);
            add_2(p,v-A[p]);
            A[p]=v;
        }
    }
    free(buf);
    return 0;
}

[BZOJ 3333]排队计划

2016年10月15日 16:40 | Comments(0) | Category:题解 | Tags:

传说中的大结论题TAT

假设每个数的后面小于它的数的个数为[tex]f[i][/tex](其位置为[tex]i[/tex]),那么逆序对数显然为[tex]\Sigma f[i][/tex]。

每次操作,只需要将涉及到的数的[tex]f[i][/tex]清为0即可。

为什么呢?任何数的后面比他小的数肯定也被一起拉出来排序了,所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢?因为这之后的比他小的位置,有的可能没被操作,有的可能被操作了。但是就算被操作了,放到后面位置的数照样会比这个数小(因为这个数如果在第一个选定位置的后面(在前面更是不受影响)还没被操作,肯定比那个第一个位置数还大)。

还有一个细节,一个被操作过的数不需要再被操作一遍,操作完了直接设为INF即可。

代码:

/**************************************************************
    Problem: 3333
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7920 ms
    Memory:24264 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=make_pair(A[L],L);
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
int ql,qr;
pii query_min(int o,int L,int R){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        int M=L+(R-L)/2;
        pii ans=make_pair(INF,INF);
        if(ql<=M)
            ans=min(ans,query_min(o<<1,L,M));
        if(qr>M)
            ans=min(ans,query_min(o<<1|1,M+1,R));
        return ans;
    }
}
int p;
void update(int o,int L,int R){
    if(L==R){
        minv[o].first=INF;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,L,M);
        else
            update(o<<1|1,M+1,R);
        maintain(o);
    }
}
 
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p){
    while(p<=lsh_siz){
        C[p]++;
        p+=lowbit(p);
    }
}
inline int sum(int p){
    int ans=0;
    while(p>0){
        ans+=C[p];
        p-=lowbit(p);
    }
    return ans;
}
 
inline int readint(){
    register int x;
    register char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
    register int i,p=0;
    if(!x){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(bf[i]+'0');
    putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
    register int i,m,pos;
    register ull ans=0;
    pii temp;
    n=readint();
    m=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        A2[i]=A[i];
    }
    sort(A2+1,A2+1+n);
    lsh_siz=unique(A2+1,A2+1+n)-A2-1;
    for(i=n;i>=1;i--){
        pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
        f[i]=sum(pos-1);
        ans+=f[i];
        add(pos);
    }
    putint(ans);
    build_tree(1,1,n);
    while(m--){
        pos=readint();
        ql=pos;
        qr=n;
        while(true){
            temp=query_min(1,1,n);
            if(temp.first>A[pos])
                break;
            p=temp.second;
            ans-=f[p];
            f[p]=0;
            update(1,1,n);
        }
        putint(ans);
    }
    return 0;
}

[BZOJ 3306]树

2016年10月12日 22:19 | Comments(0) | Category:题解 | Tags:

这个题其他操作都不难(DFS序+线段树水过),就是换根有点头疼……直接做的话要TopTree吧。

不过我们考虑用DFS序+线段树的“偷懒”做法。每次查询的时候考虑当前的根,如果这个根最初不在x的子树中,那么对目前的查询值没有影响;如果就是x,那么整个树都是x的子树;如果是x的某个后代,那么整个树里除了他的后代所在额这颗子树以外的所有部分全部变成了x的子树(试着翻转一下就明白了)。判断后代祖先以及在哪个子树这些东西可以用倍增LCA高效实现,问题就这样简单了。

代码:

/**************************************************************
    Problem: 3306
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2308 ms
    Memory:17544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
#define SEG_STD int o,int L,int R
#define MAKE_MID int M=L+(R-L)/2
// #define MAKE_CLD int lc=o<<1,rc=o<<1|1
#define LCH o<<1,L,M
#define RCH o<<1|1,M+1,R
int n;
int minv[maxnode];
int A[maxn];
void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(SEG_STD){
    if(L==R){
        minv[o]=A[L];
    }else{
        MAKE_MID;
        build_tree(LCH);
        build_tree(RCH);
        maintain(o);
    }
}
int ql,qr;
int query(SEG_STD){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        MAKE_MID;
        int ans=INF;
        if(ql<=M)
            ans=min(ans,query(LCH));
        if(qr>M)
            ans=min(ans,query(RCH));
        return ans;
    }
}
int p,v;
void update(SEG_STD){
    if(L==R){
        minv[o]=v;
    }else{
        MAKE_MID;
        if(p<=M)
            update(LCH);
        else
            update(RCH);
        maintain(o);
    }
}
inline int query(int l,int r){
    if(l<1 || l>n || r<1 || r>n)
        return INF;
    ql=l;
    qr=r;
    return query(1,1,n);
}
inline void update(int pos,int value){
    p=pos;
    v=value;
    update(1,1,n);
}
 
int first[maxn];
int next[maxn],to[maxn];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int d[maxn];
int tid[maxn];
int anc[maxn][19],dep[maxn];
int siz[maxn];
int dfs_clk=0;
void dfs(int x,int fa,int depth){
    dfs_clk++;
    tid[x]=dfs_clk;
    A[dfs_clk]=d[x];
    anc[x][0]=fa;
    dep[x]=depth;
    siz[x]=1;
    int i;
    for(i=first[x];i;i=next[i]){
        dfs(to[i],x,depth+1);
        siz[x]+=siz[to[i]];
    }
}
void process(){
    register int i,j;
    for(j=1;(1<<j)<n;j++)
        for(i=1;i<=n;i++)
            if(anc[i][j-1]!=-1)
                anc[i][j]=anc[anc[i][j-1]][j-1];
}
int root;
bool isAnc(int x){
    register int p=root,j;
    if(dep[p]<dep[x])
        return false;
    for(j=18;j>=0;j--)
        if(dep[p]-(1<<j)>=dep[x] && anc[p][j]!=-1)
            p=anc[p][j];
    return p==x;
}
int findAnc(int x,int y){
    register int j;
    for(j=18;j>=0;j--)
        if(dep[y]-dep[x]-(1<<j)>0 && anc[y][j]!=-1)
            y=anc[y][j];
    return y;
}
 
int getAns(int x){
    if(x==root){
        return query(1,n);
    }else{
        if(isAnc(x)){
            register int t=findAnc(x,root);
            register int l=tid[t],r=tid[t]+siz[t]-1;
            return min(query(1,l-1),query(r+1,n));
        }else{
            return query(tid[x],tid[x]+siz[x]-1);
        }
    }
}
 
int main(){
    int q,x,f;
    register int i;
    char buf[3];
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%d%d",&f,&d[i]);
        if(!f){
            root=i;
        }else{
            AddEdge(f,i);
        }
    }
    memset(anc,-1,sizeof(anc));
    dfs(root,-1,0);
    process();
    build_tree(1,1,n);
    while(q--){
        scanf("%s%d",buf,&x);
        if(buf[0]=='V'){
            scanf("%d",&f);
            update(tid[x],f);
        }else{
            if(buf[0]=='Q'){
                printf("%d\n",getAns(x));
            }else{
                root=x;
            }
        }
    }
    return 0;
}

[BZOJ 2186]沙拉公主的困惑

2016年10月11日 21:59 | Comments(0) | Category:题解 | Tags:

这个题啊……亦可赛艇!

答案是[tex]\varphi(m!)*n!/m![/tex]。原因很简单,把[tex][1,n!][/tex]分成长度为[tex]m![/tex]的若干段,除去第一段外每一段中与[tex]m![/tex]互质的数[tex]k[/tex]肯定满足[tex](k\bmod m!,m!)=1[/tex](否则,[tex]k[/tex]和[tex]m![/tex]就会有大于一的公因子了)。所以说每一段内与[tex]m![/tex]互质的数都有[tex]\varphi(m!)[/tex]个。

麻烦好像就在于求一个阶乘的欧拉函数。考虑一个新乘上的数能给答案带来的贡献——如果这个数是合数,它的所有因子在前面都有了,只能把他自己贡献出来;如果这个数是质数(假设为[tex]p[/tex]),出了贡献自己以外还会贡献一个[tex](1-1/p)[/tex],最后乘起来就是贡献了[tex]p-1[/tex]。筛一遍素数再递推一下就好辣~

并且……[tex]n-m[/tex]可能非常大,所以说除去[tex]m![/tex]那块要用逆元做。

(顺便说下阶乘也要递推)

代码:

/**************************************************************
    Problem: 2186
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9408 ms
    Memory:166836 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
typedef unsigned long long ull;
const int maxn=10000000;
ull R;
bool vis[maxn+5];
inline void sievePrime(){
    register int i,j,m=sqrt(maxn+0.5);
    for(i=2;i<=m;i++)
        if(!vis[i])
            for(j=i*i;j<=maxn;j+=i)
                vis[j]=true;
}
ull fac[maxn+5];
inline void sieveFac(){
    register int i;
    fac[0]=1%R;
    for(i=1;i<=maxn;i++)
        fac[i]=(fac[i-1]*(i%R))%R;
}
ull phifac[maxn+5];
inline void sievePhiFac(){
    register int i;
    phifac[1]=1%R;
    for(i=2;i<=maxn;i++){
        if(vis[i])
            phifac[i]=(phifac[i-1]*(i%R))%R;
        else
            phifac[i]=(phifac[i-1]*((i%R-1%R+R)%R))%R;
    }
}
void exgcd(ull a,ull b,ull& d,ull& x,ull& y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ull inv(ull a){
    ull d,x,y;
    exgcd(a,R,d,x,y);
    return (x+R)%R;
}
int main(){
    int T;
    int n,m;
    scanf("%d%llu",&T,&R);
    sievePrime();
    sieveFac();
    sievePhiFac();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%llu\n",(phifac[m]*((fac[n]*inv(fac[m]))%R))%R);
    }
    return 0;
}

[BZOJ 3339]Rmq Problem

2016年9月28日 13:08 | Comments(0) | Category:题解 | Tags:

万恶的标题党啊~

这个题明显扫描线辣……但是怎么扫呢?

我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值,然后用线段树维护。

从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时,需要将[tex][l,next[l]-1][/tex]([tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置)中的所有大于[tex]A[l][/tex]([tex]l[/tex]的值)的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats?

答案是否定的。注意到我们真正需要的只是叶子结点,所以其他非叶子结点的最小值全部弄成无限大,然后这样做就可以把最小值当做标记来弄了……非常精巧。

代码:

/**************************************************************
    Problem: 3339
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1988 ms
    Memory:10396 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=A[L];
    }else{
        int M=L+(R-L)/2;
        minv[o]=INF;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
    }
}
inline void paint(int o,int v){
    minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
    paint(o<<1,minv[o]);
    paint(o<<1|1,minv[o]);
    minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
    if(L==R)
        return minv[o];
    if(minv[o]<INF)
        pushdown(o);
    int M=L+(R-L)/2;
    if(pos<=M)
        return query(o<<1,L,M);
    else
        return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
    if(ql<=L && R<=qr){
        paint(o,v);
    }else{
        if(minv[o]<INF)
            pushdown(o);
        int M=L+(R-L)/2;
        if(ql<=M)
            update(o<<1,L,M);
        if(qr>M)
            update(o<<1|1,M+1,R);
    }
}
 
inline int readint(){
    register int x=0;
    register char c;
    fread(&c,1,1,stdin);
    while(!isdigit(c))
        fread(&c,1,1,stdin);
    while(isdigit(c)){
        x=x*10+c-'0';
        fread(&c,1,1,stdin);
    }
    return x;
}
int buf[21];
inline void putint(int x){
    register int i,p=0;
    if(!x){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
 
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
    int id;
    int l,r;
    int ans;
};
bool cmp1(const Query& x,const Query& y){
    if(x.l==y.l)
        return x.r<y.r;
    else
        return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
    return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
    int n,q;
    register int i,l=1,k=0;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++){
        V[i]=readint();
        vis[V[i]]=true;
        if(k==V[i])
            while(vis[k])
                k++;
        A[i]=k;
    }
    build_tree(1,1,n);
    for(i=n;i>=1;i--){
        if(!last[V[i]])
            next[i]=n+1;
        else
            next[i]=last[V[i]];
        last[V[i]]=i;
    }
    for(i=1;i<=q;i++){
        QS[i].id=i;
        QS[i].l=readint();
        QS[i].r=readint();
    }
    sort(QS+1,QS+1+q,cmp1);
    for(i=1;i<=q;i++){
        while(l<QS[i].l){
            ql=l;
            qr=next[l]-1;
            v=V[l];
            update(1,1,n);
            l++;
        }
        pos=QS[i].r;
        QS[i].ans=query(1,1,n);
    }
    sort(QS+1,QS+1+q,cmp2);
    for(i=1;i<=q;i++){
        putint(QS[i].ans);
    }
    return 0;
}

[BZOJ 1433]假期的宿舍

2016年9月27日 13:06 | Comments(0) | Category:题解 | Tags:

这几乎是个二分图匹配的裸题了……

不过有很多细节问题,比如说题面里提到的那些。还有多组数据的话注意清理数组。

代码:

/**************************************************************
    Problem: 1433
    User: danihao123
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=55;
bool G[maxn][maxn];
int n,m;
int Pei[maxn];
bool vis[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    return false;
}
int Hungray(){
    register int i,ans=0;
    memset(Pei,0,sizeof(Pei));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}
 
int Per[maxn],Bed[maxn];
bool isStudent[maxn],Back[maxn];
int main(){
    int T,N,u,v;
    register int i,j;
    scanf("%d",&T);
    while(T--){
        n=m=0;
        scanf("%d",&N);
        memset(G,0,sizeof(G));
        memset(Per,0,sizeof(Per));
        memset(Bed,0,sizeof(Bed));
        memset(isStudent,0,sizeof(isStudent));
        memset(Back,0,sizeof(Back));
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            isStudent[i]=u;
        }
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            if(isStudent[i]){
                Back[i]=u;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                Bed[i]=++m;
                if(!Back[i]){
                    Per[i]=++n;
                }
            }else{
                Per[i]=++n;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                G[Per[i]][Bed[i]]=true;
            }
            for(j=1;j<=N;j++){
                scanf("%d",&v);
                if(v && isStudent[j]){
                    G[Per[i]][Bed[j]]=true;
                }
            }
        }
        if(Hungray()==n)
            puts("^_^");
        else
            puts("T_T");
    }
    return 0;
}

[POJ 3974]Palindrome

2016年9月25日 14:38 | Comments(0) | Category:题解 | Tags:

Manacher……妙,妙啊……

这个题就要是给一个字符串,输出最大回文字串长度。Manacher即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000005;
char buf[maxn],s[maxn<<1];
int p[maxn<<1];
inline void FactStr(){
	register int i,j=0,n=strlen(buf);
	s[j++]='$';
	s[j++]='#';
	for(i=0;i<n;i++){
		s[j++]=buf[i];
		s[j++]='#';
	}
	s[j]='\0';
}
inline int Manachar(){
	register int i,n=strlen(s);
	register int mx=0,id;
	register int ans=-1;
	for(i=1;i<n;i++){
		if(i<mx)
			p[i]=min(p[2*id-i],mx-i);
		else
			p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])
			p[i]++;
		if((p[i]+i)>mx){
			id=i;
			mx=p[i]+i;
		}
		ans=max(ans,p[i]-1);
	}
	return ans;
}
int main(){
	register int Case=0;
	while(scanf("%s",buf)==1){
		if(buf[0]=='E')
			break;
		Case++;
		FactStr();
		printf("Case %d: %d\n",Case,Manachar());
	}
	return 0;
}

[POJ 1200]Crazy Search

2016年9月25日 08:50 | Comments(0) | Category:题解 | Tags:

很容易想到哈希+set判重的方法,但好像会T吧……

那么就要直接开哈希表了,但是哈希函数会很大,怎么办呢?

我们看到还有一个NK啊……这样就有一个行之有效的方法了:将字符串里的字符映射到[tex][0,NK-1][/tex],然后就可以开哈希表了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=16000005;
int length,k;
bool P[maxn];
unsigned int hash[maxn],x_pow[maxn];
unsigned int ns[maxn];
void InitHash(){
	register int i;
	for(i=length;i>=1;i--)
		hash[i]=ns[i]+hash[i+1]*k;
	x_pow[0]=1;
	for(i=1;i<=length;i++)
		x_pow[i]=x_pow[i-1]*k;
}
unsigned int Hash(int i,int L){
	return hash[i]-x_pow[L]*hash[i+L];
}
char s[maxn];
int a[128];
int main(){
	int n;
	register int i,j=0,ans=0;
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	length=strlen(s);
	for(i=0;i<length;i++){
		if(!a[s[i]]){
			a[s[i]]=j++;
		}
		if(j==k)
			break;
	}
	for(i=1;i<=length;i++){
		ns[i]=a[s[i-1]];
	}
	InitHash();
	for(i=1;i<=(length-n+1);i++){
		j=Hash(i,n);
		if(!P[j]){
			P[j]=true;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

[BZOJ 1468]Tree

2016年9月24日 14:06 | Comments(0) | Category:题解 | Tags:

点分治第一题……

这个也就是最经典的那个点分治问题了吧……参照qzc大爷的论文吧。

代码:

/**************************************************************
    Problem: 1468
    User: danihao123
    Language: C++
    Result: Accepted
    Time:816 ms
    Memory:2736 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 40005;
const int maxm = maxn * 2;
struct Edge {
    Edge *next;
    int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
    graph_cnt = 0;
    memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
    Edge *e = &pool[graph_cnt++];
    e->next = first[u];
    first[u] = e;
    e->to = v;
    e->dist = d;
}
 
int k;
int calc(vector<int>& V) {
    int size = V.size();
    int rc = size - 1;
    int ans = 0;
    if(size <= 1){
        return 0;
    }
    for(int i = 0; i < size; i++) {
        while(i < rc && V[i] + V[rc] > k) {
            rc--;
        }
        if(i == rc) {
            break;
        }
        ans += rc - i;
    }
    return ans;
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
    siz[x] = 1;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_siz(v, x);
            siz[x] += siz[v];
        }
    }
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
    bool OK = siz[x]*2 >= siz[now_root];
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            gen_best_root(v, x);
            OK = OK && (siz[v]*2 <= siz[now_root]);
        }
    }
    if(OK) {
        best_root = x;
    }
}
void add_to_V(int x, int fa, int d, vector<int>& V) {
    V.push_back(d);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(!vis[v] && v != fa) {
            add_to_V(v, x, d + e->dist, V);
        }
    }
}
int divide(int x) {
    gen_siz(x, 0);
    now_root = x;
    gen_best_root(x, 0);
    x = best_root;
    vis[x] = true;
    vector<int> V, CV;
    int ans = 0;
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        CV.clear();
        add_to_V(v, x, e->dist, CV);
        sort(CV.begin(), CV.end());
        ans -= calc(CV);
        for(int i = 0; i < CV.size(); i++) {
            V.push_back(CV[i]);
        }
    }
    V.push_back(0);
    sort(V.begin(), V.end());
    ans += calc(V);
    for(Edge *e = first[x]; e; e = e->next) {
        int v = e->to;
        if(vis[v]) {
            continue;
        }
        ans += divide(v);
    }
    return ans;
}
 
int main() {
    int n;
    scanf("%d", &n);
    clear_graph();
    for(int i = 1; i <= (n - 1); i++) {
        int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        add_edge(u, v, d);
        add_edge(v, u, d);
    }
    scanf("%d", &k);
    printf("%d\n", divide(1));
    return 0;
}

[BZOJ 1051]受欢迎的牛

2016年9月23日 13:06 | Comments(0) | Category:题解 | Tags:

Tarjan缩点第一题……

很容易想到找出度为0的点(当且仅当这样的点有一个时有解),但是在有环图上这个方法会失效。

处理方法是,用Tarjan的强联通分量算法求出所有SCC,然后把每个SCC缩成一个点,然后再在缩点之后的图上求解即可(这个图是DAG。原因很简单,要是有环还能接着缩)。

代码:

/**************************************************************
    Problem: 1051
    User: danihao123
    Language: C++
    Result: Accepted
    Time:72 ms
    Memory:1692 kb
****************************************************************/
 
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
    graph_cnt++;
    next[graph_cnt]=first[u];
    first[u]=graph_cnt;
    to[graph_cnt]=v;
}
 
int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
    dfs_clk++;
    pre[x]=low[x]=dfs_clk;
    S.push(x);
    int i,u;
    for(i=first[x];i;i=next[i]){
        u=to[i];
        if(!pre[u]){
            dfs(u);
            low[x]=min(low[x],low[u]);
        }else{
            if(!sccno[u])
                low[x]=min(low[x],pre[u]);
        }
    }
    if(low[x]==pre[x]){
        scc_cnt++;
        sccsiz[scc_cnt]=0;
        while(true){
            u=S.top();
            S.pop();
            sccno[u]=scc_cnt;
            sccsiz[scc_cnt]++;
            if(u==x)
                break;
        }
    }
}
int n;
inline void Tarjan(){
    register int i;
    for(i=1;i<=n;i++)
        if(!pre[i])
            dfs(i);
}
 
bool Out[maxn];
int main(){
    int m,u,v;
    register int i,j,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        AddEdge(u,v);
    }
    Tarjan();
    for(i=1;i<=n;i++){
        for(j=first[i];j;j=next[j]){
            u=to[j];
            if(sccno[i]!=sccno[u])
                Out[sccno[i]]=true;
        }
    }
    for(i=1;i<=scc_cnt;i++){
        if(!Out[i]){
            if(ans){
                ans=0;
                break;
            }
            ans=sccsiz[i];
        }
    }
    if(n==1)
        ans=0;
    printf("%d\n",ans);
    return 0;
}