2013 Asia Chengdu Regional Contest
B. Fibonacci Tree
解法：先跑一遍最小生成树，答案就是需要白边的最小的数量；然后再跑一遍最大生成树，答案就是需要白边的最大的数量。那么看看两个之间有没有夹着一个斐波那契数（这个可以用二分查找找出）。最后要判断图是否连通。这个可以看看最小生成树是否连了 N-1 条边。如果不是的话，图不连通。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<functional>
using namespace std
;
const int maxn
= 100010;
int N
, M
, kase
, p
[maxn
], fib
[50] = {1, 1};
struct P
{
int u
, v
, w
;
bool operator < (const P
& rhp
)const{
return w
< rhp
.w
;
}
bool operator > (const P
& rhp
)const {
return w
> rhp
.w
;
}
}G
[maxn
];
void init(int N
){
for(int i
= 1; i
<= N
; i
++) p
[i
] = i
;
}
int find(int x
){
if(p
[x
] == x
) return x
;
return p
[x
] = find(p
[x
]);
}
void unite(int a
, int b
) {
if (find(a
) == find(b
)) return;
p
[find(a
)] = find(b
);
}
int mst(){
init(N
);
int res
= 0, cnt
= 0;
for(int i
= 0; i
< M
; i
++){
int u
= G
[i
].u
, v
= G
[i
].v
, w
= G
[i
].w
;
if(find(u
) == find(v
)) continue;
unite(u
, v
);
res
+= w
;
cnt
++;
}
if(cnt
!= N
- 1) return -1;
return res
;
}
int main(){
for(int i
= 2; i
< 30; i
++){
fib
[i
] = fib
[i
- 1] + fib
[i
- 2];
}
int T
;
scanf("%d", &T
);
while(T
--){
scanf("%d%d", &N
, &M
);
for(int i
= 0; i
< M
; i
++){
scanf("%d%d%d", &G
[i
].u
, &G
[i
].v
, &G
[i
].w
);
}
sort(G
, G
+ M
);
int minimum
= mst();
sort(G
, G
+ M
, greater
<P
>());
int maximum
= mst();
bool flag
= true;
if(minimum
== -1 || maximum
== -1){
flag
= false;
}
else{
int id1
= lower_bound(fib
, fib
+ 30, minimum
) - fib
, id2
= lower_bound(fib
, fib
+ 30, maximum
) - fib
;
if(id1
== id2
) flag
= false;
}
if(flag
) printf("Case #%d: Yes\n", ++kase
);
else printf("Case #%d: No\n", ++kase
);
}
return 0;
}
J. Just Random
这个讲的是我见到的比较好的题解：传送门
#include<cstdio>
#include<algorithm>
using namespace std
;
typedef long long ll
;
ll a
, b
, c
, d
, p
, m
, kase
;
ll
gcd(ll a
, ll b
){
if(b
== 0) return a
;
return gcd(b
, a
% b
);
}
ll
cal(ll x
, ll y
){
if (x
< 0 || y
< 0) return 0;
x
++, y
++;
ll A
= x
/ p
, B
= y
/ p
;
ll C
= x
% p
, D
= y
% p
;
ll res
= p
* A
* B
+ A
* D
+ B
* C
;
C
--, D
--;
if(C
> D
) swap(C
, D
);
for(ll i
= m
; i
<= C
+ D
; i
+= p
){
if(i
< C
) res
+= i
+ 1;
else if(C
<= i
&& i
<= D
) res
+= C
+ 1;
else res
+= C
+ D
- i
+ 1;
}
return res
;
}
int main(){
int T
;
scanf("%d", &T
);
while(T
--){
scanf("%lld%lld%lld%lld%lld%lld", &a
, &b
, &c
, &d
, &p
, &m
);
ll numerator
= cal(b
, d
) - cal(a
- 1, d
) - cal(b
, c
- 1) + cal(a
- 1, c
- 1);
ll denominator
= (b
- a
+ 1) * (d
- c
+ 1);
ll divisor
= gcd(numerator
, denominator
);
printf("Case #%lld: %lld/%lld\n", ++kase
, numerator
/ divisor
, denominator
/ divisor
);
}
return 0;
}
