初见安~这是近日连测的考试题目所以我也不知道出处QwQ

题目描述

  每次小x物理作业没做完时，总是会去和老师交流感情，他们之间由此建立起来良好的师生关系。于是有一天，老师带着一道物理难题来见小x。

  这道题给出了一个有n个电阻的电路，每个电阻使用一个大写字母来按字典序依次编号，一个或者多个电阻之间串联、并联或者混联构成了电路，电阻自身就是最小的电路。

  老师说：“现在告诉了你各电路之间的关系和每个电路断路的概率，请你求出整个电路断路的概率。”

  注意，我们可以视所有的电阻组成的一个总电路两端被加上了电压，当总电路不产生电流时视为整个电路断路，若总电路为若干电路串联，则任一子电路断路视为总电路断路；若总电路为若干电路并联，则并联的所有电路断路视为总电路断路；若总电路为混联，则任一混联子电路断路视为总电路断路。

样例输入

5
(A,B)((C)(D),E)
0.2
0.3
0.4
0.5
0.6

样例输出

0.2992

题解

这个题吧……其实很好想到的就是：串联【S集合】挂掉一个就全挂掉了，也就是只有全都不挂才能不断路；并联【T集合】，全部挂掉才算挂掉。所以各自的断电概率为：

串联：， 并联：。

所以这个题真正的难点在于——怎么处理题目给出的那个括号字符串。

可以看出——并联的优先级大于串联，因为并联有类似于总和的意思。嘛，看这个字符串的话，我们肯定是从括号入手。可以想到类似于dfs分解各个区间的做法……【似乎不可行？反正我没写出来QwQ】

正解做法是：就像处理四则运算的表达式一样，如果是并联的话，我们需要注意在括号之间加一个符号以辨认，类似于'*'。

接下来看处理的思路：

我们涉及到的符号有：前后括号，乘号和逗号，如果遇到了后括号就要去匹配前括号并且让括号内的内容算出答案。然而如果遇到了括号才计算的话很麻烦，所以我们边扫边算。遇到了字母，就把这个电阻的概率放进数组s2,；如果是上述符号，就放进数组s1，遇到了后括号或者另外两种操作符的时候就把s2的值取出来用，顺便覆盖下，符号也跟着在s1里面往前面删。

当然如果是前括号的话直接扔进s1里面就可以了。

为了添加'*'的操作方便，我们把读入的s数组处理到了ss数组里。

代码有参考ls大佬】

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100
using namespace std;
typedef double ll;
int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

int n, t1 = 0, t2 = 0, m = 0;
ll p[maxn];
char s[maxn], ss[maxn], s1[maxn];
ll s2[maxn];

ll cal(ll a, ll b, char c) {
	if(c == '*') return a * b;
	else return a + b - a * b;//因为涉及到的都是 两两操作，所以简化后：1-(1-x)*(1-y)=1-(1+x*y-x-y) 
}

void work() {
	ll x;
	for(int i = 1; i <= m; i++) {
		if(ss[i] >= 'A' && ss[i] <= 'Z') s2[++t2] = p[ss[i] - 'A'];//把数值放进去 
		else if(ss[i] == ')') {while(s1[t1] != '(') x = cal(s2[t2], s2[t2 - 1], s1[t1--]), s2[--t2] = x; t1--;}//后括号就去找前括号 
		else if(ss[i] == '@') {while(t1) x = cal(s2[t2], s2[t2 - 1], s1[t1--]), s2[--t2] = x;}//到底了，开始清空之前存下来的操作符 
		else if(ss[i] == ',') {while(s1[t1] == '*') x = cal(s2[t2], s2[t2 - 1], s1[t1--]), s2[--t2] = x;  s1[++t1] = ss[i];}//
		else if(ss[i] == '*') {while(s1[t1] == '*') x = cal(s2[t2], s2[t2 - 1], s1[t1--]), s2[--t2] = x;  s1[++t1] = ss[i];}//这两行操作一样的 
		else s1[++t1] = ss[i]; //再如果就是前括号了 
		//注意，上方都是先计算出cal（）再赋值给的s2[--t2]，这里t2的值不能提前减一。 
	}
}

signed main() {
	n = read(); scanf("%s", s + 1);
	for(int i = 0; i < n; i++) scanf("%lf", &p[i]);
	
	for(int i = 1; i <= strlen(s + 1); i++) {
		if(s[i] == '(' && s[i - 1] == ')') ss[++m] = '*';
		ss[++m] = s[i];//处理s数组到ss 
	}
	
	ss[++m] = '@'; //s随便加个符号表示是最后一个了 
	work();
	printf("%.4lf\n", s2[1]);
	return 0;
}

迎评QwQ

——End——