电阻resistance_电阻大全

初见安~这是近日连测的考试题目所以我也不知道出处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——