今晚 CF A-D 题解
2026-02-27 01:07:25
发布于：广东
38阅读
0回复
0点赞
打破纪录！37min 切 ABCD！
4 题用时：2min, 2min, 18min, 15min
A
Difficulty：3- / Easy
Tag：-
显然，交换 与值为 的即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::swap(a[1], a[std::max_element(a.begin() + 1, a.begin() + n + 1) - a.begin()]);
for(int i = 1; i <= n; i++){
std::cout << a[i] << ' ';
}
std::cout << '\n';
}
}
时间复杂度：。
B
Difficulty：3- / Easy
考虑分解质因子。注意到 ，则 的质因子得包含在 的质因子内。
由于 的每个质因子指数一定不超过 ，所以 的指数取 即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
int ans = 1;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
ans *= i;
while(n % i == 0) n /= i;
}
}
ans *= n;
std::cout << ans << '\n';
}
}
时间复杂度：。
C
Difficulty：3.4 / Easy
Tag：-
首先它是往开头加的，太难受了，反转一下当成加在末尾。
由于字典序，前面的数享有最高权力，可以随便诬蔑后面的数，所以直接每次选字典序最小的即可。
选完以后记得删除后面重复的数。
namespace cjdst{
const int N = 1000000;
bool vis[N + 5];
void solve(){
int n;
std::cin >> n;
std::vector <std::vector <int>> a(n + 5);
for(int i = 1; i <= n; i++){
int len;
std::cin >> len;
std::vector <int> tmp;
for(int j = 1; j <= len; j++){
int val;
std::cin >> val;
tmp.push_back(val);
}
std::reverse(tmp.begin(), tmp.end());
for(int j:tmp){
if(vis[j]) continue;
vis[j] = 1, a[i].push_back(j);
}
for(int j:tmp){
vis[j] = 0;
}
}
for(int i = 1; i <= n; i++){
int cur = std::min_element(a.begin() + 1, a.begin() + n + 1) - a.begin();
for(int j:a[cur]){
std::cout << j << ' ';
vis[j] = 1;
}
for(int j = 1; j <= n; j++){
if(j != cur){
std::vector <int> tmp;
for(int k:a[j]){
if(vis[k]) continue;
tmp.push_back(k);
}
a[j] = tmp;
}
}
for(int j:a[cur]){
vis[j] = 0;
}
a[cur] = {1000001};
}
std::cout << '\n';
}
}
时间复杂度：。
D
Difficulty：3.6 / Easy
Tag：单调栈
首先想怎么删。
显然每次操作都要把中间最大值尽量往两边移动，最终把整个搞成一个谷状。
我们可以单调栈求出每个点最左边和最右边能搞成谷的最长的长度，求最大值即可。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5);
for(int i = 1; i <= n; i++){
std::cin >> a[i];
}
std::vector <int> left(n + 5), right(n + 5);
std::stack <int> s1, s2;
for(int i = 1; i <= n; i++){
while(!s1.empty() && a[s1.top()] < a[i]) s1.pop();
left[i] = s1.size();
s1.push(i);
}
for(int i = n; i; i--){
while(!s2.empty() && a[s2.top()] < a[i]) s2.pop();
right[i] = s2.size();
s2.push(i);
}
int ans = 0;
for(int i = 1; i <= n; i++){
ans = std::max(ans, left[i] + right[i] + 1);
}
std::cout << n - ans << '\n';
}
}
时间复杂度：。
有帮助，赞一个