3.11错题总结
wangyichenawm · · 个人记录
T2(P1049 [NOIP 2001 普及组] 装箱问题)
考试思路：把能装出来的都标记，然后找n行中最大的标记的，然后输出
时间复杂度：O(nm)
考试代码：
#include<bits/stdc++.h>
using namespace std;
int dp[35][20005],w[35],n,m;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
dp[i][w[i]]=1;
for(int j=w[i]+1;j<=m;j++)
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]);
}
for(int j=m;j>=1;j--)
{
if(dp[n][j]==1)
{
cout<<m-j;
return 0;
}
}
cout<<m;
return 0;
}错误原因：脑子宕机了，写错了
正确思路：存容量为i的背包最多能装多少东西，然后输出
时间复杂度：O(nm)
正确代码：
#include<bits/stdc++.h>
using namespace std;
int v,n,dp[100005],c[100005];
int main()
{
cin>>v>>n;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
for(int j=v;j>=c[i];j--)
dp[j]=max(dp[j],dp[j-c[i]]+c[i]);
cout<<v-dp[v];
return 0;
}T3(U542235 查找二叉树)
考试思路;骗分
时间复杂度：O(1)
考试代码：
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)
{
int ls,rs;
cin>>a[i]>>ls>>rs;
if(a[i]==x)
{
cout<<i<<'\n';
return 0;
}
}
return 0;
}错误原因：没时间写
T4(P3916 图的遍历)
考试思路：遍历一次就把遍历到的数都标记成能到达的数，最后输出
时间复杂度：O(n^2 )
考试代码：
#include<bits/stdc++.h>
using namespace std;
vector<int>e[100005],s,l;
bool vis[100005];
int d[100005],cnt;
void dfs(int u)
{
vis[u]=1;
l.push_back(u);
if(cnt<u)
{
s.clear();
for(int i=0;i<l.size();i++)
s.push_back(l[i]);
}
cnt=max(cnt,u);
for(int i=0;i<e[u].size();i++)
if(vis[e[u][i]]==0)
dfs(e[u][i]);
l.pop_back();
vis[u]=1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
while(m--)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
}
for(int i=1;i<=n;i++)
{
if(d[i]!=0)
continue;
cnt=0;
dfs(i);
while(s.size()>0)
{
d[s[s.size()-1]]=max(d[s[s.size()-1]],cnt);
s.pop_back();
}
}
for(int i=1;i<=n;i++)
cout<<d[i]<<' ';
return 0;
}错误原因：回溯了个寂寞
l.pop_back();
vis[u]=1;正确思路：边扫边记录
时间复杂度：O(n)
正确代码：
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int f[100005];
vector<int>y[100005];
int maxn=-1e9;
void dfs(int sx,int u)
{
if(f[u])
return ;
f[u]=sx;
int len=y[u].size();
for(int i=0;i<y[u].size();i++)
{
int v=y[u][i];
dfs(sx,v);
}
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,k;
cin>>x>>k;
y[k].push_back(x);
}
for(int i=n;i>=1;i--)
if(!f[i])
dfs(i,i);
for(int i=1;i<=n;i++)
cout<<f[i]<<' ';
return 0;
}T5(B3856 [语言月赛 202309] 椰奶国)
考试思路：分几种情况，哪种情况就按那种情况模拟
时间复杂度：O(?)
考试代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{
long long n,A,B,C,D,E,F,cnt=0;
bool flag=0;
cin>>n>>A>>B>>C>>D>>E>>F;
if(D-A==0)
{
int z=E-B-1;
if(z==-1)
cnt=F-C;
else if(z==0)
cnt=B*10+1-C+F;
else
{
cnt=B*10+1-C+F;
int s=B+1,t=E-1;
if(s==t)
cnt+=s*10+1;
else
cnt+=(s*10+2+t*10)/(E-B-1)*2;
}
}
else
cnt=8;
cout<<cnt<<'\n';
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}错误原因：没写完上厕所去了
正确思路：把两个时间对应的秒数求出来如果是同一天就直接相减，如果不是就加上一天的时间在减去第一天加上第二天，最后输出
时间复杂度：O(nt)
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
int T,n,h1,m1,s1,h2,m2,s2;
signed main()
{
cin>>T;
while(T--)
{
cin>>n>>h1>>m1>>s1>>h2>>m2>>s2;
int tot=0;
for(int i=0;i<=n-1;i++)
tot+=(1+i*10+1)*(i+1)/2;
int res1=0;
for(int i=0;i<=h1-1;i++)
res1+=(1+i*10+1)*(i+1)/2;
res1+=(1+(m1-1)*10+1)*m1/2;
res1+=s1+1;
int res2=0;
for(int i=0;i<=h2-1;i++)
res2+=(1+i*10+1)*(i+1)/2;
res2+=(1+(m2-1)*10+1)*m2/2;
res2+=s2+1;
if(res2>=res1)
cout<<res2-res1<<endl;
else
cout<<res2+tot-res1<<endl;
}
return 0;
}T6(P2383 狗哥玩木棒)
考试思路：骗分
时间复杂度：O(nt)
考试代码：
#include<bits/stdc++.h>
using namespace std;
int a[25];
void solve()
{
int n,cnt=0,mx=-1e9;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
cnt+=a[i];
mx=max(mx,a[i]);
}
if(cnt%n!=0||n%4!=0||cnt/4<mx)
cout<<"no\n";
else
cout<<"yes\n";
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}错误原因：不会写，也没时间写
正确思路：这题和小猫爬山很像，只是小猫爬山不要求坐满，这题要求坐满，改一下即可
时间复杂度：O(tn^2 )
正确代码：
#include<bits/stdc++.h>
using namespace std;
int a[25],box[25],n,tot;
bool flag;
bool cmp(int x,int y)
{
return x>y;
}
void dfs(int step)
{
if(flag)
return ;
if(step>n)
{
flag=1;
return ;
}
for(int i=1;i<=4;i++)
{
if(box[i]-a[step]>=0)
{
box[i]-=a[step];
dfs(step+1);
box[i]+=a[step];
}
}
return ;
}
void solve()
{
flag=0;
tot=0;
memset(box,0,sizeof box);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],tot+=a[i];
if(tot%4!=0)
{
cout<<"no\n";
return ;
}
for(int i=1;i<=4;i++)
box[i]=tot/4;
sort(a+1,a+n+1,cmp);
dfs(1);
if(flag)
cout<<"yes\n";
else
cout<<"no\n";
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}