本系列：月度做题记录
2024/10 做题笔记
文章系列：月度做题记录
- 2024/10 做题笔记
- 2024/09 做题笔记
- 2024 年 8 月做题记录
呜呜呜好多题都没来得及写。你说得对但是我 CSP-S 炸了
[Internal] 1
给你一堆边，区间和区间对应点相连（），求这张图的最小生成树。
区间数量 5e5，节点数 1e5。
暴力来做的话，就是直接建一个并查集然后 merge。写一个启发式合并可以把暴力时间优化很多，但是还是过不了。如果你做过「SCOI2016」萌萌哒，那么事实上这道题可以用类似的一个像是 ST 表上并查集的东西，好像叫做倍增并查集。
具体来说，可以像 ST 表那样拆分区间，然后在每一层都建立一个并查集。但是完全照搬萌萌哒这道题的做法不太行，因为 Kruskal 需要在线的信息。注意一层中两个区间对应相连并不意味着两个区间里的所有点彻底联通，因此我们需要在每一次询问的时候，如果两个区间可以完全合并，就继续下放，直到最底层（单点修改）。在最底层就可以加上这条边的权值了。
这样做可以保证每层每个点都只被合并一次，可以有效降低复杂度到 或者是 （实现定义）。
const int MAXN = 1e5 + 3;
int fa[21][MAXN], sz[21][MAXN], fcnt;
int lg2[MAXN];
long long ans = 0;
inline int findfa(int f, const int x) { if (fa[f][x] == x) return x; return fa[f][x] = findfa(f, fa[f][x]); }
inline void init(int x) { for (int i = 1; i <= x; i++) for (int j = 0; j < 21; j++) fa[j][i] = i, sz[j][i] = 1; }
void merge(int f, int x, int y)
{
x = fa[f][x], y = fa[f][y];
if (sz[f][y] > sz[f][x]) swap(x, y);
fa[f][y] = x;
sz[f][x] += sz[f][y];
}
struct mytp { int w, l, x, y; } ed[MAXN * 5];
inline bool operator<(const mytp& lhs, const mytp& rhs) { return lhs.w < rhs.w; }
void merge_all(int f, int x, int y, int w)
{
if (findfa(f, x) == findfa(f, y)) return;
merge(f, x, y);
if (f == 0) return void(ans = ans + w);
merge_all(f - 1, x, y, w);
merge_all(f - 1, x + (1 << (f - 1)), y + (1 << (f - 1)), w);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
init(n);
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= m; i++) {
cin >> ed[i].x >> ed[i].y >> ed[i].l >> ed[i].w;
}
sort(ed + 1, ed + m + 1);
for (int i = 1; i <= m; i++) {
int w = ed[i].w, l = ed[i].l, x = ed[i].x, y = ed[i].y;
int f = lg2[l];
merge_all(f, x, y, w);
merge_all(f, x + l - (1 << f), y + l - (1 << f), w);
}
cout << ans << '\n';
}[Internal] 2
给你一个序列 ，求它字典序最小的一个子序列，满足他是一个 的全排列。
可以维护一个单调队列，从小到大遍历 ，以确保队列中保存的是当前字典序最小子序列的一部分。单调队列的性质保证了队列中的序列始终是字典序最小的。
在遍历过程中，我们首先尝试将当前数字放入单调队列。如果我们遍历到 并且这个数字是最后一次出现，那么这意味着必须将这个数字输出。由于队列是单调递增的，因此我们可以不断从队列前端输出元素，直到遇到这个数字为止。
那么，为什么这样做能够保证字典序一定是最小的呢？
在维护一个单调递增的序列时，尽量选择更小的未被确定的数显然是正确的。
算法可以保证每个数字都被访问过。
- 如果一个数字是最后一次出现且之前被弹出，但我们之后又将它放入队列，因此队列中一定包含这个数字。
- 在入队时弹出的更大的元素中，必定不存在最后一次出现的数字。
对于单调队列的维护：当算法遇到任何比 更小的元素 时，都会优先选择 而不是 。所以，如果 是可用的元素，算法不可能跳过 而直接选择 。
算法在遇到必须放入 的时候才会放弃 之后的单调性，此时可以证明，对于上一个确定的元素到 之间，单调队列维护的都是最优解。如果之后的决策有比这个更优的选择，那么 必然会在更后面的地方出现，这显然不正确。
这里的局部最优解可以带来整体的最优解。
for (int i = 1; i <= n; i++) {
cin >> dat[i];
cnt[dat[i]]++;
}
lst.push_back(0);
for (int i = 1; i <= n; i++) {
int cur = dat[i];
if (vis[cur]) continue;
if (!inq[cur]) {
while (lst.size() && lst.back() >= cur) {
inq[lst.back()] = 0;
lst.pop_back();
}
inq[cur] = 1;
lst.push_back(cur);
}
cnt[cur]--;
if (cnt[cur] == 0) {
while (lst.size() && lst.front() <= cur) {
if (lst.front()) cout << lst.front() << ' ';
inq[lst.front()] = 0; vis[lst.front()] = 1;
lst.pop_front();
}
}
}「SDOI2016」征途
给你 个数（），划分成连续的 个段，使得每段数字之和构成长度为 的数列的方差最小。
要输出方差乘上 的结果。
首先，感觉方差这个东西不太好维护，所以说可以推一下式子。这里就直接放结果了。
发现式子的减号右边跟划分方案根本没有关系，因此我们的目标就是求 即平方和的最值。
我们记 为前 段分到第 个数的最小值。有下面这个转移：
平方和使用前缀和维护，这样我们就有了 的做法了。然后怎么优化呢？
于是咱就去学了一下斜率优化。
变换一下上面的式子，先把第一维压缩掉，把前缀和式子写进去，然后把跟 无关的挪到等号左边去：
设式子左边为 、、、，则有：
在最优决策下，有
如果我们将 视作一些点，如果我们需要最小化截距 ，已知 ，画个图是这样的：
（点 D、H 不作为决策点，为辅助点）
如果将红色线条逐个上移，那么我们会发现 C 在任何时候都不会被扫到，因此可以忽略。而且对于任意斜率也是如此。对于这个情景而言，F 为最优点，而且这个点可以保证 在 的斜率和 的斜率之间。又由于对于每一轮决策 单调递增，因此忽略最下面的两个点也无妨。
这启示着我们使用一种数据结构去维护这些点，就是单调队列，保证里面斜率单调递增/递减即可。这东西可以维护一个凸包。然后分讨一下这些点的决策到底是哪个方向就行了。
#define cmp <
using namespace std;
const int MAXN = 3005;
int last[MAXN], f[MAXN], qaq[MAXN], pre[MAXN];
int n, m;
template<class T>
inline T square(T x) { return x * x; }
int head, tail;
int que[MAXN];
inline void clear() { tail = 0, head = 1; }
inline int getx(int j) { return pre[j]; }
inline int gety(int j) { return last[j] + square(pre[j]); }
inline double slope(int fr, int bk) { return 1. * (gety(bk) - gety(fr)) / (getx(bk) - getx(fr)); }
inline void push(int k)
{
while (head < tail && slope(que[tail], k) cmp slope(que[tail - 1], que[tail]))
tail--;
que[++tail] = k;
}
inline void pop(double k)
{
while (head < tail && slope(que[head], que[head + 1]) cmp k)
head++;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(last, 0x3f, sizeof last);
last[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> qaq[i];
pre[i] = qaq[i] + pre[i - 1];
}
for (int i = 1; i <= m; i++) {
clear();
push(i - 1);
for (int j = i; j <= n; j++) {
pop(2 * pre[j]);
int k = que[head];
f[j] = last[k] + square(pre[j] - pre[k]);
push(j);
}
memcpy(last, f, sizeof(int) * (n + 1));
}
cout << f[n] * m - square(pre[n]) << '\n';
}「ARC117C」Tricolor Pyramid
题意不去叙述了。
如果把每个颜色对应 的数字，记最底下那一层是 ，玩一下会发现，第一层会有一个杨辉三角的规律。然后就是对 取模。
这个时候需要 Lucas 定理辅助一下，因为 这个模数太小了。
const int MODN = 3;
int C(int n, int m) {
if (n < m) return 0;
int res = 1;
for (int i = n - m + 1; i <= n; i++) res *= i;
for (int i = 1; i <= m; i++) res /= i;
return res % 3;
}
int lucas(int n, int m)
{
if (m == 0) return 1;
if (n < m) return 0;
return lucas(n / 3, m / 3) * C(n % 3, m % 3) % 3;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
char ch;
cin >> ch;
ans = ans + lucas(n - 1, i - 1) * (ch == 'B' ? 0 :
ch == 'W' ? 1 : 2);
ans %= MODN;
}
if (n % 2 == 0) {
// cout << "mod\n";
ans = (3 - ans) % 3;
}
ans = (ans % MODN + MODN) % MODN;
cout << (
ans == 0 ? 'B' :
ans == 1 ? 'W' : 'R'
);
}「AHOI2005」矿藏编码
哎哎题意就不放了。就是深搜然后计算 的很多次方。理论上要高精度，实际上 u128 就行了。
use std::io::{self, Read};
fn work(x: i32, ans: &mut u128, input: &mut impl Iterator<Item = u8>) {
if let Some(tmp) = input.next() {
if tmp == b'2' {
for _ in 0..4 {
work(x - 1, ans, input);
}
} else if tmp == b'0' {
*ans += 4_u128.pow(x as u32);
}
}
}
fn main() {
let mut input = String::new();
io::stdin().read_to_string(&mut input).unwrap();
let mut input = input.split_whitespace();
let k: i32 = input.next().unwrap().parse().unwrap();
let mut char_iter = input.next().unwrap().bytes();
let mut ans = 0;
work(k, &mut ans, &mut char_iter);
println!("{}", ans);
}「NOIP1998 提高组」进制位
题意略。
首先显然可以证明进制数就是表格的列数 - 1。然后你会发现这道题的 很小，所以可以 枚举然后 check。但是写起来很恶心。
char ltr[10];
string mp[10][10];
map<char, int> idxof;
map<char, int> wei;
char rewei[10];
int n;
inline void print_wei() {
for (int i = 1; i <= n; i++) {
cout << ltr[i] << "=" << wei[ltr[i]] << ' ';
}
}
inline string add(string a, string b) {
for (auto &ch : a) ch = wei[ch];
for (auto &ch : b) ch = wei[ch];
string c = "qq";
c[0] = a[0] + b[0];
c[1] = c[0] / n; c[0] %= n; c[1] += a[1] + b[1];
if (c[1] == 0) c.pop_back();
for (auto &ch : c) ch = rewei[ch];
reverse(c.begin(), c.end());
return c;
}
inline bool check() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (add(string() + ltr[i], string() + ltr[j]) != mp[i][j]) return false;
}
}
return true;
}
void dfs(int u) {
if (u == n + 1) {
if (check()) {
for (int i = 1; i <= n; i++) {
cout << ltr[i] << "=" << wei[ltr[i]] << ' ';
}
cout << '\n' << n << '\n';
throw 1;
}
return;
}
for (int i = 0; i < n; i++) {
if (!rewei[i]) {
rewei[i] = ltr[u];
wei[ltr[u]] = i;
dfs(u + 1);
rewei[i] = 0;
wei[ltr[u]] = -1;
}
}
}
int main()
{
cin >> n; n--;
string ch; cin >> ch;
for (int i = 1; i <= n; i++) {
cin >> ltr[i];
idxof[ltr[i]] = i - 1;
}
for (int i = 1; i <= n; i++) {
char r;
cin >> r;
r = idxof[r] + 1;
for (int j = 1; j <= n; j++) {
cin >> mp[r][j];
}
}
try {
dfs(1);
} catch (int) {
return 0;
};
cout << "ERROR!\n";
}「HAOI2017」方案数
https://www.luogu.com.cn/record/181138333
「ABC207E」Mod i
https://www.luogu.com.cn/record/181255389
洛谷 P6327 区间加区间 sin 和
维护两个操作，区间加、区间求 sin 和。
对于 sin 值有，
这样就可以线段树维护了。
inline void pushdown(int p)
{
if (tr[p].lz) {
updlz(p << 1, tr[p].lz);
updlz(p << 1 | 1, tr[p].lz);
tr[p].lz = 0;
}
}
inline void updlz(int p, long long val)
{
double sina = tr[p].sine, cosa = tr[p].cosine;
double sinx = sin(val), cosx = cos(val);
tr[p].sine = sina * cosx + cosa * sinx;
tr[p].cosine = cosa * cosx - sina * sinx;
tr[p].lz += val;
}「CQOI2007」涂色
假设你有一条长度为 的木板，初始时没有涂过任何颜色。你希望把它的 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 的字符串表示这个目标：。
每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 ，第二次涂成 ，第三次涂成 ，达到目标。
用尽量少的涂色次数达到目标。
数据范围 。
这道题看起来像是个区间 DP，这数据范围小得有点夸张了。对于每一个区间有两种情况：
- 如果区间两端颜色相同，如果每次区间转移只添加一侧的端点，那么可以证明这个时候不需要多涂色。
- 否则枚举断点，然后求断点两边涂色次数的和的最小值。
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> s;
int n = s.length();
s = " " + s;
memset(f, 0x3f, sizeof f);
for (int i = 1; i <= n; i++) f[i][i] = 1;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
if (s[l] == s[r]) {
f[l][r] = min(f[l + 1][r], f[l][r - 1]);
} else {
for (int m = l; m < r; m++) {
f[l][r] = min(f[l][r], f[l][m] + f[m + 1][r]);
}
}
}
}
cout << f[1][n] << '\n';
}「MX-X5-T0 / GFOI Round 1」Hypnotize
哎源批收收味。
找一串数字中是否存在两个数字相差 。数据范围 100。
两个方法：
- 暴力做 。枚举 然后依次做差判断。
- 值域做 。开个 set 记一下 然后挨个看有没有 有没有在 set 里。
int main()
{
int n, k;
set<int> s;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
s.insert(t);
}
for (auto x : s) {
if (s.count(x + k)) {
cout << "Yes\n";
return 0;
}
}
cout << "No\n";
}关路灯
https://www.luogu.com.cn/record/182325092
「ABC328E」Modulo MST
其实这个之前做过，但是因为后来被拉到题单里面了没写记录然后就只写一个记录算了。
求一个最小生成树，但是权值在模 意义下最小。
看起来很吓人对不对！但这是 ABC，然后一看数据范围 ，然后就可以开始暴力了。
「ABC174E」Logs
https://www.luogu.com.cn/record/182517337
「ABC244E」King Bombee
https://www.luogu.com.cn/record/182574143
「ABC129E」Sum Equals Xor
https://www.luogu.com.cn/record/182740646
「ABC133E」Virus Tree 2
https://www.luogu.com.cn/record/182783033
「ABC137E」Coins Respawn
https://www.luogu.com.cn/record/182796843
「POI2015」Trzy wieże (TRZ)
（证明待补充 有人看到了踢我一脚我去补）
可以证明答案的端点必定在前三个或者后三个里面。
template<int delta, class Cmp>
int bf(int l, int r, Cmp cmp)
{
int cnt[3] = { 0, 0, 0 };
int ans = 0;
for (int i = l; cmp(i, r); i += delta) {
if (s[i] == 'B') cnt[0]++;
else if (s[i] == 'C') cnt[1]++;
else cnt[2]++;
if (
(cnt[0] == 0 || cnt[1] == 0 || cnt[0] != cnt[1]) &&
(cnt[1] == 0 || cnt[2] == 0 || cnt[1] != cnt[2]) &&
(cnt[0] == 0 || cnt[2] == 0 || cnt[0] != cnt[2]))
{
ans = max(ans, abs(i - l) + 1);
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> s;
cout << max({
bf<1>(0, n, less<int>{}),
bf<1>(1, n, less<int>{}),
bf<1>(2, n, less<int>{}),
bf<-1>(n - 1, 0, greater_equal<int>{}),
bf<-1>(n - 2, 0, greater_equal<int>{}),
bf<-1>(n - 3, 0, greater_equal<int>{}),
});
}洛谷 P1638 逛画展
博览馆正在展出由世上最佳的 位画家所画的图画。
游客在购买门票时必须说明两个数字， 和 ，代表他要看展览中的第 幅至第 幅画（包含 ）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 ，数据保证一定有解。
等下为什么最近在补这么简单的题目。
本题可以双指针。给画师记个数然后双指针扫。扫到满足条件的就 ok。
for (int i = 1; i <= n; i++) cin >> id[i];
int r = 1;
cnt[id[1]]++; knd = 1;
for (int l = 1; l <= n; l++) {
while (r < n && knd < k) {
r++;
if (cnt[id[r]] == 0) knd++;
cnt[id[r]]++;
}
if (knd == k) {
if (r - l < ansr - ansl) {
ansr = r, ansl = l;
}
}
cnt[id[l]]--;
if (cnt[id[l]] == 0) knd--;
}
cout << ansl << ' ' << ansr << '\n';「CSP-S 2023」结构体
按照题意模拟即可。
实现细节比较多。直接看题目最下面的形式化定义，然后按照形式化定义写会好很多，要不然我理解了半天样例 2 都看不懂。
可以发现，对于每一个数据类型（即结构体），只要知道了其内存对齐和大小，那么在该类型被嵌套的情况下，可以推出父类型的对齐和大小。
对于一个结构体而言，我们可以存储每一个成员相对于该结构体的基地址的偏移（offset），这样在随机地址访问的时候可以二分到这个地方，而且你会发现算地址的时候很好算（可以递归计算），且形式化定义也是从偏移出发的。
对于每一个对象，你不需要真正把空间开满，只需要记住该对象在全局作用域的偏移（起始地址）和类型。这样只需要对偏移动手脚了。
要记住在操作 4（即随机地址访问）的时候对于全局作用域的对象进行判空。
因为数据量不大所以直接 string 乱飞值拷贝随便整反正时间复杂度没问题！
「CSP-S 2021」回文
「CSP-S 2021」廊桥分配
机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
L 市新建了一座机场，一共有 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
保证同一时刻只有一架飞机起降。
现在只看一个区。假如我们把所有的廊桥全部分给一个区，如果我们贪心地、每次分配编号最小的可用廊桥，那么会发现下面的性质：
因为是先来后到的原则，对于廊桥分配的数量，如果廊桥数量限制为 ，则等价于所有编号 的廊桥无法被分配到飞机。
可以预处理出两个区在最大编号为 的时候最多可以分配到廊桥的飞机数量。
「NOI Online 2021 入门组」切蛋糕
玩一下会发现这东西是分类讨论。
- 对于 2 个 0：答案是 0。
- 对于 1 个 0：如果是对半分，则答案是 1；否则答案是 2。
- 对于全都不是 0：
- 如果存在 ，相当于对半分之后再分一刀，答案是 。
- 如果存在 ，你会发现切两刀之后，因为对顶角相等，所以可以保证存在一种分法使得 。这个情况就等价于 1 个 0 时的后面的情况。
- 无论想怎么分，都不会超过 3 刀。
while (t--) {
cin >> ar[0] >> ar[1] >> ar[2];
sort(ar.begin(), ar.end());
if (ar[1] == 0) {
cout << "0\n";
} else if (ar[0] == 0) {
if (ar[1] == ar[2]) cout << "1\n";
else cout << "2\n";
} else {
if (ar[0] == ar[1] || ar[1] == ar[2]) {
cout << "2\n";
} else if (ar[0] + ar[1] == ar[2]) {
cout << "2\n";
} else {
cout << "3\n";
}
}
}！「NOI Online 2022 提高组」丹钓战
https://www.luogu.com.cn/record/184571401
「NOIP2002 提高组」字串变换
这题比较神秘。暴力广搜就能通过测试数据。但是他说这是个错题。
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> a >> b;
int n = 0;
while (cin >> rules[n].first >> rules[n].second) n++;
q.push(a);
dist[a] = 0;
while (!q.empty()) {
auto p = q.front(); q.pop();
int d = dist[p];
if (d > 10) break;
if (dist.count(b)) {
cout << dist[b] << '\n';
return 0;
}
for (int i = 0; i < n; i++) {
auto lpos = p.find(rules[i].first);
while (lpos != string::npos) {
string x = p;
x.replace(lpos, rules[i].first.size(), rules[i].second);
// cout << p << ' ' << x << '\n';
if (!dist.count(x)) {
dist[x] = d + 1;
q.push(x);
}
lpos = p.find(rules[i].first, lpos + 1);
}
}
}
if (dist.count(b)) {
cout << dist[b] << '\n';
} else {
cout << "NO ANSWER!\n";
}
}「ABC131E」Friendships
构造一个有 个节点的简单图使得恰好仅有 对节点 之间的最短距离为 。
先猜一下，如果这张图是菊花的话，那么满足条件的点对最多。看起来像是一个比较显然的结论。那么可以发现， 是 满足条件的上界。如果我们连接 ，那么这两点的最短路径变为 1。因此我们可以从菊花图的基础上构建一个图，如果 太多了就连起来让这些点对恰好减少 1 个。
int main()
{
cin >> n >> k;
int x = (n - 1) * (n - 2) / 2;
if (k > (n - 1) * (n - 2) / 2) {
cout << "-1\n";
return 0;
}
cout << n - 1 + x - k << '\n';
int cnt = 1;
for (int i = 2; i <= n; i++) cout << 1 << ' ' << i << '\n';
for (int i = 2; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (cnt > x - k) break;
cnt++; cout << i << ' ' << j << '\n';
}
}
}「ABC155E」Payment
有 种不同面值的十进制货币，每种面值分别为 。你现在需要买一个 元的东西（），而且你和店员有无限多货币，求付钱以及找零所花费的货币个数的最小值。
一眼 dp。设式子 表示第 种货币（相当于从最低位枚举）可以分别直接支付（）或者通过找零（）可消耗的最少的货币数量。
有下面的式子：
\left\\{ \begin{aligned} f(i, 0) &= \min(f(i - 1, 0), f(i - 1, 1) + 1) + a_i & \text{可以直接支付} \\\\ & & \text{或再付 1 张然后凑找零} \\\\ f(i, 1) &= \min(f(i - 1, 0), f(i - 1, 1) - 1) + 10 - a_i & \text{直接付或找零} \\\\ & & \text{多一张减掉} \\\\ \end{aligned} \right.int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> s;
reverse(s.begin(), s.end());
int n = s.size();
f[0][0] = s[0] - '0';
f[0][1] = 10 - (s[0] - '0');
for (int i = 1; i < n; i++) {
f[i][0] = min(f[i - 1][0], f[i - 1][1] + 1) + s[i] - '0';
f[i][1] = min(f[i - 1][0], f[i - 1][1] - 1) + 10 - (s[i] - '0');
}
ll ans = min(f[n - 1][0], f[n - 1][1] + 1);
cout << ans << '\n';
}或者这个题还有一个贪心策略，大概就是凑 是最优的。在这里就略了。
「ABC159E」Dividing Chocolate
切切切切切你说得对但是我没有切力。
给你一个最大 的 0/1 网格图，可以横着或者竖着切几刀，要求判断最少切几刀才可以使所有块里面 1 的个数不超过 。
注意到有一维非常小，可以 枚举。然后另一维贪心处理。
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
}
}
int ans = 1145141919;
for (int stat = 0; stat < (1 << (n - 1)); stat++) {
// slice after i
int r = __builtin_popcount(stat);
memset(cnt, 0, sizeof cnt);
for (int j = 1; j <= m; j++) {
int rd = 0;
for (int i = 0; i < n; i++) {
cnt[1][rd] += arr[i][j] - '0';
if (stat & (1 << i)) {
rd++;
}
}
for (int i = 0; i <= rd; i++) if (cnt[0][i] + cnt[1][i] > k) {
r++;
memcpy(cnt[0], cnt[1], sizeof cnt[0]);
memset(cnt[1], 0, sizeof cnt[0]);
break;
}
for (int i = 0; i <= rd; i++) {
cnt[0][i] += cnt[1][i];
if (cnt[0][i] > k) r = 0x3f3f3f3f;
}
memset(cnt[1], 0, sizeof cnt[0]);
}
ans = min(ans, r);
}
cout << ans << '\n';
}「ROI 2019 Day1」Московские числа 拍照
题意：给你一个无色序列，你现在需要给序列区间染色以构造出给定的序列，要求给出构造方案，每种颜色只能使用一次。
由于每种颜色只能使用一次，因此可以先处理出每个节点出现的最左和最右的端点。显然这两个点之间必须被涂色。因此可以试着用线段树维护涂色，将所有左右端点排序后依次染色，如果涂出来的序列恰好是给定的序列则 ok。
struct {
struct { int l, r, lz, val; } tr[5000006];
void build(int l, int r, int p = 1) {
tr[p] = {l, r, 0, 0};
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
}
inline void updlz(int p, int val) { tr[p].lz = tr[p].val = val; }
inline void pushd(int p) { if (tr[p].lz) updlz(p << 1, tr[p].lz), updlz(p << 1 | 1, tr[p].lz), tr[p].lz = 0; }
void upd(int l, int r, int x, int p = 1) {
if (l > tr[p].r || tr[p].l > r) return;
if (l <= tr[p].l && tr[p].r <= r) return updlz(p, x);
pushd(p);
upd(l, r, x, p << 1), upd(l, r, x, p << 1 | 1);
}
int qry(int x, int p = 1) {
if (tr[p].l == tr[p].r) return tr[p].val;
int mid = (tr[p].l + tr[p].r) >> 1;
pushd(p);
if (x <= mid) return qry(x, p << 1);
return qry(x, p << 1 | 1);
}
} seg;
int m, n;
int ll[300005], rr[300005], d[300005];
vector<array<int, 3>> rg;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> d[i];
if (!ll[d[i]]) ll[d[i]] = i;
rr[d[i]] = i;
}
seg.build(1, m);
for (int i = 1; i <= n; i++) if (ll[i] && rr[i]) rg.push_back({ ll[i], rr[i], i });
sort(rg.begin(), rg.end());
for (auto x : rg) {
seg.upd(x[0], x[1], x[2]);
}
for (int i = 1; i <= m; i++) {
if (seg.qry(i) != d[i]) {
cout << "-1\n";
return 0;
}
}
cout << rg.size() << '\n';
for (auto x : rg) {
cout << x[2] << ' ' << x[0] << ' ' << x[1] << '\n';
}
}
「USACO 2012 December (Gold)」First!
aka [USACO12DEC] First! G
给你一堆字符串 ，让你判断「是否有一种重新排列字母表的方式使得第 个字符串的字典序最小」。
看到字典序这个东西应该想到字典树。如果我们把所有字符串都放在字典树上的话，那么可以发现，如果我们希望一个串字典序最小，那么在这个串在每一层都应该放在第一个。每一层的约束都不多，所以可以在遍历每一层的时候处理出每一个字母的拓扑关系，然后跑拓扑排序就可以啦。
但是！要注意字典序比较是包含长度的，如果一个字符串存在前缀，那么它永远不可能排到第一个的！
string team[30005];
struct Node {
Node* child[26];
int end = 0;
Node() { memset(child, 0, sizeof child); }
};
Node* root = new Node;
void insert(const string& s)
{
Node* cur = root;
for (auto ch : s) {
if (!cur->child[ch - 'a']) cur->child[ch - 'a'] = new Node;
cur = cur->child[ch - 'a'];
}
cur->end++;
}
bool buildup(const string& s)
{
Node* cur = root;
for (auto ch : s) {
int x = ch - 'a';
for (int i = 0; i < 26; i++) {
if (i != x && cur->child[i]) addedge(i, x);
}
if (cur->end) return false;
cur = cur->child[ch - 'a'];
}
return true;
}
bool topo()
{
queue<int> q;
vector<int> res;
for (int i = 0; i < 26; i++) if (!deg[i]) q.push(i);
while (!q.empty()) {
int top = q.front(); q.pop();
res.push_back(top);
for (int e = head[top]; e; e = ed[e].nxt) {
int v = ed[e].v;
if (!--deg[v]) q.push(v);
}
}
if (res.size() != 26) return false;
return true;
}
int flag[30005], cnt;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> team[i];
insert(team[i]);
}
for (int i = 1; i <= n; i++) {
edcnt = 0;
memset(head, 0, sizeof head);
memset(deg, 0, sizeof deg);
if (buildup(team[i]) && topo()) {
flag[i] = true; cnt++;
}
}
cout << cnt << '\n';
for (int i = 1; i <= n; i++) {
if (flag[i]) cout << team[i] << '\n';
}
}「COTS 2019」Vezuv 排名
其实这个题和上面那个题是一样的，只不过需要算出方案而已。
@@ -12,7 +12,7 @@
int n, m;
-string team[30005];
+string team[25005];
struct Node {
Node* child[26];
@@ -57,7 +57,7 @@
}
return true;
}
-bool topo()
+void topo()
{
queue<int> q;
vector<int> res;
@@ -80,12 +80,13 @@
}
}
- if (res.size() != 26) return false;
- return true;
+ if (res.size() != 26) cout << "nemoguce\n";
+ else {
+ for (auto x : res) cout << char(x + 'a');
+ cout << '\n';
+ }
}
-int flag[30005], cnt;
-
int main()
{
ios::sync_with_stdio(false);
@@ -99,12 +100,10 @@
edcnt = 0;
memset(head, 0, sizeof head);
memset(deg, 0, sizeof deg);
- if (buildup(team[i]) && topo()) {
- flag[i] = true; cnt++;
+ if (buildup(team[i])) {
+ topo();
+ } else {
+ cout << "nemoguce\n";
}
}
- cout << cnt << '\n';
- for (int i = 1; i <= n; i++) {
- if (flag[i]) cout << team[i] << '\n';
- }
}「ROIR 2024 Day2」Бактерии 细菌 / 细菌实验
（ROI Regional 2024 Day2 T1. Бактерии）
发现细菌的数量在已知时刻可以 算出，因此可以二分时刻。
因为是要找第一个等于，手写二分边界太麻烦，在借鉴一种很新的二分答案写法 by EarthMessenger 之后人工拷了 iterator 的结构定义然后人工封了一个迭代器。
然后就不需要考虑边界啦！
ll delay[200005], interval[200005];
int n, m;
struct int_iter {
using iterator_category = std::random_access_iterator_tag;
using value_type = ll;
using difference_type = ll;
using pointer = ll*;
using reference = ll&;
int_iter(ll val): val(val) {}
int_iter& operator++() { val++; return *this; }
int_iter& operator+=(auto rhs) { val += rhs; return *this; }
int_iter& operator--() { val--; return *this; }
const ll operator-(const int_iter& rhs) {
return val - rhs.val;
}
ll& operator*() { return val; }
bool operator<(const int_iter& rhs) {
return val < rhs.val;
}
private:
ll val;
};
ll check(ll time, bool chk = false)
{
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (time < delay[i]) continue;
if (time < interval[i] + delay[i]) {
ans++;
continue;
}
ll digit = (time - delay[i] - interval[i]) + 1;
if (digit > 30) return LONG_LONG_MAX;
if (chk) cout << i << ' ' << digit << '\n';
ans += 1ll << digit;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> delay[i];
for (int i = 1; i <= n; i++) cin >> interval[i];
ll ans = *lower_bound(int_iter(0), int_iter(1e18), m, [](ll k, ll to_find) {
return check(k) < m;
});
if (check(ans) == m)
cout << ans << '\n';
else cout << "-1\n";
}Copyright (C) Imken Luo
This post is licensed under CC-BY-NC-SA 4.0.