1. 神经网络
来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/251/A
算法知识点: 拓扑排序
复杂度： &preview=true)
解题思路：
这道题目需要注意输入层的初始状态不用减去阈值。
为了保证使用每个点的状态去更新其他点时，该点的状态已被计算完毕，我们需要使用拓扑序来计算每个点的值。
计算完拓扑序列后，我们只需从前往后递推一遍，即可求出每个点的最终状态值。
C++ 代码：
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110,
M = N *N / 2;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N], u[N], din[N], dout[N];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void topsort()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
if (!din[i])
q[++tt] = i;
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (--din[j] == 0)
q[++tt] = j;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &f[i], &u[i]);
if (!f[i]) f[i] -= u[i];
}
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
dout[a]++, din[b]++;
}
topsort();
for (int i = 0; i < n; i++)
{
int j = q[i];
if (f[j] > 0)
{
for (int k = h[j]; ~k; k = ne[k])
f[e[k]] += f[j] *w[k];
}
}
bool flag = true;
for (int i = 1; i <= n; i++)
if (!dout[i] && f[i] > 0)
{
printf("%d %d\n", i, f[i]);
flag = false;
}
if (flag) puts("NULL");
return 0;
}
2. 双栈排序
来源：NOIP2008提高组 https://ac.nowcoder.com/acm/contest/256/D
算法知识点: 二分图,栈,染色法,贪心
复杂度： &preview=true)
解题思路：
如果只有一个栈，则整个操作顺序是固定的：
- 从前往后遍历每个数，每次先将当前数压入栈中，如果后面的所有数均比栈顶元素大，则将栈顶弹出，否则栈顶不能被弹出。
因此，我们只需考虑将每个数分配给哪个栈即可。
这里有个很强的性质：
两个数
不能被放入同一个栈中，当且仅当存在
, 且
。
有了上述性质后，我们只需将所有满足条件的点分到两个栈中去即可。这一步可以转化成图论问题：
- 如果i, j满足条件，则在i和j之间连一条边。
然后判断是否是二分图即可。
答案要求字典序最小，因此从前往后染色时，需要优先将当前点分配到第一个栈中。
C++ 代码：
#include <iostream>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std; const int N = 1010;
int n;
int a[N], f[N];
int color[N];
bool g[N][N];
bool dfs(int u, int c)
{
color[u] = c;
for (int i = 1; i <= n; i++)
if (g[u][i])
{
if (color[i] == c) return false;
if (color[i] == -1 && !dfs(i, !c)) return false;
}
return true;
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
f[n + 1] = n + 1;
memset(g, false, sizeof g);
for (int i = n; i; i--) f[i] = min(f[i + 1], a[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[i] < a[j] && f[j + 1] < a[i])
g[i][j] = g[j][i] = true;
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i++)
if (color[i] == -1 && !dfs(i, 0))
{
flag = false;
break;
}
if (!flag)
{
cout << 0 << endl;
continue;
}
stack<int> stk1, stk2;
int now = 1;
for (int i = 1; i <= n; i++)
{
if (color[i] == 0)
{
stk1.push(a[i]);
cout << "a ";
}
else
{
stk2.push(a[i]);
cout << "c ";
}
while (true)
if (stk1.size() && stk1.top() == now)
{
stk1.pop();
cout << "b ";
now++;
}
else if (stk2.size() && stk2.top() == now)
{
stk2.pop();
cout << "d ";
now++;
}
else break;
}
cout << endl;
}
return 0;
}
3. 最优贸易
来源：NOIP2009提高组 https://ac.nowcoder.com/acm/contest/257/C
算法知识点: SPFA
复杂度： &preview=true)
解题思路：
先求出：
- 从
走到
的过程中，买入水晶球的最低价格
dmin[i]； - 从
的过程中，卖出水晶球的最高价格
dmax[i]；
然后枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可。
求 dmin[i] 和 dmax[i] 时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
C++ 代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std; const int N = 100010,
M = 2000010;
int n, m;
int price[N];
int h[N], rh[N], e[M], ne[M], idx;
int dmax[N], dmin[M];
bool st[N];
void add(int *h, int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void spfa(int *d, int sign)
{
queue<int> q;
memset(st, false, sizeof st);
if (sign == 1) memset(d, 0x3f, sizeof dmax);
if (sign == 1) q.push(1), st[1] = true;
else q.push(n), st[n] = true;
while (q.size())
{
int t = q.front();
q.pop();
for (int i = sign == 1 ? h[t] : rh[t]; ~i; i = ne[i])
{
int j = e[i];
if (sign == 1 && d[j] > min(d[t], price[j]) || sign == -1 && d[j] < max(d[t], price[j]))
{
if (sign == 1) d[j] = min(d[t], price[j]);
else d[j] = max(d[t], price[j]);
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b), add(rh, b, a);
if (c == 2) add(h, b, a), add(rh, a, b);
}
spfa(dmin, 1);
spfa(dmax, -1);
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
printf("%d\n", res);
return 0;
}
4. 信息传递
来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/263/E
算法知识点: 图论,找环
复杂度： &preview=true)
解题思路：
由题意，我们需要在所有点的出度均是1的有向图中，求出最小环的长度。
首先我们考虑一下所有点的出度均是1的有向图的性质：即一个环上挂着很多路径，而且不管从哪个点出发，最终都会走到某个环上。
因此我们可以借助于栈结构来找出所有环：
从前往后扫描每个点，如果当前点没有被遍历过，则沿着出边一直走，直到走到已经被遍历过的点为止，走的过程中将所有点按顺序存入栈中。此时会有两种情况：
- 此时走到的已被遍历过的点在栈中，则栈中从该点开始，到当前点这部分就是环上的所有点；
- 此时走到的已被遍历过的点不在栈中，则说明当前只是在某个分支上走，并没有走到某个环上；
所有环的长度的最小值即是答案。
C++ 代码：
#include <iostream>
#include <algorithm>
using namespace std; const int N = 200010;
int n;
int p[N], stk[N];
bool st[N], in_stk[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
int res = n;
for (int i = 1; i <= n; i++)
if (!st[i])
{
int tt = 0;
int j = i;
while (!st[j])
{
stk[++tt] = j;
st[j] = true;
in_stk[j] = true;
j = p[j];
}
if (in_stk[j])
{
int cnt = 1;
while (stk[tt] != j)
{
in_stk[stk[tt--]] = false;
cnt++;
}
res = min(res, cnt);
}
while (tt) in_stk[stk[tt--]] = false;
}
printf("%d\n", res);
return 0;
}
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ
京公网安备 11010502036488号