无锡网站,北京建设网站圣辉友联,爱站网怎么使用,设计网站需要的知识A(签到) - Select Three Sticks
题意#xff1a; 给你一个长度为 n 的正整数序列#xff0c;你可以操作任意次#xff0c;每一次操作可以选择任意一个元素#xff0c;把它 1 或者 - 1#xff0c;问最少多少次操作可以使得序列中存在三个相同的数字以构成一个等边三角形.…A(签到) - Select Three Sticks
题意 给你一个长度为 n 的正整数序列你可以操作任意次每一次操作可以选择任意一个元素把它 1 或者 - 1问最少多少次操作可以使得序列中存在三个相同的数字以构成一个等边三角形. 思路 先 sort 一遍然后取 min 即可. 参考代码
void solve() {int n;std::cin n;std::vectorint a(n);for (int i 0; i n; i) {std::cin a[i];}std::sort(a.begin(), a.end());int min (1 31) - 1;for (int i 2; i n; i) {min std::min(min, a[i] - a[i - 2]);}std::cout min \n;
}
B(找规律) - Bright, Nice, Brilliant
题意 给定一个三角形的金字塔点亮一部分的砖块使得每一层的砖块的亮度等于当前层(从高往低)请构造出一种解使得金字塔满足要求。一个点亮的砖块可以将光传递到下面两个砖块中一个砖块的亮度为所有能够传递光的砖的数量。 思路 我们找规律可以发现只需要让最两侧也就是金字塔的最外一层点亮即可让所有砖块的亮度等于当前层数。 参考代码
void solve() {int n;std::cin n;for (int i 1; i n; i) {if (i 1) {std::cout 1\n;continue;}std::cout 1 ;for (int j 1; j i - 2; j) {std::cout 0\n;}std::cout 1\n;}
}
C (贪心) - Removing Smallest Multiples
题意 有集合 S {1,2,⋯,n}, T每次操作你可以选择一个 K然后删除集合中最小且为K的倍数代价为 K问最少需要多少代价能让S变成T。 思路 贪心。从小枚举每个k让k尽量取多次直到遇到一个位置不能删。 参考代码
void solve() {int n;std::string t;std::cin n t;ll ans{};for (int i 1; i n; i) {for (int j i; j n; ji) {if (t[j - 1] 1) {break;}if (t[j - 1] 0) {t[j - 1] 2;ans i;}}}std::cout ans \n;
}
D(贪心 双指针) - Slime Escape
题意 给定一个数组 a。初始位置为k血量HP为0。每次可以向右或者向左移动。每到达一个位置会改变HP增加当前对应位置的值多次经过一个位置只有第一次会改变HP的值ai可能是正或者负数表示HP增加和减少。当HP变成负数时你就会挂掉。问能否走出两端中的其中一端。 思路 贪心双指针。两种情况是对称的只需考虑一端出去的情况。不妨设从右端出去。 每次向右边移动一个位置就看看左边所有能到达的位置中能获得的最大血量则当前能增加的最大血量等于 max(前一个位置能增加的最大血量当前位置能增加的血量)。 记j为左边能到达的位置maxval为从k - 1到j中增加的最大血量left等于a[j]到a[k - 1]的和i为右边到达的当前位置right为a[k]到a[i]的和。 maxval即为从k移动到i的过程中能从左边获取得到的最大的生命值。 结论1如果i - 1能到达maxval所在的位置则i也能到达该位置 只需在i之前先到达该位置即可。 结论2我们只需关注right非减的位置最长非减序列假设这些位置为ps。则maxval只有在属于ps的位置才有可能改变。如果某个位置i不在ps中则能到达i当且仅当right maxval 0且i - 1可达我们只需关注x 1x1不属于ps的情况此时可以从x出发到达maxval所在的位置而到达x1时整体血量减少不可能移动到x能到达的位置的更左端。 结论3y时ps中x的下一个位置则x能到达的位置y也能到达。 因此我们可以双指针进行。i从k开始枚举对每个ij依据条件向左移动同时维护maxval即可。 参考代码
bool f(std::vectorll a, int k) {ll left 0, right 0, maxval 0;for (int i k, j k; i a.size(); i) {right a[i];if (right maxval 0) {return false;}while (j - 1 0 left a[j - 1] right 0) {left a[--j];maxval std::max(maxval, left);}}return true;
}void solve() {int n, k;std::cin n k;std::vectorll a(n);for (int i 0; i n; i) {std::cin a[i];}if (k 1 || k n || f(a, k - 1)) {std::cout Yes\n;return;}std::reverse(a.begin(), a.end());std::cout (f(a, n - k) ? Yes : No) \n;
}
