求助常数QAQ

回复帖子

@vectorwyx  2021-01-14 00:10 回复

RT,我的代码在#4 TLE了,但其他点都跑的很快,不知道为啥。有大佬愿意看一下我的代码是否有某个地方有漏洞或者说给几个比较有效的卡常方法吗QAQ,万分感谢!

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;
inline int read(){ int x=0,fh=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') fh=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*fh; }

const int N=1e5+5,lmq=1e9+7;
struct Edge{
    int to,next;
}e[N<<1];
int head[N],tot,n,k,dp[N][105][4],siz[N];
//dp[i][j][0/1/2/3]用j个监听器覆盖以i为根的子树,且i放父不放、i放父放、i不放父不放、i不放父放的方案数 

void connect(int x,int y){
    e[++tot]=(Edge){y,head[x]};
    head[x]=tot; 
}

void dfs(int now,int from){
//  printf("dfs(%d,%d)\n",now,from);
    int cnt=1;
    siz[now]=1;
    for(int i=head[now];i;i=e[i].next){
        int p=e[i].to;
        if(p==from) continue;
        ++cnt;
        dfs(p,now);
    }
    const int M=105;
    int f0[M]={1},f1[M]={1},f2[M]={1},f3[M]={1};
    //f0:前i棵子树放j个 ,每棵子树的根结点放不放无所谓 
    //f1:前i棵子树放j个,但每棵子树的根结点都不放 
    //0:i放父不放 1:i不放父不放 2:i不放父放 3:i放父放 
    //f0[0]=f1[0]=f2[0]=f3[0]=1;
    //printf("%d:\n",now);
    for(int i=head[now];i;i=e[i].next){
        int p=e[i].to;
        if(p==from) continue;
        //puts("AC");
        siz[now]+=siz[p];
        int lim=min(k,siz[p]);
        go(j,min(k,siz[now]),0){
            f0[j]=f0[j]*(dp[p][0][3]+dp[p][0][2]);
            f1[j]=f1[j]*dp[p][0][1];
            f2[j]=f2[j]*(dp[p][0][0]+dp[p][0][1]);
            f3[j]=f3[j]*dp[p][0][2];
            fo(w,1,min(j,lim)){
                //f0:i放,i的父放 
                f0[j]=(f0[j]+f0[j-w]*(0ll+dp[p][w][3]+dp[p][w][2]))%lmq;
                //f1:i不放,i的父不放,i的儿子们也全都不放 
                f1[j]=(f1[j]+1ll*f1[j-w]*dp[p][w][1])%lmq;
                //f2:i不放,父放 
                f2[j]=(f2[j]+1ll*f2[j-w]*(dp[p][w][0]+dp[p][w][1]))%lmq;
                //f3:i放,i的父不放,i的儿子们也全都不放 
                f3[j]=(f3[j]+1ll*f3[j-w]*dp[p][w][2])%lmq;
            }           
        }
        //cout<<"f3:";fo(j,0,min(k,siz[now])) printf("%d ",f3[j]);puts("");
    }
    //0:i放父不放 1:i不放父不放 2:i不放父放 3:i放父放
    int w=min(siz[now],k);
    fo(j,1,w) dp[now][j][0]=(f0[j-1]-f3[j-1]+lmq)%lmq,dp[now][j][3]=f0[j-1];
    fo(j,0,w) dp[now][j][1]=(f2[j]-f1[j]+lmq)%lmq,dp[now][j][2]=f2[j];
    if(siz[now]==1){
        dp[now][1][0]=dp[now][0][1]=0;
        dp[now][0][2]=dp[now][1][3]=1;
    }else if(siz[now]==cnt){
        dp[now][0][1]=dp[now][0][2]=dp[now][1][0]=0;
        dp[now][1][3]=1;
    }else dp[now][0][1]=dp[now][0][2]=dp[now][1][0]=dp[now][1][3]=0;
}

int main(){
    cin>>n>>k;
    fo(i,1,n-1){
        int x=read(),y=read();
        connect(x,y);
        connect(y,x);
    }
    dfs(1,0);
    cout<<(dp[1][k][0]+dp[1][k][1])%lmq;
    return 0;
}
/*
-------------------------------------------------
*/
@oisdoaiu  2021-01-14 08:17 回复 举报

玄学卡常(雾

int dec(int a, int b){
    a-=b;
    if(a<0) a+=MOD;
    return a;
}
@Flying_Bird  2021-01-14 11:04 回复 举报

这一段改成这样试一试:

fo(w,max(1,j-siz[now]+siz[p]),min(j,lim)){
                //f0:i放,i的父放 
                f0[j]=(f0[j]+f0[j-w]*(0ll+dp[p][w][3]+dp[p][w][2]))%lmq;
                //f1:i不放,i的父不放,i的儿子们也全都不放 
                f1[j]=(f1[j]+1ll*f1[j-w]*dp[p][w][1])%lmq;
                //f2:i不放,父放 
                f2[j]=(f2[j]+1ll*f2[j-w]*(dp[p][w][0]+dp[p][w][1]))%lmq;
                //f3:i放,i的父不放,i的儿子们也全都不放 
                f3[j]=(f3[j]+1ll*f3[j-w]*dp[p][w][2])%lmq;
            }

@vectorwyx

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。