T1
对于T1，一直没什么思路，然而就放弃了，这道题真的挺简单的，我们可以到着想，那么就是将末状态变为0的操作数，这就不难了，然后类似于计数排序的思想搞一就相当于利用一个桶就可以了。操作时，将费0数不断减1，将0变为当前0的个数/2下取整。这貌似是一个非常优秀的贪心
T2
暴力加边，判断1和n的父亲是否相同，如果相同，answer ++，并且暴力再次将所有的点的父亲置为自己，这样竟然有80分，可见数据之水正解：暴力加边，每次进行bfs还可以单向并查集（第一次听说）T3
贪心貌似0分，刚开始以为是贪心，每次只砍最小的奇数，如果没有奇数，那么放弃这一刀一定是最优的做法（4,4）（错的？？）正解是dpf[i][j] 表示血量为i的兵，空了j刀，这里貌似并没有听懂GG，类似于一个背包问题，可以用一个栈来维护
T1 集合
#include#include #include #include #include #include #include #include #include using namespace std;const int MAXN = 5e6 + 60, MX = 1e6;int N, a[MAXN], cnt[MAXN], res, lim;int main(){ freopen("multiset.in", "r", stdin); freopen("multiset.out", "w", stdout); scanf("%d", &N); for (int i = 1; i <= N; ++i) { scanf("%d", &a[i]); lim = max(lim, a[i]); ++cnt[a[i]]; } int l = 0, z = cnt[0]; for (int i = 1; i <= lim; ++i) { ++res; z = (z + 1) / 2; z += cnt[i]; } for (; z > 1; z = (z + 1) / 2) ++res; printf("%d\n", res); return 0;}
T2道路分组
#include#include #include #include #include #include #include using namespace std;const int N=500010;typedef long long ll;int n, m;int vis[N], u[N], v[N];vector vec[N];bool dfs(int u){ if (vis[u]) return false; if (u == n) return true; vis[u] = 1; bool ret = false; for (int i = 0; i < vec[u].size(); i++) { ret = dfs(vec[u][i]); if (ret) return true; } return false;} int read(){ char ch = getchar(); int x = 0; while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) {x = x*10+(ch-'0');ch=getchar();} return x;}bool check(int sta, int las){ for (int i = sta; i <= las; i++) vec[u[i]].push_back(v[i]); bool ret = dfs(1); for (int i = sta; i <= las; i++) { vis[u[i]] = vis[v[i]] = 0; vec[u[i]].clear(); } vis[1] = 0; return ret;} int main(){ freopen("road.in","r",stdin); freopen("road.out","w",stdout); n = read(), m = read(); for (int i = 0; i < m; i++) { //scanf("%d%d", &u[i], &v[i]); u[i] = read(); v[i] = read(); } int now = 0, ans = 0; while (now < m) { int i; for (i = 1; i + now <= m; i <<= 1) if (check(now, now + i - 1)) break; i >>= 1; int nowtmp = now + i; for (; i > 0; i >>= 1) if (nowtmp + i <= m && !check(now, nowtmp + i - 1)) nowtmp += i; ans++; now = nowtmp; } cout << ans << endl;}
T3补刀
#include#include #include #include #include #include using namespace std;const int MAXN = 1000 + 10;int a[MAXN];int cnt[MAXN], sta[MAXN], c[MAXN];int f[MAXN][MAXN];int main(){ freopen("cs.in", "r", stdin); freopen("cs.out", "w", stdout); int T; scanf("%d", &T); for (int num = 1; num <= T; ++num) { int N, maxn = 0; scanf("%d", &N); memset(cnt, 0, sizeof(cnt)); memset(c, 0, sizeof(c)); memset(f, 0, sizeof(f)); for (int i = 1; i <= N; ++i) { scanf("%d", &a[i]); ++cnt[a[i]]; maxn = max(maxn, a[i]); } int top = 0; for (int i = 1; i <= maxn; ++i) if (cnt[i] == 0) sta[++top] = i; else { while (cnt[i] > 1 && top > 0) {c[sta[top--]] = i; --cnt[i];} c[i] = i; } int ans = 0; for (int i = 1; i <= maxn; ++i) for (int j = 0; j <= i; ++j) { if (j > 0) f[i][j] = f[i - 1][j - 1]; if (c[i] != 0 && j + c[i] - i < i) f[i][j] = max(f[i][j], f[i - 1][j + c[i] - i] + 1); ans = max(ans, f[i][j]); } printf("%d\n", ans); } return 0;}