4.29错题总结
wangyichenawm · · 个人记录
T2(P8739 [蓝桥杯 2020 国 C] 重复字符串)
考试思路：把字符串平均分成k段，每一段每个字母取出现最多次的，然后统计改变次数
考试代码：
#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
正确代码：
#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 普及组] 数列)
考试思路：骗分
考试代码：
#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进制
正确代码：
#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] 宇宙密码)
考试思路：拿的部分分
考试代码：
#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;
}错误原因：没想出正解
正确思路：直接枚举每一个数，然后直接判断就可以了
正确代码：
#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] 统计子矩阵)
考试思路：暴力+二位前缀和
考试代码：
#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;
}错误原因：没看清数据范围
正确思路：用双指针写，但是建议用前缀和优化
正确代码：
#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)
考试思路：骗分
考试代码：
#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的边，检查这两个端点是否属于同一个集合。如果属于同一个集合，说明添加这条边会形成环，需要将这条边删除；否则，将这两个端点对应的集合进行合并。最后输出结果
正确代码：
#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;
}