2.25错题总结
wangyichenawm · · 个人记录
T1( P1481 魔族密码)
考试思路：用find()+dp，只要find()返回值不是-1，就可以转移
时间复杂度：O(n^2 )
考试代码：
#include<bits/stdc++.h>
using namespace std;
string s[2005];
int dp[2005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
if(s[i].find(s[j])!=-1)
dp[i]=max(dp[i],dp[j]+1);
}
int mx=-1e9;
for(int i=1;i<=n;i++)
mx=max(mx,dp[i]);
cout<<mx;
return 0;
}错误原因：没考虑到是前缀，并且不能用find，不是前缀find也有返回值
正确思路：用substr()+dp，只要substr()返回值=s[j]，就可以转移
时间复杂度：O(n^2 )
正确代码：
#include<bits/stdc++.h>
using namespace std;
string s[2005];
int dp[2005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
if(s[i].substr(0,s[j].size())==s[j])
dp[i]=max(dp[i],dp[j]+1);
}
int mx=-1e9;
for(int i=1;i<=n;i++)
mx=max(mx,dp[i]);
cout<<mx;
return 0;
}T3(P9122 [USACO23FEB] Stamp Grid B)
考试思路：把能盖的章都盖了，然后再判断有没有没盖上的，如果有则是盖不了的，没有就是盖的了
时间复杂度：O(tn^3 )
考试代码：
#include<bits/stdc++.h>
using namespace std;
char a[25][25],b[25][25],c[25][25];
int n,k;
void th(int x,int y)
{
bool flag1=0,flag2=0,flag3=0,flag4=0;
for(int i=x;i<=x+k-1;i++)
{
for(int j=y;j<=y+k-1;j++)
{
if(b[i-x+1][j-y+1]=='*'&&a[i][j]!='*')
flag1=1;
if(b[j-y+1][i-x+1]=='*'&&a[i][j]!='*')
flag2=1;
if(b[k-i+x-1][j-y+1]=='*'&&a[i][j]!='*')
flag3=1;
if(b[k-j+y-1][i-x+1]=='*'&&a[i][j]!='*')
flag4=1;
if(flag1==1&&flag1==flag2&&flag2==flag3&&flag3==flag4)
break;
}
}
if(flag1==0)
for(int i=x;i<=x+k-1;i++)
for(int j=y;j<=y+k-1;j++)
c[i][j]=b[i-x+1][j-y+1];
if(flag2==0)
for(int i=x;i<=x+k-1;i++)
for(int j=y;j<=y+k-1;j++)
c[i][j]=b[j-y+1][i-x+1];
if(flag3==0)
for(int i=x;i<=x+k-1;i++)
for(int j=y;j<=y+k-1;j++)
c[i][j]=b[k-i+x][j-y+1];
if(flag4==0)
for(int i=x;i<=x+k-1;i++)
for(int j=y;j<=y+k-1;j++)
c[i][j]=b[k-j+y][i-x+1];
return ;
}
void solve()
{
memset(c,0,sizeof c);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
cin>>k;
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
cin>>b[i][j];
for(int i=1;i<=n-k+1;i++)
for(int j=1;j<=n-k+1;j++)
th(i,j);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(c[i][j]!=a[i][j])
{
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}错误原因：没打完
正确思路：同上
时间复杂度：O(tn^3 )
正确代码：
#include<bits/stdc++.h>
using namespace std;
char a[25][25],b[25][25],c[25][25];
int n,k;
void fz()
{
char d[25][25]={};
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
d[i][j]=b[j][k-i+1];
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
b[i][j]=d[i][j];
return ;
}
void ks()
{
for(int i=1;i<=n-k+1;i++)
{
for(int j=1;j<=n-k+1;j++)
{
bool flag=0;
for(int i1=i;i1<i+k;i1++)
{
for(int j1=j;j1<j+k;j1++)
{
if(a[i1][j1]!='*'&&b[i1-i+1][j1-j+1]=='*')
{
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag==0)
for(int i1=i;i1<i+k;i1++)
for(int j1=j;j1<j+k;j1++)
if(b[i1-i+1][j1-j+1]=='*')
c[i1][j1]=b[i1-i+1][j1-j+1];
}
}
}
void solve()
{
memset(c,0,sizeof c);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
cin>>k;
for(int i=1;i<=k;i++)
for(int j=1;j<=k;j++)
cin>>b[i][j];
for(int i=1;i<=4;i++)
{
ks();
fz();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(c[i][j]!=a[i][j]&&a[i][j]=='*')
{
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}T4(P10483 小猫爬山)
考试思路：dfs+剪枝，边循环边模拟
时间复杂度：O(?)
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1e9,a[25],b[25];
void dfs(int sd,int step)
{
if(sd>=ans)
return ;
if(step>n)
{
ans=min(ans,sd);
return ;
}
if(sd==0)
{
b[1]=a[step];
dfs(sd+1,step+1);
}
else
{
bool flag=0;
for(int i=1;i<=sd;i++)
{
if(m-b[i]>=a[step])
{
b[i]+=a[step];
flag=1;
break;
}
}
if(flag==0)
{
b[sd+1]=a[step];
dfs(sd+1,step+1);
}
else
dfs(sd,step+1);
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
reverse(a+1,a+n+1);
dfs(0,1);
cout<<ans;
return 0;
}错误原因：没有回溯，没有考虑多种情况
正确思路：dfs+剪枝+回溯，边循环边模拟
时间复杂度：O(?)
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[35],st[35],ans=1e9,n,w;
void dfs(int u,int s)
{
if(s>n)
{
ans=min(ans,u);
return ;
}
if(u>=ans)
return ;
for(int i=1;i<=u;i++)
{
if(st[i]+a[s]<=w)
{
st[i]+=a[s];
dfs(u,s+1);
st[i]-=a[s];
}
}
st[u+1]=a[s];
dfs(u+1,s+1);
st[u+1]-=a[s];
return ;
}
signed main()
{
cin>>n>>w;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
reverse(a+1,a+n+1);
dfs(0,1);
cout<<ans;
return 0;
}T5(P1348 Couple number)
考试思路：骗分
时间复杂度：O(1);
考试代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int a,b;
cin>>a>>b;
cout<<0<<'\n';
return 0;
}错误原因：没时间了
正确思路：数学题，(a+b)(a-b)=a(a-b)+b(a-b)=a^2-ab+ab-b^2=a^2-b^2 ,因为(a+b),(a-b) 奇偶性相同，所以(a+b),(a-b) 要么都是奇数，要么是4的倍数
时间复杂度：O(b-a)
正确代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,ans=0;
cin>>a>>b;
for(int i=a;i<=b;i++)
if(i%2!=0||i%4==0)
ans++;
cout<<ans;
return 0;
}T6(P8604 [蓝桥杯 2013 国 C] 危险系数)
考试思路：骗分
时间复杂度：O(1);
考试代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout<<2;
return 0;
}错误原因：没时间了
正确思路：简单的图论，删除的点都跑一遍，遇到那个点就不走那个点看能不能到达，能就不是，不能就+1
时间复杂度：O(n^2 )
正确代码：
using namespace std;
vector<int>a[1005];
bool vis[1005];
int cnt=1e9,y;
void dfs(int x,int s,int sum)
{
if(x==y)
{
cnt=min(cnt,sum);
return ;
}
vis[x]=1;
for(int i=0;i<a[x].size();i++)
{
if(a[x][i]==s)
continue;
if(vis[a[x][i]]==1)
continue;
dfs(a[x][i],s,sum+1);
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
int x,ans=0;
cin>>x>>y;
for(int i=1;i<=n;i++)
{
if(i==x||i==y)
continue;
dfs(x,i,1);
if(cnt==1e9)
ans++;
cnt=1e9;
for(int j=1;j<=n;j++)
vis[j]=0;
}
cout<<ans;
return 0;
}