5.20错题总结
wangyichenawm · · 个人记录
T3(P9241 [蓝桥杯 2023 省 B] 飞机降落)
考试思路：按照输入顺序模拟
考试代码：
#include<bits/stdc++.h>
using namespace std;
struct N
{
int t,d,l;
}a[15];
void solve()
{
int n,t=0,d=0,l=0,jlsj=0;
bool flag=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].t>>a[i].d>>a[i].l;
for(int i=1;i<=n;i++)
{
if(a[i].t>=jlsj)
{
t=a[i].t;
d=a[i].d;
l=a[i].l;
jlsj=t+l;
}
else if(a[i].t<jlsj&&a[i].t+a[i].d>=jlsj)
{
t=a[i].t;
d=a[i].d;
l=a[i].l;
jlsj+=l;
}
else
{
flag=1;
break;
}
}
if(flag==1)
cout<<"NO\n";
else
cout<<"YES\n";
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}错误原因：没想出正解
正确思路：直接暴搜
正确代码：
#include<bits/stdc++.h>
using namespace std;
const int N=15;
#define int long long
struct node
{
int t,d,l,r;
}f[N];
int t,n,vis[N];
bool flag;
void dfs(int dep,int now)
{
if(dep==n)
{
flag=1;
return ;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]&&f[i].r<now)
return ;
if(!vis[i]&&f[i].r>=now)
{
vis[i]=1;
if(f[i].l>now)
dfs(dep+1,f[i].l+f[i].t);
else
dfs(dep+1,now+f[i].t);
vis[i]=0;
}
}
}
string solve()
{
cin>>n;
flag=0;
int k;
for(int i=1;i<=n;i++)
{
cin>>f[i].l>>k>>f[i].t;
f[i].r=f[i].l+k;
}
for(int i=1;i<=n;i++)
{
vis[i]=1;
dfs(1,f[i].l+f[i].t);
vis[i]=0;
}
if(flag)
return "YES\n";
return "NO\n";
}
signed main()
{
int T;
cin>>T;
while(T--)
cout<<solve();
return 0;
}T4(P1067 [NOIP 2009 普及组] 多项式输出)
考试思路：直接按照题目模拟
考试代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,a;
cin>>n>>a;
if(a<0)
cout<<'-';
a=abs(a);
cout<<a<<"x^"<<n;
for(int i=n-1;i>=0;i--)
{
cin>>a;
if(a==0)
continue;
if(a<0)
cout<<"-";
else
cout<<"+";
a=abs(a);
if(a==1&&i!=0)
{
if(i==1)
cout<<"x";
else if(i!=0)
cout<<"x^"<<i;
continue;
}
if(i==1)
cout<<a<<"x";
else if(i==0)
cout<<a;
else
cout<<a<<"x^"<<i;
}
return 0;
}错误原因：没有判断n为0时
正确思路：直接按照题目模拟
正确代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,a;
cin>>n>>a;
if(a<0)
cout<<'-';
a=abs(a);
if(a==1)
{
if(n==0)
cout<<a;
else
cout<<"x^"<<n;
}
else
cout<<a<<"x^"<<n;
for(int i=n-1;i>=0;i--)
{
cin>>a;
if(a==0)
continue;
if(a<0)
cout<<"-";
else
cout<<"+";
a=abs(a);
if(a==1&&i!=0)
{
if(i==1)
cout<<"x";
else if(i!=0)
cout<<"x^"<<i;
continue;
}
if(i==1)
cout<<a<<"x";
else if(i==0)
cout<<a;
else
cout<<a<<"x^"<<i;
}
return 0;
}T5(P7667 [JOI 2018 Final] 美术展览 / Art Exhibition)
考试思路：二维前缀和+暴力
考试代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,sum[500005],mx=-1e9;
struct N
{
int cc,jz;
}a[500005];
bool cmp(N x,N y)
{
if(x.cc!=y.cc)
return x.cc<y.cc;
return x.jz<y.jz;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].cc>>a[i].jz;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
sum[i]+=sum[i-1]+a[i].jz;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
int mxx=-1e9,mnx=1e9;
for(int z=j;z<=i;z++)
{
mxx=max(mxx,a[z].cc);
mnx=min(mnx,a[z].cc);
}
mx=max(mx,sum[i]-sum[j-1]-(mxx-mnx));
}
}
cout<<mx;
return 0;
}错误原因：方法错了
正确思路：前缀和
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
int n,ans,dp[N];
struct node
{
int a,b;
}s[N];
bool cmp(node aa,node bb)
{
return aa.a<bb.a;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>s[i].a>>s[i].b;
sort(s+1,s+n+1,cmp);
for(int i=1;i<n;i++)
dp[i]=s[i].b-s[i+1].a+s[i].a;
int maxi=0;
for(int i=1;i<=n;i++)
{
int t=s[i].b;
ans=max(ans,t+maxi);
maxi=max(maxi+dp[i],0ll);
}
cout<<ans;
return 0;
}