工業(yè)統(tǒng)計1-9工作報告

工業(yè)統(tǒng)計1-9月份工作匯報

一、工業(yè)產(chǎn)值統(tǒng)計完成情況

紅星街道現(xiàn)有工業(yè)企業(yè)128家，其中：規(guī)模以上企業(yè)8家、規(guī)模以下企業(yè)35家，個體企業(yè)85家。1-9月份工業(yè)總產(chǎn)值64848萬元、完成年度計劃53%、與去年同期增幅10%；銷售產(chǎn)值60361萬元、比去年同期增長9.1%；其中：規(guī)模以上企業(yè)總產(chǎn)值43978萬元、與去年同期增幅15%；規(guī)模以下企業(yè)總產(chǎn)值20870萬元、比去年同期增長12%；規(guī)模以上企業(yè)銷售產(chǎn)值40530萬元、與去年同期增幅15%，規(guī)模下企業(yè)銷售產(chǎn)值19831萬元、比去年同期增長11%。二、工業(yè)經(jīng)濟(jì)運行主要特點

（1）8個規(guī)模企業(yè)，行業(yè)發(fā)展不均。其中：電力行業(yè)由于年初以來充沛的雨水，電力的產(chǎn)值迅猛增長，縣電力公司產(chǎn)值18561萬元，同比增長39%；其余七家行業(yè)不同，產(chǎn)值下降，同比負(fù)增長。

（2）規(guī)模以下工業(yè)平穩(wěn)增長，全街道有七家規(guī)下小水電企業(yè)，雨水的充沛給這個行業(yè)帶來較快的發(fā)展。此外，規(guī)下其他行業(yè)，如砂石料、磚等建材行業(yè)也取得了順利的發(fā)展。

沈必林

201*年10月9日

擴(kuò)展閱讀：解題報告9——距離統(tǒng)計

IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

《距離統(tǒng)計》解題報告

1、

題目描述①

農(nóng)夫約翰的鄰居牧師有N個農(nóng)場(2≤N≤40,000)，它們從1到N標(biāo)號。有M條水平和豎直的不同長度(1到1000)的道路連接這些農(nóng)場，下面是農(nóng)場地圖，農(nóng)場標(biāo)號為F1到F7，道路上的數(shù)字表示道路的長度：

139F13F42F7F6F320F27F5

每一個農(nóng)場最多直接與4個農(nóng)場相連，這4個農(nóng)場分別在他的北面，南面，東面，西面。而且，農(nóng)場只可能在道路的兩端，一個農(nóng)場可以在多條道路的端點上。沒有兩條道路相交，并且恰好有一條路徑連接任意兩個農(nóng)場。

農(nóng)夫約翰弄丟了農(nóng)場的地圖，現(xiàn)在他必須通過存在電腦里的信息重新繪制地圖。電腦里的數(shù)據(jù)包含這樣的行，一行描述一條道路：

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

農(nóng)夫約翰提供了一個正整數(shù)K，(1≤K≤1,000,000,000)，他想要知道有多少個不同的農(nóng)場對滿足他們之間的距離最多是K（距離是指從一個農(nóng)場到另一農(nóng)場所要經(jīng)過的總的道路長度）。你只需要輸出這樣的農(nóng)場對的個數(shù)（不包含兩個農(nóng)場相同的農(nóng)場對）。

輸入文件：

第一行是一個用空格分開的兩個數(shù)：N,M，分別代表農(nóng)場數(shù)和道路數(shù)。第2行到第m+1行，每一行描述一條道路。一行包括3個整數(shù)F1，F(xiàn)2，L和一個”N”，”S”，”E”，”W”中的字符D。F1和F2表示道路連接的兩個農(nóng)場，L

①

題目來源：Usaco201*GreenContest

第1頁共10頁IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

是道路的長度。D是道路的方向（從農(nóng)場F1到F2的）。

第M+2行是一個正整數(shù)K。輸出文件：

第一行一個數(shù)，表示農(nóng)場對的個數(shù)。輸入樣例761613E639E357S413N2420W472S10輸出樣例5

有5個點對滿足條件：

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

2、算法分析。

根據(jù)題目的描述：任意兩個農(nóng)場之間恰好有一條路徑，這就暗示著，這些農(nóng)場以及農(nóng)場之間的道路形成了一棵樹！如果先求出任意兩點之間的路徑，然后再判斷，這個時間復(fù)雜度是O(n2)的。這個算法沒有充分利用樹的性質(zhì)，而只是利用了圖的稀疏性，才使求任意兩點的距離只需要O(n2)了。但樹不僅僅只是稀疏圖，它是非常特殊的稀疏圖。O(n2)的算法用到樹上，實在是太浪費了。

上面的算法枚舉了所有的點對，造成了復(fù)雜度非常高。而計數(shù)是不是就一定要枚舉呢？不是的，但可以肯定地是，我們不能一個一個點對的判斷能不能滿足條件。但是，卻能一堆一堆的判斷！能比較少的時間內(nèi)求出一大堆點對中有多少個能夠滿足條件。

在這里，考慮兩堆點，兩堆點都是一個連通的點集。他們之間用一條邊分開，

第2頁共10頁IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

看下面的圖：

SABTuv

現(xiàn)在要求出一個點在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)應(yīng)該滿足條件dist(u,A)+dist(B,v)≤K-dist(A,B)。

對于同一個u來說，只需要求dist(B,v)≤k-dist(A,B)-dist(u,A)的點的個數(shù)，如果把T中的點按照到B的距離從小到大排好了序，那么通過二分就有效的求出了這些點的個數(shù)。如果樹中總共有n個點，那么就只需要用約O(nlog2n)的時間判斷出約O(n2)各點對。

判斷了兩個點分別在S和T中的點對后，就只剩下兩個點都在S中、兩個點都在T中的點對了。這樣，S和T變成了互不相關(guān)的兩個部分。原來的問題被分成了規(guī)模更小的子問題。這樣就可以遞歸的求出在兩個點都在S中和兩個點都在T中的滿足條件的點對的個數(shù)。

如果每一次都能夠把S和T中的點分的比較均勻，那么就可以在有效的時間內(nèi)得出解。如果不考慮樹的特殊性，分得均勻是很難做到的。例如n-1個點都與另外的一個點連邊，這個就很難分得均勻，算法的復(fù)雜度退化了很多，不會比原來的O(n2)的要優(yōu)。

盡量不考慮樹的特殊性，既然不能構(gòu)造到一條邊，把樹分成兩個基本相等的

第3頁共10頁IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

部分，那么，可以考慮這樣的兩個部分：

點集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)，這個也可以在排序后通過二分有效的得出答案。

那么，這樣的集合劃分能不能夠分得均勻呢？

還是不考慮樹的特殊性，不難發(fā)現(xiàn)，如果以一個點A作為根節(jié)點建樹，它的兒子樹中，有一棵樹的節(jié)點的個數(shù)超過了[n/2]，那么，可以把根節(jié)點換成A的那個兒子。例如下面的圖，要把根節(jié)點從A移到B。

AB

第4頁共10頁IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

這樣做以后，就保證了根的每一個兒子形成的子樹中，沒有一棵樹的節(jié)點個數(shù)超過了[n/2]。下面證明可以這些子樹分成最多3個集合，使得每一個集合的子樹的節(jié)點總數(shù)不超過[n/2]。

證明很容易，最初的集合就是每一棵子樹就是一個集合，如果集合的個數(shù)大于等于4，那么就把這些集合分成兩個大的集合，每一個集合中的集合的個數(shù)至少是2，那么一定有一個大的集合中節(jié)點的總數(shù)不超過[n/2]。那么可以把這個大的集合中的所有的集合合并成一個集合。那么，集合數(shù)就減少了。直到個數(shù)小于等于3為止。

那么在剩下的3個集合中，選擇兩個節(jié)點數(shù)較小的集合，把他們合并，這樣根節(jié)點所有的兒子樹就分成了兩個集合，不難發(fā)現(xiàn)，節(jié)點數(shù)多的那個集合中的節(jié)點數(shù)不超過[2n/3]，而節(jié)點數(shù)少的那個集合的節(jié)點的個數(shù)不少于[n/3]。

[2n/3]與[n/3]算不算均勻呢？不管，來考慮復(fù)雜度。由于要求出一個點在S中另一個點在T中的距離小于等于K的點對的個數(shù)，這個需要把S和T中的點按照到A的距離排序，這個可以在O(nlog2n)的時間內(nèi)實現(xiàn)，找到一個這樣的A點和把子樹分成集合，要用O(n)時間就可以實現(xiàn)了。考慮最壞的情況，每一次分治都把兒子點集分成了2n/3,n/3的兩個點集，那么有n個點的樹的復(fù)雜度f(n)滿足：

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

不難證明，nlog3nlog2n≤f(n)≤nlog3/2nlog2n，由于都只是差一個常數(shù)，所以分治的算法的的時間復(fù)雜度是O(nlog22n)。

這個算法相對于O(n2)已經(jīng)優(yōu)化了很多，但是，能不能變得跟低了？能不能利用這棵樹的特殊性呢？還有待于繼續(xù)挖掘……②

[參考文獻(xiàn)]

《算法藝術(shù)與信息學(xué)競賽》

劉汝佳黃亮著

[討論]

與何林的討論得出的是O(nlog2nlog2n)的算法，得知樓天成也是這個復(fù)雜度，

不過用基數(shù)排序后復(fù)雜度就是O(nlog2n)了。

②

可以用基數(shù)排序，但是那個復(fù)雜度已經(jīng)與長度的范圍有關(guān)了

第5頁共10頁IOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

[感謝]

何林、金愷、樓天成

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*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

ifiIOI201*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

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*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

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*國家集訓(xùn)隊第3輪作業(yè)湖南省長沙市長郡中學(xué)栗師

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]

友情提示：本文中關(guān)于《工業(yè)統(tǒng)計1-9工作報告》給出的范例僅供您參考拓展思維使用，工業(yè)統(tǒng)計1-9工作報告：該篇文章建議您自主創(chuàng)作。

來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時刪除。

《工業(yè)統(tǒng)計1-9工作報告》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請保留原作者信息,謝謝!
鏈接地址：http://www.7334dd.com/gongwen/647270.html

• 上一篇：關(guān)于滄州市商貿(mào)流通工作情況的報告
• 下一篇：鋼貿(mào)企業(yè)貸款申請報告 1