计蒜客-Arab Collegiate Programming Contest 2015
\(B\)
题意
给定两个有理数 \(\frac{a}{b},\ \frac{c}{d}\),求他们的 \(gcd\) 和 \(lcm\)
解
考虑求解 \(gcd\)
先将 \(\frac{a}{b},\ \frac{c}{d}\) 化为最简有理数
在保证能被 \(\frac{a}{b},\ \frac{c}{d}\) 整除的情况下,分母必须是最小,分子必须是最大。
分母要最小,即为 \(LCM(b,\ d)\)
所以
\[ gcd = \frac{GCD(a\cdot \frac{LCM(b,\ d)}{b},\ c\cdot \frac{LCM(b,\ d)}{d})}{LCM(b,\ d)} \]
即
\[ gcd = \frac{GCD(a\cdot \frac{d}{GCD(b,\ d)},\ c\cdot \frac{b}{GCD(b,\ d)})}{LCM(b,\ d)} \]
由于
\[ GCD(\frac{d}{GCD(b,\ d)},\ \frac{b}{GCD(b,\ d)}) = 1 \]
所以 \(gcd\) 分子为
\[ GCD(a,\ c) \]
所以
\[ gcd = \frac{GCD(a,\ c)}{LCM(b,\ d)} \]
相应的
\[ lcm = \frac{ac}{bd}\cdot \frac{LCM(b,\ d)}{GCD(a,\ c)} \]
即
\[ lcm = \frac{LCM(a,\ c)}{GCD(b,\ d)} \]
\(code\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%lld%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 5e4 + 7;
const double PI = acos(-1);
const double EPS = 1e-8;
using namespace std;
int t;
LL a, b, c, d;
LL gcd(LL x, LL y) {return y ? gcd(y, x % y) : x;}
int main()
{
scanf("%d", &t);
while(t--) {
scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
LL g1 = gcd(a, b);
LL g2 = gcd(c, d);
a /= g1, b /= g1;
c /= g2, d /= g2;
LL gcdac = gcd(a, c);
LL lcmbd = b * d / gcd(b, d);
LL gcdbd = gcd(b, d);
LL lcmac = a * c / gcd(a, c);
LL g3 = gcd(gcdac, lcmbd);
LL g4 = gcd(lcmac, gcdbd);
printf("%lld/%lld %lld/%lld\n", gcdac / g3, lcmbd / g3, lcmac / g4, gcdbd / g4);
}
return 0;
}
下回 \(tmd\) 直接找规律
\(E\)
题意
给定 \(A + B + 1\) 个数,给定 \(A\) 个 \(\&\) 运算符和 \(B\) 个 \(\mid\) 运算符,询问怎样的安排方式,使得从左至右运算的结果最大。
解
考虑分析二进制位。
贪心猜想,必须先连续进行与运算,然后连续进行或运算,这样得到的结果才最大。
一种感性的理解是,即使“或”在前面成功保护 \(1\) ,在后面的“与”中也会丧失这个 \(1\) 。
具体证明不会。
\(code\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%lld%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e5 + 7;
const double PI = acos(-1);
const double EPS = 1e-8;
using namespace std;
int t, A, B;
LL a[N];
int main()
{
scanf("%d", &t);
while(t--) {
scanf("%d %d", &A, &B);
int n = A + B + 1;
for(int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
LL ans = a[1];
for(int i = 2; i <= A + 1; ++i)
ans &= a[i];
//cout<<ans<<endl;
for(int i = A + 2; i <= A + 1 + B; ++i)
ans |= a[i];
printf("%lld\n", ans);
}
return 0;
}
/*
2
1 1
1 4 5
1
2 2
2 3 11 4 5
*/
不会做就直接找规律
\(K\)
题意
给定一棵 \(n\) 个点的树,定义 \(vulnerable\ road\) 为切断就影响两端点连通性的边,现在允许新建一条路,询问新建一条路之后图上 \(vulnerable\ road\) 的最少数量为?
解
只需要找到一条最长的链,将首尾联通即可,记链上节点共有 \(x\) 个,答案即为 \(n - x\)。
本质上就是求一个树的直径。考虑两次 \(dfs\) ,第一次从任意节点开始找到距离其最远的叶子节点,第二次从该叶子节点开始找到距离其最远的叶子节点。
\(code\)
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%lld%c", a[i], " \n"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int MOD = 1e9 + 7;
const int N = 1e4 + 7;
const double PI = acos(-1);
const double EPS = 1e-8;
using namespace std;
int t, n, vis[N];
vector<int> g[N];
void dfs(int x, int &res, int &root, int step)
{
if(!vis[x]) {
vis[x] = 1;
if(step > res) root = x, res = step;
for(auto i: g[x])
dfs(i, res, root, step + 1);
}
}
void ini(int n)
{
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i)
g[i].clear();
}
int main()
{
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
ini(n);
for(int i = 1; i < n; ++i) {
int a, b;
scanf("%d %d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
int root = 1, res = 0;
dfs(root, res, root, 1);
memset(vis, 0, sizeof(vis));
dfs(root, res, root, 1);
printf("%d\n", n - res);
}
return 0;
}
模板题,找树的直径就行。