首页 > 其他 > 详细

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

时间:2017-01-16 22:22:22      阅读:239      评论:0      收藏:0      [点我收藏+]

每日一练

 

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!