专栏文章

4.29错题总结

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

文章操作

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

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

T2(P8739 [蓝桥杯 2020 国 C] 重复字符串)

考试思路：把字符串平均分成k段，每一段每个字母取出现最多次的，然后统计改变次数

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int vis[100005][35];
char a[100005];
string s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s;
	n=s.size()/n;
	for(int i=0;i<s.size();i+=n)
		for(int j=1;j<=n;j++)
			vis[j][s[i+j-1]-'a']++;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int mx=-1e9,i1=-1;
		for(int j=0;j<26;j++)
		{
			if(vis[i][j]>mx)
			{
				mx=vis[i][j];
				i1=j;
			}
		}
		a[++cnt]=i1;
	}
	for(int i=0;i<s.size();i+=n)
		for(int j=1;j<=n;j++)
			if(s[i+j-1]!=a[j]+'a')
				ans++;
	cout<<ans;
	return 0;
}

错误原因：没有考虑-1的情况

正确思路：先判断字符串能不能整除k，能就正常来，不能就输出-1

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int vis[100005][35];
char a[100005];
string s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s;
    if(s.size()%n!=0)
    {
        cout<<-1;
        return 0;
    }
	n=s.size()/n;
	for(int i=0;i<s.size();i+=n)
		for(int j=1;j<=n;j++)
			vis[j][s[i+j-1]-'a']++;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int mx=-1e9,i1=-1;
		for(int j=0;j<26;j++)
		{
			if(vis[i][j]>mx)
			{
				mx=vis[i][j];
				i1=j;
			}
		}
		a[++cnt]=i1;
	}
	for(int i=0;i<s.size();i+=n)
		for(int j=1;j<=n;j++)
			if(s[i+j-1]!=a[j]+'a')
				ans++;
	cout<<ans;
	return 0;
}

T3(P1062 [NOIP 2006 普及组] 数列)

考试思路：骗分

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int k,n;
	cin>>k>>n;
	cout<<981;
	return 0;
}

错误原因：时间不够了

正确思路：观察一下就会发现，第n项就是n的k进制

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int n,k;
	cin>>k>>n;
	int p=1,ans=0;
	while(n)
	{
		if(n%2)
			ans+=p;
		n/=2;
		p*=k;
	}
	cout<<ans;
	return 0;
}

T4(B3689 [语言月赛 202212] 宇宙密码)

考试思路：拿的部分分

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,k;
string a;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>a>>k;
	if(n==k&&n==1)
	{
		if(a[0]=='0')
			cout<<"0\n1\n9\n";
		else if(a[0]=='9')
			cout<<"0\n8\n9\n";
		else
		{
			char a1=a[0]-1,a3=a[0]+1;
			cout<<a1<<'\n'<<a[0]<<'\n'<<a3<<'\n';
		}
	}
	return 0;
}

错误原因：没想出正解

正确思路：直接枚举每一个数，然后直接判断就可以了

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,k;
string s;
bool check(int x)
{
	string t="";
	t+=to_string(x);
	int l=t.size();
	for(int i=1;i<=n-l;i++)
		t="0"+t;
	l=t.size();
	int cnt=0;
	for(int i=0;i<l;i++)
    {
		int x=s[i]-'0';
		int y=t[i]-'0';
		if((x==0&&y==9)||(x==9&&y==0)||(abs(x-y)==1))
			cnt++;
		else if(x!=y)
			return 0;
	} 
	return (cnt<=k);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>a>>k;
	s=to_string(a);
	int len=s.size();
	for(int i=1;i<=n-len;i++)
		s="0"+s;
	int l=0,r=pow(10,n)-1;
	for(int i=l;i<=r;i++)
		if(check(i))
			cout<<i<<"\n";
	return 0;
}

T5(P8783 [蓝桥杯 2022 省 B] 统计子矩阵)

考试思路：暴力+二位前缀和

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
long long sum[505][505];
int n,m,k,ans,a[505][505];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			sum[i][j]+=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	for(int x1=1;x1<=n;x1++)
	{
		for(int y1=1;y1<=m;y1++)
		{
			for(int x2=1;x2<=x1;x2++)
			{
				for(int y2=1;y2<=y1;y2++)
				{
					if(x1==x2&&y1==y2)
					{
						if(a[x1][y1]<=k)
							ans++;
						continue;
					}
					if(sum[x1][y1]+sum[x2-1][y2-1]-sum[x1][y2-1]-sum[x2-1][y1]<=k)
						ans++;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

错误原因：没看清数据范围

正确思路：用双指针写，但是建议用前缀和优化

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int a[N][N],b[N];
int s[N][N];
signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int j=1;j<=m;j++)
		for(int i=1;i<=n;i++)	
			s[i][j]=s[i-1][j]+a[i][j];
	for(int x=1;x<=n;x++)
	{
		for(int y=x;y<=n;y++)
		{
			for(int j=1;j<=m;j++)
				b[j]=s[y][j]-s[x-1][j];
			int l=1,r=1,sum=b[1];
			while(r<=m)
			{
				while(sum<=k&&r<=m)
				{
					ans+=r-l+1;
					sum+=b[++r];
				}
				while(sum>k&&l<=r)
					sum-=b[l++];
			}
		}
	}
	cout<<ans;
	return 0;
}

T6(P3535 [POI 2012] TOU-Tour de Byteotia)

考试思路：骗分

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout<<"3\n2 3\n5 9\n3 5";
	return 0;
}

错误原因：时间不够

正确思路：初始化并查集，对于两端点编号都大于k的边，先将它们对应的集合进行合并，因为这些边不会影响编号小于等于k的节点是否在环上。对于至少有一个端点编号小于等于k的边，检查这两个端点是否属于同一个集合。如果属于同一个集合，说明添加这条边会形成环，需要将这条边删除；否则，将这两个端点对应的集合进行合并。最后输出结果

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+5;
int fa[4*N];
struct stu
{
	int u,v;
}s[N],ans[N];
int get(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=get(fa[x]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>s[i].u>>s[i].v;
		if (s[i].u>s[i].v)
			swap(s[i].u,s[i].v);
	}
	for(int i=1;i<=m;i++)
	{
		int x=s[i].u,y=s[i].v;
		if(x>k&&y>k)
		{
			int u=get(x),v=get(y);
			if(u!=v)
				fa[u]=v;
		}
	}
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		int x=s[i].u,y=s[i].v;
		if(x<=k||y<=k)
		{
			int u=get(x),v=get(y);
			if (u!=v)
				fa[u]=v;
			else
			{
				cnt++;
				ans[cnt]={x,y};
			}
		}
	}
	cout<<cnt<<"\n";
	for(inti=1;i<=cnt;i++)
		cout<<ans[i].u<<" "<<ans[i].v<<"\n";
	return 0;
}

评论

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

正在加载评论...