?

第一題 神經(jīng)網(wǎng)絡(luò)

【題目描述】

人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network）是一種新興的具有自我學(xué)習(xí)能力的計(jì)算系統(tǒng)，在模式識(shí)別、函數(shù)逼近及貸款風(fēng)險(xiǎn)評(píng)估等諸多領(lǐng)域有廣泛的應(yīng)用。對(duì)神經(jīng)網(wǎng)絡(luò)的研究一直是當(dāng)今的熱門方向，蘭蘭同學(xué)在自學(xué)了一本神經(jīng)網(wǎng)絡(luò)的入門書籍后，提出了一個(gè)簡(jiǎn)化模型，他希望你能幫助他用程序檢驗(yàn)這個(gè)神經(jīng)網(wǎng)絡(luò)模型的實(shí)用性。

在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個(gè)神經(jīng)元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：

圖中，X1—X3是信息輸入渠道，Y1－Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個(gè)內(nèi)在參數(shù)。
神經(jīng)元按一定的順序排列，構(gòu)成整個(gè)神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個(gè)中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。下圖是一個(gè)簡(jiǎn)單的三層神經(jīng)網(wǎng)絡(luò)的例子。

蘭蘭規(guī)定，Ci服從公式：（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目）

?

?

公式中的Wji（可能為負(fù)值）表示連接j號(hào)神經(jīng)元和 i號(hào)神經(jīng)元的邊的權(quán)值。當(dāng) Ci大于0時(shí)，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時(shí)，下一秒它會(huì)向其他神經(jīng)元傳送信號(hào)，信號(hào)的強(qiáng)度為Ci。如此．在輸入層神經(jīng)元被激發(fā)之后，整個(gè)網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿?dòng)下進(jìn)行運(yùn)作。
現(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（Ci），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)。

?

【輸入格式】

輸入文件第一行是兩個(gè)整數(shù)n（1≤n≤200）和p。接下來n行，每行兩個(gè)整數(shù)，第i＋1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開始時(shí)狀態(tài)必然為0。再下面P行，每行由兩個(gè)整數(shù)i，j及一個(gè)整數(shù)Wij，表示連接神經(jīng)元i、j的邊權(quán)值為Wij。

?

【輸出格式】

輸出文件包含若干行，每行有兩個(gè)整數(shù)，分別對(duì)應(yīng)一個(gè)神經(jīng)元的編號(hào)，及其最后的狀
態(tài)，兩個(gè)整數(shù)間以空格分隔。僅輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由
小到大順序輸出！
若輸出層的神經(jīng)元最后狀態(tài)均為 0，則輸出 NULL。

?

【樣例輸入】

5 6
1 0
1 0
0 1
0 1
0 1
1 3 1
1 4 1
1 5 1
2 3 1
2 4 1
2 5 1?

?
【樣例輸出】

3 1

4 1

5 1

?

【分析】

用遞歸寫的話，很好寫恩。注意題目中給的判定條件。

?

第二題 偵探推理

忽略囧。

?

第三題 加分二叉樹

【題目描述】

設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：
subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分?jǐn)?shù)
若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。
試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；
（1）tree的最高加分
（2）tree的前序遍歷

?

【輸入格式】

第1行：一個(gè)整數(shù)n（n＜30），為節(jié)點(diǎn)個(gè)數(shù)。
第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)＜100）。

?

【輸出格式】

第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過4,000,000,000）。
第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷。

?

【樣例輸入】

5
5 7 1 2 10?

?
【樣例輸出】

145
3 1 2 4 5?

?
【分析】

區(qū)間動(dòng)歸。

?

第四題 傳染病控制

【題目描述】

近來，一種新的傳染病肆虐全球。蓬萊國(guó)也發(fā)現(xiàn)了零星感染者，為防止該病在蓬萊國(guó)大范圍流行，該國(guó)政府決定不惜一切代價(jià)控制傳染病的蔓延。不幸的是，由于人們尚未完全認(rèn)識(shí)這種傳染病，難以準(zhǔn)確判別病毒攜帶者，更沒有研制出疫苗以保護(hù)易感人群。于是，蓬萊國(guó)的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經(jīng)過 WHO（世界衛(wèi)生組織）以及全球各國(guó)科研部門的努力，這種新興傳染病的傳播途徑和控制方法已經(jīng)研究消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國(guó)疾控中心制定一個(gè)有效的控制辦法。

研究表明，這種傳染病的傳播具有兩種很特殊的性質(zhì)；

第一是它的傳播途徑是樹型的，一個(gè)人X只可能被某個(gè)特定的人Y感染，只要Y不
得病，或者是XY之間的傳播途徑被切斷，則X就不會(huì)得病。

第二是，這種疾病的傳播有周期性，在一個(gè)疾病傳播周期之內(nèi)，傳染病將只會(huì)感染一
代患者，而不會(huì)再傳播給下一代。

這些性質(zhì)大大減輕了蓬萊國(guó)疾病防控的壓力，并且他們已經(jīng)得到了國(guó)內(nèi)部分易感人群的潛在傳播途徑圖（一棵樹）。但是，麻煩還沒有結(jié)束。由于蓬萊國(guó)疾控中心人手不夠，同時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而沒有被控制的傳播途徑就會(huì)引起更多的易感人群被感染（也就是與當(dāng)前已經(jīng)被感染的人有傳播途徑相連，且連接途徑?jīng)]有被切斷的人群）。當(dāng)不可能有健康人被感染時(shí)，疾病就中止傳播。所以，蓬萊國(guó)疾控中心要制定出一個(gè)切斷傳播途徑的順序，以使盡量少的人被感染。你的程序要針對(duì)給定的樹，找出合適的切斷順序。

?

【輸入格式】

輸入格式的第一行是兩個(gè)整數(shù)n（1≤n≤300）和p。表示有N個(gè)人，接下來p行，每一行有兩個(gè)整數(shù)i和j，表示節(jié)點(diǎn)i和j間有邊相連（意即，第i人和第j人之間有傳播途徑相連）。其中節(jié)點(diǎn)1是已經(jīng)被感染的患者。

?

【輸出格式】

只有一行，輸出總共被感染的人數(shù)。

?

【樣例輸入】

7 6
1 2
1 3
2 4
2 5
3 6
3 7?

?
【樣例輸出】

3

?

【分析】

很自然的會(huì)想到貪心，但是應(yīng)該用搜索。貪心是不對(duì)的。

對(duì)于第K個(gè)周期。首先我們計(jì)算下一個(gè)周期有哪些點(diǎn)是被傳染了的。然后枚舉下一個(gè)周期中的點(diǎn)哪一個(gè)被切斷。因?yàn)閠ot是全局變量，所以記得要減會(huì)tot的值。

代碼

第一題

#include <stdio.h> #define MAXN 210 int pre[MAXN][MAXN],c[MAXN],u[MAXN],w[MAXN][MAXN]; bool end[MAXN],v[MAXN]; bool have; int n,m,x,y,z; void find(int x) {if (v[x])return;v[x] = 1;int tem = 0;for (int i = 1;i <= pre[x][0];++i) {int y = pre[x][i];find(y);if (c[y] > 0)tem += w[y][x] * c[y];}tem -= u[x];c[x] = tem; } int main() {scanf("%d%d",&n,&m);for (int i = 1;i <= n;++i) {scanf("%d%d",&c[i],&u[i]);if (c[i] != 0)v[i] = 1;}for (int i = 1;i <= m;++i) {scanf("%d%d%d",&x,&y,&z);w[x][y] = z;pre[y][++pre[y][0]] = x;end[x] = 1;}for (int i = 1;i <= n;++i)if (!end[i]) {find(i);if (c[i] > 0) {have = 1;printf("%d %d\n",i,c[i]);}}if (!have)printf("NULL\n");return 0; }

?

第三題

#include <stdio.h> #define MAXN 60 int f[MAXN][MAXN],mid[MAXN][MAXN],a[MAXN]; int n; int find(int x,int y) {if (x > y)return 1;if (f[x][y])return f[x][y];if (x == y)f[x][y] = a[x];else {int tem;for (int i = x;i <= y;++i) {tem = find(x,i - 1) * find(i + 1,y) + a[i];if (tem > f[x][y]) {f[x][y] = tem;mid[x][y] = i;}}}return f[x][y]; } void out(int x,int y) {if (x > y)return;if (x == y)printf("%d ",x);else {printf("%d ",mid[x][y]);out(x,mid[x][y] - 1);out(mid[x][y] + 1,y);} } int main() {scanf("%d",&n);for (int i = 1;i <= n;++i)scanf("%d",&a[i]);printf("%d\n",find(1,n));out(1,n);return 0; }

第四題

#include <stdio.h> #include <limits.h> #define MAXN 310 int f[MAXN],bl[MAXN][MAXN]; int ans = INT_MAX,n,p,x,y,tot; void build(int x) {for (int i = 1;i <= bl[x][0];++i) {int y = bl[x][i];int j;for (j = 1;j <= bl[y][0];++j)if (bl[y][j] == x)break;bl[y][j] = bl[y][bl[y][0]--];build(y);} } void find(int k) {if (tot > ans)return;int t = 0;for (int i = 1;i <= n;++i)if (f[i] == k)for (int j = 1;j <= bl[i][0];++j) {f[bl[i][j]] = k + 1;++tot;t = 1;}--tot;for (int i = 1;i <= n;++i)if (f[i] == k + 1) {f[i] = 0;find(k + 1);f[i] = k + 1;}++tot;for (int i = 1;i <= n;++i)if (f[i] == k + 1) {f[i] = 0;--tot;}if ((!t) && (tot < ans))ans = tot; } int main() {scanf("%d%d",&n,&p);for (int i = 1;i <= p;++i) {scanf("%d%d",&x,&y);bl[x][++bl[x][0]] = y;bl[y][++bl[y][0]] = x;}build(1);f[1] = 1;tot = 1;find(1);printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/sephirothlee/archive/2010/11/01/1866614.html

總結(jié)

以上是生活随笔為你收集整理的NOIP2003提高组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。