题意 裸题 匈牙利算法
Wa 了一发 忘了 vis[i]=0
哈哈哈，写的匈牙利 有问题!!! 这道竟然过了，
应该 是 if（vis[i]&& ma[i][x]）
{
balabal
}
vis[i]不用归零。
#include <cstdio>
#include <vector>
#include<cstring>
#include<iostream>
using namespace std;
int cp[501][501];
int p[501];
bool vis[501];
int K,M,N;
bool fin(int x)
{
for(int i=1;i<=N;i++)
{
if(vis[i]==0)
{
vis[i]=1;
if((cp[x][i]&&p[i]==0)||cp[x][i]&&fin(p[i]))
{
p[i]=x;
return true;
}
vis[i]=0;
}
}
return false;
}
int main()
{
int a,b;
while(scanf("%d",&K)&&K!=0)
{
scanf("%d",&M);
scanf("%d",&N);
int ans=0;
memset(cp,0,sizeof(cp));
memset(p,0,sizeof(p));
for(int i=0;i<K;i++)
{
scanf("%d%d",&a,&b);
cp[a][b]=1;
}
for(int i=1;i<=M;i++)
{
memset(vis,0,sizeof(vis));
if(fin(i))
{
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
理解 汉诺塔 问题，递归
谢谢 大佬的博客
关于 递归 问题 从后 往前推，中间输出 a->c 让 递归去解决 之前 和之后的问题。如果 要 到达 a (1) b(n-1) c(0) 的效果，需要 往前推 的情况，就能知道 递归出口
# include <stdio.h>
void hanoi ( int n, char a, char b, char c ) //这里代表将a柱子上的盘子借助b柱子移动到c柱子
{ if (1 == n) //如果是一个盘子直接将a柱子上的盘子移动到c
{
printf("%c-->%c\n",a,c);
}
else
{
hanoi ( n-1, a, c, b ) ; //将a柱子上n-1个盘子借助c柱子，移动到b柱子
printf("%c-->%c\n",a , c) ; //再直接将a柱子上的最后一个盘子移动到c
hanoi ( n-1, b, a, c ) ; //然后将b柱子上的n-1个盘子借助a移动到c
}
}
int main ()
{ int n ;
printf( "Input the number of diskes:") ;
scanf("%d",&n) ;
hanoi ( n, 'A' , 'B' , 'C' ) ;
return 0;
}
这一年 理论AV AC 姿势 涨了不少，但是 代码能力 并没有 呀。
复习 了一下 汉诺塔，递归,之前wa 的代码 使用的 1<<64 但是 居然不对，换成 pow(2.0,i)就对了，excuse me ,！！
题解： 算一道 DP 吧 看了别人的代码 A的 我太 vegetable了吧，
感谢 大佬的 博客
#include <iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
unsigned long long dp[1001];
int main()
{
// freopen("e://duipai//data.txt","r",stdin);
// freopen("e://duipai//out1.txt","w",stdout);
dp[1]=1;
dp[2]=3;
dp[3]=5;
dp[0]=0;
unsigned long long x=((1<<64)-1);
// cout<<x<<endl;
for(int i=4;i<=64;i++)
{
dp[i]=(1<<64)-1;
for(int j=1;j<=i;j++)
{
x=2*dp[j]+pow(2.0,i-j)-1;
// cout<<2*dp[j]+(1<<(i-j-1))-1+(1<<(i-j-1))<<endl;
if(x<dp[i])
{
dp[i]=x;
//cout<<i<<" "<<j<<" "<<dp[i]<<endl;
}
}
}
while(cin>>n)
{
cout<<dp[n]<<endl;
}
return 0;
}
//#include<cstdio>
//#include<cstring>
//#include<ctime>
//#include<cstdlib>
//int main(void)
//{
// freopen("e://duipai//data.txt","w",stdout);
// // srand(time(NULL));
// int n=64;//n多少自己定
// while(n)
// {
// printf("%d\n",n--);
// }
// return 0;
//}
//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<cmath>
//
//using namespace std;
//
//const int INF=99999999;
//
//int f[65];
//
//void Init(){
// f[1]=1; f[2]=3;
// for(int i=3;i<65;i++){
// int minx=INF;
// for(int x=1;x<i;x++)
// if(2*f[x]+pow(2.0,i-x)-1<minx)
// minx=2*f[x]+pow(2.0,i-x)-1;
//
// /*写成下面这样就错了,估计是tmp溢出了
// for(int x=1;x<i;x++){
// int tmp=2*f[x]+pow(2.0,i-x)-1;
// if(tmp<minx)
// minx=tmp;
// }
// */
// f[i]=minx;
// }
//}
//
//int main(){
//
// //freopen("input.txt","r",stdin);
//
// freopen("e://duipai//data.txt","r",stdin);
// freopen("e://duipai//out2.txt","w",stdout);
// int n;
// Init();
// while(~scanf("%d",&n)){
// printf("%d\n",f[n]);
// }
// return 0;
//}
汉诺塔③
今天终于 一A 了一题了，题意 只通过 B 来转移 ， 原来 是
A(n) B(0) C(0) -> A(1) B(0) C(n-1) ->A(0) B(1) C(n-1) ->A
C(0) ->A(n-1) B(1) C(0) ->A(n-1) B(0) C(1) 重复 通过B 把 两边n-1 换位置的 次数为 dp[n-1] 由 上面可知 有三次 换位置 加上 把A中最下面一个 移到 B, B 移到C 总共 3*dp[n-1]+2，
#include <iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
unsigned long long dp[1001];
int main()
{
// freopen("e://duipai//data.txt","r",stdin);
// freopen("e://duipai//out1.txt","w",stdout);
dp[0]=0;
dp[1]=2;
dp[2]=8;
dp[3]=26;
for(int i=4;i<=35;i++)
{
dp[i]=dp[i-1]*3+2;
}
while(cin>>n)
{
cout<<dp[n]<<endl;
}
return 0;
}
#include <iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
unsigned long long dp[1001];
unsigned long long sum[1001];
unsigned long long dp2[1001];
int main()
{
// freopen("e://duipai//data.txt","r",stdin);
// freopen("e://duipai//out1.txt","w",stdout);
dp[0]=0;
dp[1]=2;
dp[2]=8;
sum[0]=0;
sum[1]=2;
sum[2]=10;
dp2[1]=1;
dp2[2]=4;
for(int i=3;i<=35;i++)
{
dp[i]=dp[i-1]*3+2;
sum[i]=sum[i-1]+dp[i];
dp2[i]=sum[i-1]+i;
}
int t;
cin>>t;
while(t--)
{
cin>>n;
// cout<<dp[n]<<endl;
cout<<2*dp2[n-1]+2<<endl;
}
return 0;
}
找规律 吧 ，普通的汉诺塔，每一片的移动次数。
#include<iostream>
#include<cmath>
using namespace std;
int n;
int k;
int main()
{
unsigned long long xy;
int t;
cin>>t;
while(t--)
{
cin>>n>>k;
xy=pow(2.0,n-k);
cout<<xy<<endl;
}
return 0;
}
汉诺塔 ⑥
找规律 ， 汉诺塔 在移动过程中 可能产生的情况 一共有多少种？
#include<iostream>
#include<cmath>
using namespace std;
int n;
int k;
int main()
{
//cout<<log2(68630377364883)/log2(3)<<endl;
unsigned long long xy;
int t;
cin>>t;
while(t--)
{
cin>>n;
xy=pow(3.0,n);
cout<<xy<<endl;
}
return 0;
}
谢谢大佬的博客
可能理解的不够吧，还是wa 了几发
，想了一下 ，n 在 A或C 的话，n-1 必在 在它本身或者 辅助 a2 中。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[65];
int b[65];
int c[65];
int po[65];
bool hanoi(int x,int a1,int a2,int a3)
{
if(x<=0)
{
return true;
}
if(x==1&&po[x]!=a2)
{
return true;
}
else{
if(po[x]==a1)
{
if(po[x-1]==a1)
return hanoi(x-2,a1,a2,a3);
else if(po[x-1]==a2)
return hanoi(x-2,a3,a1,a2);
}
else if(po[x]==a3)
{
if(po[x-1]==a2)
return hanoi(x-2,a2,a3,a1);
else if(po[x-1]==a3)
return hanoi(x-2,a1,a2,a3);
}
}
return false;
}
int main()
{
int t;
cin>>t;
int n;
int aa,bb,cc;
while(t--)
{
cin>>n;
cin>>aa;
for(int i=1;i<=aa;i++)
{
cin>>a[i];
po[a[i]]=1;
}
cin>>bb;
for(int i=1;i<=bb;i++)
{
cin>>b[i];
po[b[i]]=2;
}
cin>>cc;
for(int i=1;i<=cc;i++)
{
cin>>c[i];
po[c[i]]=3;
}
if(hanoi(n,1,2,3))
{
cout<<"true"<<endl;
}
else
{
cout<<"false"<<endl;
}
}
return 0;
}
复习了一下 llu 输入 unsigned long long 引用传值
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;// 输入输出用llu
int po[65];
void hanoi(int n,ull m,int *a,int &ac,int *b,int &bc,int *c,int &cc)
{
if(m==0)
{
while(n)
{
a[ac++]=n--;
}
}
else
{
if(m<(ull)pow(2.0,n-1))
{
// cout<<"<< "<< (ull)pow(2.0,n-1)<<endl;
a[ac++]=n;
hanoi(n-1,m,a,ac,c,cc,b,bc);
}
else
{
// cout<<">= "<< m-(ull)pow(2.0,n-1)<<endl;
c[cc++]=n;
ull temp=m-(ull)pow(2.0,n-1);
hanoi(n-1,temp,b,bc,a,ac,c,cc);
}
}
}
int main()
{
int t;
cin>>t;
ull m;
int n;
int a[65];
int b[65];
int c[65];
while(t--)
{
scanf("%d %llu",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int ac,bc,cc;
ac=bc=cc=0;
hanoi(n,m,a,ac,b,bc,c,cc);
if(ac)
{
cout<<ac<<" ";
cout<<a[0];
}
else
{
cout<<0;
}
for(int i=1;i<ac;i++)
{
cout<<" "<<a[i];
}
cout<<endl;
if(bc)
{
cout<<bc<<" ";
cout<<b[0];
}
else
{
cout<<0;
}
for(int i=1;i<bc;i++)
{
cout<<" "<<b[i];
}
cout<<endl;
if(cc)
{
cout<<cc<<" ";
cout<<c[0];
}
else
{
cout<<0;
}
for(int i=1;i<cc;i++)
{
cout<<" "<<c[i];
}
cout<<endl;
}
return 0;
}
判断 第m 次移动的汉诺塔是那一块，改了上面 汉诺塔 8 的代码 1 A了。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;// 输入输出用llu
int po[65];
void hanoi(int n,ull m,int *a,int &ac,int *b,int &bc,int *c,int &cc)
{
if(m==0)
{
cout<<n+1<<endl;
return ;
}
else
{
if(m<(ull)pow(2.0,n-1))
{
// cout<<"<< "<< (ull)pow(2.0,n-1)<<endl;
a[ac++]=n;
hanoi(n-1,m,a,ac,c,cc,b,bc);
}
else
{
// cout<<">= "<< m-(ull)pow(2.0,n-1)<<endl;
c[cc++]=n;
ull temp=m-(ull)pow(2.0,n-1);
hanoi(n-1,temp,b,bc,a,ac,c,cc);
}
}
}
int main()
{
int t;
ull m;
int n;
int a[65];
int b[65];
int c[65];
while(scanf("%d %llu",&n,&m)&&(n!=0))
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int ac,bc,cc;
ac=bc=cc=0;
hanoi(n,m,a,ac,b,bc,c,cc);
}
return 0;
}
改了一下 汉诺塔 ⑨ 1 A了 ，就记录一下 之前 是那根柱子，最后在那根柱子即可，判断在哪根柱子可以 看 柱子上是否有该 盘子即可。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;// 输入输出用llu
int po[65];
int ans=0;
int f=0;
int f2=0;
void hanoi(int n,ull m,int *a,int &ac,int *b,int &bc,int *c,int &cc)
{
if(m==0)
{
ans=n+1;
return ;
}
else
{
if(m<(ull)pow(2.0,n-1))
{
// cout<<"<< "<< (ull)pow(2.0,n-1)<<endl;
a[ac++]=n;
hanoi(n-1,m,a,ac,c,cc,b,bc);
}
else
{
// cout<<">= "<< m-(ull)pow(2.0,n-1)<<endl;
c[cc++]=n;
ull temp=m-(ull)pow(2.0,n-1);
if(temp==0)
{
f=a[ac-1];
}
hanoi(n-1,temp,b,bc,a,ac,c,cc);
}
}
}
int main()
{
int t;
ull m;
int n;
int a[65];
int b[65];
int c[65];
scanf("%d",&t);
while(t--)
{
scanf("%d %llu",&n,&m);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
int ac,bc,cc;
ac=bc=cc=0;
hanoi(n,m,a,ac,b,bc,c,cc);
// cout<<f<<" f"<<endl;
if(ac)
{
if(a[ac-1]==f)
{
cout<<ans<<" "<<1;
}
}
if(bc)
{
if(b[bc-1]==f)
{
cout<<ans<<" "<<2;
}
}
if(cc)
{
if(c[cc-1]==f)
{
cout<<ans<<" "<<3;
}
}
if(ac)
{
if(a[ac-1]==ans)
{
cout<<" "<<1<<endl;
}
}
if(bc)
{
if(b[bc-1]==ans)
{
cout<<" "<<2<<endl;
}
}
if(cc)
{
if(c[cc-1]==ans)
{
cout<<" "<<3<<endl;
}
}
}
return 0;
}
12月23号做了牛客网的题，(╥╯^╰╥) 初赛没有进，被高中生的吊打了，努力一点应该能进的。 题还是挺水的，抖机灵，看发挥吧。
