2022年9月20日的测试(SCOI2005专场)
T1 扫雷
思考起来很简单，对于任意一个输入的\(a[i]\)，它会约束的格子只有\(i-1,i,i+1\)三个，也就是只要算出当前在\(i-1,i\)位置摆放的情况，就能算出\(i\)位置的情况，显然\(place[1]\)（place数组是摆放情况）是不确定的，所以我们需要计算它为1或0的两种可能性，递推式也不难想到：
\[place[i]=a[i-1]-place[i-1]-place[i-2] \]如果当前的\(place[i]\)算出来不等于\(0||1\)当前的情况就可以作废
最后如果\(place[n+1]==0\)（即不用在\(n+1\)摆放就可以满足），那么\(ans++\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int a[maxn];int pl[maxn];
bool valid(int x){return x==1||x==0;}
int ans=0;int n;
void calc(int f/*0,1*/)
{
memset(pl,0,sizeof pl);
pl[1]=f;int flag=0;
for(int i=2;i<=n+1;i++)
{
pl[i]=a[i-1]-pl[i-1]-pl[i-2];
if(!valid(pl[i]))
{
flag=1;
break;
}
}
if(pl[n+1]==0&&flag==0)ans++;
}
int main()
{
freopen("sweeper.in","r",stdin);
freopen("sweeper.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
calc(0),calc(1);
printf("%d",ans);
return 0;
}
T2 互不侵犯
义眼状压\(dp\)，定义\(dp[i][j][t]\)为前\(i\)行一共填了\(t\)个数，当前第\(i\)行填的是第\(j\)个合法数时的方案数
预处理
遍历 \(i=[1,1<<n-1]\),如果i&(i<<1))||i&(i>>1)那么当前是不合法的，跳过
否则放入数组里并记录其二进制下1的个数\(bitcount(x)\)
状态转移
\[dp[i][j][t]+=dp[i-1][las][t-num[j]],t\ge num[j] \]其中:
\(i,j,t\)为定义所示,\(las\)枚举的是\(i-1\)行填的数，\(num[j]\)是当前这个数的1的个数
答案
\(\sum^{cnt}_{i=1}dp[n][i][k]\)(\(cnt\)是总共有效数字个数)
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=10;
long long dp[maxn][1<<maxn-1][100];//摆完了前i行，第i行为j，一共用了t个国王时的方案数
int n,k;
int sta[1<<maxn+10],cnt;
int num[1<<maxn+10];/*数出第i个状态有多少个1*/
int count_one(int x)
{
int ans=0;
while(x)
{
if(x&1)ans++;
x>>=1;
}
return ans;
}
void pre()
{
for(int i=0;i<=(1<<n)-1;i++)/*枚举可能的状态i*/
{
if((i&(i<<1))||(i&(i>>1)))continue;
sta[++cnt]=i,num[cnt]=count_one(i);
}
}
signed main()
{
freopen("king.in","r",stdin);
freopen("king.out","w",stdout);
scanf("%d%d",&n,&k);
pre();
for(int j=1;j<=cnt;j++)dp[1][j][num[j]]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)/*当前*/
for(int las=1;las<=cnt;las++)/*上一行*/
{
if((sta[j]&sta[las])||(sta[j]&(sta[las]<<1))||(sta[j]&(sta[las]>>1)))continue;
for(int plc=num[j];plc<=k;plc++)
dp[i][j][plc]+=dp[i-1][las][plc-num[j]];
}
long long ans=0;
for(int i=1;i<=cnt;i++)ans+=dp[n][i][k];
printf("%lld",ans);
return 0;
}
T3 城市
义眼弱智最小生成树板子
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10000;
struct Edge{int u,v,nex;int w;}E[maxn];
int tote,head[maxn];
void add(int u,int v,int w)
{
E[++tote].u=u,E[++tote].v=v,E[tote].w=w;
E[tote].nex=head[u],head[u]=tote;
}
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int f[maxn];int ans=-1;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool cmp(Edge x,Edge y){return x.w<=y.w;}
int main()
{
// freopen("city.in","r",stdin);
// freopen("city.out","w",stdout);
int n,m;
n=read(),m=read();
int u,v,w;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
E[i].u=read(),E[i].v=read(),E[i].w=read();
sort(E+1,E+m+1,cmp);
int sel=0;
for(int i=1;i<=m-1;i++)
{
int fu=find(E[i].u),fv=find(E[i].v);
if(fu==fv)continue;
else
{
f[fu]=fv;
sel++;
ans=max(ans,E[i].w);
}
}
printf("%d %d",sel,ans);
return 0;
}
/*
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8*/
T4 最大子矩阵和(改了好久)
题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入格式
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式
只有一行为k个子矩阵分值之和最大为多少。
样例 #1
样例输入 #1
3 2 2
1 -3
2 3
-2 3
样例输出 #1
9
突破口\(m==1||m==2\)
首先定义\(dp[i][j][k]\)（\(k\)在\(m\)不同的情况下表示不同的含义）
\(m==1\)
\(dp\)定义：第\(i\)个选了\(k\)段,第\(i\)个选/不选的最大值
转移
\[ \left\{ \begin{aligned} dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0])\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][1],dp[i-1][j-1][0]),j\ge1 \end{aligned} \right. \]\(m==2\)
思路：对于当前第\(i\)行，考虑合并第一列和第二列，那么一共就有\(5\)种如下情况
\(1,0\)分别表示当前列选与不选
\[\left\{ \begin{aligned} 1:00\quad\quad\quad\quad\\ 2:10\quad\quad\quad\quad\\ 3:01\quad\quad\quad\quad\\ 4:11 两列为一块\\ 5:11 两列为两块\\ \end{aligned} \right. \]转移
\[\left\{ \begin{aligned} dp[i][j][1]=max(dp[i-1][j][t],dp[i][j][1]),t\in[1,5]\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \quad\\ dp[i][j][2]=max(dp[i-1][j][2],dp[i-1][j][5],\max_{t=1}^{5}dp[i-1][j-1][t])\quad\quad\quad\\ dp[i][j][3]=max(dp[i-1][j][3],dp[i-1][j][5],\max_{t=1}^{5}dp[i-1][j-1][t])\quad\quad\quad\\ dp[i][j][4]=max(dp[i-1][j][4],\max_{t=1}^{5}dp[i-1][j-1][t])\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ dp[i][j][5]=max(dp[i-1][j-1][2],dp[i-1][j-1][3],\max_{t=1}^{5}dp[i-1][j-2][t])\\ \end{aligned} \right. \](其中有关于\(t\)的都是枚举直接新建块，不做拼接操作)
那么代码就好写了，唯一的坑点是，枚举情况\(5\)的时候，默认\(j\)已经大于等于\(2\)了，所以要特判
Code
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=10000;
const int maxk=15;
int sum[3][maxn];
int mat[maxn][3];
int n,m,k;
int dp[maxn][maxk][7];
signed main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%lld",&mat[i][j]);
if(m==1)
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);
if(j>=1)
dp[i][j][1]=max(dp[i-1][j][1],max(dp[i-1][j-1][1],dp[i-1][j-1][0]))+mat[i][1];
}
}
printf("%lld",max(dp[n][k][1],dp[n][k][0]));
}
else
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
int maxx=-1;for(int t=1;t<=5;t++)maxx=max(maxx,dp[i-1][j-1][t]);
for(int t=1;t<=5;t++)dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][t]);
if(j!=0)
{
dp[i][j][2]=max(max(dp[i-1][j][2],dp[i-1][j][5]),maxx)+mat[i][1];
dp[i][j][3]=max(max(dp[i-1][j][3],dp[i-1][j][5]),maxx)+mat[i][2];
dp[i][j][4]=max(dp[i][j][4],dp[i-1][j][4]+mat[i][1]+mat[i][2]);
dp[i][j][4]=max(dp[i][j][4],maxx+mat[i][1]+mat[i][2]);
}
if(j>=2)
{
dp[i][j][5]=max(dp[i][j][5],max(max(dp[i-1][j-1][2],dp[i-1][j-1][3]),dp[i-1][j][5])+mat[i][1]+mat[i][2]);
maxx=-1;for(int t=1;t<=5;t++)maxx=max(maxx,dp[i-1][j-2][t]);
dp[i][j][5]=max(dp[i][j][5],maxx+mat[i][1]+mat[i][2]);
}
}
}
long long ans=-1ll;
for(int i=1;i<=5;i++)ans=max(ans,dp[n][k][i]);
printf("%lld",ans);
}
return 0;
}
最后要感谢机房不知名好兄弟的陪伴
