2022-9-20
T1：
扫雷
一眼看上去是一个DP题，但通过观察样例以及自己列举数据可以发现，若整个矩阵的第一个已确定是否有雷，那么整个矩阵都可以确定了。因此所有情况只可能有\(0\)或\(1\)或\(2\)种方案。所以我们枚举第一个为\(0\)或\(1\)，代表没有雷或有雷，再依次确定剩下的位置，若在某个位置与上面有冲突，那么这种情况即不存在。
代码：
#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;
int n,a[MAXN],dp[MAXN],flag=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
if(a[1]==3||a[n]==3){printf("0");return 0;}
for(int j=0;j<=1;j++)
{
memset(dp,-1,sizeof(dp));
dp[1]=j;
dp[0]=0;
for(int i=1;i<=n;i++)
{
if(a[i]==0)
{
if(dp[i-1]||dp[i]){break;}
dp[i+1]=0;
}
else if(a[i]==1)
{
if(dp[i-1]&&dp[i]){break;}
else if((!dp[i-1])&&(!dp[i]))
{
if(i<n)dp[i+1]=1;
else break;
}
else dp[i+1]=0;
}
else if(a[i]==2)
{
if(i==1)
{
if(!dp[i])break;
if(i<n)dp[i]=dp[i+1]=1;
else break;
}
else
{
if((!dp[i-1])&&(!dp[i])){break;}
else if(dp[i-1]&&dp[i])dp[i+1]=0;
else
{
if(i<n)dp[i+1]=1;
else break;
}
}
}
else if(a[i]==3)
{
if((!dp[i-1])||(!dp[i])){break;}
if(i<n)dp[i+1]=1;
else break;
}
if(i==n)flag++;
}
}
printf("%d",flag);
return 0;
}
T2：
互不侵犯
一道经典的状压\(DP\)，设\(DP[i][j][k]\)表示当前在第\(i\)行，已经放了\(j\)个国王,并且该行的状态为\(k\)时的方案数。每次枚举上一行的状态，若与该行状态不冲突则方案数累加。
代码 ：
#include<bits/stdc++.h>
#define MAXN 10
#define int long long
using namespace std;
int n,k,dp[11][110][1030],ans=0;//第i行,已经放了j个,状态为k
vector<int> sta;
void init()
{
for(int i=0;i<(1<<n);i++)
{
if(i&(i<<1))continue;
sta.push_back(i);
}
}
int num(int n)
{
int ans=0;
while(n)
{
ans+=(n&1);
n>>=1;
}
return ans;
}
signed main()
{
scanf("%lld%lld",&n,&k);
init();
for(int i=0;i<sta.size();i++)
{
dp[1][num(sta[i])][sta[i]]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<sta.size();j++)
{
for(int l=0;l<=k;l++)
{
int nu=num(sta[j]);
if(l-nu<0)continue;
for(int kk=0;kk<sta.size();kk++)
{
if(sta[kk]&sta[j])continue;
if(sta[kk]&(sta[j]<<1))continue;
if(sta[kk]&(sta[j]>>1))continue;
dp[i][l][sta[j]]+=dp[i-1][l-nu][sta[kk]];
}
}
}
}
for(int i=0;i<sta.size();i++)
ans+=dp[n][k][sta[i]];
printf("%lld",ans);
return 0;
}
T3：
繁忙的都市
最小生成树板子，不多赘述。
代码：
#include<bits/stdc++.h>
#define MAXM 100010
#define MAXN 310
using namespace std;
int n,m,x,y,z,tot=0,maxans=0,cnt=0;
int father[MAXN];
int fa(int data)
{
if(father[data]==data)return data;
return father[data]=fa(father[data]);
}
struct edge
{
int l,r,w;
}ed[MAXM];
bool cmp(edge a,edge b)
{
return a.w<b.w;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
ed[++tot].l=x;
ed[tot].r=y;
ed[tot].w=z;
}
for(int i=1;i<=n;i++)
father[i]=i;
sort(ed+1,ed+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(fa(ed[i].l)==fa(ed[i].r))continue;
maxans=max(maxans,ed[i].w);
father[fa(ed[i].l)]=father[fa(ed[i].r)];
cnt++;
if(cnt==n-1)break;
}
printf("%d %d",n-1,maxans);
return 0;
}
T4：
最大子矩阵
一道比较毒瘤的题。
观察数据范围，发现\(m=1、2\)。当\(m=1\)时，题目便是求选\(k\)段的最大子段和，\(DP\)比较方便。而当\(m=2\)时，\(DP\)就比较繁琐了。设\(dp[i][j][k]\)表示当前在第\(i\)行，已经取了\(j\)个矩阵，并且当前行与上一行的状态为\(k\)时的最大和。其中\(k\)取\(1到5\)，分别代表该行两个都不取、只取左边的，只取右边的、取左右两边并且不作为一个整体(即左边在一个矩阵里，右边在一个矩阵里)和取两边并且作为一个整体这\(5\)种情况。在\(DP\)时，这\(5\)种情况要分别从上一行转移过来。注意情况很多，有序枚举避免遗漏。