牛客练习赛6

A题：

方法一：一元二次方程求解，但是会有精度误差，+1个点特判一下。

#include <bits/stdc++.h>using namespace std;typedef unsigned long long ll;ll t; ll x,y,z;int main() {//freopen("in.txt","r",stdin); ll n;scanf("%lld%lld",&n,&t);ll ans = 0;for(ll i = 1; i <= n; i++) {scanf("%lld%lld%lld",&x,&y,&z);ll cnt;if(y==0&&z==0) continue;if(z==0) cnt = t/(x+y);else if(z!=0) {ll sq = ((x+y)-z/2)*((x+y)-z/2) + 2*z*t;sq = sqrt(sq) + z/2 - (x+y);cnt = (sq/z);}if((cnt+1)*(x+y)+(cnt+1)*cnt/2*z<=t)cnt++;ll tmp = cnt*(x+y) + cnt*(cnt-1)/2*z;if(t-tmp>=x) {ans += (t-(cnt+1)*x);}else {ans +=(t-cnt*x-(t-tmp));}}cout<<ans<<endl;return 0; } View Code

方法二：二分

二分是很坑的，二分上界是2e9，中间结果爆数据类型。大佬的解法是处理一下mid，2e9 >= (mid-1)*mid/2*z，移项一下。

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll n,t,ans,res; ll x,y,z;int main() {scanf("%lld%lld",&n,&t);for(ll i = 1ll; i <= n; i++) {scanf("%lld%lld%lld",&x,&y,&z);ll l = 1,r= 2000000000;ans = 0;while(l<=r) {ll mid = (l+r)>>1;if(2000000000/mid>=(mid-1)*z/2&&(1ll*(x+y)*mid+1ll*(mid-1)*mid/2*z)<=t){l = mid+1;ans = mid;}else r = mid - 1;}ll tmp = (1ll*(x+y)*ans+1ll*(ans-1)*ans/2*z);ll tt = 0;tt += tmp - 1ll*ans*x;if(x<t-tmp) tt+=t-tmp-x;res+=tt;}printf("%lld\n",res);return 0; } View Code

 

 

D题：

当时脑子短路，不知道为什么要二分t，然后b全部都减t，处理a变与不变。当然感觉也是可以的，但是硬是90%。无语了~~~

看了题解，简直吐血~

贪心，先把a给变了，然后对应的max(0,b[i]-a[i])；

看来以后得大胆的贪心~~~

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 200005; ll a[MAXN],b[MAXN];int main() {int n,x;ll y;cin>>n>>x>>y;for(int i = 0; i < n; i++) scanf("%lld",&a[i]);for(int i = 0; i < n; i++) scanf("%lld",&b[i]);sort(a,a+n);sort(b,b+n);for(int i = 0; i < x; i++) if(a[i]<y) a[i] = y;sort(a,a+n);ll ans = 0;for(int i = 0; i < n; i++) {ans = max(ans,b[i]-a[i]);}printf("%lld\n",ans);return 0; } View Code

 

B题：

给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和.

这题就有意思了，看上去很简答，其实很灵活的。

分为两个部分，anstag[x]：x即子树的贡献。那么每次修改x，anstag[x] +=deg[x] + 1, 他的父亲结点+2，父亲的父亲+1

但是，还是不够，你会发现，他的父亲节点，和他的父亲的父亲，和父亲的兄弟的贡献还没算，就是只要统计，tag[x] 节点被操作的次数。

父亲结点被操作的次数*2，父亲的父亲被操作的次数*1，兄弟结点被操作的次数*1

#include <bits/stdc++.h>using namespace std;const int maxn = 100005; const int mod = 19260817;typedef long long ll; int fa[maxn]; ll anstag[maxn]; ll sontag[maxn]; ll tag[maxn]; int deg[maxn];int main() {freopen("in.txt","r",stdin);int n,m;scanf("%d%d",&n,&m);for(int i = 2; i <= n; i++) {scanf("%d",&fa[i]);deg[i] ++;deg[fa[i]]++;}ll res = 0;for(int z = 1; z <= m; z++) {int x;scanf("%d",&x);anstag[x] +=deg[x] + 1;anstag[fa[x]]+=2;anstag[fa[fa[x]]]++;tag[x]++;sontag[fa[x]]++;ll ans = anstag[x]%mod;ans = ( ans + tag[fa[x]]*2) % mod;ans = ( ans + tag[fa[fa[x]]]) % mod;ans = ( ans + sontag[fa[x]] - tag[x])%mod;ans = ( ans * z )%mod;res = (res + ans)%mod;}printf("%lld\n",res);return 0; }

 

 

 

转载于:https://www.cnblogs.com/TreeDream/p/7856783.html

总结

以上是生活随笔为你收集整理的牛客练习赛6的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。