专栏文章

2.25错题总结

wwangyichenawm
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq4jxoc
此快照首次捕获于
2025/12/03 22:51
3 个月前
此快照最后确认于
2025/12/03 22:51
3 个月前
查看原文

T1( P1481 魔族密码)

考试思路：用find()+dp，只要find()返回值不是-1，就可以转移

时间复杂度：O(n2n^2)

考试代码：
CPP
#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(n2n^2)

正确代码：
CPP
#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(tn3tn^3)

考试代码：
CPP
#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(tn3tn^3)

正确代码：
CPP
#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(?)

考试代码：
CPP
#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(?)

正确代码：
CPP
#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);

考试代码：
CPP
#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)=a2−ab+ab−b2=a2−b2(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)奇偶性相同，所以(a+b),(a−b)(a+b),(a-b)要么都是奇数，要么是4的倍数

时间复杂度：O(b-a)

正确代码：
CPP
#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);

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<2;
	return 0;
}

错误原因：没时间了

正确思路：简单的图论，删除的点都跑一遍，遇到那个点就不走那个点看能不能到达，能就不是，不能就+1

时间复杂度：O(n2n^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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...