4.8错题总结
wangyichenawm · · 个人记录
T2(P1234 小 A 的口头禅)
考试思路：统计以a[i][j]为头能组成的"hehe"的数量
考试代码：
#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
int n,m,ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j+3<=m)
{
if(a[i][j]=='h'&&a[i][j+1]=='e'&&a[i][j+2]=='h'&&a[i][j+3]=='e')
ans++;
}
if(j-3>=1)
{
if(a[i][j]=='e'&&a[i][j-1]=='h'&&a[i][j-2]=='e'&&a[i][j-3]=='h')
ans++;
}
if(i+3<=n)
{
if(a[i][j]=='h'&&a[i+1][j]=='e'&&a[i+2][j]=='h'&&a[i+3][j]=='e')
ans++;
}
if(i-3>=1)
{
if(a[i][j]=='e'&&a[i-1][j]=='h'&&a[i-2][j]=='e'&&a[i-3][j]=='h')
ans++;
}
}
}
cout<<ans<<'\n';
return 0;
}错误原因：没考虑周全
正确思路：找到h就判断四个方向是否有"hehe"，有多少个就加多少个
正确代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char a[1005][1005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='h')
{
if(a[i-1][j]=='e'&&a[i-2][j]=='h'&&a[i-3][j]=='e')
ans++;
if(a[i+1][j]=='e'&&a[i+2][j]=='h'&&a[i+3][j]=='e')
ans++;
if(a[i][j-1]=='e'&&a[i][j-2]=='h'&&a[i][j-3]=='e')
ans++;
if(a[i][j+1]=='e'&&a[i][j+2]=='h'&&a[i][j+3]=='e')
ans++;
}
}
}
cout<<ans;
return 0;
}T5(P11380 [GESP202412 八级] 排队)
考试思路：把输出0的分拿了，再把结果小于1000000007，的分拿了
考试代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
map<int,int>mp;
int n,m,ans=1;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
if(mp[u]==v||mp[v]==u)
{
cout<<0;
return 0;
}
mp[u]=v;
mp[v]=u;
}
for(int i=1;i<=n-m;i++)
{
ans*=i;
ans%=mod;
}
cout<<ans<<'\n';
return 0;
}错误原因：没时间写了
正确思路：并查集
正确代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1,MOD=1e9+7;
int fa[N],l[N],r[N],n,m,ans=0,sum=1,F=0;
struct stu
{
int a1,a2,f;
}a[N];
int Father(int x)
{
if(fa[x]!=x)
return fa[x]=Father(fa[x]);
return x;
}
bool comp(stu b1,stu b2)
{
if(b1.a1==b2.a1&&b1.a2==b2.a2&&b1.f!=b2.f)
F=1;
if(b1.a1==b2.a1)
return b1.a2<b2.a2;
return b1.a1<b2.a1;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
fa[i]=i;
for(int i=1,x,y;i<=m;++i)
{
cin>>x>>y;
if(r[x]==y||l[y]==x)
continue;
if(r[x]||l[y]||Father(x)==Father(y))
{
cout<<"0";
return 0;
}
r[x]=y;
l[y]=x;
fa[Father(y)]=Father(x);
}
for(int i=1;i<=n;++i)
ans+=(Father(i)==i);
for(int i=1;i<=ans;++i)
sum=(sum*i)%MOD;
cout<<sum;
return 0;
}T6(P1205 [USACO1.2] 方块转换 Transformations)
考试思路：每种都判断一遍
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n;
char a[15][15],b[15][15],yq[15][15];
void xz()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[j][n-i+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=b[i][j];
}
bool pd()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]!=yq[i][j])
return 1;
return 0;
}
void fz()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][n-j+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=b[i][j];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>yq[i][j];
if(pd()==0)
{
cout<<6;
return 0;
}
xz();
if(pd()==0)
{
cout<<3;
return 0;
}
xz();
if(pd()==0)
{
cout<<2;
return 0;
}
xz();
if(pd()==0)
{
cout<<1;
return 0;
}
xz();
fz();
if(pd()==0)
{
cout<<4;
return 0;
}
xz();
if(pd()==0)
{
cout<<5;
return 0;
}
xz();
if(pd()==0)
{
cout<<5;
return 0;
}
xz();
if(pd()==0)
{
cout<<5;
return 0;
}
cout<<7;
return 0;
}错误原因：要按先后顺序来输出符合的
正确思路：按顺序判断一遍
正确代码：
#include<bits/stdc++.h>
using namespace std;
int n,mn=100;
char a[15][15],b[15][15],yq[15][15];
void xz()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[j][n-i+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=b[i][j];
}
bool pd()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]!=yq[i][j])
return 1;
return 0;
}
void fz()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][n-j+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=b[i][j];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>yq[i][j];
xz();
if(pd()==0)
mn=min(mn,3);
xz();
if(pd()==0)
mn=min(mn,2);
xz();
if(pd()==0)
mn=min(mn,1);
xz();
fz();
if(pd()==0)
mn=min(mn,4);
xz();
if(pd()==0)
mn=min(mn,5);
xz();
if(pd()==0)
mn=min(mn,5);
xz();
if(pd()==0)
mn=min(mn,5);
xz();
fz();
if(pd()==0)
mn=min(mn,6);
if(mn==100)
cout<<7;
else
cout<<mn;
return 0;
}