题解:第一题:
dp[i] 表示我们给这棵树再分配了i的度数
dp[i] = max(dp[j] + f[i - j + 1] - f[1]), 因为我们只考虑连在叶子节点上,所以只有叶子节点贡献改变
#include<bits/stdc++.h> using namespace std; const int M = 2020; int n, val[M], dp[M]; int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int T; scanf("%d", &T); while(T--){ scanf("%d", &n); for(int i = 1; i < n; i++)scanf("%d", &val[i]); memset(dp, 0, sizeof(dp)); dp[0] = n * val[1]; for(int i = 1; i < n - 1; i++) for(int j = i - 1; j >= 0; j--) dp[i] = max(dp[i], dp[j] + val[i - j + 1] - val[1]); if(n == 1)printf("0 "); else printf("%d ", dp[n - 2]); } }
第二题:首先去除这个很烦的mod : ∑(i = 1~n) (k - k / i * i ) --> n*k - ∑(i = 1~(min(n, k)) (k / i * i ),
k/i 有很多重复,分块求等差数列
#include<bits/stdc++.h> using namespace std; #define ll unsigned long long ll ans; int main(){ freopen("b.in","r",stdin); freopen("b.out","w",stdout); ll n, k; scanf("%I64d%I64d", &n, &k); ans += n * k; ll res = min(n, k); ll lf = 1, rg; while(lf <= res){ rg = k / (k/lf); if(rg > res) rg = res; ans -= (lf + rg) * (rg - lf + 1) / 2 * (k / lf); lf = rg + 1; } printf("%I64d ", ans); }
第三题:
#include<bits/stdc++.h> using namespace std; int n, m, k; bool check(int p){ long long ret = 0; if(k - 1 >= p - 1){ ret += 1LL * p * (p - 1) / 2; ret += 1LL *(k - p); } else ret += 1LL*(2 * p - k) * (k - 1) / 2; if(n - k >= p - 1){ ret += 1LL * p * (p - 1) / 2; ret += 1LL * (n - k - p + 1); } else ret += 1LL * (2*p - 1 - n + k) * (n - k) / 2; return ret <= m - p; } int main(){ freopen("c.in","r",stdin); freopen("c.out","w",stdout); int T; scanf("%d", &T); while(T--){ int ans = 1; scanf("%d%d%d", &n, &m, &k); int rg = m - n + 1, lf = 1; while(lf <= rg){ int mid = (lf + rg) >> 1; if(check(mid))ans = mid, lf = mid + 1; else rg = mid - 1; } printf("%d ", ans); } }