2017寒假练习题解 第一周 1.16-1.22

每日一练

1.16

Problem A Simple Molecules

题意：给一个三元分子各原子的共价键数，问能否构造出符合题意的分子。

简析：设三个原子共价键数分别为a,b,c，且原子1与2,2与3,3与1,之间相连的键数为x,y,z，

　　　　　　　　　　　　　　　　　　得到线性方程组

$$ \left\{
\begin{aligned}
a  = z + x \\
b  = x + y\\
c  = y + z
\end{aligned}
\right.
$$

　　　　　　　　　　　　　　　　　　容易解得

$$ \left\{
\begin{aligned}
x  = \frac{a + b - c}{2} \\
y  = \frac{b + c - a}{2}\\
z  = \frac{c + a - b}{2}
\end{aligned}
\right.
$$

　　只要解得x，y，z都是非负整数即可，否则无解。

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    int x = a + b - c, y = b + c - a, z = c + a - b;
    if(x < 0 || y < 0|| z < 0 || x % 2 || y % 2 || z % 2) puts("Impossible");
    else printf("%d %d %d\n", x / 2 , y / 2 , z / 2 );
    return 0;
}

参考代码

Problem B Rational Resistance

题意：给无限多个单位电阻，每次只能串联或者并联一个单位电阻，问最少要几个电阻才能构造出阻值为a/b的电阻。

简析：先反过来考虑，假设一个电阻的阻值为$\frac{x}{y}$，串联一个单位电阻，其阻值变化为$\frac{x + y}{y} > 1$.

　　　如果并联一个单位电阻，其阻值变化为$\frac{x}{x + y} < 1$.

　　　现在回到原来的问题，我们只要判断a与b的大小就能知道这个电阻是串联了一个单位电阻还是并联了一个单位电阻。

　　　如果$a > b$，那么是由$\frac{a - b}{b}$与1串联得到，如果$a < b$，那么是由$\frac{a}{b - a}$与1并联得到。

　　　只要重复这个过程直到a与b有一个为0结束。

　　　需要注意的是，纯粹的模拟这个过程是会TLE的，例如a = 1e18, b = 1, 显然不能重复 a -= b, ans++; 1e18次。

　　　正确的做法是 ans += a / b, a %= b; 于是变成了辗转相除的过程，复杂度为$O(logN)$。

#include <iostream>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b) {return ( a % b ? gcd(b, a % b) : 0 ) + a / b;}
int main()
{
    LL a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

参考代码

2017寒假练习题解 第一周 1.16-1.22

原文：http://www.cnblogs.com/chdacm/p/6291153.html