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; }
方法二：二分
二分是很坑的，二分上界是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 ",res); return 0; }
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 ",ans); return 0; }
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 ",res); return 0; }