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; }
全部评论
(0) 回帖