T1
题面
给定一个序列，求将序列分成三段（不能有空），将每一段的和的绝对值加起来的最大值。
题解
前缀和一下，发现分割点为 \(l\) , \(r\) 的情况下贡献为 $ \lvert {sum_{l - 1} } \rvert + \lvert {sum_r - sum_{l - 1} } \rvert + \lvert {sum_n - sum_r} \rvert$ ,分类讨论即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
int n,a[N],maxn[N],minn[N];
inline int read(){register int s = 0,w = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-')w = -1;ch = getchar();}while(isdigit(ch)){s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;
}
void Readinit(){n = read();for(int i = 1; i <= n; i++){a[i] = a[i - 1] + read();minn[i] = a[i];maxn[i] = a[i];}
}
void solve(){for(int i = 2; i <= n; i++){minn[i] = min(minn[i - 1],a[i]);maxn[i] = max(maxn[i - 1],a[i]);}int ans = 0;for(int i = 1; i < n; i++){if(a[i] <= a[n] && minn[i - 1] <= a[i] && minn[i - 1] >= 0){ans = max(ans,a[n]);}if(a[i] >= a[n] && a[i] >= minn[i - 1] && minn[i - 1] >= 0){ans = max(ans,2 * a[i] - a[n]);}if(a[i] <= maxn[i - 1] && a[i] <= a[n] && maxn[i - 1] >= 0){ans = max(ans,2 * (maxn[i - 1] - a[i]) + a[n]);}if(a[n] <= a[i] && a[n] <= maxn[i - 1] && maxn[i - 1] >= 0){ans = max(ans,2 * maxn[i - 1] - a[n]);}}for(int i = 1; i < n; i++){if(a[i] <= a[n] && minn[i - 1] <= a[i] && minn[i - 1] < 0){ans = max(ans,a[n] - 2 * minn[i - 1]);}if(a[i] >= a[n] && a[i] >= minn[i - 1] && minn[i - 1] < 0){ans = max(ans,2 * (a[i] - minn[i - 1]) - a[n]);}if(a[i] <= maxn[i - 1] && a[i] <= a[n] && maxn[i - 1] < 0){ans = max(ans,-2 * a[i] + a[n]);}if(a[n] <= a[i] && a[n] <= maxn[i - 1] && maxn[i - 1] < 0){ans = max(ans,a[n]);}}printf("%lld\n", ans);
}
signed main(){int T = 1;while(T--){Readinit();solve();}return 0;
}T2
题面
给定 \(n\) 和 \(n\) 个整数 \(a_1, a_2, \cdots, a_n\)，问至少修改多少个 \(a_i\)（每次修改可以把某个 \(a_i\) 修改成任意值），才能使相邻两个 \(a\) 之间的二进制表示至多有一位不同。
题解
考虑dp，设 \(f_i\) 表示 \(1~i\) 中最多能保留多少，答案明显为 \(n - max\{f_i\}\)。
不难想到转移，\(f_i=max^{j=i - 1}_{j = 1} \{[popcount(j - i + 1) \le j - i + 1]f_j\}+1\),复杂度\(O(n^2)\)
考虑优化，不难发现，只有从\(j=i-30\) 到 \(j=i-1\), \(f_j\)的值才有可能最优，仅从前三十转移即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,a[N],f[N];
inline int read(){register int s = 0,w = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-')w = -1;ch = getchar();}while(isdigit(ch)){s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;
}
void Readinit(){n = read();for(int i = 1; i <= n; i++){a[i] = read();f[i] = 0;}
}
void solve(){f[1] = 1;for(int i = 2; i <= n; i++){for(int j = max(1,i - 30); j <= i - 1; j++){int x = (a[i] ^ a[j]),k = 0;while(x){++k;x = x - (x & -x);}if(k <= i - j){f[i] = max(f[i],f[j] + 1);}} }int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans,f[i]);}printf("%d\n", max(0,n - ans));
}
signed main(){int T = 1;while(T--){Readinit();solve();}return 0;
}T3
题面
定义函数 \(f(x)\)，若 \(x\) 是偶数，则 \(f(x) = \frac{x}{2}\)，否则 \(x\) 是奇数，\(f(x) = 3x + 1\)。
给定 \(k\)，定义函数 \(g(x)\) 为 \(f(x)\) 调用 \(k\) 次，即 \(g(x) = f(f(\cdots f(x)))\)。
如 \(k = 1\) 时，\(g(x) = f(x)\)，\(k = 2\) 时，\(g(x) = f(f(x))\)，\(k = 3\) 时，\(g(x) = f(f(f(x)))\)，以此类推。
现在给定 \(n, k\)，求 \(\sum\limits_{x = 1}^n g(x)\)。由于答案可能很大，只需要输出其对 \(10^9 + 7\) 取模的结果。
题解
一个数列题，考验选手的数学功底。
设 \(dfs(l,len,d,k)\) 为还剩 \(k\) 次 \(f（）\) 操作，数列起点为 \(l\)，公差为 \(d\)，长度为 \(len\)。
分类讨论一下
-
当 \(d\) 为偶数时，一次操作不会影响奇偶性，往下递归即可。
-
当 \(d\) 为奇数时，能发现该数列奇偶交错，可以拆成两个等差数列处理。
细节看代码。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n,k;
int ans = 0;
int dfs(int l,int len,int d,int k){if(k == 0){return (l + l + (len - 1) * d) % mod * (len % mod) % mod * ((mod + 1) / 2) % mod;}if(d % 2 == 0){if(l % 2 == 0){return dfs(l / 2,len,d / 2,k - 1) % mod;}return dfs(l * 3 + 1,len,d * 3,k - 1) % mod;}return (dfs(l,(len + 1) / 2,2 * d,k) + dfs(l + d,len / 2,2 * d,k)) % mod;
}
inline int read(){register int s = 0,w = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-')w = -1;ch = getchar();}while(isdigit(ch)){s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;
}
void Readinit(){n = read();k = read();ans = 0;
}
void solve(){printf("%lld\n", dfs(1,n,1,k));
}
signed main(){int T = 1;while(T--){Readinit();solve();}return 0;
}T4
题面
给定 \(n, k\) 和 \(a_1, a_2, \cdots, a_n\)，现在对于每个 \(1 \le i \le n\) 的 \(i\)，求所有满足长为 \(k\) 的序列 \(b_1, b_2, \cdots, b_k\) 满足 \(b_j \ge 1\) 且这个序列所有元素的最小公倍数是 \(i\)，其序列元素权值乘积的和。
也就是对每个 \(i\) 求出，所有满足 \(b_1, \cdots, b_k\) 的最小公倍数是 \(i\) 的序列 \(b\)，\(a_{b_1} \times a_{b_2} \times \cdots a_{b_k}\) 的和。由于答案可能很大，只需要求出对 \(998244353\) 取模的结果。
题解
设最小公倍数恰好为 \(i\) 的和为 \(f_i\),公倍数为i的和为 \(g_i\)。
容易看出 \(g_i = \sum_{j|i} f_j\) ，所以有 \(f_i = g_i - \sum_{j|i且i \neq j} f_j\)
考虑怎么求 \(g_i\) ，会发现这东西特别好求，明显有 \(\g_i=(\sum_{j|i} a_j)^k\)
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100005
const int mod = 998244353;
int n,k,a[N];
int f[N],g[N];
int ksm(int x,int y){int ans = 1;while(y){if(y & 1)ans = ans * x % mod;x = x * x % mod;y >>= 1; }return ans;
}
inline int read(){register int s = 0,w = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-')w = -1;ch = getchar();}while(isdigit(ch)){s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;
}
void Readinit(){n = read();k = read();for(int i = 1; i <= n; i++)a[i] = read();
}
void solve(){for(int i = 1; i <= n; i++){for(int j = 1; i * j <= n; j++){g[i * j] += a[i];g[i * j] %= mod; }}for(int i = 1; i <= n; i++){g[i] = ksm(g[i],k) % mod;f[i] = g[i];}f[1] = ksm(a[1],k) % mod;for(int i = 1; i <= n; i++){for(int j = 2; i * j <= n; j++){f[i * j] -= f[i];f[i * j] = (f[i * j] % mod + mod) % mod;}}for(int i = 1; i <= n; i++)printf("%lld ",f[i]);
}
signed main(){int T = 1;while(T--){Readinit();solve();}return 0;
}附加
题面
给定 \(n\)，求在 \(1 \sim n\) 中选择最多的数，使得选出来的数没有任何两个是整除关系。即不存在 \(i \neq j\)，\(i\) 是 \(j\) 的约数且 \(i, j\) 都被选择。
在选出最多数的情况下，还需要最小化选出的数的和。输出这个和。
题解
推一下式子。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
inline int read(){register int s = 0,w = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-')w = -1;ch = getchar();}while(isdigit(ch)){s = (s << 3) + (s << 1) + (ch ^ 48);ch = getchar();}return s * w;
}
void Readinit(){n = read();
}
int ksm(int x,int y){int ans = 1;while(y){if(y & 1)ans *= x;x *= x;y >>= 1;}return ans;
}
void solve(){int ans = 0;if(n % 2 == 0)--n;for(int x = 0; ksm(3,x) <= n; x++){int l = n / ksm(3,x + 1),r = n / ksm(3,x);if(l * ksm(3,x + 1) <= n)++l;if(l % 2 == 0)++l;if(r % 2 == 0)--r;if(l <= r){int d = (r - l) / 2 + 1;ans += ((l + r) * d / 2) * ksm(2,x);}}printf("%lld\n", ans);
}
signed main(){int T = 1;while(T--){Readinit();solve();}return 0;
}