Code – 第15页 – 柳婼の blog

L3-011 直捣黄龙 (30 分)-PAT 团体程序设计天梯赛 GPLT

本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式：

输入第一行给出 2 个正整数 N（2 ≤ N ≤ 200，城镇总数）和 K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后 N-1 行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有 K 行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由 3 个大写英文字母组成的字符串。

输出格式：

按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->...->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10

输出样例：

PAT->PTA->PDS->DBY
3 30 210

分析：本题相对比较简单，只需要根据题目要求调整最短路径的判定条件就好，为了方便操作，这里大本营代号（字符串）与数值之间要做一个映射～ntoi保存名字到编号的转换，iton保存编号到名字的转换，num中储存各个大本营敌军数量，Num中存储歼敌总数，path中存储每个大本营由哪个地方过来的，Dis存储出发点到各点的最短距离，sum中存储路径数，liberation存储了解放的大本营个数～

#include <bits/stdc++.h>
using namespace std;
struct node {
	int id, dis;
	bool friend operator < (const node &a, const node &b) {
		return a.dis > b.dis;
	}
};
int n, k, s, t, cnt, d, num[205], Num[205], path[205], Dis[205], vis[205], sum[205], liberation[205];
map<string, int> ntoi;
map<int, string> iton;
vector<pair<int, int>> E[205];
vector<int> ans;
string S, T, u, v;
void Dijskra() {
	fill(Dis, Dis + 205, 1e9);
	Dis[s] = 0;
	sum[s] = 1;
	priority_queue<node> Q;
	Q.push(node{s, 0});
	while (!Q.empty()) {
		int Now = Q.top().id, D = Q.top().dis;
		Q.pop();
		if (vis[Now]) continue;
		vis[Now] = 1;
		for (auto it : E[Now]) {
			int V = it.first, DIS = it.second;
			if (Dis[V] > D + DIS) {
				Num[V] = Num[Now] + num[V];
				sum[V] = sum[Now];
				liberation[V] = liberation[Now] + 1;
				Dis[V] = D + DIS;
				Q.push(node{V, Dis[V]});
				path[V] = Now;
			} else if (Dis[V] == D + DIS) {
				sum[V] += sum[Now];
				if (liberation[V] < liberation[Now] + 1) {
					liberation[V] = liberation[Now] + 1;
					Num[V] = Num[Now] + num[V];
					Q.push(node{V, Dis[V]});
					path[V] = Now;
				} else if (liberation[V] == liberation[Now] + 1) {
					if (Num[V] < Num[Now] + num[V]) {
						Num[V] = Num[Now] + num[V];
						Q.push(node{V, Dis[V]});
						path[V] = Now;
					}
				}
				
			}
		}
	}
}
int main() {
	cin >> n >> k >> S >> T;
	for (int i = 0; i < n - 1; i++) {
		cin >> u >> d;
		ntoi[u] = ++cnt;
		iton[cnt] = u;
		num[cnt] = d;
	}
	ntoi[S] = 0, iton[0] = S, t = ntoi[T];
	for (int i = 0; i < k; i++) {
		cin >> u >> v >> d;
		E[ntoi[u]].push_back({ntoi[v], d});
		E[ntoi[v]].push_back({ntoi[u], d});
	}
	Dijskra();
	d = t;
	while(d) {
		ans.push_back(d);
		d = path[d];
	}
	cout << iton[0];
	for (int i = ans.size() - 1; i >= 0; i--) cout << "->" << iton[ans[i]];
	cout << '\n' << sum[t] << ' ' << Dis[t] << ' ' << Num[t] << '\n';
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct node {

int id, dis;

bool friend operator < (const node &a, const node &b) {

return a.dis > b.dis;

}

};

int n, k, s, t, cnt, d, num[205], Num[205], path[205], Dis[205], vis[205], sum[205], liberation[205];

map<string, int> ntoi;

map<int, string> iton;

vector<pair<int, int>> E[205];

vector<int> ans;

string S, T, u, v;

void Dijskra() {

fill(Dis, Dis + 205, 1e9);

Dis[s] = 0;

sum[s] = 1;

priority_queue<node> Q;

Q.push(node{s, 0});

while (!Q.empty()) {

int Now = Q.top().id, D = Q.top().dis;

Q.pop();

if (vis[Now]) continue;

vis[Now] = 1;

for (auto it : E[Now]) {

int V = it.first, DIS = it.second;

if (Dis[V] > D + DIS) {

Num[V] = Num[Now] + num[V];

sum[V] = sum[Now];

liberation[V] = liberation[Now] + 1;

Dis[V] = D + DIS;

Q.push(node{V, Dis[V]});

path[V] = Now;

} else if (Dis[V] == D + DIS) {

sum[V] += sum[Now];

if (liberation[V] < liberation[Now] + 1) {

liberation[V] = liberation[Now] + 1;

Num[V] = Num[Now] + num[V];

Q.push(node{V, Dis[V]});

path[V] = Now;

} else if (liberation[V] == liberation[Now] + 1) {

if (Num[V] < Num[Now] + num[V]) {

Num[V] = Num[Now] + num[V];

Q.push(node{V, Dis[V]});

path[V] = Now;

}

int main() {

cin >> n >> k >> S >> T;

for (int i = 0; i < n - 1; i++) {

cin >> u >> d;

ntoi[u] = ++cnt;

iton[cnt] = u;

num[cnt] = d;

}

ntoi[S] = 0, iton[0] = S, t = ntoi[T];

for (int i = 0; i < k; i++) {

cin >> u >> v >> d;

E[ntoi[u]].push_back({ntoi[v], d});

E[ntoi[v]].push_back({ntoi[u], d});

}

Dijskra();

d = t;

while(d) {

ans.push_back(d);

d = path[d];

}

cout << iton[0];

for (int i = ans.size() - 1; i >= 0; i--) cout << "->" << iton[ans[i]];

cout << '\n' << sum[t] << ' ' << Dis[t] << ' ' << Num[t] << '\n';

return 0;

}

L3-009 长城 (30 分)-PAT 团体程序设计天梯赛 GPLT

正如我们所知，中国古代长城的建造是为了抵御外敌入侵。在长城上，建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵，值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台，并迅速接力地传递到总部。

现在如图1所示，若水平为南北方向、垂直为海拔高度方向，假设长城就是依次相联的一系列线段，而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。

进一步地，假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的，每个烽火台只负责向北方（图1中向左）瞭望，而且一旦有外敌入侵，只要敌人与烽火台之间未被山体遮挡，哨兵就会立即察觉。当然，按照这一军规，对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情，他就会立即以狼烟或烽火的形式，向其南方的烽火台传递警报，直到位于最南侧的总部。

以图2中的长城为例，负责守卫的四个烽火台用蓝白圆点示意，最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情，将被哨兵们发现并沿红色折线将警报传递到总部。当然，就这个例子而言只需两个烽火台的协作，但其他位置的敌情可能需要更多。

然而反过来，即便这里的4个烽火台全部参与，依然有不能覆盖的（黄色）区域。

另外，为避免歧义，我们在这里约定，与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例，若A、B、C、D点均共线，且在D点设置一处烽火台，则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。

好了，倘若你是秦始皇的太尉，为不致出现更多孟姜女式的悲剧，如何在保证长城安全的前提下，使消耗的民力（建造的烽火台）最少呢？

输入格式：

输入在第一行给出一个正整数N（3 ≤ N ≤105），即刻画长城边缘的折线顶点（含起点和终点）数。随后N行，每行给出一个顶点的x和y坐标，其间以空格分隔。注意顶点从南到北依次给出，第一个顶点为总部所在位置。坐标为区间[−109,109)内的整数，且没有重合点。

输出格式：

在一行中输出所需建造烽火台（不含总部）的最少数目。

输入样例：

10
67 32
48 -49
32 53
22 -44
19 22
11 40
10 -65
-1 -23
-3 31
-7 59

输出样例：

分析：根据题目易知，我们需要判断一共有几个凸出来的点。可以借助堆栈结构，从南到北判断每个点是否为凸出点，不是的话说明可以被前面某个烽火台观测到，直接弹出就不用管了。每次判断三个点，当前输入点l，上一个留在堆栈内的待观察点mid和再前面一个点r，如果直线lr的斜率是否大于等于（题目特殊规定）直线lmid的斜率，是的话说明不是凸出来点。当栈中存在大于2个的点时，表示mid点为烽火。top表示栈顶，X,Y中存储折线顶点坐标，tower为模拟堆栈数组，vis数组中记录某个点是否被标记为烽火台，函数isConcave判断是否是凹点或平行中点～

#include <bits/stdc++.h>
using namespace std;
long long n, top, ans, X[100005], Y[100005], tower[100005], vis[100005];
bool isConcave (const int &l, const int &mid, const int &r) {
    return (Y[r] - Y[l]) * (X[mid] - X[l]) >= (Y[mid] - Y[l]) * (X[r] - X[l]);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i];
        if (top) {
            while (top > 1 && isConcave(i, tower[top], tower[top - 1])) top--;
            if (top != 1 && !vis[tower[top]]) vis[tower[top]] = 1, ans++;
        }
        tower[++top] = i;
    }
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

long long n, top, ans, X[100005], Y[100005], tower[100005], vis[100005];

bool isConcave (const int &l, const int &mid, const int &r) {

return (Y[r] - Y[l]) * (X[mid] - X[l]) >= (Y[mid] - Y[l]) * (X[r] - X[l]);

}

int main() {

cin >> n;

for (int i = 0; i < n; i++) {

cin >> X[i] >> Y[i];

if (top) {

while (top > 1 && isConcave(i, tower[top], tower[top - 1])) top--;

if (top != 1 && !vis[tower[top]]) vis[tower[top]] = 1, ans++;

}

tower[++top] = i;

}

cout << ans;

return 0;

}

L3-006 迎风一刀斩 (30 分)-PAT 团体程序设计天梯赛 GPLT

迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。

这里假设原始大旗的四边都与坐标轴是平行的。

输入格式：

输入第一行给出一个正整数N（≤20），随后给出N对多边形。每个多边形按下列格式给出：

kx1y1⋯xkyk

其中k（2<k≤10）是多边形顶点个数；(xi,yi)（0≤xi,yi≤108）是顶点坐标，按照顺时针或逆时针的顺序给出。

注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意3个相邻顶点不共线。

输出格式：

对每一对多边形，输出YES或者NO。

输入样例：

8
3 0 0 1 0 1 1
3 0 0 1 1 0 1
3 0 0 1 0 1 1
3 0 0 1 1 0 2
4 0 4 1 4 1 0 0 0
4 4 0 4 1 0 1 0 0
3 0 0 1 1 0 1
4 2 3 1 4 1 7 2 7
5 10 10 10 12 12 12 14 11 14 10
3 28 35 29 35 29 37
3 7 9 8 11 8 9
5 87 26 92 26 92 23 90 22 87 22
5 0 0 2 0 1 1 1 2 0 2
4 0 0 1 1 2 1 2 0
4 0 0 0 1 1 1 2 0
4 0 0 0 1 1 1 2 0

输出样例：

YES
NO
YES
YES
YES
YES
NO
YES

分析：要让两个图形能够拼接成矩形只有四种情况 1.两个直角三角形 2.两个矩形 3.一个三角形配一个五角形 4.两个直角梯形。由于题目特殊的旋转限制，直角边只会和x轴或y轴平行。非矩形情况首先判断是不是有边数 – 1 的直角边，然后判断两个图形斜边是否相等。四边形则先判断是否是两个直角梯形，是的话高且斜边都相等则符合，如果是两个矩形任意一边相等即可。k1表示第一个图形的斜率，k2表示第二个图形的斜率，SLength中储存较短的平行于x轴的边，LLength中储存较长的平行于x轴的边，SWidth中储存较短的平行于y轴的边，LWidth中储存较长的平行于y轴的边，res表示有多少条直角边，dif为两点距离～

#include <bits/stdc++.h>
using namespace std;
int n, k1, k2, SLength, LLength, SWidth, LWidth, res, dif, D1, D2, a, b;
vector<pair<int, int>> A(10), B(10);
void deal(const vector<pair<int, int>> &C, const int &l) {
    res = SLength = LLength = SWidth = LWidth = 0;
    for (int i = 0; i < l; i++) {
        if (C[i].first == C[(i + 1) % l].first) {
            res++;
            dif = abs(C[i].second - C[(i + 1) % l].second);
            if (dif > LLength) SLength = LLength, LLength = dif;
            else SLength = dif;
        } else if (C[i].second == C[(i + 1) % l].second) {
            res++;
            dif = abs(C[i].first - C[(i + 1) % l].first);
            if (dif > LWidth) SWidth = LWidth, LWidth = dif;
            else SWidth = dif;
        }
    }
}
string judge() {
    if (k1 > 5 || k2 > 5) return "NO";
    if (k1 == 4 && k2 == 4) {
        deal(A, k1);
        if (res == 4) {
            D1 = LLength, D2 = LWidth;
            deal(B, k2);
            if (res != 4) return "NO";
            if (D1 == LLength || D2 == LWidth || D2 == LLength || D1 == LWidth) return "YES";
        } else if (res == 3) {
            if (SWidth == 0) D1 = LWidth, D2 = LLength - SLength;
            else  D1 = LLength, D2 = LWidth - SWidth;
            deal(B, k2);
            if (res != 3) return "NO";
            if (SWidth == 0 && D1 == LWidth && D2 == LLength - SLength) return "YES";
            else if (SLength == 0 && D1 == LLength && D2 == LWidth - SWidth) return "YES";

        }
        return "NO";
    }
    if (k2 > k1) swap(k1, k2), swap(A, B);
    deal(A, k1);
    if (res != k1 - 1) return "NO";
    D1 = LLength - SLength, D2 = LWidth - SWidth;
    deal(B, k2);
    if (res != k2 - 1) return "NO";
    if ((D1 == LLength  && D2 == LWidth) || (D2 == LLength && D1 == LWidth)) return "YES";
    return "NO";
}
int main() {
    cin >> n;
    while (n--) {
        cin >> k1;
        for (int i = 0; i < k1; i++) cin >> A[i].first >> A[i].second;
        cin >> k2;
        for (int i = 0; i < k2; i++) cin >> B[i].first >> B[i].second;
        cout << judge() << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, k1, k2, SLength, LLength, SWidth, LWidth, res, dif, D1, D2, a, b;

vector<pair<int, int>> A(10), B(10);

void deal(const vector<pair<int, int>> &C, const int &l) {

res = SLength = LLength = SWidth = LWidth = 0;

for (int i = 0; i < l; i++) {

if (C[i].first == C[(i + 1) % l].first) {

res++;

dif = abs(C[i].second - C[(i + 1) % l].second);

if (dif > LLength) SLength = LLength, LLength = dif;

else SLength = dif;

} else if (C[i].second == C[(i + 1) % l].second) {

res++;

dif = abs(C[i].first - C[(i + 1) % l].first);

if (dif > LWidth) SWidth = LWidth, LWidth = dif;

else SWidth = dif;

}

string judge() {

if (k1 > 5 || k2 > 5) return "NO";

if (k1 == 4 && k2 == 4) {

deal(A, k1);

if (res == 4) {

D1 = LLength, D2 = LWidth;

deal(B, k2);

if (res != 4) return "NO";

if (D1 == LLength || D2 == LWidth || D2 == LLength || D1 == LWidth) return "YES";

} else if (res == 3) {

if (SWidth == 0) D1 = LWidth, D2 = LLength - SLength;

else D1 = LLength, D2 = LWidth - SWidth;

deal(B, k2);

if (res != 3) return "NO";

if (SWidth == 0 && D1 == LWidth && D2 == LLength - SLength) return "YES";

else if (SLength == 0 && D1 == LLength && D2 == LWidth - SWidth) return "YES";

}

return "NO";

}

if (k2 > k1) swap(k1, k2), swap(A, B);

deal(A, k1);

if (res != k1 - 1) return "NO";

D1 = LLength - SLength, D2 = LWidth - SWidth;

deal(B, k2);

if (res != k2 - 1) return "NO";

if ((D1 == LLength && D2 == LWidth) || (D2 == LLength && D1 == LWidth)) return "YES";

return "NO";

}

int main() {

cin >> n;

while (n--) {

cin >> k1;

for (int i = 0; i < k1; i++) cin >> A[i].first >> A[i].second;

cin >> k2;

for (int i = 0; i < k2; i++) cin >> B[i].first >> B[i].second;

cout << judge() << '\n';

}

return 0;

}

L3-023 计算图 (30 分)–PAT 团体程序设计天梯赛 GPLT

“计算图”（computational graph）是现代深度学习系统的基础执行引擎，提供了一种表示任意数学表达式的方法，例如用有向无环图表示的神经网络。图中的节点表示基本操作或输入变量，边表示节点之间的中间值的依赖性。例如，下图就是一个函数 f(x1,x2)=lnx1+x1x2−sinx2 的计算图。

现在给定一个计算图，请你根据所有输入变量计算函数值及其偏导数（即梯度）。例如，给定输入x1=2,x2=5，上述计算图获得函数值 f(2,5)=ln(2)+2×5−sin(5)=11.652；并且根据微分链式法则，上图得到的梯度 ∇f=[∂f/∂x1,∂f/∂x2]=[1/x1+x2,x1−cosx2]=[5.500,1.716]。

知道你已经把微积分忘了，所以这里只要求你处理几个简单的算子：加法、减法、乘法、指数（ex，即编程语言中的 exp(x) 函数）、对数（lnx，即编程语言中的 log(x) 函数）和正弦函数（sinx，即编程语言中的 sin(x) 函数）。

友情提醒：

常数的导数是 0；x 的导数是 1；ex 的导数还是 ex；lnx 的导数是 1/x；sinx 的导数是 cosx。
回顾一下什么是偏导数：在数学中，一个多变量的函数的偏导数，就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中，当我们对 x1 求偏导数 ∂f/∂x1 时，就将 x2 当成常数，所以得到 lnx1 的导数是 1/x1，x1x2 的导数是 x2，sinx2 的导数是 0。
回顾一下链式法则：复合函数的导数是构成复合这有限个函数在相应点的导数的乘积，即若有 u=f(y)，y=g(x)，则 du/dx=du/dy⋅dy/dx。例如对 sin(lnx) 求导，就得到 cos(lnx)⋅(1/x)。

如果你注意观察，可以发现在计算图中，计算函数值是一个从左向右进行的计算，而计算偏导数则正好相反。

输入格式：

输入在第一行给出正整数 N（≤5×104），为计算图中的顶点数。

以下 N 行，第 i 行给出第 i 个顶点的信息，其中 i=0,1,⋯,N−1。第一个值是顶点的类型编号，分别为：

0 代表输入变量
1 代表加法，对应 x1+x2
2 代表减法，对应 x1−x2
3 代表乘法，对应 x1×x2
4 代表指数，对应 ex
5 代表对数，对应 lnx
6 代表正弦函数，对应 sinx

对于输入变量，后面会跟它的双精度浮点数值；对于单目算子，后面会跟它对应的单个变量的顶点编号（编号从 0 开始）；对于双目算子，后面会跟它对应两个变量的顶点编号。

题目保证只有一个输出顶点（即没有出边的顶点，例如上图最右边的 -），且计算过程不会超过双精度浮点数的计算精度范围。

输出格式：

首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值，其间以一个空格分隔，行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后 3 位。

输入样例：

7
0 2.0
0 5.0
5 0
3 0 1
6 1
1 2 3
2 5 4

输出样例：

11.652
5.500 1.716

分析：结构体A中存储相关节点信息，de[i]表示第i个点是否被其他节点调用操作到，使用deal做dfs操作来根据题意进行题目的模拟运行，其中，c为1表示求导，c为0表示正常晕眩，index表示当前节点信息，to为求偏导数得目标，Record则是一个dfs下的记忆优化，start为一个可以作为出发点的节点。依题意输入数据后，遍历找出一个出发点节点，然后直接丢到deal函数中即可得到答案～注意导数运算的相关规则～

#include <bits/stdc++.h>
using namespace std;
struct node {
    int which, op1, op2;
    double value;
}A[50001];
int N, start = -1, cnt, de[50001];
map<bool, map<int, map<int, double>>> Record;
double deal(int c, int index, int to) {
    if (Record[c][index][to]) return Record[c][index][to];
    if (A[index].which == 0) return Record[c][index][to] = c ? (index == to ? 1.0 : 0.0) : A[index].value;
    else if (A[index].which == 1) return Record[c][index][to] = deal(c, A[index].op1, to) + deal(c, A[index].op2, to);
    else if (A[index].which == 2) return Record[c][index][to] = deal(c, A[index].op1, to) - deal(c, A[index].op2, to);
    else if (A[index].which == 3) return Record[c][index][to] = c ? (deal(1, A[index].op1, to) * deal(0, A[index].op2, to) + deal(0, A[index].op1, to) * deal(1, A[index].op2, to)) : (deal(0, A[index].op1, to) * deal(0, A[index].op2, to));
    else if (A[index].which == 4) return Record[c][index][to] = c ? exp(deal(0, A[index].op1, to)) * deal(1, A[index].op1, to) : exp(deal(0, A[index].op1, to));
    else if (A[index].which == 5) return Record[c][index][to] = c ? 1.0 / deal(0, A[index].op1, to) * deal(1, A[index].op1, to) : log(deal(0, A[index].op1, to));
    else  return Record[c][index][to] = c ? cos(deal(0, A[index].op1, to)) * deal(1, A[index].op1, to) : sin(deal(0, A[index].op1, to));
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i].which);
        if (A[i].which == 0) {
            ++cnt;
            scanf("%lf", &A[i].value);
        } else if (A[i].which < 4) {
            scanf("%d%d", &A[i].op1, &A[i].op2);
            de[A[i].op1] = de[A[i].op2] = 1;
        } else {
            scanf("%d", &A[i].op1);
            de[A[i].op1] = 1;
        }
    }
    while(de[++start]);
    printf("%.3lf\n", deal(0, start, N));
    for (int i = 0; i < N; i++) {
        if (A[i].which == 0) printf("%.3lf%c", deal(1, start, i), --cnt ? ' ' : '\n');
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct node {

int which, op1, op2;

double value;

}A[50001];

int N, start = -1, cnt, de[50001];

map<bool, map<int, map<int, double>>> Record;

double deal(int c, int index, int to) {

if (Record[c][index][to]) return Record[c][index][to];

if (A[index].which == 0) return Record[c][index][to] = c ? (index == to ? 1.0 : 0.0) : A[index].value;

else if (A[index].which == 1) return Record[c][index][to] = deal(c, A[index].op1, to) + deal(c, A[index].op2, to);

else if (A[index].which == 2) return Record[c][index][to] = deal(c, A[index].op1, to) - deal(c, A[index].op2, to);

else if (A[index].which == 3) return Record[c][index][to] = c ? (deal(1, A[index].op1, to) * deal(0, A[index].op2, to) + deal(0, A[index].op1, to) * deal(1, A[index].op2, to)) : (deal(0, A[index].op1, to) * deal(0, A[index].op2, to));

else if (A[index].which == 4) return Record[c][index][to] = c ? exp(deal(0, A[index].op1, to)) * deal(1, A[index].op1, to) : exp(deal(0, A[index].op1, to));

else if (A[index].which == 5) return Record[c][index][to] = c ? 1.0 / deal(0, A[index].op1, to) * deal(1, A[index].op1, to) : log(deal(0, A[index].op1, to));

else return Record[c][index][to] = c ? cos(deal(0, A[index].op1, to)) * deal(1, A[index].op1, to) : sin(deal(0, A[index].op1, to));

}

int main() {

scanf("%d", &N);

for (int i = 0; i < N; i++) {

scanf("%d", &A[i].which);

if (A[i].which == 0) {

++cnt;

scanf("%lf", &A[i].value);

} else if (A[i].which < 4) {

scanf("%d%d", &A[i].op1, &A[i].op2);

de[A[i].op1] = de[A[i].op2] = 1;

} else {

scanf("%d", &A[i].op1);

de[A[i].op1] = 1;

}

while(de[++start]);

printf("%.3lf\n", deal(0, start, N));

for (int i = 0; i < N; i++) {

if (A[i].which == 0) printf("%.3lf%c", deal(1, start, i), --cnt ? ' ' : '\n');

}

return 0;

}

L3-022 地铁一日游 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！

魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每 K 公里增加 1 元车费。

例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为 2 + 4 = 6 元。

为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。

坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都 1 号线和 2 号线都经过人民广场站，则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。

输入格式:
输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤ K ≤ 106)，加 1 元车费。

接下来 M 行，每行由以下格式组成：

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。

注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。

最后有 Q 行，每行一个正整数 Xi**，表示森森尝试从编号为 **Xi 的站点出发。

输出格式:
对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。

输入样例:
6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
4
2
3
4
5

输出样例:
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6

分析：Ter[i]数组表示第i个节点是不是两端的站点，Station中存储站点i直接能留下认证照的站点，Ans中存储站点i最终能留下认证照的站点，Fur_Dis中存储每个花费下能到达的最远距离，由于所有票价都有一个2的基础，所以加布加都可以。刚开始将地图的信息输入至Edge中，并记录两侧端点的信息。由于相同的两个站点也可能有不同距离的路线，所以这里需要取最小值。然后用Floyd最短路算法求出两个站点之间最短的路线。然后再遍历出每个节点到达的所有距离需要多少花费，如果该花费是最小值，说明该站点可以拍照。最后再通过简单的dfs，找出一个站点能以其他可换乘的车站作为中转点，可以到达的所有站点～

#include <bits/stdc++.h>
using namespace std;
const int Mx = 1e9;
int N, M, K, Q, from, to, dis, Ter[201], Edge[201][201];
map<int, set<int>> Station;
map<int, set<int>> Ans;
void DFS(int Start, int Now) {
    for (auto it : Station[Now]) {
        if (Ans[Start].count(it)) continue;
        Ans[Start].insert(it);
        DFS(Start, it);
    }
}
int main() {
    for (int i = 1; i <= 200; i++)
        for (int j = 1; j <= 200; j++)
            Edge[i][j] = Mx;
    scanf("%d %d %d", &N, &M, &K);
    while (M--) {
        scanf("%d", &from);
        Ter[from] = 1;
        while (1) {
            scanf("%d %d", &dis, &to);
            Edge[from][to] = Edge[to][from] = min(Edge[from][to], dis);
            from = to;
            if (getchar() == '\n') break;
        }
        Ter[to] = 1;
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++) 
                if (i != j) Edge[i][j] = min(Edge[i][j], Edge[i][k] + Edge[k][j]);
    for (int i = 1; i <= N; i++) {
        map<int, int> Fur_Dis;
        Ans[i].insert(i);
        for (int j = 1; j <= N; j++) {
            if (Edge[i][j] != Mx) {
                if (Ter[j] == 1) Station[i].insert(j);
                if (Edge[i][j] > Fur_Dis[Edge[i][j] / K]) Fur_Dis[Edge[i][j] / K] = Edge[i][j];
            }
        }
        for (int j = 1; j <= N; j++)
            if (Edge[i][j] == Fur_Dis[Edge[i][j] / K]) Station[i].insert(j);
    }
    for (int i = 1; i <= N; i++) DFS(i, i);
    scanf("%d", &Q);
    while (Q--) {
        scanf("%d", &from);
        for (auto it : Ans[from]) 
            printf("%d%c", it, (it != *Ans[from].rbegin()) ? ' ' : '\n');
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int Mx = 1e9;

int N, M, K, Q, from, to, dis, Ter[201], Edge[201][201];

map<int, set<int>> Station;

map<int, set<int>> Ans;

void DFS(int Start, int Now) {

for (auto it : Station[Now]) {

if (Ans[Start].count(it)) continue;

Ans[Start].insert(it);

DFS(Start, it);

}

int main() {

for (int i = 1; i <= 200; i++)

for (int j = 1; j <= 200; j++)

Edge[i][j] = Mx;

scanf("%d %d %d", &N, &M, &K);

while (M--) {

scanf("%d", &from);

Ter[from] = 1;

while (1) {

scanf("%d %d", &dis, &to);

Edge[from][to] = Edge[to][from] = min(Edge[from][to], dis);

from = to;

if (getchar() == '\n') break;

}

Ter[to] = 1;

}

for (int k = 1; k <= N; k++)

for (int i = 1; i <= N; i++)

for (int j = 1; j <= N; j++)

if (i != j) Edge[i][j] = min(Edge[i][j], Edge[i][k] + Edge[k][j]);

for (int i = 1; i <= N; i++) {

map<int, int> Fur_Dis;

Ans[i].insert(i);

for (int j = 1; j <= N; j++) {

if (Edge[i][j] != Mx) {

if (Ter[j] == 1) Station[i].insert(j);

if (Edge[i][j] > Fur_Dis[Edge[i][j] / K]) Fur_Dis[Edge[i][j] / K] = Edge[i][j];

}

for (int j = 1; j <= N; j++)

if (Edge[i][j] == Fur_Dis[Edge[i][j] / K]) Station[i].insert(j);

}

for (int i = 1; i <= N; i++) DFS(i, i);

scanf("%d", &Q);

while (Q--) {

scanf("%d", &from);

for (auto it : Ans[from])

printf("%d%c", it, (it != *Ans[from].rbegin()) ? ' ' : '\n');

}

return 0;

}

L3-019 代码排版 (30 分)-PAT 团体程序设计天梯赛 GPLT

某编程大赛中设计有一个挑战环节，选手可以查看其他选手的代码，发现错误后，提交一组测试数据将对手挑落马下。为了减小被挑战的几率，有些选手会故意将代码写得很难看懂，比如把所有回车去掉，提交所有内容都在一行的程序，令挑战者望而生畏。

为了对付这种选手，现请你编写一个代码排版程序，将写成一行的程序重新排版。当然要写一个完美的排版程序可太难了，这里只简单地要求处理C语言里的for、while、if-else这三种特殊结构，而将其他所有句子都当成顺序执行的语句处理。输出的要求如下：

默认程序起始没有缩进；每一级缩进是 2 个空格；
每行开头除了规定的缩进空格外，不输出多余的空格；
顺序执行的程序体是以分号“;”结尾的，遇到分号就换行；
在一对大括号“{”和“}”中的程序体输出时，两端的大括号单独占一行，内部程序体每行加一级缩进，即：

{
  程序体
}

{

程序体

}

for的格式为：

for (条件) {
  程序体
}

for (条件) {

程序体

}

while的格式为：

while (条件) {
  程序体
}

while (条件) {

程序体

}

if-else的格式为：

if (条件) {
  程序体
}
else {
  程序体
}

if (条件) {

程序体

}

else {

程序体

}

输入格式：

输入在一行中给出不超过 331 个字符的非空字符串，以回车结束。题目保证输入的是一个语法正确、可以正常编译运行的 main 函数模块。

输出格式：

按题面要求的格式，输出排版后的程序。

输入样例：

int main() {int n, i; scanf("%d", &n);if( n>0)n++;else if (n<0) n--; else while(n<10)n++; for(i=0; i<n; i++ ){ printf("n=%d\n", n);}return 0; }

1	int main() {int n, i; scanf("%d", &n);if( n>0)n++;else if (n<0) n--; else while(n<10)n++; for(i=0; i<n; i++ ){ printf("n=%d\n", n);}return 0; }

输出样例：

int main()
{
  int n, i;
  scanf("%d", &n);
  if ( n>0) {
    n++;
  }
  else {
    if (n<0) {
      n--;
    }
    else {
      while (n<10) {
        n++;
      }
    }
  }
  for (i=0;  i<n; i++ ) {
    printf("n=%d\n", n);
  }
  return  0;
}

int main()

{

int n, i;

scanf("%d", &n);

if ( n>0) {

n++;

}

else {

if (n<0) {

n--;

}

else {

while (n<10) {

n++;

}

for (i=0; i<n; i++ ) {

printf("n=%d\n", n);

}

return 0;

}

分析：point表示当前处理的文本位置，space储存但前需要在行首加多少空格，mark表示自动补充的大括号数量，use表示是否开启了大括号自动补充。在Function函数内，集成了’跳过无效空格’、’空格输出’、’关键字匹配’以及’补充的打括号补全’功能，很好用。刚开始我们需要将int main ()部分单独输出，因为该部分可能存在不可移出的空格。然后对于剩下的主体部分，主要分成三个模块处理——’大括号匹配整理’、’关键字匹配整理’以及’其余代码匹配整理’。特别注意在有些关键字后面添加了代码没有自带大括号，需要自己去补全并记录相关数量信息。在space为0时结束程序，剩下的就是简单的模拟即可～

#include <bits/stdc++.h>
using namespace std;
int point, space = 2, mark, tp, cnt, use, temp;
string s;
int Function(int c) {
    if (c == 0) while (s[point] == ' ') point++;
    else if (c == 1) for (int i = 0; i < space; i++) cout << ' ';
    else if (c == 2) {
        if (s.substr(point, 2) == "if" && (s[point + 2] == '(' || s[point + 2] == ' ')) return 2;
        else if (s.substr(point, 3) == "for" && (s[point + 3] == '(' || s[point + 3] == ' ')) return 3;
        else if (s.substr(point, 4) == "else" && (s[point + 4] == '(' || s[point + 4] == ' ')) return 4;
        else if (s.substr(point, 5) == "while" && (s[point + 5] == '(' || s[point + 5] == ' ')) return 5;
    } else if (c == 3) {
        Function(0);
        if (Function(2) == 4) return 0;
        while (mark) {
            space -= 2;
            Function(1);
            cout << "}\n";
            mark--;
        } 
    }
    return 0;
}
int main() {
    getline(cin, s);
    Function(0);
    for (int i = point; s[i] != ')'; i++) cout << s[i];
    cout << ")\n{\n";
    point = s.find('{') + 1;
    while (1) {
        Function(0);
        temp = Function(2);
        if (s[point] == '{') {
            Function(1);
            cout << "{\n";
            space += 2;
            point++;
        } else if (s[point] == '}') {
            space -= 2;
            Function(1);
            cout << "}\n";
            if (space == 0) return 0;
            Function(3);
            point++;
        } else if (temp) {
            Function(1);
            cout << s.substr(point, temp);
            point += temp;
            if (temp != 4) {
                Function(0);
                tp = point;
                cnt = 0;
                while(tp < s.size()) {
                    if (s[tp] == '(') cnt++;
                    else if (s[tp] == ')') cnt--;
                    tp++;
                    if (cnt == 0) break;
                }
                cout << ' ' << s.substr(point, tp - point);
                point = tp;
            }
            cout <<  " {\n";
            space += 2;
            Function(0);
            if (s[point] != '{') {
                use = 1;
                mark++;
            } else {
                use = 0;
                point++;
            }
        } else {
            Function(1);
            cnt = s.find(';', point);
            cout << s.substr(point, cnt - point + 1) << '\n';
            point = cnt + 1;
            if (use && mark) {
                space -= 2;
                Function(1);
                cout << "}\n";
                mark--;
                Function(3);
            }
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int point, space = 2, mark, tp, cnt, use, temp;

string s;

int Function(int c) {

if (c == 0) while (s[point] == ' ') point++;

else if (c == 1) for (int i = 0; i < space; i++) cout << ' ';

else if (c == 2) {

if (s.substr(point, 2) == "if" && (s[point + 2] == '(' || s[point + 2] == ' ')) return 2;

else if (s.substr(point, 3) == "for" && (s[point + 3] == '(' || s[point + 3] == ' ')) return 3;

else if (s.substr(point, 4) == "else" && (s[point + 4] == '(' || s[point + 4] == ' ')) return 4;

else if (s.substr(point, 5) == "while" && (s[point + 5] == '(' || s[point + 5] == ' ')) return 5;

} else if (c == 3) {

Function(0);

if (Function(2) == 4) return 0;

while (mark) {

space -= 2;

Function(1);

cout << "}\n";

mark--;

}

return 0;

}

int main() {

getline(cin, s);

Function(0);

for (int i = point; s[i] != ')'; i++) cout << s[i];

cout << ")\n{\n";

point = s.find('{') + 1;

while (1) {

Function(0);

temp = Function(2);

if (s[point] == '{') {

Function(1);

cout << "{\n";

space += 2;

point++;

} else if (s[point] == '}') {

space -= 2;

Function(1);

cout << "}\n";

if (space == 0) return 0;

Function(3);

point++;

} else if (temp) {

Function(1);

cout << s.substr(point, temp);

point += temp;

if (temp != 4) {

Function(0);

tp = point;

cnt = 0;

while(tp < s.size()) {

if (s[tp] == '(') cnt++;

else if (s[tp] == ')') cnt--;

tp++;

if (cnt == 0) break;

}

cout << ' ' << s.substr(point, tp - point);

point = tp;

}

cout << " {\n";

space += 2;

Function(0);

if (s[point] != '{') {

use = 1;

mark++;

} else {

use = 0;

point++;

}

} else {

Function(1);

cnt = s.find(';', point);

cout << s.substr(point, cnt - point + 1) << '\n';

point = cnt + 1;

if (use && mark) {

space -= 2;

Function(1);

cout << "}\n";

mark--;

Function(3);

}

return 0;

}