暴力搜索是3^n,过不了。

但是我们可以使用折半搜索。

开个map存一下即可。

#include<bits/stdc++.h>
#define LL long long
#define N 30
#define re register
using namespace std;
LL read()
{
    LL x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
int n;LL need;
LL a[N],b[N],c[N];
LL ans=0;int m;
map<LL,int>ma;
LL quick(re LL a,re LL x)
{
    re LL res=1;
    while(x)
    {
        if(x&1)res=res*a;
        a=a*a;x>>=1;
    }
    return res;
}
void dfs(re int x,re LL sum)
{
    if(x==m+1)
    {
        if(!ma.count(sum))ma[sum]=1;
        else ma[sum]++;
        return;
    }
    if(sum>need)return;
    if(sum==need){ans++;return;}
    dfs(x+1,sum);
    dfs(x+1,sum+a[x]);
    dfs(x+1,sum+b[x]);
}
void dfs2(re int x,re LL sum)
{
    if(x==n+1)
    {
        ans+=ma[need-sum];
        return;
    }
    if(sum>need)return;
    if(sum==need){ans++;return;}
    dfs2(x+1,sum);
    dfs2(x+1,sum+a[x]);
    dfs2(x+1,sum+b[x]);
}
int main()
{
    freopen("building.in","r",stdin);
    freopen("building.out","w",stdout);
    n=read();need=read();m=(n>>1)+(n&1);
    for(re int i=1;i<=n;++i)a[i]=read();
    for(re int i=1;i<=n;++i)
    {
        LL x=a[i];
        re int num=0;
        while(x)
        {
            if(x&1)num++;
            x>>=1;
        }
        b[i]=quick(2,num);
    }
    dfs(1,0);dfs2(m+1,0);
    printf("%lld\n",ans);
}
/*
20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/
T1

重点是找到性质!(做题一定要抓住本质)。

#include<bits/stdc++.h>
#define LL long long
#define N 200003
#define M 300003
#define INF 300000000000003
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
struct EDEG{
    int nextt,to;
}w[M];
struct edge{
    int x,y,v;
}e[M];
int tot=0;
int n,m;
int head[N],vis[N];
void add(int a,int b)
{
    tot++;
    w[tot].nextt=head[a];
    w[tot].to=b;
    head[a]=tot;
}
int cnt=0,top=0,timer=0;
int dfn[N],low[N],stackk[N];
void tarjan(int x)
{
    dfn[x]=low[x]=++timer;
    vis[x]=1;
    stackk[++top]=x;
    for(int i=head[x];i;i=w[i].nextt)
    {
        int v=w[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(vis[v])low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x])
    {
        int siz=0;
        int t;
        do{
            t=stackk[top--];
            vis[t]=0;
            siz++;
        }while(t!=x);
        if(siz>=2)cnt++;
    }
}
LL ans=INF;
bool check(int mid)
{
    for(int i=1;i<=n;++i)head[i]=0,vis[i]=0,dfn[i]=0,low[i]=0,stackk[i]=0;
    cnt=0;top=0;timer=0;tot=0;
    for(int i=1;i<=m;++i)
      if(e[i].v>mid)add(e[i].x,e[i].y);
    for(int i=1;i<=n;++i)
      if(!dfn[i])tarjan(i);
    if(cnt)return 0;
    else return 1;
}
int main()
{
    freopen("pestc.in","r",stdin);
    freopen("pestc.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;++i)
      e[i].x=read(),e[i].y=read(),e[i].v=read();
    int l=0,r=1000000005;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid;
        else l=mid+1;
    }
    printf("%d\n",ans);
}
/*
*/
T2

dsu on tree可做。然后我代码里打了所有的数据点。

#include<bits/stdc++.h>
#define LL long long
#define N 200003
#define INF 300000000000003
#define re register
using namespace std;
LL read()
{
    LL x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
struct EDEG{
    int nextt,to;
}w[N*2];
int tot=0;
int n;
int head[N],ans[N][5],fa[N],a[N],b[N],du[N],son[N],tong[N],siz[N];
int c[N];
void add(int a,int b)
{
    tot++;
    w[tot].nextt=head[a];
    w[tot].to=b;
    head[a]=tot;
}
int query(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=x&(-x);
    }
    return ans;
}
void modify(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=x&(-x);
    }
}
void work1()
{
    for(re int i=2;i<=n;++i)
    {
        int x=fa[i];
        while(x!=0)
        {
            if(a[x]>a[i])ans[x][1]++;
            else if(a[x]==a[i])ans[x][2]++;
            else ans[x][3]++;
            x=fa[x];
        }
    }
    for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);
}
void work2()
{
    int num=0;
    for(re int i=1;i<=n;++i)
    {
        if(!son[i])
        {
            modify(a[i],1);
            tong[a[i]]++;
            num++;
            re int x=fa[i];
            while(x!=0)
            {
                 ans[x][2]+=tong[a[x]];
                 ans[x][1]+=query(a[x]-1);
                 ans[x][3]+=num-ans[x][2]-ans[x][1];
                 tong[a[x]]++;
                 modify(a[x],1);
                 num++;
                 x=fa[x];
            }
        }
    }
    for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);
}
void work3()
{
    for(re int i=2;i<=n;++i)
    {
        if(a[i]<a[1])ans[1][1]++;
        else if(a[i]==a[1])ans[1][2]++;
        else ans[1][3]++;
    }
    for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);
}
void dfs1(re int x)
{
    siz[x]=1;re int maxson=0;
    for(re int i=head[x];i;i=w[i].nextt)
    {
        re int v=w[i].to;
        dfs1(v);
        if(siz[v]>maxson)maxson=siz[v],son[x]=v;
        siz[x]+=siz[v];
    }
}
int SON;
void update(re int x,re int k)
{
    /*ans[x][2]+=tong[a[x]];
    ans[x][3]+=query(a[x]-1);
    ans[x][1]+=n-ans[x][2]-ans[x][3];*/

    for(re int i=head[x];i;i=w[i].nextt)
    {
        re int v=w[i].to;
        if(v==SON)continue;
        modify(a[v],k);
        tong[a[v]]+=k;
        update(v,k);
    }
}
void dfs2(re int x,re int op)
{
    for(re int i=head[x];i;i=w[i].nextt)
    {
        re int v=w[i].to;
        if(v==son[x])continue;
        dfs2(v,0);
    }
    if(son[x])dfs2(son[x],1),SON=son[x],modify(a[son[x]],1),tong[a[son[x]]]++;
    update(x,1);SON=0;
    ans[x][2]+=tong[a[x]];
    ans[x][1]+=query(a[x]-1);
    ans[x][3]+=siz[x]-1-ans[x][2]-ans[x][1];
    //
    if(!op)update(x,-1);
}
void work4()
{
    sort(b+1,b+1+n);
    int num=unique(b+1,b+1+n)-(b+1);
    for(re int i=1;i<=n;++i)
      a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    //for(int i=1;i<=n;++i)printf("!!%d\n",a[i]); 
    for(re int i=2;i<=n;++i)add(fa[i],i);
    memset(son,0,sizeof(son));
    dfs1(1);dfs2(1,1);
    for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]);
}
int main()
{
    freopen("ginkgo.in","r",stdin);
    freopen("ginkgo.out","w",stdout);
    n=read();
    for(re int i=2;i<=n;++i)fa[i]=read(),son[fa[i]]++,du[fa[i]]++,du[i]++;
    for(re int i=1;i<=n;++i)b[i]=a[i]=read();
    if(n<=1000){work1();return 0;}
    int flagg1=0,flagg2=0;
    for(re int i=1;i<=n;++i)
    {
        if(du[i]>2)flagg1=1;
        if(du[i]==n-1)flagg2=1;
    }
    if(!flagg1){work2();return 0;}
    if(flagg2){work3();return 0;}
    work4();
}
/*
5
1 1 1 1
1 1 1 1 1

3
1 2
1 2 3

3
1 1
1 1 1
*/
T3dsu on tree

其实开桶也并不需要用启发式合并。

每次进入子树前记录一下桶里的值,出来的时候减去即可。

然鹅题解里的算法比较神奇。

因为一个求小于,一个求等于,所以开了两个树状数组。

01-10 14:27