2018 CCPC 吉林站 G题
用不超过1e4个1Ω的电阻，通过多次并联或串联，构造出一个接近目标大小的等效电阻。目标电阻为(0.1<=r<=0.9)的实数，构造出的等效电阻与目标大小相差不能超过1e-7。
这题比较假，标算说是直接拆成几个埃及分数之和就好了，也就是把几组并联的电阻再串起来。当然随便弄会用掉太多电阻，所以随机一下或者是暴力一下，数据比较弱就过了。
当时想的是连分数分解，大部分情况下用不了多少电阻。但是对于特殊数据，像0.1000001这种会挂，暴力打表发现有几千个这样的数就没敢写。后来发现数据比较水根本没这种情况可以过，但中间还因为分解的精度问题wa了很多遍。(以后连分数分解一定要写成有理分数做gcd的。)
#include <bits/stdc++.h>using namespace std;
typedef double db;
int d[100],dc;
db x;bool ok(){
db r=d[dc-1];
for (int i=dc-2;i>=0;i--){
r=d[i]+1/r;
}//cout<<1/r-x<<'\n';return fabs(1/r-x)<9e-8;
}int al[50000],ar[50000],ap[50000],ac;
int main()
{int kase=0; int T; cin>>T;
//for (x=0.1;x<0.9;x+=0.0000001){while (cin>>x){
db r=x;
dc=0;
do{
r=1/r;
d[dc++]=(int)(r+1e-13);
r-=(int)(r+1e-13);
}while (!ok());
kase++;
//for (int i=0;i<dc;i++) cout<<d[i]<<' '; cout<<'\n';int un=accumulate(d,d+dc,0),u0=0;
if (d[dc-1]==1){
dc--;
d[dc-1]++;
}printf("Case %d:\n%d ",kase,un);
ac=0;
for (int i=dc-1;i>=0;i--){
if (i==dc-1){
al[ac]=0,ar[ac]=1,ap[ac]=!(i&1),ac++;
u0=2;
for (int j=0;j<d[i]-2;j++)
al[ac]=u0++,ar[ac]=un++,ap[ac]=!(i&1),ac++;
}else{
for (int j=0;j<d[i];j++)
al[ac]=u0++,ar[ac]=un++,ap[ac]=!(i&1),ac++;
}}printf("%d\n",ac);
for (int i=0;i<ac;i++){
printf("%d %d %d\n",ap[i],al[i],ar[i]);
}}//cout<<cnt<<'\n';return 0;
}