HDU 5977 Garden of Eden [에덴동산]

전언

시간이 촉박하면 가장 관건적인 고차원 접두사와 부분만 쓴다

소개하다.

사실 나도 처음에 이런 것을 몰랐지만 나도 해냈다. 나 자신은 그를 하나의 dp로 생각했다. 왜냐하면 접두사와 그 자체가 가장 짧은 dp이기 때문이다.dp의 한 가지 사상은 우리가 반드시 dp[i][j]가 미지의 것이라고 충분히 가정해야 한다는 것이다. 그러나 이 상태를 내놓는 식은 이미 알고 있다. 비록 이런 상태를 내놓는 식 자체는 구할 수 없다고 생각하지만.아주 간단합니다. 바로 dp를 요구합니다. [(1010...)2] d p [ ( 1010... ) 2] 이러한 식의 값은 괄호 안의 이진수의 출현 횟수와 이진수의 임의의 1개 또는 여러 위치의 0이 1이 되는 새로운 이진수의 출현 횟수의 합을 의미한다.(좀 까다롭다).가령 이 2진수(1010)2(1010)2라고 가정하면 모든 2진수의 최고위를 4위로 한정한다면 지금 이 식은 구할 필요가 없다. 만약에 한 자리를 더 늘려 5위로 한다면 그가 표시한 것은 사실 dp[(01010)2] dp[(01010)2]의 상태이고 dp[(11010) 2] dp[(110) 2]의 값을 더하면 된다.이것도 혹은 욕심에 나타난다.복잡도 O(nlogn);

제면

아침 일찍 와서 국수를 보충하다.모든 색을 포함하는 나무의 경로를 구하는 것이다.점마다 색깔이 있어요.

해법

점수는 생각하지 마세요.이 문제의 유일한 난점은 위에서 이미 말했는데, 유일한 세부 사항은 바로 점에 있는 권이다. 권점의 순서를 자세히 생각해 보자.구체적인 조작은 코드를 보아라.

코드

#include
#define LL long long
using namespace std;
const int _ =5e4+4,INF = 2e9;
struct edge{
    int to,nt;
}e[_<<1];
int head[_],size[_],root;
bool vis[_];
int n,k,cnt,all,MX,K,col[_];
LL ans,tong1[1025],tong2[1025];
inline void add(register int a,register int b){
    e[++cnt].to=a,e[cnt].nt=head[b],head[b]=cnt;
}
void getroot(register int now,register int fa){
    int mx=0;size[now]=1;
    for(register int i=head[now];i;i=e[i].nt){
        if(vis[e[i].to]||e[i].to==fa)continue;
        getroot(e[i].to,now);
        size[now]+=size[e[i].to];
        if(size[e[i].to]>mx)mx=size[e[i].to];
    }
    mx=max(mx,all-size[now]);
    if(MX>mx)root=now,MX=mx;
    return;
}
void dfs(register int now,register int fa,register int len){
    for(register int i=head[now];i;i=e[i].nt){
        if(e[i].to==fa)continue;
        if(vis[e[i].to])continue;
        tong1[len|(1<1<1<inline LL getdis(register int now,register int len){
    tong1[(1<1<0,(1<//cout<
    /*for(register int i=0;i<=K;++i){
        cout<
    for(register int i=0;ifor(register int j=K;j>=0;--j){
            if(!((1<1<0;
    for(register int i=0;i<=K;++i)ret+=tong1[i]*(tong2[(i^K)]);
    //ret+=tong1[k]*(tong2[0]-1);
    for(register int i=0;i<=K;++i)tong1[i]=tong2[i]=0;
    //cout<
    return ret;
}
void divide(register int now){
    vis[now]=1;
    ans+=getdis(now,0);
    for(register int i=head[now];i;i=e[i].nt){
        if(vis[e[i].to])continue;
        ans-=getdis(e[i].to,(1<int main(){
    //freopen("data.in","r",stdin);
    while(~scanf("%d%d",&n,&k)){

        memset(head,0,sizeof(head));
        K=(1<1;
        memset(vis,0,sizeof(vis));cnt=0;ans=0;
        for(register int i=1;i<=n;++i)scanf("%d",&col[i]),col[i]--;
        for(register int i=1;iregister int a,b;
            scanf("%d%d",&a,&b);
            add(a,b);add(b,a);
        }
        all=n;MX=INF;
        getroot(1,0);

        divide(root);
        printf("%lld
",ans);
    }
    return 0;
}

총결산

YCB가 조금 딱딱하지 않은 점분치를 추천해 주셔서 감사합니다. 저와 같은 고구마가 딱 맞습니다.