T1 神奇的幻方
按照题意模拟即可。
T2 信息传递
也是很水的一道题。有两种方法可以做。第一种是tarjan来求最小环，这个代码量略大。另外一种就是利用改版并查集，father数组存的是最远的祖先。具体实现看代码
#include<bits/stdc++.h>
using namespace std;
int f[200010],d[200010],n,minn,last;
int find(int x){
if (f[x]!=x){
int tmp=f[x];
f[x]=find(f[x]);
d[x]+=d[tmp];
}
return f[x];
}
int main(){
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++) f[i]=i;
minn=0x7f7f7f7f;
for (int i=1;i<=n;i++) {
int t;
cin>>t;
int x=find(i),y=find(t);
if (x!=y) f[x]=y,d[i]=d[t]+1;
else minn=min(minn,d[i]+d[t]+1);
}
cout<<minn;
return 0;
}
T3 斗地主
这题挺有意思的，写完后发现会了很多斗地主技巧。首先一个显而易见的事实：有顺子时打顺子不一定是最优的，比如说我有一副 3 4 5 6 6 7 7 8 9 10，如果要打最长的顺子，这套牌要分三次才能打完。于是乎，我们只能暴力枚举了。另外其实还需要考虑其他的细节，但是这一题是随机数据，所以不加这些细节也能AC。如果要更高端的解法请移步这一题。
#include<bits/stdc++.h>
using namespace std;
int t,n,a[20],ans;
void dfs(int x){
if (x>ans) return;
int s1,s2,s3,s4;
s1=s2=s3=s4=0;
for(int i=1;i<=14;i++)//统计单牌与对子
{
if(a[i]==1) s1++;
if(a[i]==2) s2++;
}
for(int i=1;i<=14;i++)//四带的牌
if(a[i]==4)
{
s4++;
if(s1>=2) s1-=2;
else if(s2>=2) s2-=2;
else if(s2>=1) s2--;
}
for(int i=1;i<=14;i++)//三带的牌
if(a[i]==3)
{
s3++;
if(s1>=1) s1--;
else if(s2>=1) s2--;
}
ans=min(ans,x+s1+s2+s3+s4);//手中没牌，更新方案
//以下枚举顺子
int j;
for(int i=1;i<=8;i++){
for (j=i;j<=12;j++){
a[j]--;
if (a[j]<0) break;
if(j-i>=4) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]++;
}
for (int i=1;i<=10;i++){
for(j=i;i<=12;j++){
a[j]-=2;
if(a[j]<0) break;
if(j-i>=2) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]+=2;
}
for (int i=1;i<=11;i++){
for(j=i;i<=12;j++){
a[j]-=3;
if(a[j]<0) break;
if(j-i>=1) dfs(x+1);
}
if (j>=13) j--;
while (j>=i) a[j--]+=3;
}
}
int main(){
freopen("landlords.in","r",stdin);
freopen("landlords.out","w",stdout);
cin>>t>>n;
for(int i=1;i<=t;i++){
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if (x==0) a[14]++;
if (x==1) a[12]++;
if (x==2) a[13]++;
if (x>=3) a[x-2]++;
}
ans=0x7f7f7f;
dfs(0);
cout<<ans<<endl;
}
return 0;
}