召唤神坤
- 有意思🤔(ikun)。
- 虽然是第一题但也要配得上神坤的身份。
思路1
- 枚举分母,选择一个数据结构来选出分母两侧最大的两个数做分子。
- 2s常数大些也无碍。
- 我选择好写的ST表
思路2
- 写两个 d p dp dp 分别表示 1 1 1 到 i i i 的最大值, i i i 到 n n n 的最大值。再枚举。
- 这个不放码了看的别人的思路。
signed main() {int T = 1;
// T = read();while (T--) {int n = read();vector<int> a(n + 1), logn(n + 1);vector<vector<int>> f(n + 1, vector<int>(30));for (int i = 1; i <= n; ++i) f[i][0] = a[i] = read();logn[0] = -1;for (int i = 1; i <= n; ++i) logn[i] = logn[i >> 1] + 1;for (int j = 1; j <= logn[n]; ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);}}int ans = 0;for (int i = 2; i < n; ++i) {int l = 1, r = i - 1, s = logn[r - l + 1];int wi = max(f[l][s], f[r - (1 << s) + 1][s]);l = i + 1, r = n, s = logn[r - l + 1];int wk = max(f[l][s], f[r - (1 << s) + 1][s]);ans = max(ans, (wi + wk) / a[i]);}write(ans);}return 0;
}
聪明的交换策略
分析
- 依据题意就是要么 0 0 0 左 1 1 1 右,要么 1 1 1 左 0 0 0 右。
- 考虑 0 0 0 左还是 0 0 0 右即可。考虑 1 1 1 也行一样的。
signed main() {int T = 1;
// T = read();while (T--) {int n = read();string s; cin >> s;vector<int> pos;for (int i = 0; i < s.size(); ++i) {if (s[i] ^ '1') pos.push_back(i);}int ans = 1e17, tmp1 = 0, tmp2 = 0;for (int i = 0; i < pos.size(); ++i) tmp1 += pos[i] - i;ans = min(ans, tmp1);for (int i = pos.size() - 1, j = n - 1; i >= 0; --i, --j) tmp2 += j - pos[i];ans = min(ans, tmp2);write(ans);}return 0;
}
怪兽突击
ps:总觉得codeforces做过。。
思路
- 枚举每个 i i i (当然要小于等于 k k k )。
signed main() {int T = 1;
// T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= n; ++i) b[i] = read();priority_queue<int, vector<int>, greater<int>> pq;int ans = 1e17, cnt = 0;for (int i = 1; i <= n && i <= k; ++i) {cnt += a[i];pq.push(a[i] + b[i]);ans = min(ans, cnt + (k - i) * pq.top());}write(ans);}return 0;
}
蓝桥快打
思路
- 根据 A , C A,C A,C 可以得出攻击次数的范围, B ≤ n ⋅ x B\leq n\cdot x B≤n⋅x 。
signed main() {int T = 1;T = read();while (T--) {int a = read(), b = read(), c = read();int r = a / c + (a % c > 0);writeln(b / r + (b % r > 0));}return 0;
}
奇怪的段
思路
- d p dp dp
- 方程: d p i = m a x ( d p i − 1 , j , d p i − 1 , j − 1 ) + a i ⋅ p j dp_i=max(dp_{i-1,j},dp_{i-1,j-1})+a_i\cdot p_j dpi=max(dpi−1,j,dpi−1,j−1)+ai⋅pj 。
- 注意有负数
signed main() {int T = 1;
// T = read();while (T--) {int n = read(), k = read();vector<int> a(n + 1), p(k + 1);vector<vector<int>> dp(n + 1, vector<int>(201, -1e15));dp[0][0] = 0;for (int i = 1; i <= n; ++i) a[i] = read();for (int i = 1; i <= k; ++i) p[i] = read();for (int i = 1; i <= n; ++i) {for (int j = 1; j <= k; ++j) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i] * p[j];}}write(dp[n][k]);}return 0;
}
小蓝的反击
ps:是个区间求解问题,涉及基础数论。
思路
- 枚举每一个 i i i ,找到最小位置 j j j 满足 A ∣ ∏ k = i j 1 a k , B ∣ ∏ k = i j 2 a k A| \prod_{k=i}^{j_1}a_k,\;B|\prod_{k=i}^{j_2}a_k A∣∏k=ij1ak,B∣∏k=ij2ak 。
- 如果 j 1 j_1 j1 不存在那么往后再也不能整除 A A A 了。如果 j 2 j_2 j2 不存在,那么从 j 1 j_1 j1 到 n n n 都能整出 A A A 。都存在只有 j 2 > j 1 j_2 >j_1 j2>j1 才对答案有贡献。
- 对 A , B A,B A,B 质因数分解记录因子和各因子数量。
- 对 A , B A,B A,B 每一个因子做前缀和。
- 二分枚举区间询问是否存在(该有的因子和数量都要满足)。
ps:前缀和那儿显然是个二维的,试想质因数分解有可能出现因数很大的情况,第二维是因数大小会 M E L MEL MEL ,所以第二维应该为数量,而数量最多是10(前十个质数相乘已经 > 1 0 9 >10^9 >109 )。看题解有个 d p dp dp 的,巨,我不会。
signed main() {auto getFactor = [&] (int v) {vector<pii> vec;for (int i = 2; i <= v / i; ++i) {if (!(v % i)) {vec.push_back({i, 0});while (!(v % i)) v /= i, ++vec.back().second;}}if (v ^ 1) vec.push_back({v, 1});return vec;};int T = 1;
// T = read();while (T--) {int n = read(), a = read(), b = read();auto vec1 = getFactor(a), vec2 = getFactor(b);vector<vector<int>> prefa(n + 1, vector<int>(10)), prefb(n + 1, vector<int>(10));for (int i = 1; i <= n; ++i) {int u = read();for (int j = 0; j < vec1.size(); ++j) {int tmp = u, v = vec1[j].first;while (!(tmp % v)) {++prefa[i][j];tmp /= v;}prefa[i][j] += prefa[i - 1][j];}for (int j = 0; j < vec2.size(); ++j) {int tmp = u, v = vec2[j].first;while (!(tmp % v)) {++prefb[i][j];tmp /= v;}prefb[i][j] += prefb[i - 1][j];}}auto find = [&] (int i, int j, int cnt, int op) {int l = i, r = n, tmp = op? prefb[i - 1][j]: prefa[i - 1][j];int ans = -1;while (l <= r) {int mid = (l + r) >> 1, v = op? prefb[mid][j]: prefa[mid][j];if (v - tmp >= cnt) ans = mid, r = mid - 1;else l = mid + 1;}return ans;};long long int ans = 0;for (int i = 1; i <= n; ++i) {int pos1 = i;for (int j = 0; j < vec1.size(); ++j) {int pos = find(i, j, vec1[j].second, 0);if (pos ^ -1) pos1 = max(pos1, pos);else {pos1 = -1;break;}}if (pos1 == -1) break;int pos2 = i;for (int j = 0; j < vec2.size(); ++j) {int pos = find(i, j, vec2[j].second, 1);if (pos ^ -1) pos2 = max(pos2, pos);else {pos2 = -1;break;}}if (pos2 == -1) ans += (n - pos1 + 1) * 1ll;else if (pos2 > pos1) ans += (pos2 - pos1) * 1ll;}// write(ans);cout << ans;}return 0;
}