【Codeforces】好题详解第一期 1400分构造（附详细代码）

用户11952558

发布于 2026-01-09 14:07:04

1860

前言

1400分即为一个分水岭，相关题目需要思维与较强代码能力，我本人也是困在这个分水岭一段时间了，并且相关题解对于新手来说很不友好，可能会用到c++17，甚至20语法，并且个人特色非常鲜明。而我都会用简洁，大家都能听懂的语言，并配上图片讲解，代码也只用C++98的语法，尽量让大家都能听懂。

此系列尽量每星期一更，希望能帮到大家

题目为我一星期做到三四十道题精心挑选的7道，都值得一做

题目

Problem 1909C - Heavy Intervals
Problem 1923C - Find B
Problem 1901C - Add, Divide and Floor
Problem 1864C - Divisor Chain
Problem 1837D - Bracket Coloring
Problem 1790E - Vlad and a Pair of Numbers
Problem 2171D - Permutation Connection

1. Problem - 1909C - Heavy Intervals

Pinely round 3 div2 C 思维量：4星代码难度：2星

前置知识

栈的使用

题目大意

n个区间，与n个val，可以打乱顺序左端点，右端点，val顺序，使得最后一一对应的乘积和最小

模型抽象

我们先举例几个特殊情况

当空间之间有重叠区间: [1,4], [2,5] 通过"剥洋葱"方式，内层区间配小权值，外层区间配大权值：最内层[2,4] → 小权值中间层[1,5] → 大权值此时，空间转化为下面，并且小区间对小值，大区间对大值，可使和最小

空间无重叠此时，就直接小区间对小值，大区间对大值即可

因此，可以得出结论：先排序所有左端点，右端点，val值，再如果区间之间有重叠，就如图剥洋葱即可，并记录区间长度

不重叠，就直接记录区间长度最后，再小区间对小值，大区间对大值

题目解决

当模型出来后，如果你学过栈，并且写过括号的匹配的问题，就可以抽象成左端点为左括号，右端点为右括号，再括号匹配，就直接成了模板题

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);

int val[100010];
struct node
{
    int n;
    int fl;//左0右1
}num[200010];
int dist[100010];
int pos;
bool cmp(node&x, node&y)
{
    return x.n < y.n;
}
bool cmp2(int x, int y)
{
    return x > y;
}
void solve()
{
    int n; cin >> n;
    pos = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i].n;
        num[i].fl = 0;
    }
    for (int i = n+1; i <= 2*n; i++)
    {
        cin >> num[i].n;
        num[i].fl = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
    }
    sort(num + 1, num + 1 + 2 * n,cmp);
    sort(val + 1, val + 1 + n, cmp2);
    stack<node> st;
    for (int i = 1; i <= 2*n; i++)
    {
        if (num[i].fl == 0)st.push(num[i]);
        else
        {
            node a = st.top();
            st.pop();
            dist[++pos] = -a.n + num[i].n;
        }
    }
    sort(dist + 1, dist + 1 + pos);
    int ret = 0;
    for (int i = 1; i <= pos; i++)
    {
        ret += val[i] * dist[i];
    }
    cout << ret << endl;
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

2. Problem - 1923C - Find B

Educational round 162 C 思维量：4星代码难度：2星

前置知识

前缀和

题目大意

给定数列（不为0），和多个区间查询，对每个区间判断：能否在保持总和不变的前提下，构造出对应元素不相等的新区间

如{2，4，1}区间可构造{1，3，3}，2和1不同，4和3不同，1和3不同

题目用例解析

数列：1 2 1 4 5 查询1：[1,5],构造[2,1,2,3,6] 查询2：[4,4]，不行，一个数没法相等查询3：[3,4]，可以，[2,3] 查询4：[1,3]，不可以，因为和为4，而4分成3个数必定有2个1，肯定会撞车

模型抽象

先举特例

所有元素为1，铁定不行
一个数，也不行

由题目用例解析可得，我们是要快速算出区间元素之和的，因此先要一个前缀和数组

此外，我们感到1是敌人，越少越好

我们再举个例子 {6，1，1，1}这个区间，可以吗我们试一下，可以构造成{0，2，2，2}，但是题目规定不能为0 但是{7，1，1，1}就能构造成{1，2，2，2}，为最极限情况

因此，我们得出结论，和要保底能先让所有位置取到1，如果该位置原本是1，那么就要取2（这也印证了我们1是敌人这个推测）

题目解决

首先，我们就可以总结成公式区间和 >= 位置数 + 1的个数

因此，我们就要模仿前缀和，快速查询区间的1的个数 cnt1[i] = cnt1[i - 1] + (num[i] == 1 ? 1 : 0);

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
int num[300010];
int f[300010];
int cnt1[300010];
void solve()
{
    int n; int q; cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] + num[i];
        cnt1[i] = cnt1[i - 1] + (num[i] == 1 ? 1 : 0);
    }
    while (q--)
    {
        int l; int r; cin >> l >> r;
        if (l == r)
        {
            cout << "NO" << endl;
            continue;
        }
        int sum = f[r] - f[l - 1];
        int sum1 = cnt1[r] - cnt1[l - 1];
        int val = r - l + 1;
        if (sum >= sum1 + val)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

3. Problem - 1901C - Add, Divide and Floor

Education round 158 div2 C 思维量：3星代码难度：2星

前置知识

无

题目大意

数组a，每次任选一个数x，所有数做[(a[i]+x)/2](向下取整)，多少次可使所有数字相同

题目用例解析

{2，1，2，1，2}，选x=1，得到{1，1，1，1，1}

由于其它题目用例迷惑性较强，因此不做解析

模型抽象

首先，我们的目的是让所有点聚集，因此只用考虑最大，最小的点能相同，其他点必定相同

两个点离得较远时，我们x点无论在哪都是可以将它们的距离变为1/2

但有边界情况要考虑比如{5，6}这两个点，选0时变成{2，3}，选1，变成{3，3}。选奇数可以立马相等，但选偶数就会浪费一次但{6，7}选0时可以立马相等，选1，变成{3，4}。因此选偶数

因此，小数为奇选奇，为偶选偶

题目解决

干脆这样就选0，1得了，以不变应万变

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;
int r[200010];
int pos;
void solve()
{
    int n; cin >> n;
    int M = 0; int m = 1e9 + 10;
    pos = 0;
    for (int i = 1; i <= n; i++)
    {
        int s;
        cin >> s;
        M = max(M, s);
        m = min(m, s);
    }
    while (M != m)
    {
        int x = 0;
        int cha = M - m;
        if (m % 2 == 0)x = 0;
        else x = 1;
        M = (M + x) / 2;
        m = (m + x) / 2;
        r[++pos] = x;
       
    }
    if (n == 1)
    {
        cout << 0 << endl;
    }
    else if (pos <= n)
    {
        cout << pos << endl;
        for (int i = 1; i <= pos; i++)
        {
            cout << r[i] << " ";
        }
        cout << endl;
    }
    else
    {
        cout << pos << endl;
    }
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

4. Problem - 1864C - Divisor Chain

Harbour space scholarship contest 2023~2024 C 思维量：3星代码难度：4星

题目大意

数n，减去因数变成新值，再减去新值的因数，最后变为1，每个数只能减去2次以内

如3->2(3有因数1)->1(2有因数1)

前置知识

逻辑运算

用例解析

5 > 4 > 2 > 1

模型抽象

从5这个用例可以发现一条可行路径：奇数 -> 偶数 -> 2^k -> 1

并且，由于n为10的9次方，结果却是1000个以内，只可能用log才能缩小到这个数量级

奇数 -> 偶数可以减去一个1，那么偶数 -> 2^k可以怎么做？

再举个例子，98如何变为64？98 -> 66(减32) -> 64(减去2)

此外，由于每个数用2次，从2^k减到1会都用一次，那么剩下一次呢？就是再偶数 -> 2^k用了

因此，我们考虑将数字转为2进制 1100010（98）-> 1000010(66) -> 1000000(64)是不是明了了呢

因此，先将数字非最高位的1消掉，再2^k不断减到1

模型解决

首先，介绍一个求二进制位数的模板

int weishu(int s)
{
    int ret = 0;
    while (s)
    {
        ret++;
        s >>= 1;
    }
    return ret;
}

n&(1<<pos)的bool类型就能判断出第pos位是否为1，为1就减去

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;
int num[1010];
int pos1;
int weishu(int s)
{
    int ret = 0;
    while (s)
    {
        ret++;
        s >>= 1;
    }
    return ret;
}
void solve()
{
    int n; cin >> n;
    pos1 = 0;
    num[++pos1] = n;
    int cnt = weishu(n);
    int pos = 0;
    while (n != ((ll)1 << (cnt-1)))//将n减到2的倍数
    {
        if (n & ((ll)1 << pos))
        {
            n -= ((ll)1 << pos);
            num[++pos1] = n;
        }
        pos++;
    }
    while (n != 1)
    {
        n /= 2;
        num[++pos1] = n;
    }
    cout << pos1 << endl;
    for (int i = 1; i <= pos1; i++)
    {
        cout << num[i] << " ";
    }
    cout << endl;
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

5. Problem - 1837D - Bracket Coloring

Educational round 149 D 思维量：3星代码难度：3星

前置知识

栈

题目大意

美丽括号包括合法的括号与所有括号翻一下就合法的括号，如何分组让括号串全为美丽括号？如：（（））（），））（（）（都为美丽括号（第一组本身合法，第二组反转合法）

用例分析

((())))(：前6个本身合法，最后两个反转合法因此11111122（前6个为组1，后2个为组2）

模型抽象

首先，左括号和右括号需要个数相等，否则无法分配，不等直接-1

只要左括号和右括号个数相等，我们就能通过分组，使其匹配，无非是分组多少的问题

那么，要几组呢？

如）（）（（）））（（）（）（首先，我们先将本身合法的括号抽出，就变成了））（（，此时可以所有括号反转，变合法

因此，推测最多只用分两组就可以以不变应万变（以不变构造应万变也是cf构造题的经常性的套路）

因此，我们先用栈找出所有本来就合法的队列，用一个used数组标记，剔除，分为一组，剩下的就是要反转的的一组了

模型解决

注意，这题有个细节：若只能分一组，就先特判并输出

用两个栈分别遍历分组即可

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;
int ret[200010];
int pos;
int used[200010];
void solve()
{
    int n; cin >> n;
    int flag = 0;
    string kuo; cin >> kuo;
    kuo = " " + kuo;
    for (int i = 0; i <= n+3; i++)
    {
        ret[i] = 0;
        used[i] = 0;
    }
    stack<int> st4;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (used[i])continue;
        if (kuo[i] == ')')st4.push(i);
        else
        {
            if (st4.empty())continue;
            int s = st4.top();
            st4.pop();
            cnt += 2;
        }
    }
    if (cnt == n)
    {
        cout << 1 << endl;
        for (int i = 1; i <= n; i++)
        {
            cout << 1 << " ";
        }
        cout << endl;
        return;
    }
    stack<int> st;
    int l = 0; int r = 0;
    for (int i = 1; i <= n; i++)
    {
        if (kuo[i] == '(')l++;
        else r++;
    }
    if (l != r)
    {
        cout << -1 << endl;
        return;
    }
    stack<int> st2;
    for (int i = 1; i <= n; i++)
    {
        if (i == 8)
        {
            int sss = 1;
        }
        if (kuo[i] == '(')st2.push(i);
        else
        {
            if (st2.empty())continue;
            int s = st2.top();
            st2.pop();
            used[i] = used[s] = 1;
            flag = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (used[i])continue;
        if (kuo[i] == ')')st.push(i);
        else
        {
            if (st.empty())continue;
            int s = st.top();
            st.pop();
            if (flag == 1)used[i] = used[s] = 2;
            else used[i] = used[s] = 1;
        }
    }
    int c1 = 0; int c2 = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (used[i] == 1)c1 = 1;
        if (used[i] == 2)c2 = 1;
    }
    cout << c1 + c2 << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << used[i] << " ";
    }
    cout << endl;
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

6. Problem - 1790E - Vlad and a Pair of Numbers

Round 847 div3 E 思维量：4星代码难度：4星

前置知识

按位逻辑运算

题目大意

x，y两个数平均数 = 异或数 = x，求x，y

题目用例分析（都用二进制写）

输入：2输出：3 1 首先x，y的和为100，异或为10

首先，最高位异或为0，和为1，因此最高位为0，0，需要前一位进位倒数第二为和为0，异或为1，前面需要进位，因此 x，y这一位为1，0，需要进位第一位和0，异或为0，前面需要进位，因此分别为1，1

模型抽象

X，y和sum为2*n（n为偶）/2*n+1（n为奇），异或为n

我们从最高位开始填数

当sum，n的第pos位排列组合有4种方式

sum为1，n为0：x为0，y为0，需要前面进位/会进位，x为1，y为1，需要前面进位
Sum为0，n为0：x为0，y为0/会进位x为1，y为1
sum为0，和为1：进位，x为1，y为0，需要前面进位
sum为1，和为1：进位，x为1，y为0

我们就是要严格再这里面选方案，凑出结果，否则就是不行

问题解决

因此，我们弄一个need变量，去处理进位，当上一位需要进位，need就赋为1，如果这一位有进位的情况，就没问题，否则就是不行

此外，对于一个数加，一个数不加的情况，我们两个数雨露均沾一下

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;
int shuwei(int s)
{
    int ret = 0;
    while (s)
    {
        s >>= 1;
        ret++;
    }
    return ret;
}
void solve()
{
    int n; cin >> n;
    int sum = 0;
    if (n % 2 == 1)sum = 2 * n + 1;
    else sum = 2 * n;
    int pos = shuwei(sum);
    int xr = sum / 2;
    pos-=2;
    int r1=0; int r2=0;
    //r1 += (1LL << (pos + 1));
    int need = 1;//需要进位
    int flag = 0;
    while (pos >= 0)
    {
        if (sum & (1LL << pos) && (xr & (1LL << pos)))
        {
            if (need)
            {
                cout << "-1" << endl;
                return;
            }
            if (flag == 0)
            {
                r1 += (1LL << pos);
            }
            else
            {
                r2 += (1LL << pos);
            }
            flag = 1 - flag;
            need = 0;
        }
        else if ((!(sum & (1LL << pos))) && (xr & (1LL << pos)))
        {
            if (need == 0)
            {
                cout << -1 << endl;
                return;
            }
            if (flag == 0)
            {
                r1 += (1LL << pos);
            }
            else
            {
                r2 += (1LL << pos);
            }
            flag = 1 - flag;
        }
        else if (sum & (1LL << pos) && (!(xr & (1LL << pos))))
        {
            if (need == 1)
            {
                r1 += (1LL << pos);
                r2 += (1LL << pos);
            }
            need = 1;
        }
        else
        {
            if (need == 1)
            {
                r1 += (1LL << pos);
                r2 += (1LL << pos);
            }
            need = 0;
        }
        pos--;
    }
    if (r1 == 0 || r2 == 0)
    {
        cout << -1 << endl;
        return;
    }
    cout << r1 << " " << r2 << endl;
}
signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

7. Problem - 2171D - Permutation Connection

思维量：4星代码难度：2星

Round 1065 div3 D

Rae Taylor and Trees (easy version)

前置知识

前后缀，归并（有助于理解）

题目大意

一个排列（1到n单独出现的数组），前小后大的数可以连在一起，是否连n-1次能将所有数连在一起？（即构成一棵树）

题目用例讲解

2 4 6 1 3 5

首先，1能与任何元素连接，因此1，3 1，5能连一条线现在，1，3，5为一个块我们再连2，4 6，4，将前面连为一个块最后，将4，5连接，即把两个块连接，即所有数连接

模型抽象

这个用例中，我们将几个块连接，那么可以将块连接的条件是什么呢

回顾块1：2，4，6 块2：1，3，5 由于4小于5，因此能用4，5相连将块连在一起

因此，条件就是：前面块的最小数小于后面块的最大数

当我们遍历到一个数时，那就说明前面的数都可以有连接前后块的接口

假设所有数的前后都能有接口连接，那么将这些接口相连，就是最终可以的答案

可参考归并排序

题目解决

因此题目抽象成：遍历数组2次，弄出premin,sufmax两个数组，存放前缀最小值，和后缀最大值，当所有premin[i] < sufmax[i],就行，否则不行

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;

int num[200010];
int premin[200010];
int sufmax[200010];
void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    for (int i = 0; i <= n + 3; i++)
    {
        premin[i] = sufmax[i] = 0;
    }
    premin[1] = num[1];
    for (int i = 2; i <= n; i++)
    {
        premin[i] = min(premin[i - 1], num[i]);
    }
    for (int i = n; i >= 1; i--)
    {
        sufmax[i] = max(sufmax[i + 1], num[i]);
    }
    int flag = 1;
    for (int i = 1; i <= n; i++)
    {
        if (premin[i - 1] > sufmax[i])
        {
            flag = 0;
            break;
        }
    }
    if (flag == 1)
    {
        cout << "YES" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
}

总结

这七道题目涵盖了栈、前缀和、位运算、贪心、构造等多种算法技巧，都是很好的思维训练题。

保持思考，持续刷题！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-07，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度