i64 count(i64 n, int x){ if (n == 0) return0; vector<int> nums; while (n) { nums.push_back(n % 10); n /= 10; } i64 res = 0; int len = nums.size(); for (int i = len - 1; i >= 0; i--) { i64 pow10 = 1; for (int j = 0; j < i; j++) pow10 *= 10; i64 high = 0; for (int j = len - 1; j > i; j--) high = high * 10 + nums[j]; int cur = nums[i]; i64 low = 0; for (int j = i - 1; j >= 0; j--) low = low * 10 + nums[j]; if (x != 0) { if (cur > x) res += (high + 1) * pow10; elseif (cur == x) res += high * pow10 + (low + 1); else res += high * pow10; } else { if (high == 0) continue; // 跳过前导零 if (cur > 0) res += high * pow10; else res += (high - 1) * pow10 + (low + 1); } } return res; }
intmain(){ i64 a, b; while (cin >> a >> b, a || b) { if (a > b) swap(a, b); for (int i = 0; i <= 9; i++) cout << count(b, i) - count(a - 1, i) << " "; cout << '\n'; } }
intmain(){ int n, c, m; cin >> n >> c >> m; vector<Task> tasks(n); for (int i = 0; i < n; i++) cin >> tasks[i].c >> tasks[i].m >> tasks[i].v; int S = 1 << n; vector<int> sumc(S, 0), summ(S, 0), sumv(S, 0); vector<bool> ok(S, false); // 预处理:哪些子集可以被一台服务器处理 for (int s = 1; s < S; s++) { int lb = s & -s; // lowbit int i = __builtin_ctz(lb); // 第几个任务 int prev = s ^ lb; // 去掉最低位的 1 sumc[s] = sumc[prev] + tasks[i].c; summ[s] = summ[prev] + tasks[i].m; sumv[s] = sumv[prev] + tasks[i].v; if (sumc[s] <= c && summ[s] <= m) ok[s] = true; } int dp[n + 1][S]; memset(dp, 0, sizeof dp); for (int k = 1; k <= n; k++) { for (int s = 0; s < S; s++) { dp[k][s] = dp[k - 1][s]; // 第 k 台服务器不处理任何任务 // 枚举 s 的子集 sub for (int sub = s; sub; sub = (sub - 1) & s) { if (ok[sub]) dp[k][s] = max(dp[k][s], dp[k - 1][s ^ sub] + sumv[sub]); } } } for (int k = 1; k <= n; k++) cout << dp[k][S - 1] << '\n'; }
子集枚举技巧:
1 2 3 4
// 从大到小枚举 s 的所有子集 for (int sub = s; sub; sub = (sub - 1) & s) { // sub 依次是 s 的各个子集 }
constint N = 6010; int n; int happy[N]; int h[N], e[N], ne[N], idx; int f[N][2]; bool has_fa[N];
voidadd(int u, int v){ e[idx] = v, ne[idx] = h[u], h[u] = idx++; }
voiddfs(int u){ f[u][1] = happy[u]; // 选 u,加上 u 的快乐值 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; dfs(j); f[u][0] += max(f[j][0], f[j][1]); // 不选 u,子节点随便 f[u][1] += f[j][0]; // 选 u,子节点不能选 } }
intmain(){ cin >> n; for (int i = 1; i <= n; i++) cin >> happy[i]; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; has_fa[u] = true; add(v, u); // v 是 u 的上司 } // 找根节点(没有上司的人) int root = 1; while (has_fa[root]) root++; dfs(root); cout << max(f[root][0], f[root][1]); }
constint N = 310; int n, m; int h[N][N]; int f[N][N]; // 记忆化数组 int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
intdp(int x, int y){ int& v = f[x][y]; // 引用,方便修改 if (v != -1) return v; // 已经算过,直接返回 v = 1; // 至少可以站在原地 for (int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; if (a >= 1 && a <= n && b >= 1 && b <= m && h[x][y] > h[a][b]) v = max(v, dp(a, b) + 1); } return v; }
intmain(){ cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> h[i][j]; memset(f, -1, sizeof f); int res = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) res = max(res, dp(i, j)); // 枚举起点 cout << res; }