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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。