T1神奇的幻方
思路:
制定一个lrow记录上一个数字所在的行数，lcolume记录上一个数字所在的列数，然后根据题目的描述进行更改即可
上代码:
#include <iostream>
#include <cstdio>
using namespace std; const int Maxn = ;
int n,a[Maxn][Maxn]; int main() {
scanf("%d",&n);
int mid=n/+,Max=n*n;
int lrow=,lcolume=mid;
a[lrow][lcolume]=;
for(int i=; i<=Max; ++i) {
if(lrow== && lcolume!=n)
lrow=n,a[lrow][++lcolume]=i;
else if(lrow!= && lcolume==n)
lcolume=,a[--lrow][lcolume]=i;
else if(lrow== && lcolume==n)
a[++lrow][lcolume]=i;
else if(lrow!= && lcolume!=n) {
if(a[lrow-][lcolume+]==)
a[--lrow][++lcolume]=i;
else
a[++lrow][lcolume]=i;
}
}
for(int i=; i<=n; ++i) {
for(int j=; j<=n; ++j)
printf("%d ",a[i][j]);
printf("\n");
}
return ;
}
T2 信息传递
思路:
讲真这道题是有各种各样的作法...这里给出的是拓扑排序+dfs
上代码:
#include <iostream>
#include <cstdio> using namespace std; const int M = 2e5 + ;
int n,minn=0x7fffffff;
int t[M],ru[M];
bool v[M]; void topo(int i)
{
int v=t[i];
t[i]=;
ru[v]--;
if(!ru[v]) topo(v);
} void dfs(int x,int steps)
{
if(v[x])///环完成
{
if(steps<minn) minn=steps;///更新
return;
}
v[x]=true;
dfs(t[x],steps+);
return;
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&t[i]);
ru[t[i]]++;
}
for(int i=;i<=n;i++)
if(!ru[i]) topo(i);
for(int i=;i<=n;i++)
if(ru[i] && !v[i]) dfs(i,);
printf("%d",minn);
return ;
}
T3 斗地主
数据保证：所有的手牌都是随机生成的。
思路:
首先说在前面,这题有好几种解法....
什么bfs啊,什么dfs+贪心啊,什么dp啊.
然而我只会dfs+贪心以及dp版的,但是由于懒嘛,就只写dp版的啦~
具体完整版请出门右拐通往gaoji大佬的博客园:www.cnblogs.com/zwfymqz/
搜索斗地主:你会看到你想要的
坑点:
如上大红字,这就是为什么贪心差不多可以过的原因了吧~
在做题的时候一定要将循环里的变量搞清楚!这次吃了大亏了...qwq
上代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath> using namespace std; const int M = ;
int T,n,ans;
///手牌的组数,每组手牌的张数,记录的答案
int dp[M][M][M][M];
///dp[i][j][k][l]表示打出i套四张,j套三张,k套两张,l张单牌所需要的最少步数
int cnum[M],happens[M/];
int num[]={,,,}; int calc(int one,int two,int three,int four,int king)
{
if(king==)///只出现一张大小王
{
one++; ///当作一张单牌
king--; ///清空
}
if(king==) ///当做一张单牌来用
return dp[four][three][two][one];
else
//return min(dp[four][three][two][one+2],dp[four][three][two+1][one]);
return min(dp[four][three][two][one+],dp[four][three][two][one]+);
///当做2张单牌,或者当做一对对牌
} void dfs(int now) ///now是指已经操作的次数
{
if(now>=ans) ///最优性剪枝,这个重要
return;
memset(happens,,sizeof(happens));///清空
for(int i=;i<=;i++)
happens[cnum[i]]++; ///记录出现几次的牌有几种
ans=min(ans,now+calc(happens[],happens[],happens[],happens[],cnum[]));
for(int k=;k<=;k++) ///k表示几顺子
{
for(int i=;i<=;i++)
{
int j;
for(j=i;j<= && cnum[j]>=k;j++)///若可能组成k顺子
{
cnum[j]-=k; ///耗费掉了
if(j-i+>=num[k])
dfs(now+); ///组成k顺子成功!!!
}
for(j--;j>=i;j--)
cnum[j]+=k; ///回溯
}
}
} int main()
{
scanf("%d%d",&T,&n);
memset(dp,,sizeof(dp));
///上面那个其实没什么用...可有可无
dp[][][][]=;
///当每张都不打出去的时候,步数为0
for(int i=;i<=n;i++) ///four
for(int j=;j<=n;j++) ///three
for(int k=;k<=n;k++) ///two
for(int l=;l<=n;l++) ///one
if(i*+j*+k*+l<=n) ///在范围之内
{
///赋值为最坏情况:当每张牌都一张一张的打出去
///故将dp数组memset大概是没什么用的
dp[i][j][k][l]=i+j+k+l;
if(i)
{
///将4张牌进行分解
///(3+1) || (2+2)
dp[i][j][k][l]=min(dp[i][j][k][l],min(dp[i-][j+][k][l+],dp[i-][j][k+][l]));
///(2+1+1) || (1+1+1+1)
dp[i][j][k][l]=min(dp[i][j][k][l],min(dp[i-][j][k+][l+],dp[i-][j][k][l+]));
if(k>=)
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-][j][k-][l]+),
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-][j][k-][l]+);
///四带一对对牌(一个对牌)
if(l>=)
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-][j][k][l-]+);
///四带一对单牌(2张单牌)
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-][j][k][l]+);
///什么都不带
}
if(j)
{
///将3张牌进行分解
///(2+1) || (1+1+1)
dp[i][j][k][l]=min(dp[i][j][k][l],min(dp[i][j-][k+][l+],dp[i][j-][k][l+]));
if(k)
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-][k-][l]+);
///三带一对
if(l)
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-][k][l-]+);
///三带一
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-][k][l]+);
///什么都不带
}
if(k)
{
///将2张牌进行分解
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k-][l+]);
///一对牌
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k-][l]+);
}
if(l)///一张单牌
dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k][l-]+);
}
while(T--)
{
memset(cnum,,sizeof(cnum));
///多组数据
ans=n;
///最差情况
int ai,meiyong;
for(int i=;i<=n;i++)
{ ///读入数码,以及花色(讲真没啥用)
scanf("%d%d",&ai,&meiyong);
if(ai==)
cnum[]++;
///储存A(尖?),把A转化为14数码
else
cnum[ai]++;
///其他的按原来数码进行储存(大小王也一样~)
}
dfs();
printf("%d\n",ans);
}
return ;
}