荟聚奇文、博采众长、见贤思齐
当前位置:公文素材库 > 报告体会 > 工作报告 > 工业统计1-9工作报告

工业统计1-9工作报告

网站:公文素材库 | 时间:2019-05-29 02:12:36 | 移动端:工业统计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
相关文章