5.6错题总结
wangyichenawm · · 个人记录
T2(B3702 [语言月赛202301] 华小科的旅行开始了)
考试思路：直接按照题目模拟
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
int x,y;
}a[1005][1005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>sx>>sy;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j].x>>a[i][j].y;
while(a[sx][sy].x!=0||a[sx][sy].y!=0)
{
cout<<sx<<' '<<sy<<'\n';
int xx=a[sx][sy].x,yy=a[sx][sy].y;
sx=xx,sy=yy;
}
cout<<sx<<' '<<sy<<'\n';
return 0;
}错误原因：是先列后行
正确思路：直接按照题目模拟
正确代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
int x,y;
}a[1005][1005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n>>sx>>sy;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j].x>>a[i][j].y;
while(a[sx][sy].x!=0||a[sx][sy].y!=0)
{
cout<<sx<<' '<<sy<<'\n';
int xx=a[sx][sy].x,yy=a[sx][sy].y;
sx=xx,sy=yy;
}
cout<<sx<<' '<<sy<<'\n';
return 0;
}T4(P1195 口袋的天空)
考试思路：骗分
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
struct N
{
int x,y,l;
}a[10005];
bool cmp(N A,N b)
{
return A.l<b.l;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
if(n-m>k)
{
cout<<"No Answer\n";
return 0;
}
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].l;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n-k;i++)
ans+=a[i].l;
cout<<ans;
return 0;
}错误原因：没时间，就写了个骗分程序
正确思路：最小生成树模版
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
int n,m,k,ans;
int fa[4*N];
struct edge
{
int x, y, z;
}a[N];
bool cmp(edge aa,edge bb)
{
return aa.z<bb.z;
}
int get(int x)
{
if(fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
void unite(int x,int y)
{
x=get(x);
y=get(y);
if(x!=y)
fa[x]=y;
return ;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
int cnt=n;
for(int i=1;i<=m;i++)
{
int f1=get(a[i].x),f2=get(a[i].y);
if(f1!=f2)
{
unite(f1, f2);
ans+=a[i].z;
cnt--;
if(cnt==k)
{
cout<<ans;
return 0;
}
}
}
cout<<"No Answer";
return 0;
}T5(P1609 最小回文数)
考试思路：暴力
考试代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool pd(int i1)
{
int i=i1,j=0;
while(i!=0)
{
j*=10;
j+=i%10;
i/=10;
}
if(j==i1)
return 1;
else
return 0;
}
int s;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>s;
for(int i=s+1;;i++)
{
if(pd(i)==1)
{
cout<<i<<'\n';
return 0;
}
}
return 0;
}错误原因：不会写正解
正确思路：ABCDDCBA>ABCDEFGH, 直接反过来即可。奇数个，把中间的数升位,把ABCDtEFGH变成ABCD(t+1)DCBA。偶数个，变成ABC(D+1)(D+1)CBA,当然要特判全9的情况
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
string s;
signed main()
{
cin>>s;
int len=s.size();
string l=s.substr(0,len/2), r;
if(len%2==0)
r=s.substr(len/2);
else
r=s.substr(len/2+1);
string fl=l;
reverse(fl.begin(),fl.end());
if(l+fl>l+r)
{
if(len%2==0)
cout<<l+fl;
else
cout<<l<<s[len/2]<<fl;
}
else
{
if(len%2==1&&s[len/2]<'9')
{
s[len/2]++;
cout<<l<<s[len/2]<<fl;
}
else
{
s[len/2]='0';
bool flag=0;
for(int i=l.size()-1;i>=0;i--)
{
if(l[i]<='8')
{
l[i]++;
flag=1;
break;
}
else l[i]='0';
}
if(flag==0)
{
cout<<1;
for(int i=1;i<=s.size()-1;i++)
cout<<0;
cout<<1;
}
else
{
fl=l;
reverse(fl.begin(),fl.end());
if(len%2==0)
cout<<l+fl;
else
cout<<l<<s[len/2]<<fl;
}
}
}
return 0;
}T6(P11486 「Cfz Round 5」Mata rainen)
考试思路：骗分
考试代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout<<"No";
return 0;
}错误原因：没时间
正确思路：n点、m条点对。要求构造一棵树，所有的s_i 到t_i 的路径，正好把所有的树边全部走了一次(不能多也不能少)。
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int x[N],y[N];
int fa[N];
int get(int x)
{
if(x==fa[x])
return x;
return fa[x]=get(fa[x]);
}
void unite(int x ,int y)
{
x=get(x);
y=get(y);
if(x!=y)
fa[x]=y;
return ;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
cin>>x[i]>>y[i];
for(int i=1;i<=m;i++)
{
int nx=get(x[i]);
int ny=get(y[i]);
if(nx!=ny)
unite(nx,ny);
else
{
cout<<"No";
return 0;
}
}
cout<<"Yes"<<endl;
for(int i=1;i<=m-1;i++)
cout<<x[i]<<" "<<y[i]<<endl;
int pre=x[m];
for(int i=1;i<=n;i++)
{
if(get(i)==i&&get(i)!=get(x[m]))
{
cout<<pre<<" "<<i<<endl;
pre=i;
}
}
cout<<pre<<" "<<y[m];
return 0;
}