当前位置：首页 > news >正文

牛客刷题-Day34

news 2026/3/26 20:26:02

今日刷题：$1001-1004$

1001 NC16679 [NOIP2003]神经网络

题目描述

人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。

在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子：

神经元〔编号为 $1$）
图中，$X_1—X_3$ 是信息输入渠道，$Y_1－Y_2$ 是信息输出渠道，$C1$ 表示神经元目前的状态，$U_i$ 是阈值，可视为神经元的一个内在参数。神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经无分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。

兰兰规定，$C_i$ 服从公式：（其中 $n$ 是网络中所有神经元的数目）

公式中的 $W_{ji}$（可能为负值）表示连接 $j$ 号神经元和 $i$ 号神经元的边的权值。当 $C_i$ 大于 $0$ 时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为 $C_i$。

如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（$C_i$），要求你的程序运算出最后网络输出层的状态。

输入描述

第一行是两个整数 $n$（$1≤n≤200$）和 $p$。
接下来 $n$ 行，每行两个整数，第 $i＋1$ 行是神经元i最初状态和其阈值（$U_i$），非输入层的神经元开始时状态必然为 $0$。
再下面 $P$ 行，每行由两个整数 $i$，$j$ 及一个整数 $W_{ij}$，表示连接神经元 $i$、$j$ 的边权值为 $W_{ij}$。

输出描述

包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。
仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！
若输出层的神经元最后状态均为 $0$，则输出 NULL。

示例

输入

输出

3 1
4 1
5 1

解题思路

确定输入层之后，按照拓扑序排序来完成每一层的计算，最后出度为 $0$ 的即为输出层。

C++ 代码

// NC16679
#include <bits/stdc++.h>
using namespace std;
const int N = 210;int n, m;
struct Node {int c, u, out; // 状态 阈值 出度
} a[N];int g[N][N];
bool flag[N][N];
int in_degree[N];int main() {if (scanf("%d%d", &n, &m) != 2) return 0;queue<int> q;for (int i = 1; i <= n; i++) {scanf("%d%d", &a[i].c, &a[i].u);if (a[i].c > 0) {q.push(i);} else {a[i].c -= a[i].u;}}while (m--) {int i, j, w;scanf("%d%d%d", &i, &j, &w);g[i][j] = w;flag[i][j] = true;in_degree[j]++;a[i].out++;}while (!q.empty()) {int t = q.front();q.pop();if (a[t].c > 0) {for (int j = 1; j <= n; j++) {if (flag[t][j]) {a[j].c += g[t][j] * a[t].c;}}}for (int j = 1; j <= n; j++) {if (flag[t][j]) {in_degree[j]--;if (in_degree[j] == 0) {q.push(j);}}}}int cnt = 0;for (int i = 1; i <= n; i++) {if (a[i].out == 0 && a[i].c > 0) {printf("%d %d\n", i, a[i].c);cnt++;}}if (cnt == 0) puts("NULL");return 0;
}

1002 NC16541 [NOIP2013]车站分级

题目描述

一条单向的铁路线上，依次有编号为 $1, 2, …, n$ 的 $n $ 个火车站。每个火车站都有一个级别，最低为 $1$ 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 $x$，则始发站、终点站之间所有级别大于等于火车站 $x$ 的都必须停靠。
注意：起始站和终点站自然也算作事先已知需要停靠的站点。

例如，下表是 $ 5 $ 趟车次的运行情况。其中，前 $ 4$ 趟车次均满足要求，而第 $5$ 趟车次由于停靠了 $3$ 号火车站（$2$ 级）却未停靠途经的 $6$ 号火车站（亦为 $2$ 级）而不满足要求。

现有 $m$ 趟车次的运行情况（全部满足要求），试推算这 $ n$ 个火车站至少分为几个不同的级别。

输入描述

第一行包含 $2$ 个正整数 $n, m$，用一个空格隔开。
第 $i + 1$ 行 $(1 ≤ i ≤ m)$ 中，首先是一个正整数 $s_i\ (2 ≤ s_i ≤ n)$，表示第 $ i$ 趟车次有 $s_i$ 个停靠站；接下来有 $ s_i$ 个正整数，表示所有停靠站的编号，从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

输出描述

一个正整数，即 $n$ 个火车站最少划分的级别数。

示例1

输入

9 2 
4 1 3 5 6 
3 3 5 6

输出

示例2

输入

输出

备注

对于 $ 20%$ 的数据，$1 ≤ n, m ≤ 10$；
对于 $50\%$ 的数据，$1 ≤ n, m ≤ 100$；
对于 $100\%$ 的数据，$1 ≤ n, m ≤ 1000$。

解题思路

拓扑排序，即对于每列车可以确定其行程里，未经停车站的级别是小于所有经停车站的。因此经过所有的列车行程可以确定一个有向图，该图的节点深度就是级别的最少划分数

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int n, m, s;
int g[N][N], d[N], depth[N];
int st[N], p[N];int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {memset(st, 0, sizeof st);scanf("%d", &s);for (int j = 1; j <= s; j++) {scanf("%d", &p[j]);st[p[j]] = 1;}for (int j = p[1]; j <= p[s]; j++)if (!st[j])for (int k = 1; k <= s; k++)if (!g[j][p[k]]) {g[j][p[k]] = 1;d[p[k]]++;}}memset(st, 0, sizeof st);queue<int> q;for (int i = 1; i <= n; i++)if (d[i] == 0) {depth[i] = 1;q.push(i);}while (q.size()) {auto t = q.front();st[t] = 1;q.pop();for (int i = 1; i <= n; i++)if (g[t][i] && !st[i]) {d[i]--;if (d[i] == 0) {depth[i] = depth[t] + 1;q.push(i);}}}int ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, depth[i]);printf("%d\n", ans);return 0;
}

1002 NC20115 [HNOI2015]菜肴制作

题目描述

知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。 ATM 酒店为小 A 准备了 $N$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 $N$ 的顺序编号，预估质量最高的菜肴编号为 $1$。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 $M$ 条形如“$i$ 号菜肴必须先于 $j$ 号菜肴制作”的限制，我们将这样的限制简写为 $<i,j>$。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A能尽量先吃到质量高的菜肴：

也就是说，

$(1)$ 在满足所有限制的前提下，$1$ 号菜肴“尽量”优先制作；
$(2)$ 在满足所有限制，$1$ 号菜肴“尽量”优先制作的前提下，$2$ 号菜肴“尽量”优先制作；
$(3)$ 在满足所有限制，$1$ 号和 $2$ 号菜肴“尽量”优先的前提下，$3$ 号菜肴“尽量”优先制作；
$(4)$ 在满足所有限制，$1$ 号和 $2$ 号和 $3$ 号菜肴“尽量”优先的前提下，$4$ 号菜肴“尽量”优先制作；
$(5) $以此类推。
例 1：共 $4$ 道菜肴，两条限制 $<3,1>$、$<4,1>$，那么制作顺序是 $3,4,1,2$。

例 2：共 $5$ 道菜肴，两条限制 $<5,2>$、$<4,3>$，那么制作顺序是 $1,5,2,4,3$。

例 1 里，首先考虑 $1$，因为有限制 $<3,1>$ 和 $<4,1>$，所以只有制作完 $3$ 和 $4$ 后才能制作 $1$，而根据 $(3)$，$3$ 号又应“尽量”比 $4$ 号优先，所以当前可确定前三道菜的制作顺序是 $3,4,1$；接下来考虑 $2$，确定最终的制作顺序是 $3,4,1,2$。

例 2 里，首先制作 $1$ 是不违背限制的；接下来考虑 $2$ 时有 $<5,2>$ 的限制，所以接下来先制作 $5$ 再制作 $2$；接下来考虑 $3$ 时有 $<4,3>$ 的限制，所以接下来先制作 $4$ 再制作 $3$，从而最终的顺序是 $1,5,2,4,3$。现在你需要求出这个最优的菜肴制作顺序。无解输出 Impossible! （不含引号，首字母大写，其余字母小写）

输入描述

第一行是一个正整数 $D$，表示数据组数。
接下来是 $D$ 组数据。
对于每组数据：
第一行两个用空格分开的正整数 $N$ 和 $M$，分别表示菜肴数目和制作顺序限制的条目数。
接下来 $M$ 行，每行两个正整数 $x,y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴制作的限制。（注意：$M$ 条限制中可能存在完全相同的限制）

输出描述

输出文件仅包含 $D$ 行，每行 $N$ 个整数，表示最优的菜肴制作顺序，或者 Impossible! 表示无解（不含引号）。

示例

输入

输出

1 5 3 4 2 
Impossible! 
1 5 2 4 3

备注

$100\%$ 的数据满足 $N,M≤100000,D≤3$。

解题思路

按照正常的拓扑序来实现，那么会先输出所有入度为 $0$ 的点，显然是不符合题意的，以题干里的例 2，顺序会是 $1,4,5,3,2$，显然不符合要求，因为即使受到限制，序号小的也要先输出。那么可以反过来思考，反向建图，则在排序时，优先处理序号大的点，因为序号大的点需要最后处理，只需要在最后输出答案时反过来输出序列即可

C++ 代码

// NC20115
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;int D, n, m;
int h[N], e[N], ne[N], idx, d[N];
int ans[N];void add(int x, int y) {e[idx] = y;ne[idx] = h[x];h[x] = idx++;
}int main() {scanf("%d", &D);while (D--) {idx = 0;memset(h, -1, sizeof h);memset(d, 0, sizeof d);scanf("%d%d", &n, &m);while (m--) {int x, y;scanf("%d%d", &x, &y);add(y, x);d[x]++;}int cnt = 0;priority_queue<int> q;for (int i = 1; i <= n; i++)if (d[i] == 0)q.push(i);while (!q.empty()) {auto t = q.top();q.pop();ans[++cnt] = t;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];d[j]--;if (d[j] == 0)q.push(j);}}if (cnt == n) {for (int i = cnt; i; i--)printf("%d ", ans[i]);printf("\n");} else {puts("Impossible!");}}return 0;
}

1004 NC14352 旅行

题目描述

小 z 放假了，准备到 RRR 城市旅行，其中这个城市有 $N$ 个旅游景点。小 z 时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍 RRR 城。
小 z 很开心，直接就把钱一次性缴足了。然而小 z 心机很重，他想选择的路程尽量长。
然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小 z 吗？
需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.

输入描述

本题包含多组输入，第一行输入一个整数 $t$，表示测试数据的组数
每组测试数据第一行输入两个数 $N,M$ 表示 RRR 城一共有的旅游景点的数量，以及 RRR 城中有的路的数量。
接下来 $M$ 行，每行三个数，$a$，$b$，$c$ 表示从 $a$ 景点和 $b$ 景点之间有一条长为 $c$ 的路
$t<=40;3<=N,M<=1000;1<=a,b<=N;1<=c<=100$

输出描述

每组数据包含一行，输出一个数，表示整条路程的路长。
如果找不到可行解，输出 $-1$.

示例

输入

输出

说明：请注意这是一个稀疏图

解题思路

枚举中间点，求出其到其他点的最短路（司机在两点间会走最短路径），答案是最长的两个最短路之和的最大值。

C++ 代码

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;int t, n, m, ans;
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
int dist[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}void dijkstra(int u) {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[u] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, u});while (heap.size()) {auto t = heap.top();heap.pop();int ver = t.y, distance = t.x;if (st[ver])continue;st[ver] = true;for(int i = h[ver]; i != -1; i = ne[i]) {int j = e[i];if(dist[j] > dist[ver] + w[i]){dist[j] = dist[ver] + w[i];heap.push({dist[j], j});}}}
}int main() {scanf("%d", &t);while (t--) {idx = 0;ans = -1;memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while (m--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}for (int i = 1; i <= n; i++) { // 枚举中间点dijkstra(i);int a = 0, b = 0;for (int j = 1; j <= n; j++) {if (dist[j] == 0x3f3f3f3f)continue;if (dist[j] > a) {b = a;a = dist[j];} else if (dist[j] > b) {b = dist[j];}}if (a && b)ans = max(ans, a + b);}printf("%d\n", ans);}return 0;
}

查看全文

http://www.jsqmd.com/news/442459/