牛客小白月赛69题解
A
比较 和
的大小关系即可。
注意要开 long long。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main()
{
cin>>a>>b;
if(a/b>a%b)puts("niuniu eats less than others");
if(a/b<a%b)puts("niuniu eats more than others");
if(a/b==a%b)puts("same");
return 0;
}
B
将玩具从大到小排序。
每次选择最大的两个玩具捆绑购买显然最优。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000001],s,i;
int main()
{
cin>>n;
for(i=1;i<=n;i=i+1)cin>>a[i];
sort(a+1,a+n+1);
for(i=n;i>=1;i=i-2)s=s+a[i];
cout<<s;
return 0;
}
C
暴力枚举顺序的全排列，按照该顺序计算答案取最大值。
注意细节即可。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
long long i,n,t,p,a[10],b[10],c[10],x[10],y[10],q[10],s,d,e;
int main()
{
cin>>n>>t>>p;
for(i=1;i<=n;i=i+1)
{
cin>>a[i]>>b[i]>>c[i]>>x[i]>>y[i];
q[i]=i;
}
do
{
d=0;e=0;
for(i=1;i<=n;i=i+1)
{
d=d+x[q[i]];if(d>t)break;
e=e+max(c[q[i]],a[q[i]]-d*b[q[i]]-y[q[i]]*p);
}
s=max(s,e);
}
while(next_permutation(q+1,q+n+1));
cout<<s;
return 0;
}
D
Solution 1
二分答案，并查集。
在二分答案后需要修复的道路数量为当前连通块个数 。
将权值从小到大排序，用并查集维护类似 的贪心，确定修哪些道路，直到连通块个数为
。
确定完修哪些道路后，按照权值从大到小匹配操作最优。
注意要开 long long。
时间复杂度 。
Solution 2
考虑每次二分答案后贪心过程是不变的，所以求出最小生成树的边后直接贪心计算答案即可。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
long long n,m,c,i,j,f[100001],b[100001],k,s;
pair<long long,pair<long long,long long> >a[100001];
long long g(long long x)
{
if(x==f[x])return x;
return f[x]=g(f[x]);
}
int main()
{
cin>>n>>m>>c;
for(i=1;i<=n;i=i+1)f[i]=i;
for(i=1;i<=m;i=i+1)cin>>a[i].second.first>>a[i].second.second>>a[i].first;
sort(a+1,a+m+1);
for(i=1;i<=m;i=i+1)
{
if(g(a[i].second.first)!=g(a[i].second.second))
{
b[++k]=a[i].first;
f[g(a[i].second.first)]=g(a[i].second.second);
}
if(k==n-1)break;
}
for(i=k;i>=1;i=i-1)
{
s=s+b[i]*(k-i+1);
if(s>c){cout<<b[i];return 0;}
}
cout<<0;return 0;
}
E/F
Easy
枚举三个点，先判断是否满足三点不共线，如满足，求出两两之间距离，如有相同，则为等腰三角形。
时间复杂度 。
#include<bits/stdc++.h>
using namespace std;
long long n,x[3003],y[3003],i,j,k,s;
int main()
{
cin>>n;
for(i=1;i<=n;i=i+1)cin>>x[i]>>y[i];
for(i=1;i<=n;i=i+1)
for(j=i+1;j<=n;j=j+1)
for(k=j+1;k<=n;k=k+1)
{
if(((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])==(x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k])&&(x[i]*2!=x[j]+x[k]||y[i]*2!=y[j]+y[k]))||
((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])==(x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])&&(x[j]*2!=x[i]+x[k]||y[j]*2!=y[i]+y[k]))||
((x[i]-x[k])*(x[i]-x[k])+(y[i]-y[k])*(y[i]-y[k])==(x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])&&(x[k]*2!=x[i]+x[j]||y[k]*2!=y[i]+y[j])))
s=s+1;
}
cout<<s;
return 0;
}
Hard
枚举等腰三角形的顶点，记录剩余点到顶点的距离，如相同距离有 个，则对答案产生
的贡献 。
再排除三点共线的情况即可。
时间复杂度看个人实现， 可通过，
常数足够小也可通过。
#include<bits/stdc++.h>
using namespace std;
long long n,x[10001],y[10001],a[1001][1001],b,c,d[2000002],e,i,j;
int main()
{
cin>>n;
for(i=1;i<=n;i=i+1)
{
cin>>x[i]>>y[i];
x[i]=x[i]+500;y[i]=y[i]+500;
a[x[i]][y[i]]=1;
}
for(i=1;i<=n;i=i+1)
{
for(j=1;j<=n;j=j+1)
if(i!=j)
{
e=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
c=c+d[e]++;
}
for(j=1;j<=n;j=j+1)
if(i!=j)
{
e=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
d[e]=0;
}
for(j=1;j<=n;j=j+1)
if(i!=j&&2*x[i]-x[j]>=0&&2*x[i]-x[j]<=1000&&2*y[i]-y[j]>=0&&2*y[i]-y[j]<=1000)
b=b+a[2*x[i]-x[j]][2*y[i]-y[j]];
}
cout<<c-b/2;
return 0;
}
G
组合数，模拟。
由二项式定理得到每一项系数，组合数预处理得出，由于模数不保证是质数，杨辉三角递推，时间复杂度 。
corner case 比较多，需注意，具体可看 std 的实现。
#include<bits/stdc++.h>
using namespace std;
char a,b,c[100];
long long x,y,z,n,p,q,i,j,k,f[1111][1111],d[1111];
int main()
{
cin>>c;
cout<<c<<" = ";
q=strlen(c);
for(i=1;i<q;i=i+1)
{
if(c[i]>=48&&c[i]<=57)x=x*10+c[i]-48;
else{a=c[i];break;}
}
if(x==0)x=1;
for(i=1;i<q;i=i+1)
if(c[i]=='+'){z=i;break;}
for(i=z+1;i<q;i=i+1)
{
if(c[i]>=48&&c[i]<=57)y=y*10+c[i]-48;
else{b=c[i];break;}
}
if(y==0)y=1;
for(i=1;i<q;i=i+1)
if(c[i]=='%'){z=i;break;}
for(i=z+1;i<q;i=i+1)
{
if(c[i]>=48&&c[i]<=57)p=p*10+c[i]-48;
else break;
}
z=0;
for(i=1;i<q;i=i+1)
if(c[i]=='^'){z=i;break;}
if(z==0)n=1;
else
{
for(i=z+1;i<q;i=i+1)
{
if(c[i]>=48&&c[i]<=57)n=n*10+c[i]-48;
else break;
}
}
if(a==b)
{
x=x+y;k=1;
for(i=1;i<=n;i=i+1)k=k*x%p;
if(k==0)cout<<0;
else if(k==1)
{
if(n>1)cout<<a<<"^"<<n<<"%"<<p;
else cout<<a<<"%"<<p;
}
else
{
if(n>1)cout<<k<<"*"<<a<<"^"<<n<<"%"<<p;
else cout<<k<<"*"<<a<<"%"<<p;
}
return 0;
}
f[0][0]=1;
for(i=1;i<=n+1;i=i+1)
for(j=1;j<=i;j=j+1)f[i][j]=(f[i-1][j]+f[i-1][j-1])%p;
for(i=0;i<=n;i=i+1)
{
d[i]=f[n+1][i+1];
for(j=1;j<=i;j=j+1)d[i]=d[i]*y%p;
for(j=1;j<=n-i;j=j+1)d[i]=d[i]*x%p;
}
for(i=0;i<=n;i=i+1)if(d[i]>0)k=k+1;
if(k==0){cout<<0;return 0;}
if(k==1)
{
for(i=0;i<=n;i=i+1)
if(d[i]>0)
{
if(d[i]==1)
{
if(i==0)
{
cout<<a;
if(n>1)cout<<"^"<<n;
cout<<"%"<<p;
}
else if(i==n)
{
cout<<b;
if(n>1)cout<<"^"<<n;
cout<<"%"<<p;
}
else
{
cout<<a;
if(n-i>1)cout<<"^"<<n-i;
cout<<"*"<<b;
if(i>1)cout<<"^"<<i;
cout<<"%"<<p;
}
}
else
{
if(i==0)
{
cout<<d[i]<<"*"<<a;
if(n>1)cout<<"^"<<n;
cout<<"%"<<p;
}
else if(i==n)
{
cout<<d[i]<<"*"<<b;
if(n>1)cout<<"^"<<n;
cout<<"%"<<p;
}
else
{
cout<<d[i]<<"*"<<a;
if(n-i>1)cout<<"^"<<n-i;
cout<<"*"<<b;
if(i>1)cout<<"^"<<i;
cout<<"%"<<p;
}
}
}
return 0;
}
cout<<"(";k=0;
for(i=0;i<=n;i=i+1)
if(d[i]>0)
{
if(k==1)cout<<"+";
if(d[i]==1)
{
k=1;
if(i==0)
{
cout<<a;
if(n>1)cout<<"^"<<n;
}
else if(i==n)
{
cout<<b;
if(n>1)cout<<"^"<<n;
}
else
{
cout<<a;
if(n-i>1)cout<<"^"<<n-i;
cout<<"*"<<b;
if(i>1)cout<<"^"<<i;
}
}
else
{
k=1;
if(i==0)
{
cout<<d[i]<<"*"<<a;
if(n>1)cout<<"^"<<n;
}
else if(i==n)
{
cout<<d[i]<<"*"<<b;
if(n>1)cout<<"^"<<n;
}
else
{
cout<<d[i]<<"*"<<a;
if(n-i>1)cout<<"^"<<n-i;
cout<<"*"<<b;
if(i>1)cout<<"^"<<i;
}
}
}
cout<<")%"<<p;
return 0;
}