【持续更新】2024牛客寒假算法基础集训营1题解 | JorbanS

字符串匹配

int n;
string DD = "DFS", dd = "dfs";void solve() {int D = 0, d = 0;string s; cin >> n >> s;for (int i = 0; i < n; i ++)if (s[i] == DD[D]) D ++;else if (s[i] == dd[d]) d ++;cout << (D >= 3) << ' '  << (d >= 3) << endl;
}

有以下四种基本图形，排列组合即可

int n;
pii a[N];int solve() {cin >> n;for (int i = 0; i < n; i ++) cin >> a[i].bb >> a[i].aa;sort(a, a + n);int res = 3;bool down = false, L = false, R = false, left = false, right = false;bool ll = false, rr = false;for (int i = 0; i < n; i ++) {if (a[i].aa == 0 && a[i].bb == 2) down = true;if (a[i].aa == -1 && a[i].bb == 1) left = true;if (a[i].aa == 1 && a[i].bb == 1) right = true;if (a[i].aa < 0) ll = true;if (a[i].aa > 0) rr = true;if (i) {if (a[i].aa == a[i - 1].aa) {if (a[i].aa < 0) L = true;else R = true;} else if (a[i].aa - 1 == a[i - 1].aa && a[i].bb + a[i - 1].bb == 3) {if (a[i - 1].aa < 0) L = true;else if (a[i].aa > 0) R = true;}}}if (L && R || down && left && right) return 0;if (L && right && down || R && left && down) return 0;if (down && left || down && right || left && right) return 1;if (L && right || R && left || L && down || R && down) return 1;if (L && rr || R && ll) return 1;if (left && down && rr || right && down && ll) return 1;if (L || R || down || left || right || ll && rr) return 2;return 3;
}

排序后，前缀和人等待的时间，二分查找鸡插队的时间点

int n, m;
ll t, q;
ll a[N];bool check(ll x) {int l = upper_bound(a + 1, a + n + 1, x) - a;ll res = (n - l + 1) * t;return res <= q;
}ll solve() {ll l = 0, r = a[n];while (l < r) {ll mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid + 1;}return l + t;
}int main() {FastIOcin >> n >> m >> t;for (int i = 1; i <= n; i ++) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i ++) a[i] += a[i - 1];while (m --) {cin >> q;cout << solve() << endl;}return 0;
}

题为贪心误导人，暴力枚举情况，复杂度为 $O(T\times 3^n)\le 6\times 10^6$

int n, m, res;
int a[N], c[N];void dfs(int d = 0) {if (d == m) {for (int i = 1; i <= n; i ++) c[i] = a[i];sort(c + 1, c + n + 1);int t = upper_bound(c + 1, c + n + 1, a[1]) - c - 1;t = n + 1 - t;res = min(res, t);return;}int u = b[d].aa, v = b[d].bb;a[u] += 3;dfs(d + 1);a[u] -= 3;a[v] += 3;dfs(d + 1);a[v] -= 3;a[u] ++, a[v] ++;dfs(d + 1);a[u] --, a[v] --;
}int solve() {cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> a[i];for (int i = 0; i < m; i ++) cin >> b[i].aa >> b[i].bb;res = n;dfs();return res;
}

前缀和即可

int n, m;
pii a[N];ll solve() {cin >> n >> m;for (int i = 0; i < n; i ++) cin >> a[i].aa >> a[i].bb;sort(a, a + n);for (int i = 1; i < n; i ++) a[i].bb += a[i - 1].bb;for (int i = n - 1; i >= 0; i --)if (a[i].aa - m <= a[i].bb) return a[i].bb + m;return m;
}

概率分析，第一个人的概率更平均，答案不唯一，我大概意思一下，一发过了

int n, a, b;string solve() {cin >> n;a = b = 0;while (n --) {int x, y, r; cin >> x >> y >> r;x = max(abs(x), abs(y));if (x <= 70) a ++;else b ++;}if (1.0 * a / b > 1.2) return bb;return aa;
}

计算阴影部分面积即可

double solve() {double c, d, h, w; cin >> c >> d >> h >> w;return c * w * 3;
}

int solve() {int n; cin >> n;int res = n / 6;return n % 6 ? res * 2 : res;
}