工业统计1-9工作报告

工业统计1-9工作报告

工业统计1-9月份工作汇报

一、工业产值统计完成情况

红星街道现有工业企业128家，其中：规模以上企业8家、规模以下企业35家，个体企业85家。1-9月份工业总产值64848万元、完成年度计划53%、与去年同期增幅10%；销售产值60361万元、比去年同期增长9.1%；其中：规模以上企业总产值43978万元、与去年同期增幅15%；规模以下企业总产值20870万元、比去年同期增长12%；规模以上企业销售产值40530万元、与去年同期增幅15%，规模下企业销售产值19831万元、比去年同期增长11%。二、工业经济运行主要特点

（1）8个规模企业，行业发展不均。其中：电力行业由于年初以来充沛的雨水，电力的产值迅猛增长，县电力公司产值18561万元，同比增长39%；其余七家行业不同，产值下降，同比负增长。

（2）规模以下工业平稳增长，全街道有七家规下小水电企业，雨水的充沛给这个行业带来较快的发展。此外，规下其他行业，如砂石料、砖等建材行业也取得了顺利的发展。

沈必林

201*年10月9日

扩展阅读：解题报告9——距离统计

IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

《距离统计》解题报告

1、

题目描述①

农夫约翰的邻居牧师有N个农场(2≤N≤40,000)，它们从1到N标号。有M条水平和竖直的不同长度(1到1000)的道路连接这些农场，下面是农场地图，农场标号为F1到F7，道路上的数字表示道路的长度：

139F13F42F7F6F320F27F5

每一个农场最多直接与4个农场相连，这4个农场分别在他的北面，南面，东面，西面。而且，农场只可能在道路的两端，一个农场可以在多条道路的端点上。没有两条道路相交，并且恰好有一条路径连接任意两个农场。

农夫约翰弄丢了农场的地图，现在他必须通过存在电脑里的信息重新绘制地图。电脑里的数据包含这样的行，一行描述一条道路：

Thereisaroadoflength10runningnorthfromFarm#23toFarm#17Thereisaroadoflength7runningeastfromFarm#1toFarm#17

农夫约翰提供了一个正整数K，(1≤K≤1,000,000,000)，他想要知道有多少个不同的农场对满足他们之间的距离最多是K（距离是指从一个农场到另一农场所要经过的总的道路长度）。你只需要输出这样的农场对的个数（不包含两个农场相同的农场对）。

输入文件：

第一行是一个用空格分开的两个数：N,M，分别代表农场数和道路数。第2行到第m+1行，每一行描述一条道路。一行包括3个整数F1，F2，L和一个”N”，”S”，”E”，”W”中的字符D。F1和F2表示道路连接的两个农场，L

①

题目来源：Usaco201*GreenContest

第1页共10页IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

是道路的长度。D是道路的方向（从农场F1到F2的）。

第M+2行是一个正整数K。输出文件：

第一行一个数，表示农场对的个数。输入样例761613E639E357S413N2420W472S10输出样例5

有5个点对满足条件：

1-4(3),4-7(2),1-7(5),3-5(7)和3-6(9)。

2、算法分析。

根据题目的描述：任意两个农场之间恰好有一条路径，这就暗示着，这些农场以及农场之间的道路形成了一棵树！如果先求出任意两点之间的路径，然后再判断，这个时间复杂度是O(n2)的。这个算法没有充分利用树的性质，而只是利用了图的稀疏性，才使求任意两点的距离只需要O(n2)了。但树不仅仅只是稀疏图，它是非常特殊的稀疏图。O(n2)的算法用到树上，实在是太浪费了。

上面的算法枚举了所有的点对，造成了复杂度非常高。而计数是不是就一定要枚举呢？不是的，但可以肯定地是，我们不能一个一个点对的判断能不能满足条件。但是，却能一堆一堆的判断！能比较少的时间内求出一大堆点对中有多少个能够满足条件。

在这里，考虑两堆点，两堆点都是一个连通的点集。他们之间用一条边分开，

第2页共10页IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

看下面的图：

SABTuv

现在要求出一个点在S，另一个点在T中的距离小于等于K的点对。点集S中的点u到点集T中的点v的距离dist(u,v)=dist(u,A)+dist(A,B)+dist(B,v)，其中A,B是唯一的一对相邻的不在同一个点集中的点。对于不同的u,v来说，dist(A,B)总是一个定值，所以，(u,v)应该满足条件dist(u,A)+dist(B,v)≤K-dist(A,B)。

对于同一个u来说，只需要求dist(B,v)≤k-dist(A,B)-dist(u,A)的点的个数，如果把T中的点按照到B的距离从小到大排好了序，那么通过二分就有效的求出了这些点的个数。如果树中总共有n个点，那么就只需要用约O(nlog2n)的时间判断出约O(n2)各点对。

判断了两个点分别在S和T中的点对后，就只剩下两个点都在S中、两个点都在T中的点对了。这样，S和T变成了互不相关的两个部分。原来的问题被分成了规模更小的子问题。这样就可以递归的求出在两个点都在S中和两个点都在T中的满足条件的点对的个数。

如果每一次都能够把S和T中的点分的比较均匀，那么就可以在有效的时间内得出解。如果不考虑树的特殊性，分得均匀是很难做到的。例如n-1个点都与另外的一个点连边，这个就很难分得均匀，算法的复杂度退化了很多，不会比原来的O(n2)的要优。

尽量不考虑树的特殊性，既然不能构造到一条边，把树分成两个基本相等的

第3页共10页IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

部分，那么，可以考虑这样的两个部分：

点集S和点集T包含了所有的点，他们有且仅有只有一个公共点：

TSAuv

上面的S和T共用了一个点A，那么在S中的点u（不是A）到在T中的点v（不是A）的距离dist(u,v)=dist(A,u)+dist(A,v)。那么，dist(A,v)≤k-dist(A,u)，这个也可以在排序后通过二分有效的得出答案。

那么，这样的集合划分能不能够分得均匀呢？

还是不考虑树的特殊性，不难发现，如果以一个点A作为根节点建树，它的儿子树中，有一棵树的节点的个数超过了[n/2]，那么，可以把根节点换成A的那个儿子。例如下面的图，要把根节点从A移到B。

AB

第4页共10页IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

这样做以后，就保证了根的每一个儿子形成的子树中，没有一棵树的节点个数超过了[n/2]。下面证明可以这些子树分成最多3个集合，使得每一个集合的子树的节点总数不超过[n/2]。

证明很容易，最初的集合就是每一棵子树就是一个集合，如果集合的个数大于等于4，那么就把这些集合分成两个大的集合，每一个集合中的集合的个数至少是2，那么一定有一个大的集合中节点的总数不超过[n/2]。那么可以把这个大的集合中的所有的集合合并成一个集合。那么，集合数就减少了。直到个数小于等于3为止。

那么在剩下的3个集合中，选择两个节点数较小的集合，把他们合并，这样根节点所有的儿子树就分成了两个集合，不难发现，节点数多的那个集合中的节点数不超过[2n/3]，而节点数少的那个集合的节点的个数不少于[n/3]。

[2n/3]与[n/3]算不算均匀呢？不管，来考虑复杂度。由于要求出一个点在S中另一个点在T中的距离小于等于K的点对的个数，这个需要把S和T中的点按照到A的距离排序，这个可以在O(nlog2n)的时间内实现，找到一个这样的A点和把子树分成集合，要用O(n)时间就可以实现了。考虑最坏的情况，每一次分治都把儿子点集分成了2n/3,n/3的两个点集，那么有n个点的树的复杂度f(n)满足：

f(n+1)=f(2n/3+1)+f(n/3+1)+O((n+1)log2(n+1))。

不难证明，nlog3nlog2n≤f(n)≤nlog3/2nlog2n，由于都只是差一个常数，所以分治的算法的的时间复杂度是O(nlog22n)。

这个算法相对于O(n2)已经优化了很多，但是，能不能变得跟低了？能不能利用这棵树的特殊性呢？还有待于继续挖掘……②

[参考文献]

《算法艺术与信息学竞赛》

刘汝佳黄亮著

[讨论]

与何林的讨论得出的是O(nlog2nlog2n)的算法，得知楼天成也是这个复杂度，

不过用基数排序后复杂度就是O(nlog2n)了。

②

可以用基数排序，但是那个复杂度已经与长度的范围有关了

第5页共10页IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

[感谢]

何林、金恺、楼天成

3、

程序

const

inputfile="dstats.in";outputfile="dstats.out";maxn=40000;var

n,m,maxlen,ans:longint;

node,first,count,max,list,dist:array[1..maxn]oflongint;visited:array[1..maxn]ofboolean;next:array[1..maxnshl1]oflongint;edge:array[0..maxnshl1,1..3]oflongint;

procedureinit;var

i,p:longint;begin

assign(input,inputfile);reset(input);readln(n,m);p:=0;

fori:=1tomdobegin

inc(p);readln(edge[p,1],edge[p,2],edge[p,3]);inc(p);

edge[p,1]:=edge[p-1,2];edge[p,2]:=edge[p-1,1];edge[p,3]:=edge[p-1,3];end;

readln(maxlen);close(input);

fori:=1tondonode[i]:=i;end;

proceduresort(l,r:longint);var

i,j,k,t:longint;begin

i:=l;j:=r;

k:=dist[node[(l+r)shr1]];whileiIOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

ifiIOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

i:=next[i]end;

ifr-l+1-count[k]>max[k]thenmax[k]:=r-l+1-count[k];ifmax[k]0dobegin

ifnotvisited[edge[i,2]]thensearch1(edge[i,2],t,dis+edge[i,3]);i:=next[i]endend;var

i,j,t,count1,count2:longint;begin

fori:=ltordobegin

visited[node[i]]:=false;first[node[i]]:=0end;

fori:=l1tor1dobegin

next[i]:=first[edge[i,1]];first[edge[i,1]]:=iend;

minmax:=maxlongint;search(node[l]);

fori:=ltordovisited[node[i]]:=false;search(w);

i:=first[w];j:=0;whilei>0dobegin

inc(j);list[j]:=edge[i,2];i:=next[i]end;

sortlist(1,j);

count1:=0;count2:=0;count[w]:=0;fori:=1tojdo

ifcount1IOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

inc(count1,count[list[i]]);count[list[i]]:=1end

elsebegin

inc(count2,count[list[i]]);count[list[i]]:=2end;

fori:=ltordovisited[node[i]]:=false;visited[w]:=true;dist[w]:=0;i:=first[w];

whilei>0dobegin

search1(edge[i,2],count[edge[i,2]],edge[i,3]);i:=next[i]end;

fori:=ltordoifnode[i]=wthenbreak;node[i]:=node[l];node[l]:=w;i:=l+1;j:=r;

whileiIOI201*国家集训队第3轮作业湖南省长沙市长郡中学栗师

fori:=l1tor1do

if(count[edge[i+1,1]]=2)or(count[edge[i+1,2]]=2)thenbreak;mid1:=i;getroot:=wend;

proceduregetans(l,r,l1,r1:longint);var

root,mid,mid1:longint;begin

ifl=rthenexit;ifl+1=rthenbegin

ifedge[l1,3]

友情提示：本文中关于《工业统计1-9工作报告》给出的范例仅供您参考拓展思维使用，工业统计1-9工作报告：该篇文章建议您自主创作。

来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。

《工业统计1-9工作报告》由互联网用户整理提供,转载分享请保留原作者信息,谢谢!
链接地址：http://www.bsmz.net/gongwen/647270.html

• 上一篇：关于沧州市商贸流通工作情况的报告
• 下一篇：钢贸企业贷款申请报告 1