9.16
原来史可以连着吃
挂了100
t1
简单贪心,不多解释。
没有大样例爆了
code
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
int minn;
int T;
int cnt2, cnt3, cnt4;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> T;while (T--){cin >> cnt2 >> cnt3 >> cnt4;int ans = 0;if (cnt3 == cnt4 && cnt3 == 0){cout << cnt2 / 5 << "\n";continue;}if (cnt3 / 2 >= cnt4) // 3 3 4{ans += cnt4;cnt3 -= 2 * cnt4;if (cnt3 >= cnt2) // 2 2 3 3ans += cnt2 / 2;else{ans += cnt3 / 2;cnt2 -= cnt3 / 2 * 2;//注意 /2 后再*2 ,只有满2才减ans += cnt2 / 5; // 2 2 2 2 2}}else // 剩2,4{ans += cnt3 / 2;cnt4 -= cnt3 / 2;if (cnt2 > cnt4 / 2) // 2 4 4{ans += cnt4 / 2;cnt2 -= cnt4 / 2;if (cnt4 % 2 == 1)if (cnt2 >= 3)++ans, cnt2 -= 3;ans += cnt2 / 5;}elseans += cnt2;}cout << ans << "\n";}return 0;
}
t2
考虑分成链与点dp ,详见代码
code
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10;
const int mod = 998244353;
int n, ans;
int a[N], dp[N];inline int km(int a, int b)
{int ans = 1;while (b){if (b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i)//将边看作有向cin >> a[i];sort(a + 1, a + 1 + n); // 排序并不影响结果,有序更好算dp[0] = 1;for (int i = 1; i <= n; ++i){for (int j = a[i - 1] + 1; j <= a[i]; ++j) for (int k = j; k; --k)dp[k] = (dp[k] + dp[k - 1]) % mod; // 倒序避免更新重 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]ans = (ans + dp[1]) % mod;ans = (ans - a[i]) % mod;for (int j = 1; j <= a[i]; ++j)dp[j - 1] = (dp[j - 1] + (j - 1) * j % mod * dp[j] % mod) % mod;}cout << ans * km(2, mod - 2) % mod << "\n";//正向与反向,/2return 0;
}
t3
不是哥们,wyx \(O(n^2log_n)\) 过了,我的就 T ??? (虽然正解 \(O(nlog_n)\) )
正解为树型dp状物。
code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k;
vector<int> e[N];
int dis[N], cnt, lim;void dfs(int x, int f)
{dis[x] = 1;for (auto y : e[x]){if (y == f)continue;dfs(y, x);dis[x] = min(dis[x], dis[y] + 1);}for (auto y : e[x]){if (y == f)continue;if (dis[x] + dis[y] <= 0)continue;dis[x] = max(dis[x], dis[y] + 1);}if (dis[x] > lim)dis[x] = -lim, ++cnt;
}inline bool check(int up)
{lim = up;cnt = 0;dfs(1, 0);if (dis[1] > 0)++cnt;return cnt <= k;
}inline int fen()
{int l = 1, r = n, ans = r;while(l<=r){int mid = (l + r) >> 1;if(check(mid))r = mid - 1, ans = mid;elsel = mid + 1;}return ans;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for (int i = 1, u, v; i < n; ++i){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}int ans = fen();cout << ans;return 0;
}
t4
咕,太过神秘了。
累了,不想写了,凑合看。