工業(yè)統(tǒng)計(jì)1-9工作報(bào)告

工業(yè)統(tǒng)計(jì)1-9月份工作匯報(bào)

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

紅星街道現(xiàn)有工業(yè)企業(yè)128家，其中：規(guī)模以上企業(yè)8家、規(guī)模以下企業(yè)35家，個(gè)體企業(yè)85家。1-9月份工業(yè)總產(chǎn)值64848萬元、完成年度計(jì)劃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ì)運(yùn)行主要特點(diǎn)

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

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

沈必林

201*年10月9日

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

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

《距離統(tǒng)計(jì)》解題報(bào)告

1、

題目描述①

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

139F13F42F7F6F320F27F5

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

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

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

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

輸入文件：

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

①

題目來源：Usaco201*GreenContest

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

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

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

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

有5個(gè)點(diǎn)對(duì)滿足條件：

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

2、算法分析。

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

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

在這里，考慮兩堆點(diǎn)，兩堆點(diǎn)都是一個(gè)連通的點(diǎn)集。他們之間用一條邊分開，

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

看下面的圖：

SABTuv

現(xiàn)在要求出一個(gè)點(diǎn)在S，另一個(gè)點(diǎn)在T中的距離小于等于K的點(diǎn)對(duì)。點(diǎn)集S中的點(diǎn)u到點(diǎn)集T中的點(diǎn)v的距離dist(u,v)=dist(u,A)+dist(A,B)+dist(B,v)，其中A,B是唯一的一對(duì)相鄰的不在同一個(gè)點(diǎn)集中的點(diǎn)。對(duì)于不同的u,v來說，dist(A,B)總是一個(gè)定值，所以，(u,v)應(yīng)該滿足條件dist(u,A)+dist(B,v)≤K-dist(A,B)。

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

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

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

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

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

部分，那么，可以考慮這樣的兩個(gè)部分：

點(diǎn)集S和點(diǎn)集T包含了所有的點(diǎn)，他們有且僅有只有一個(gè)公共點(diǎn)：

TSAuv

上面的S和T共用了一個(gè)點(diǎn)A，那么在S中的點(diǎn)u（不是A）到在T中的點(diǎn)v（不是A）的距離dist(u,v)=dist(A,u)+dist(A,v)。那么，dist(A,v)≤k-dist(A,u)，這個(gè)也可以在排序后通過二分有效的得出答案。

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

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

AB

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

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

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

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

[2n/3]與[n/3]算不算均勻呢？不管，來考慮復(fù)雜度。由于要求出一個(gè)點(diǎn)在S中另一個(gè)點(diǎn)在T中的距離小于等于K的點(diǎn)對(duì)的個(gè)數(shù)，這個(gè)需要把S和T中的點(diǎn)按照到A的距離排序，這個(gè)可以在O(nlog2n)的時(shí)間內(nèi)實(shí)現(xiàn)，找到一個(gè)這樣的A點(diǎn)和把子樹分成集合，要用O(n)時(shí)間就可以實(shí)現(xiàn)了�？紤]最壞的情況，每一次分治都把兒子點(diǎn)集分成了2n/3,n/3的兩個(gè)點(diǎn)集，那么有n個(gè)點(diǎ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，由于都只是差一個(gè)常數(shù)，所以分治的算法的的時(shí)間復(fù)雜度是O(nlog22n)。

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

[參考文獻(xiàn)]

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

劉汝佳黃亮著

[討論]

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

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

②

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

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

ifiIOI201*國家集訓(xùn)隊(duì)第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)隊(duì)第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)隊(duì)第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)計(jì)1-9工作報(bào)告》給出的范例僅供您參考拓展思維使用，工業(yè)統(tǒng)計(jì)1-9工作報(bào)告：該篇文章建議您自主創(chuàng)作。

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

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

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