hdu 4786 Fibonacci Tree http://acm.hdu.edu.cn/showproblem.php?pid=4786
copyright@ts 算法源于ts，用最小生成树可以求出最小权值，把所有边权取反可以求出最大权值，算法是如果有个斐波那契数在最小到最大值之间，就一定能构成。也就是如果大了就把1边换成0边，反之亦然。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const int M=;
class Kruskal { ///最小生成树(无向图)o(ME*logME)
typedef int typec;///边权的类型
static const int ME=M;///边的个数
static const int MV=M;///点的个数
class UnionFindSet { ///并查集
int par[MV];
public:
void init() {
mt(par,-);
}
int getroot(int x) {
int i=x,j=x,temp;
while(par[i]>=) i=par[i];
while(j!=i) {
temp=par[j];
par[j]=i;
j=temp;
}
return i;
}
bool unite(int x,int y) {
int p=getroot(x);
int q=getroot(y);
if(p==q)return false;
if(par[p]>par[q]) {
par[q]+=par[p];
par[p]=q;
} else {
par[p]+=par[q];
par[q]=p;
}
return true;
}
} f;
struct E {
int u,v;
typec w;
friend bool operator < (E a,E b) {
return a.w<b.w;
}
} e[ME];
int le,num,n;
typec res;
public:
void init(int tn){///传入点的个数
n=tn;
le=res=;
f.init();
num=;
}
void add(int u,int v,typec w) {
e[le].u=u;
e[le].v=v;
e[le].w=w;
le++;
}
typec solve(){///返回-1不连通
sort(e,e+le);
for(int i=; i<le&&num<n; i++) {
if(f.unite(e[i].u,e[i].v)) {
num++;
res+=e[i].w;
}
}
if(num<n) res=-;
return res;
}
}gx;
struct IN{
int u,v,w;
}e[M];
int F[];
void yes(){
puts("Yes");
}
void no(){
puts("No");
}
int main(){
F[]=F[]=;
for(int i=;i<;i++){
F[i]=F[i-]+F[i-];
}
int t,n,m;
while(~scanf("%d",&t)){
for(int cas=;cas<=t;cas++){
scanf("%d%d",&n,&m);
gx.init(n);
for(int i=;i<m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
gx.add(e[i].u,e[i].v,e[i].w);
}
int sma=gx.solve();
printf("Case #%d: ",cas);
if(sma==-){
no();
continue;
}
gx.init(n);
for(int i=;i<m;i++){
gx.add(e[i].u,e[i].v,-e[i].w);
}
int big=-gx.solve();
bool flag=false;
for(int i=;i<;i++){
if(sma<=F[i]&&F[i]<=big){
flag=true;
break;
}
}
if(flag){
yes();
}
else{
no();
}
}
}
return ;
}
Hard Disk Drive http://acm.hdu.edu.cn/showproblem.php?pid=4788
简单计算。1kb当成1000b，但是计算机当成1024b是1kb，所以输入1kb，实际上只有1000b/1024b个kb。
#include<cstdio>
char op[];
char cmp[][]={"B","KB","MB","GB","TB","PB","EB","ZB","YB"};
int main(){
int t,pre;
double now;
while(~scanf("%d",&t)){
for(int cas=;cas<=t;cas++){
scanf("%d[%s",&pre,op);
now=pre;
int num=;
for(int i=;i<;i++){
if(cmp[i][]==op[]){
num=i;
break;
}
}
for(int i=;i<num;i++){
now*=;
now/=;
}
printf("Case #%d: %.2f",cas,(pre-now)*/pre);
puts("%");
}
}
return ;
}
Just Random http://acm.hdu.edu.cn/showproblem.php?pid=4790
题目要求 算 (x + y) mod p = m的概率，其中x属于a，b区间 y属于c，d区间。copyright@ts
考虑选择是随机等概率的。所以概率是出现上式的个数除以总的个数。总的个数好求，就是这个矩形区间长乘宽。
然后可以将矩形每一个点的值画出来，
1 2 3 4 5 这个是长度区间
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
这个是宽度区间
可以发现斜着的值是相等的。
矩阵中3,4,5的个数都是相等的，1,2构成的三角形分为第一区间，中间都相等的分为第二区间，后面的三角形分为第三区间。
因为是mod p 所以每p个会出现一个，所以第一第三区间中都是等差数列，求首项公差项数去求和，中间只要算出个数乘斜着的长度就是总的个数。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef __int64 LL;
LL gcd(LL a,LL b) { ///最大公约数
return b?gcd(b,a%b):a;
}
int main() {
int t;
LL a,b,c,d,p,m;
while(~scanf("%d",&t)) {
for(int cas=; cas<=t; cas++) {
scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&p,&m);
if((b-a+)>(d-c+)) {
swap(a,c);
swap(b,d);
}
LL ans=;
LL k=(a+c-m)/p;///第一个区间
if(a+c-m>=&&(a+c-m)%p!=) {
k++;
}
if(k*p+m<=b+c-) {
LL first=k*p+m;
LL t=first-c;
LL a1=t-a+;
LL num=(b+c--first)/p+;
ans+=(a1+a1+p*(num-))*num/;
}
k = (b+c-m)/p;///第二个区间
if((b+c-m)>=&&(b+c-m)%p!=) {
k++;
}
if(k*p+m<=a+d) {
LL first=k*p+m;
LL num=(a+d-first)/p+;
ans+=num*(b-a+);
}
k=(a+d+-m)/p;///第三个区间
if(a+d+-m>=&&(a+d+-m)%p!=) {
k++;
}
if(k*p+m<=b+d) {
LL first=k*p+m;
LL num=(b+d-first)/p+;
LL t=first-d;
LL a1=b-t+;
ans+=(a1+a1-p*(num-))*num/;
}
printf("Case #%d: ",cas);
if(!ans) {
puts("0/1");
continue;
}
LL fenmu=(b-a+)*(d-c+);
LL d=gcd(ans,fenmu);
printf("%I64d/%I64d\n",ans/d,fenmu/d);
}
}
return ;
}
Assignment For Princess http://acm.hdu.edu.cn/showproblem.php?pid=4781
构造一个图，n点m边，边权是1到m。保证没有重边没有自环。保证两两可达。任意一个回路的边权和要是3的倍数。
首先把n个点连成一个环。先满足两两可达的条件，1到2，。。。。n-1到n就直接用前一个的点的值来作为边权，n到1要算一下之前的和，然后选一个值保证总和是3的倍数。
构造成环以后，剩下的边只要考虑形成的环是3的倍数就行。
n^2的枚举两个点来连，能连的条件是他们之间没有边，并且构成的回路要是3的倍数。假设当前枚举到我们要加 i ---> j 如果和我们之前的大环小到大是同向的，那么就会和大环中的 j到i构成环。也就是说这个边 mod 3的余数 要和大环中i到j的余数相同。比如图中，如果想加入1到3，那么他会和原图的3->4->1构成环也就是他mod3要等于原来1到2到3的和mod3.
如果是反向的，那就要和大环中求和 mod 3 ==0 。可以预处理出大环1到 i的和，通过相减的关系就可以求出任意一段的和。
如图，如果要加3到1的，那就会和原来的1到2到3 形成环。也就是要和1到2到3的和相加是3的倍数。
#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=;
struct G{
struct E{
int u,v,w;
}e[M];
int le;
void init(){
le=;
}
void add(int u,int v,int w){
e[le].u=u;
e[le].v=v;
e[le].w=w;
le++;
}
}g;
bool mat[M][M];
int sum[M];
bool vis[M];
int main() {
int t,n,m;
while(~scanf("%d",&t)) {
for(int cas=; cas<=t; cas++) {
scanf("%d%d",&n,&m);
printf("Case #%d:\n",cas);
g.init();
sum[]=;
sum[]=;
mt(vis,);
for(int i=; i<n; i++) {
vis[i]=true;
g.add(i,i+,i);
sum[i+]=sum[i]+i;
}
for(int i=; i<; i++) {
if((n+i+sum[n])%==) {
vis[n+i]=true;
g.add(n,,n+i);
break;
}
}
mt(mat,);
for(int i=; i<g.le; i++) {
int u=g.e[i].u;
int v=g.e[i].v;
mat[u][v]=true;
mat[v][u]=true;
}
bool ok=true;
for(int e=n; e<=m; e++) {
if(vis[e]) continue;
bool add=false;
for(int i=; i<=n; i++) {
for(int j=; j<=n; j++) {
if(i==j) continue;
if(mat[i][j]) continue;
if(i<j) {
int tmp=sum[j]-sum[i];
if(e%==tmp%) {
g.add(i,j,e);
add=true;
mat[i][j]=true;
mat[j][i]=true;
break;
}
} else {
int tmp=sum[j]-sum[i];
if((e+tmp)%==) {
g.add(i,j,e);
add=true;
mat[i][j]=true;
mat[j][i]=true;
break;
}
}
}
if(add) break;
}
if(!add) {
ok=false;
break;
}
}
if(ok) {
for(int i=; i<g.le; i++) {
printf("%d %d %d\n",g.e[i].u,g.e[i].v,g.e[i].w);
}
} else {
puts("-1");
}
}
}
return ;
}
end