CodeTON Round 7 (Div. 1 + Div. 2)

cf 题解

题解

发布日期: 2023-11-30

CodeTON Round 7 (Div. 1 + Div. 2)

Dashboard - CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

总结一下，秒了A，然后BC连续WA。然后就做不下去了|，VP还是差点感觉。

A. Jagged Swaps

A

800 —— 思维

题意

给定一个长度为 n 的序列 a。给定操作：从$[2, n-1]$ 中选择一个下标 i ，需要保证选择的数严格大于两边的数字，然后交换$a_i和a_{i+1}$ 。问能否在有限次的操作后使得每一个$a_i=i$ 。

解题思路

可能我就是800高手(❌), 可以看出，只要保证第一个数$a_1=1$ 即可，其他的数可以通过操作实现归位。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10;

int n, m; 
int a[N];

void solve()    
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
    }

    if (a[1] == 1) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

B. AB Flipping

B

900 —— 贪心，字符串

题意

给定一个由 A 和 B 组成的字符串。给定一个操作：选择一个索引 i ，保证 $s_i=A,s_{i+1}=B$ ，然后交换 $s_i$ 和 $s_{i+1}$ 。每个索引只能选择一次。求最多可以操作的次数

解题思路

最开始，我想的是每个B前有多少个A，就是可以操作多少次，没有考虑到每个下标只能操作一次。然后wa2，然后想不出，就去开 c 了。

正解?：找到最左边的A，和最右边的B。然后差值就是最大可操作的次数。证明？不懂怎么证明，贪心不都是靠猜嘛( )

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10;

ll n, m; 

void solve()    
{
    cin >> n;
    string s;
    cin >> s;

    int idx1 = -1, idx2 = -1;
    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] == 'A')
        {
            idx1 = i;
            break;
        }
    }


    for (int i = 0; i < s.size(); i ++ )
    {
        if (s[i] == 'B')
        {
            idx2 = i;
        }
    }    
    //如果全是A或者全是B
    if (idx1 == -1 || idx2 == -1) cout << 0 << endl;
    //注意不能取负值，最小操作次数是0
    else cout << max(idx2 - idx1, 0) << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

C. Matching Arrays

C

1400 —— 贪心，排序

开不出B，那我开C，笑死，C也wa2

题意

给定两个大小为 n 的数组 a 和 b。有一处 $a_i>b_i$ ，就是一个妙处。现在给定一个整数 x ，需要判断通过重新排列 b 中的元素，使得正好有 x 个妙处。如果可能，需要输出一种 b 的有效重排方式。

解题思路

贪心的想，让 b 中最小的 x 个数与 a 中最大的 x 个数去比较；b 中最大的 n-x 个数与 a 中最小的 n-x 个数去比较就可以。

但我犯了一个错误：因为比较需要，a数组也进行了排列，可实际上输出排列后的 b 数组应该对应原来 a 数组的位置，因为a 数组原则上是不能排列的。其实只需要再开一个下标数组根据 a 数组来排列就可以定位到原 a 数组。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 2e5 + 10;

int n, m; 

void solve()    
{
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1), b(n + 1);

    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> b[i];

    //c存储下标，根据a的大小排序
    vector<int> c(n + 1);
    iota(c.begin(), c.end(), 0);
    sort(c.begin(), c.end(), [&](int i, int j){
        return a[i] < a[j];
    });

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    //cnt存储满足条件的对数,f存储排序后(归为前)的新的b序列
    int idx = 1, cnt = 0;
    vector<int> f(n + 1);
    for (int i = x + 1; i <= n; i ++ )
    {
        f[idx] = b[i];
        if (a[idx ++ ] > b[i]) cnt ++ ;
    }

    for (int i = 1; i <= x; i ++ )
    {   
        f[idx] = b[i];
        if (a[idx ++ ] > b[i]) cnt ++ ;
    }

    //归位
    vector<int> g(n + 1);
    for (int i = 1; i <= n; i ++ )
    {
        //根据i找到对应a原来的下标，也就是c的作用
        g[c[i]] = f[i];
    }   

    //如果不能正好满足x个，就是不可以
    if (cnt != x)
    {
        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
    //归为后的序列
    for (int i = 1; i <= n; i ++ )
    {
        cout << g[i] << " ";
    }

    cout << endl;  
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

D. Ones and Twos

D

1700 —— 区间维护？

理所应当？的没有看到连续子区间，然后以为很简单，最终样例都没过

题意

给定一个长度为 n 由 1 和 2 组成的数组 a。查询 q 次，有两种查询：1 s，检查有没有子数组总和等于 s；2 i v，将 $a_i$ 的值改为 v。

解题思路

发现是要求连续子区间后，就无从下手了。可实际上并不难 111111。

状态只有四种：

$[1…1]$
[1…2]
[2…1]
[2…2]

假定现在和为 sum，那么我们一定可以得到 sum - 2 的值，也就是只要现在的和 sum 和查询的和 s 的差值为偶数，那么一定存在。如果是奇数，我们只需要删掉一个 1，就可以得到第一种状态。所以我们需要维护的就是头部的第一个 1 的位置，和尾部的第一个 1 的位置就可以。因为 1 之前的数都是 2，所以我们可以知道去掉的值是多少 (感觉这一步比较关键，写的时候也都想到了，但没有想到第一个 1 之前全是 2，所以没想通如何维护) 。

采用 set 来维护

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e5 + 10;

int n, m; 
int a[N];

void solve()    
{
    cin >> n >> m;

    //st维护1出现的下标
    set<int> st;
    int sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if (a[i] == 1) st.insert(i);
        sum += a[i];
    }

    while (m -- )
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int s;
            cin >> s;
            if (sum == s) cout << "YES" << endl;
            else if (sum < s) cout << "NO" << endl;
            //sum > s的一般情况：
            else
            {
                //z为差值
                int z = sum - s;
                //如果差值为偶数，那么一定存在
                if (!(z&1)) cout << "YES" << endl;
                else if (!st.empty())
                {
                    //删掉头尾1区间的元素，因为1头尾的1之前全是2，所以我们可以找到删除的值
                    if (z >= (min(*st.begin() - 1, n - *st.rbegin()) << 1) + 1) cout << "YES" << endl;
                    else cout << "NO" << endl;
                }
                else cout << "NO" << endl;
            }
        }
        else
        {
            //更新维护st和sum
            int idx, v;
            cin >> idx >> v;
            if (a[idx] == 1) st.erase(idx);
            sum -= a[idx];
            a[idx] = v;
            sum += a[idx];
            if (a[idx] == 1) st.insert(idx);
        }
    }
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

E. Permutation Sorting

E

2100 —— 数据结构，树状数组

Problem - E - Codeforces

扔一个题目链接。总的来说用树状数组维护单点修改和实现区间查询。没学过树状数组，然后看了很久。大概明白了题解的含义，可也只是大概了。等之后学了再来补档。写了3天，vp了三场，学到了很多，也充分了解到自己的不足。刷题的同时，还是不能扔下学习了。没有基础的奠定，~~不能上分~~，向下补题会很难。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10;

int n, m;
int a[N], ans[N], c[N << 1];

void add(int x, int k)
{
    for (; x <= n << 1; x += x & -x) c[x] += k;
} 

int ask(int x)
{
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
}

//利用树状数组维护单点修改和实现区间查询
//将数组拆环。
void solve()    
{
    cin >> n;
    memset(c, 0, sizeof(int) * n << 1);
    vector<PII> e;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if (i <= a[i]) 
        {
            e.pb({i, a[i]});
            e.pb({i + n, a[i] + n});
        }  
        else e.pb({i, a[i] + n});
    }

    sort(e.begin(), e.end(), greater<PII>());

    for (auto [l,r] : e)
    {
        if (l <= n) ans[a[l]] = r - l - ask(r) + ask(l - 1);
        add(r, 1);
    }

    for (int i = 1; i <= n; i ++ ) cout << ans[i] << " ";
    cout << endl;
}

int main()  
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin >> t; while (t -- )
    solve();

    return 0;
}

han yue

https://ich-liebe.github.io/2023/11/30/CF_CodeTON_Round_7_Div1+Div2/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 han yue !

cf 题解

Stream流

javase_Stream流

2023-12-01 javase

javase

2023牛客寒假基础集训营2

牛客寒假算法基础集训营2题解

2023-11-29 题解

题解 2023牛客寒假

CodeTON Round 7 (Div. 1 + Div. 2)

A

题意

解题思路

代码

B

题意

解题思路

代码

C

题意

解题思路

代码

D

题意

解题思路

代码

E

代码

你的赏识是我前进的动力