题目链接:Here
AcWing 3805. 环形数组
签到题,循环减少出现次数,如果是 cnt[x] = 1
的话加入新的数组中
const int N = 1e3 + 10;
int cnt[N];
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
memset(cnt, 0, sizeof(cnt));
int n; cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x, cnt[x] += 1;
vector<int> b;
for (int i = 0; i < n; ++i) {
if (cnt[a[i]] == 1) b.push_back(a[i]);
cnt[a[i]] -= 1;
}
cout << b.size() << "\n";
for (int x : b) cout << x << " ";
cout << "\n";
}
}
AcWing 3804. 构造字符串
参考了一下 Y总的代码,
主要思路在于分情况考虑
-
\(k > n\) 时,找到字符串中最小的字符
c
,先输出S
然后输出 \(k - n\) 个c
- \(k \le n\)? 时,如同背包一样逆序处理,具体请看代码理解
bool cnt[30];
int n, k; string s;
char get_min() {
for (int i = 0; i < 26; ++i) if (cnt[i]) return i + ‘a‘;
return -1;
}
char get_nxt(int t) {
for (int i = t + 1; i < 26; ++i) if (cnt[i]) return i + ‘a‘;
return -1;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
memset(cnt, 0, sizeof(cnt));
cin >> n >> k >> s;
for (int i = 0; i < n; ++i) cnt[s[i] - ‘a‘] = 1;
if (k > n) {
cout << s;
char c = get_min();
for (int i = n; i < k; ++i) cout << c;
cout << "\n";
} else {
string ss(k, ‘a‘);
for (int i = k - 1; i >= 0; --i) {
char c = get_nxt(s[i] - ‘a‘);
if (c != -1) {
ss[i] = c;
for (int j = 0; j < i; ++j) ss[j] = s[j];
break;
}
ss[i] = get_min();
}
cout << ss << "\n";
}
}
}
AcWing 3805. 环形数组
经典 线段树 板子,注意数组大小为 \(n\) 的 \(4\) 倍
const ll N = 2e5 + 10, inf = 1e18;
int n, m, w[N];
struct node {int l, r; ll dt, mn;} tr[N << 2];
void pushup(int u) { tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn); }
void pushdown(int u) {
auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
l.dt += root.dt, l.mn += root.dt;
r.dt += root.dt, r.mn += root.dt;
root.dt = 0; // 更新 LZ 标记
}
void build(int u, int l, int r) {
if (l == r) tr[u] = {l, r, 0, w[l]};
else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void update(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) tr[u].dt += d, tr[u].mn += d;
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) update(u << 1, l, r, d);
if (r > mid) update(u << 1 | 1, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].mn;
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll ans = inf;
if (l <= mid)ans = query(u << 1, l, r);
if (r > mid) ans = min(ans, query(u << 1 | 1, l, r));
return ans;
}
}
int main() {
// cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) cin >> w[i];
build(1, 0, n - 1);
cin >> m;
while (m--) {
int l, r, d; char c;
scanf("%d %d%c", &l, &r, &c);
// cin >> l >> r >> c;
if (c == ‘\n‘) {
if (l <= r) cout << query(1, l, r);
else cout << min(query(1, l, n - 1), query(1, 0, r));
cout << "\n";
} else {
cin >> d;
if (l <= r)update(1, l, r, d);
else update(1, l, n - 1, d), update(1, 0, r, d);
}
}
}