->点我进原题
-> 7-1 序列调度
-> 7-2 最大最小差
-> 7-3 二叉树最短路径长度
-> 7-4 方案计数
7-1 序列调度 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(10 MB\)
Description
有一个 \(N\) 个数的序列 \(A\)：\(1\)，\(2\)，……，\(N\)。有一个后进先出容器 \(D\)，容器的容量为 \(C\)。如果给出一个由 \(1\) 到 \(N\) 组成的序列，那么可否由 \(A\) 使用容器 \(D\) 的插入和删除操作得到。
Input
第 \(1\) 行，2个整数 \(T\) 和 \(C\)，空格分隔，分别表示询问的组数和容器的容量，\(1≤T≤10\)，\(1≤C≤N\)。
第 \(2\) 到 \(T+1\) 行，每行的第1个整数 \(N\)，表示序列的元素数，\(1≤N≤10000\)。接下来 \(N\) 个整数，表示询问的序列。
Output
\(T\) 行。若第 \(i\) 组的序列能得到，第 \(i\) 行输出 \(Yes\)；否则，第 \(i\) 行输出 \(No\), \(1≤i≤T\)。
Sample Input
2 2
5 1 2 5 4 3
4 1 3 2 4
Sample Output
No
Yes
思路
不需要真正去建栈，只需要去模拟，找规律能发现符合栈的序列只可能是类似于
x, x+1, x+2, ... x+n, y, y-1, y-2, ... x+n+1, y+1, y+2, ...
的形式，所以只要输入，然后 \(O(n)\) 对序列进行判断即可，对于题中的容量 \(C\)，保证每一段降序序列不超过 \(C\) 个即可。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == ‘-‘), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
int stk[10001], top;
int n, now, book, maxn;
signed main(){
int t = read(), c = read();
while(t --){
n = read();
now = 1;
maxn = 0;
book = 1;
for(rg int i = 1; i <= n; ++i){
int tmp = read();
if(tmp == now){
now ++;
} else if(tmp < now){
if(tmp == maxn - 1){
maxn = tmp;
} else{
book = 0;
}
} else{
if(tmp - now >= c){
book = 0;
}
maxn = tmp;
now = tmp + 1;
}
}
if(book) printf("Yes\n");
else printf("No\n");
}
return 0;
}
7-2 最大最小差 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(100 ms\)
内存限制 \(64 MB\)
Description
对 \(n\) 个正整数，进行如下操作：每一次删去其中两个数 \(a\) 和 \(b\)，然后加入一个新数：\(a*b+1\)，如此下去直到 只剩下一个数。所有按这种操作方式最后得到的数中，最大的为 \(max\)，最小的为 \(min\)，计算 \(max-min\)。
Input
第1行：\(n\)，数列元素的个数，\(1<=n<=16\)。
第2行：\(n\) 个用空格隔开的数 \(x\)，\(x<=10\)。
Output
1行，所求 \(max-min\)。
Sample Input
3
2 4 3
Sample Output
2
思路
优先队列裸题。
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline ll read(){
rg ll f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == ‘-‘), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
priority_queue<ll> qmin;
priority_queue<ll, vector<ll> , greater<ll> > qmax;
signed main(){
int n;
cin >> n;
for(rg int i = 1; i <= n; ++i){
ll tmp = read();
qmax.push(tmp);
qmin.push(tmp);
}
for(rg int i = 1; i < n; ++i){
ll u = qmax.top();
qmax.pop();
ll v = qmax.top();
qmax.pop();
qmax.push(u * v + 1);
u = qmin.top();
qmin.pop();
v = qmin.top();
qmin.pop();
qmin.push(u * v + 1);
}
printf("%lld", qmax.top() - qmin.top());
return 0;
}
7-3 二叉树最短路径长度 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(1000 ms\)
内存限制 \(10 MB\)
Description
给定一棵二叉树 \(T\)，每个结点赋一个权值。计算从根结点到所有结点的最短路径长度。路径长度定义为：路径上的每个顶点的权值和。
Input
第1行，\(1\) 个整数 \(n\)，表示二叉树 \(T\) 的结点数，结点编号 \(1..n\)，\(1≤n≤20000\)。
第2行，\(n\) 个整数，空格分隔，表示 \(T\) 的先根序列，序列中结点用编号表示。
第3行，\(n\) 个整数，空格分隔，表示 \(T\) 的中根序列，序列中结点用编号表示。
第4行，\(n\) 个整数 \(Wi\)，空格分隔，表示 \(T\) 中结点的权值，\(-10000≤Wi≤10000\)，\(1≤i≤n\)。
Output
1行，n个整数，表示根结点到其它所有结点的最短路径长度。
Sample Input
4
1 2 4 3
4 2 1 3
1 -1 2 3
Sample Output
1 0 3 3
思路
建树跑spfa即可，这里建图用了一个很巧妙的方法，详情见代码。
代码
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 500010
#define rg register
using namespace std;
const int inf = 0x7fffffff;
struct edge{
int nxt, to, w;
}e[100001];
int tot = 0, head[100001], n;
int fo[20001], mo[20001];
int vis[20001] = {0}, dis[20001], val[20001];
queue <int> q;
inline int read(){
int x=0,f=0;
char ch=getchar();
while(!isdigit(ch)) f|=(ch==‘-‘),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
inline void init(int s){
for(int i=1;i<=n;i++){
dis[i]=inf;
vis[i]=false;
}
dis[s]=0;
q.push(s);
}
inline void add(int u,int v,int w){
e[++tot].to=v;
e[tot].nxt=head[u];
e[tot].w=w;
head[u]=tot;
}
inline void spfa(int s){
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
}
inline int build(int lp, int rp, int li, int ri){
if(lp > rp || li > ri){
return -1;
}
for(rg int i = li; i <= ri; ++i){
if(fo[lp] == mo[i]){
int ls = build(lp + 1, i - li + lp, li, i - 1);
int rs = build(i - li + lp + 1, rp, i + 1, ri);
if(ls != -1) add(fo[lp], ls, val[ls]);
if(rs != -1) add(fo[lp], rs, val[rs]);
}
}
return fo[lp];
}
int main(){
n=read();
for(rg int i = 1; i <= n; ++i) fo[i] = read();
for(rg int i = 1; i <= n; ++i) mo[i] = read();
for(rg int i = 1; i <= n; ++i) val[i] = read();
build(1, n, 1, n);
init(1);
spfa(1);
for(int i=1;i<=n;i++){
printf("%d",dis[i]+val[1]);
if(i != n) printf(" ");
}
return 0;
}
7-4 方案计数 (100 分)
代码长度限制 \(16 KB\)
时间限制 \(200 ms\)
内存限制 \(64 MB\)
Description
组装一个产品需要 \(n\) 个零件。生产每个零件都需花费一定的时间。零件的生产可以并行进行。有些零件的生产有先后关系，只有一个零件的之前的所有零件都生产完毕，才能开始生产这个零件。如何合理安排工序，才能在最少的时间内完成所有零件的生产。在保证最少时间情况下，关键方案有多少种，关键方案是指从生产开始时间到结束时间的一个零件生产序列，序列中相邻两个零件的关系属于事先给出的零件间先后关系的集合，序列中的每一个零件的生产都不能延期。
Input
第 \(1\) 行，\(2\) 个整数 \(n\) 和 \(m\)，用空格分隔，分别表示零件数和关系数，零件编号 \(1\)..\(n\)，\(1≤n≤10000\), \(0≤m≤100000\) 。
第 \(2\) 行，\(n\) 个整数 \(Ti\)，用空格分隔，表示零件 \(i\) 的生产时间，\(1≤i≤n，1≤Ti≤100\) 。
第 \(3\) 到 \(m+2\) 行，每行两个整数 \(i\) 和 \(j\)，用空格分隔，表示零件 \(i\) 要在零件 \(j\) 之前生产。
Output
第1行，1个整数，完成生产的最少时间。
第2行，1个整数，关键方案数，最多100位。
如果生产不能完成，只输出1行，包含1个整数0.。
Sample Input
4 4
1 2 2 1
1 2
1 3
2 4
3 4
Sample Output
4
2
思路
题目翻译过来就是求关键路径条数和最短完成时间。首先因为他可能是一个不连通的图，所以我们要引入虚源和虚汇来把他变成符合求关键路径的模式（这点很重要！！）；其次求路径条数的过程中，我用的是计数原理，把每一点向后走关键路径的个数统计下来，把所有的乘起来即可，要注意这道题的数据很大，要用高精乘；所求最短的时间即为求关键路径中的 \(late[n+1]\)。
一定要注意：当你引入虚源和虚汇将其与其他点连边之后，数据就变大了，数组就不能只开 \(10^5\) 了！！yysy我在这里被卡了一周...
代码
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define rg register
#define ll long long
using namespace std;
inline int read(){
rg int f = 0, x = 0;
rg char ch = getchar();
while(!isdigit(ch)) f |= (ch == ‘-‘), ch = getchar();
while( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f? -x: x;
}
const int N = 200001;
const int M = 200001;
struct edge{
int nxt, to, w;
}e[M];
int tot = 0, head[M], n, m, deg[N] = {0}, cnt = 0, od[N] = {0};
int val[N];
queue <int > q;
int topo[N], critical[N], early[N] = {0}, late[N] = {0};
int out[N];
int a[200], b[200], c[200], len1 = 1, len2, len3;
inline void multi(int a[], int b[], int c[], int &len1, int &len2, int &len3){//b = a * n
len3 = len1 + len2 - 1;
for(int i = 1; i <= len2; ++i)
for(int j = 1; j <= len1; ++j){
c[i + j - 1] += a[j] * b[i];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
if(c[len3 + 1] > 0) len3 ++;
}
inline void add(rg int u, rg int v, rg int w){
e[++tot].nxt = head[u];
e[tot].to = v;
e[tot].w = w;
head[u] = tot;
}
inline void toposort(){
q.push(0);
while(!q.empty()){
int u = q.front();
q.pop();
topo[++ cnt] = u;
for(rg int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(--deg[v] == 0) q.push(v);
}
}
}
inline void criticalroad(){
for(rg int i = 0; i <= n + 1; ++i) early[i] = 0;
for(rg int i = 1; i <= cnt; ++i){
int u = topo[i];
for(rg int j = head[u]; j; j = e[j].nxt){
int v = e[j].to;
early[v] = max(early[v], early[u] + e[j].w);
}
}
for(rg int i = 0; i <= n + 1; ++i) late[i] = early[n + 1];
for(rg int i = cnt; i >= 1; --i){
int u = topo[i];
for(rg int j = head[u]; j; j = e[j].nxt){
int v = e[j].to;
late[u] = min(late[u], late[v] - e[j].w);
}
}
cnt = 0;
for(rg int i = 0; i <= n + 1; ++i){
int u = i;
for(rg int j = head[u]; j; j = e[j].nxt){
int v = e[j].to;
int re = early[u];
int rl = late[v] - e[j].w;
if(re == rl){
out[u] ++;
}
}
}
}
signed main(){
n = read(), m = read();
for(rg int i = 1; i <= n; ++i){
val[i] = read();
}
for(rg int i = 1; i <= m; ++i){
int u = read(), v = read(), w = val[u];
add(u, v, w);
deg[v] ++;
od[u] ++;
}
for(rg int i = 1; i <= n; ++i){
if(!deg[i]) add(0, i, 0), deg[i] ++;
if(!od[i]) add(i, n + 1, val[i]), deg[n + 1] ++;
}
toposort();
if(cnt != n + 2){
cout << 0;
return 0;
}
criticalroad();
cout << late[n + 1] << endl;
a[1] = 1;
for(rg int i = 0; i <= n + 1; ++i){
if(!out[i] || out[i] == 1) continue;
else{
memset(c, 0, sizeof(c));
int u = out[i];
int tot = 0;
while(u){
b[++tot] = u % 10;
u /= 10;
}
len2 = tot;
multi(a, b, c, len1, len2, len3);
for(int j = 1; j <= len3; ++j) a[j] = c[j], len1 = len3;
}
}
for(rg int i = len1; i >= 1; --i){
printf("%d", a[i]);
}
return 0;
}
数据结构上机到此为止啦！！！