5.29 周四题目解析
T1
P2637 第一次，第二次，成交！
原代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1005],qq=-1e9,jg,num;
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a+1,a+m+1);
int maxx=a[m];
for(int i=1;i<=maxx;i++)
{
int ans=0,num=0;
for(int j=1;j<=m;j++)
{
if(a[j]>=i)ans++;
}
num=ans*i;
if(num>qq)
{
qq=num;
jg=i;
}
}
cout<<jg<<" "<<qq;
return 0;
} 思路：将所有价钱从小到大排个序，循环判断若用第i个价钱作为标准，有几个人能够买。
不过要记住：能够购买的人数可能会大于干草总数，若大于，那就最多只能卖n份。
最后找出能赚最多钱的最小售价，以及赚的钱数。
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[1005],qq=-1e9,jg,num;
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a+1,a+m+1);
int maxx=a[m];
for(int i=1;i<=maxx;i++)
{
int ans=0,num=0;
for(int j=1;j<=m;j++)
{
if(a[j]>=i)ans++;
}
if(ans>n)ans=n;
num=ans*i;
if(num>qq)
{
qq=num;
jg=i;
}
}
cout<<jg<<" "<<qq;
return 0;
} T2
P1293 班级聚会
原代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int id,jl,ans=1e9;
string md;
struct node
{
int gs,len;
string name;
}a[200];
signed main()
{
while(1)
{
id++;
cin>>a[id].gs>>a[id].len>>a[id].name;
if(a[id].name=="Moscow")break;
}
for(int i=1;i<=id;i++)
{
int num=0;
for(int j=1;j<=id;j++)
{
jl=abs(a[i].len-a[j].len);
num=num+a[j].gs*jl;
}
if(num<ans)
{
ans=num;
md=a[i].name;
}
}
cout<<md<<" "<<ans;
return 0;
} 思路：将所有城市的距离从小到大排序，循环寻找花费最少的城市，记录其名字和花费，最后输出。
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int id,jl,ans=1e9;
string md;
struct node
{
int gs,len;
string name;
}a[200];
int cmp(node a,node b)
{
return a.len<b.len;
}
signed main()
{
while(1)
{
id++;
cin>>a[id].gs>>a[id].len>>a[id].name;
if(a[id].name=="Moscow")break;
}
sort(a+1,a+id+1,cmp);
for(int i=1;i<=id;i++)
{
int num=0;
for(int j=1;j<=id;j++)
{
jl=abs(a[i].len-a[j].len);
num=num+a[j].gs*jl;
}
if(num<ans)
{
ans=num;
md=a[i].name;
}
}
cout<<md<<" "<<ans;
return 0;
} T3
P4826 [USACO15FEB] Superbull S
原代码：无
思路：首先由题可知, 每头牛之间都可以有决斗，一共进行n-1次决斗，使其总得分最大。可以看成先处理每头牛之间的权值异或，再建图跑一个最大生成树，输出其总和。
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int n,id,ans,a[2005],fa[N*N];
struct node
{
int u,v,w;
}e[N*N];
int cmp(node a,node b)
{
return a.w>b.w;
}
int f(int a)
{
if(fa[a]==a)return a;
fa[a]=f(fa[a]);
return fa[a];
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
e[++id]={i,j,a[i]^a[j]};
}
}
sort(e+1,e+id+1,cmp);
for(int i=1;i<=id;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
int fu=f(u),fv=f(v);
if(fu!=fv)
{
fa[fu]=fv;
ans+=w;
}
}
cout<<ans;
return 0;
} T4
T614223 [NOIP 2009 普及组] 多项式输出
原代码：（应该是这样的，我看不了之前的提交记录）
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[105];
signed main()
{
cin>>n;
for(int i=1;i<=n+1;i++)
{
cin>>a[i];
}
for(int i=1;i<=n+1;i++)
{
int xs=a[i],cs=n-i+1;
if(xs==0)continue;
if(xs>=1)
{
if(i!=1)cout<<"+";
if(xs==1)
{
if(i==n+1)cout<<xs;
else cout<<"x";
}
else
{
if(i==n+1)cout<<xs;
else cout<<xs<<"x";
}
}
else
{
cout<<"-";
if(xs==-1)
{
if(i==n+1)cout<<xs;
else cout<<"x";
}
else
{
if(i==n+1)cout<<xs;
else cout<<xs<<"x";
}
}
if(cs==0)continue;
if(cs!=1)cout<<"^"<<cs;
}
return 0;
} 思路：按题目来就行，就是要注意很多的细节。
1.对于符号，若第一项是正数，则不输出，否则都要输出符号（+/-）。
2.对于系数，如果不为0就输出，若是1，直接输出x，若是-1，输出-x。
3.对于x,当系数和次数都不为0时输出。
4.对于次数，当次数大于 1 时输出(^a)，否则不输出。
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[105];
signed main()
{
cin>>n;
for(int i=1;i<=n+1;i++)
{
cin>>a[i];
}
for(int i=1;i<=n+1;i++)
{
int xs=a[i],cs=n-i+1;
if(xs==0)continue;
if(xs>=1)
{
if(i!=1)cout<<"+";
if(xs==1)
{
if(i==n+1)cout<<xs;
else cout<<"x";
}
else
{
if(i==n+1)cout<<xs;
else cout<<xs<<"x";
}
}
else
{
cout<<"-";
if(xs==-1)
{
if(i==n+1)cout<<abs(xs);
else cout<<"x";
}
else
{
if(i==n+1)cout<<abs(xs);
else cout<<abs(xs)<<"x";
}
}
if(cs==0)continue;
if(cs!=1)cout<<"^"<<cs;
}
return 0;
} T5
T614224 [蓝桥杯 2023 省 B] 飞机降落
原代码：
思路：
AC代码：