长春火车站哪个区,马洪旭 做的网站大学,电子商务网站建设需要学什么,无锡市太湖新城建设网站召唤神坤
有意思#x1f914;#xff08;ikun#xff09;。虽然是第一题但也要配得上神坤的身份。
思路1
枚举分母#xff0c;选择一个数据结构来选出分母两侧最大的两个数做分子。2s常数大些也无碍。我选择好写的ST表
思路2
写两个 d p dp dp 分别表示 1 1 1 到 i…召唤神坤
有意思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();vectorint a(n 1), logn(n 1);vectorvectorint f(n 1, vectorint(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;vectorint 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();vectorint 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_queueint, vectorint, greaterint 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_imax(dp_{i-1,j},dp_{i-1,j-1})a_i\cdot p_j dpimax(dpi−1,j,dpi−1,j−1)ai⋅pj 。注意有负数
signed main() {int T 1;
// T read();while (T--) {int n read(), k read();vectorint a(n 1), p(k 1);vectorvectorint dp(n 1, vectorint(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_{ki}^{j_1}a_k,\;B|\prod_{ki}^{j_2}a_k A∣∏kij1ak,B∣∏kij2ak 。如果 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 j2j1 才对答案有贡献。对 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) {vectorpii 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);vectorvectorint prefa(n 1, vectorint(10)), prefb(n 1, vectorint(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;
}
