A 区间最大值
#include<iostream> using namespace std; int main() { int n, m; cin>> n >> m; while(m--) { int l, r; cin >> l >> r; int ans = 0; // [l, r]区间，找到其中分块的每一块左端点，维护最大值 for (int i = l; i <= r; i = n / (n / i) + 1) { ans = max(ans, n % i); } cout << ans << endl; } }
B 模块改造
#include<stdio.h> int main(){ int s,t,i; char sr[50]={0}; scanf("%s",sr+1); s=0;t=0; for(i=1;i<50;++i) { if(sr[i]=='1')t=i; else { if(sr[i-1]=='1') printf("%02d:%02d - %02d:%02d\n",s/2,s%2*30,t/2,t%2*30); s=i; } } if(t==0)printf("00:00 - 00:00"); return 0; }
C 矩阵变换
D 猪猪也想C位出道
E 爬塔
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; int n, m; string s; set<PII> mp[11]; // mp[len] = {{l1, r1}, {l2, r2}, ...} // 转化问题：通关的最大关卡数 == 最长区间和为0且合法数 void solve() { int l, r; cin >> l >> r; /// 从最长区间开始枚 for (int i = 10; i >= 1; i--) { // 找到>=l的位置 auto it = mp[i].lower_bound({l, -1}); if(it == mp[i].end()) continue; // 如果左右都在内部，满足能从[l, r]中任意位置开始，走i步区间和位0且合法 if(it->first >= l && it->second <= r) { cout << i << '\n'; return ; } } cout << 0 << '\n'; } int main() { // n位01， s是01串，m是询问 cin >> n >> s >> m; s = " " + s; for (int i = 1; i <= n; i++) { int ans = 0; for (int j = i; j <= i + 9; j++) { if(s[j] == '1') ans++; else ans--; if(ans < 0) break; if(ans == 0) mp[j - i + 1].insert({i, j}); } } while(m--) { // 每次询问：l，r，问从[l, r]任意位置开始能通关的最大关卡数 solve(); } }
F 一个很大的数
题解：
样例：
void solve() { int n; cin >> n; int x, k; int res = 1; while(n--) { cin >> x >> k; res = (res * (2 * k + 1)) % mod; } cout << res << endl; }
G 猪猪补习班
H 变换01串
题意：
op == 1：询问 [l, r] 区间修改为全0或1的最小操作次数
op == 2：对 [l, r] 区间进行按位取反
（修改：对字符串前缀或后缀按位取反）
思路：
3. 盲猜结论：前缀后缀改0改1 等价于 前缀全改0
4. 由此：010010：发现其实对前缀有1的地方修改（0会要在改一次变回），那么操作1的答案：区间段数 - 1
5. 线段树维护：
1. tr[]:区间段数 2. LL[]:区间左端点是0还是1 3. RR[]:区间右端点是0还是1 4. add[]:懒标记 5. 段数 = 两端交界处相同则需要 -1
#include<bits/stdc++.h> const int N = 100010; using namespace std; #define ls u<<1 #define rs u<<1|1 int n, m; string s; int tr[N << 2], L[N << 2], R[N << 2], add[N << 2]; // LL, RR 维护当前区间左右端点的01信息 int LL[N << 2], RR[N << 2]; void pushup(int u) { tr[u] = tr[ls] + tr[rs]; if(RR[ls] != LL[rs]) tr[u]++; LL[u] = LL[ls]; RR[u] = RR[rs]; } void pushdown(int u) { if(add[u]) { LL[ls] ^= 1, RR[ls] ^= 1, add[ls] ^= 1; LL[rs] ^= 1, RR[rs] ^= 1, add[rs] ^= 1; add[u] ^= 1; } } void build(int u, int l, int r) { L[u] = l, R[u] = r; if(l == r) { tr[u] = 0; // 你想想：询问 [2, 2] 是不是不用操作，就是0步（一段 - 1） if(s[l] == '0') LL[u] = RR[u] = 0; else LL[u] = RR[u] = 1; return ; } int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u); } void modify(int u, int l, int r) { int ll = L[u], rr = R[u]; if(ll >= l && rr <= r) { LL[u] ^= 1, RR[u] ^= 1, add[u] ^= 1; return ; } pushdown(u); int mid = ll + rr >> 1; if(l <= mid) modify(ls, l, r); if(r > mid) modify(rs, l, r); pushup(u); } // [0, 1, 2] = [段数，左端点，右端点] vector<int> query(int u, int l, int r) { vector<int> now; vector<int> ans = {0, -1, -1}; int ll = L[u], rr = R[u]; if(ll >= l && rr <= r) { return vector<int>({tr[u], LL[u], RR[u]}); } pushdown(u); int res = 0; int mid = ll + rr >> 1; if(l <= mid) { now = query(ls, l, r); ans[0] += now[0]; if(ans[2] == -1) ans[2] = now[2]; ans[1] = now[1]; } if(r > mid) { now = query(rs, l, r); ans[0] += now[0]; // 上一个query执行，两段交界处不等，段数++ if(ans[2] != -1 && ans[2] != now[1]) ans[0]++; ans[2] = now[2]; if(ans[1] == -1) ans[1] = now[1]; // 如果上面一个query没执行，ans还是初始值 } return ans; } void solve() { cin >> n >> m; cin >> s; s = '@' + s; build(1, 1, n); while(m--) { int op, l, r; cin >> op >> l >> r; if(op == 1) { cout << query(1, l, r)[0] << endl; } else { modify(1, l, r); } } } signed main() {solve();}
法二：树状数组
#include <iostream> using namespace std; const int N = 100010; int tr[N], n, m; string s; int lowbit(int x) { return x & -x; } int sum(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += tr[i]; return res; } void add(int x, int c) { for (int i = x; i <= N; i += lowbit(i)) tr[i] += c; } int main() { cin >> n >> m; cin >> s; s = '@' + s; for (int i = 2; i <= n; i++) if(s[i] != s[i - 1]) add(i, 1); while(m--) { int op, l, r; cin >> op >> l >> r; if(op == 1) { int res = sum(r) - sum(l); cout << res << endl; } else { if(l > 1) { if(sum(l) - sum(l - 1)) add(l, -1); else add(l, 1); } if(r < n) { if(sum(r + 1) - sum(r)) add(r + 1, -1); else add(r + 1, 1); } } } }
I V字钩爪
题意： 任意取多次，每次取两个（间隔为k），问最大价值。
思路：
转化题意：取出K组数，（每组都是偶数个），使其之和最大。
1.外层for k
2.内层从 i 起始步长为k，维护一个最小值 mn（防止最后是奇数，我们需要删一个（选最小的删）），注意这里是每隔一个数维护。（因为不能保证删了一个该组中最小的数，前缀是就偶数个。）
3.sum 加上每组的最大值
int a[N]; void solve() { int n, k; cin >> n >> k; int sum = 0; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= k; i++) { int cnt = 0, mn = 1e17; for (int j = i; j <= n; j += k) { cnt ++ ; if(cnt & 1) mn = min(mn, a[j]); sum += a[j]; } if(cnt & 1) sum -= mn; } cout << sum << ' '; }
