bzoj4543[POI2014]Hotel

摘要:
标题链接bzoj4543[POI2014]酒店解决方案不是一个简单的问题。我很傻。它真的是n^2。这不是某人的问题~有趣~枚举点被转换为无根树。暴力子树中点的深度计数传递使abcd被称为四子树。然后向下推一个深度为k、数量为e的新子树。子树由s保持,s的传递由cnt保持;代码#include#include#includeinline read(){intx=0,f=1;charc=getchar();while{iff=-1;c=getchar();}while x=x*10+c“0”,c=getchar();返回x*f;}intn;组成最大值=5007;结构节点{intv,next;节点:v,next{};}边缘[maxn˂˂1];intnum,头[maxn];inlinevoidadd_edge{edge[++num]=节点;head[u]=num;}intdp[maxn][maxn];intdeep[maxn],mx=0,cnt[maxn},tmp[maxn]s[maxn];voiddfs{tmp[deep[x]]++;mx=std::max;对于{intv=edge[i].v;ifcontinue;deep[v]=deep[x]+1;dfs(v,x);}}intmain(){n=read();对于{u=read(,v=read);add_edge(u,v);add-edge(v,u);}longlonglongentans=0;对于{intv=edge[j].v;mx=0;deep[v]=1;dfs(v,i);对于{ans+=s[k]*tmp[k];s[k]+=tmp[k]*cnt[k],cnt[k+=tmp[k];tmp[k]=0;}}memset;内存集;}输出函数return0;}

题目链接

bzoj4543 [POI2014]Hotel

题解

这不是裸地点分嘛 ,我真傻,真的
n^2 这不是是sb题,~滑稽 ~
枚举点转换为无根树,暴力子树中点的深度
计数转移
令a b c d为已知四颗子树,则新来一颗深度为k的点数为e的子树
推下式子
(new_ans=e*(a*b+a*c+b*c+d*a+d*b+d*c))
用s维护 ((a*b+a*c+b*c+d*a+d*b+d*c .....))
用cnt维护((a+b+c+d+e+....))
s的转移为 (s + cnt * tmp);

代码

#include<algorithm>
#include<cstring>
#include<cstdio>
inline int read() {
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c >'9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
    return x * f;
}
int n;
const int maxn = 5007;
struct Node {
    int v,next;
    Node(int a = 0,int b = 0):  v(a),next(b) {};
}edge[maxn << 1];
int num,head[maxn];
inline void add_edge(int u,int v) {
    edge[++num] = Node(v,head[u]);head[u] = num;
} 
int dp[maxn][maxn]; 
int deep[maxn],mx = 0,cnt[maxn],tmp[maxn],s[maxn];
void dfs(int x,int fa) { 
    tmp[deep[x]] ++;
    mx = std::max(mx,deep[x]);
    for(int i = head[x];i;i = edge[i].next) {
        int v = edge[i].v;
        if(v == fa) continue;
        deep[v] = deep[x] + 1;
        dfs(v,x);
    }
}
int main() { 
    n = read(); 
    for(int u,v,i = 1;i < n;++ i) { 
        u = read() , v = read(); 
        add_edge(u,v);add_edge(v,u); 
    }
    long long int ans = 0;
    for(int i = 1;i <= n;++ i) {
        for(int j = head[i];j;j = edge[j].next) {
            int v = edge[j].v;
            mx = 0;
            deep[v] = 1;
            dfs(v,i);
            for(int k = 1;k <= mx;++ k) {  
                ans += s[k] * tmp[k]; 
                s[k] += tmp[k] * cnt[k]; 
                cnt[k] += tmp[k];
                tmp[k] = 0;
            }
        }
        memset(s,0,sizeof s);
        memset(cnt,0,sizeof cnt);
    }
    printf("%lld
",ans);
    return 0;	
}

免责声明:文章转载自《bzoj4543[POI2014]Hotel》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇bzoj1079[SCOI2008]着色方案luogu P1026 统计单词个数下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

一個傳統的C2C網站的用戶充值的过程

#region 插入用户汇款充值记录 public void UserRemittance(UserAccountRecord userAccountRecord, WebBankAccountRecord webBankAccountRecord) { /// <...

Simple HTTP Proxy Server Implementation, based on wcol Projects Michael Vorburger's Private Homepage

Simple HTTP Proxy Server Implementation, based on wcol - Projects - Michael Vorburger's Private Homepage PROJECTNAME HTTPProxy Server DATE& STATUS Clickherefor more informat...

Boost Getting Started on Unix Variants

Boost Getting Started on Unix Variants Getting Started on Unix Variants Index 1Get Boost 2The Boost Distribution 3Header-Only Libraries 4Build a Simple Program Using Boost4....

Linux创建用户、设置密码、修改用户、删除用户命令

与大家分享下Linux系统中创建用户、设置密码、修改用户、删除用户的命令,希望对你有所帮助。 useradd testuser 创建用户testuserpasswd testuser 给已创建的用户testuser设置密码说明:新创建的用户会在/home下创建一个用户目录testuserusermod --help 修改用户这个命令的相关参数user...

MFC中对话框的数据交换(DDX)和数据校验(DDV)

MFC中对话框的数据交换(DDX)和数据校验(DDV)<reference MFC TNO 26>DDX : dialog data exchangeDDV : dialog data validation文档描述MFC中的DDX DDV机制,如何使用DDX_和DDV_ 函数和定制自己的DDX_ ,DDV_函数; Dialog Data Exch...

【已解决】phpMyAdmin中导入mysql数据库文件时出错:您可能正在上传很大的文件,请参考文档来寻找解决办法...

期间,用phpMyAdmin去导入90M左右的mysql数据库文件时出错: 您可能正在上传很大的文件,请参考文档来寻找解决方法。 【解决过程】 1.很明显,是文件太大,无法导入。即上传文件大小有限制。 所以要去解除此限制。 之前其实也遇到类似的问题,之前就解决了。 这次只是再去找到对应的配置的地方,修改配置,应该就可以了。...