[数据结构与算法]Codeforces Global Round 20记录

自闭的构造场。一周不练，该场VP回到解放前qwq。

C-Unequal Array（GOOD）

思路

• 最优解的性质：选取的区间一定连续。否则产生2个满足$equatility$条件的一对数
• 剔除与问题无关的区间。至少要消灭原数组多余的equatity对
  • 方法是作用于第一个满足$a_i=a_{i+1}$的i和最后一个满足$a_j=a_{j+1}$的j组成的区间[i+1,j]。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
    int t;
    cin >> t;
    for(int i = 0;i<t;i++)
    {
        int n;
        cin >> n;
        int a[n];
        for(int k = 0;k<n;k++) cin >> a[k];
        int firstid = INT_MAX;
        int lastid = -1;
        for(int k = 0;k<n-1;k++)
        {
            if(a[k] == a[k + 1])
            {
                firstid = min(firstid,k);
                lastid =  max(lastid,k);
            }
        }
        if(lastid == -1 || firstid == lastid) cout << 0 << endl;
        else if(lastid == firstid + 1) cout << 1 << endl;
        else cout << lastid - firstid - 1 << endl;
    }
    system("pause");
    return 0;
}

D题-Cyclic Rotation

思路

• 考察由a生成b的过程，判断匹配：不断将a中与末尾相同的元素移动到末尾。故b中最后一块相等元素块从左往右第一个元素就能和a的最后一个元素匹配。对a的倒数第二个元素，同理。一直到最前（没有考虑倒数第二个及之前的qwq）
• 利用双指针。从后向前匹配b和a。b中多余的项目计入multiset中。
• 学习multiset的删除：利用迭代器删除，只删除一个。直接erase，全部删除。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
    int t;
    cin >> t;
    for(int i = 0;i<t;i++)
    {
        int n;
        cin >> n;
        int a[n],b[n];
        for(int k = 0;k<n;k++) cin >> a[k];
        for(int k = 0;k<n;k++) cin >> b[k];
        multiset<int> s;
        int p = n - 1,q = n - 1;
        bool flag = true;
        while(p >= 0 && q>=0)
        {
            int curb = b[p];
            while(p - 1 >= 0 && b[p - 1] == curb) 
            {
                s.insert(curb);
                p--;
            }
            if(b[p] == a[q]) {p--;q--;}
            else
            {
                multiset<int>::iterator iter = s.find(a[q]);
                if(iter!=s.end())
                {
                    q--;
                    s.erase(iter);
                }
                else
                {
                    flag = false;
                    break;
                }
            }
        }
        if(!flag)
        {
            cout << "NO" << endl;
        }
        else
        {
            while(q >=0)
            {
                multiset<int>::iterator iter = s.find(a[q]);
                if(iter!=s.end())
                {
                    s.erase(iter);
                }
                else
                {
                    flag = false;
                    break;
                }
                q--;
            }
            if(!flag) cout << "NO" << endl;
            else cout << "YES" << endl; 
        }
    }
    system("pause");
    return 0;
}

E-notepad.exe（交互题）-搜索空间的减少很GOOD

思路

• n种可能的高度。1-n。
  • 如果在每种高度搜索最小width query数量不可接受。
• 特殊条件入手：每个单词都摆在一行，之间仅有一个空格。且最后无尾随空格。可以采用二分查找搜索出这个最小width,设为S。
• 关键一步：对给定的高度H，下界是$S?(H?1)$（空格最多减少H-1个，且每行无尾随空格）（减小搜索空间）.因此对每个高度，最优解的搜索空间为$[S?H+1,S]$.
  • 最优解取值必须是H的倍数。而在[S-H+1,S]中仅有$?S/H??H$满足条件。
  • 因此对每个高度H，查询$width=?S/H?$，如果查询结果等于H，则更新答案。
• 总结：本题关键在于求出当H=1,摆放所有单词需要的最小width;其他高度的搜索空间不能超过这个最小width。以及这些其他高度最多能使得这个最小width还能减少的面积（每一行末尾至多能少一个空格）。从而减少对于每个高度的搜索空间。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
    int n;
    cin >> n;
    int l  =1,r = n * 2000  + 1 + n;
    while(l < r)
    {
        int m = (l + r) >> 1;
        cout << "?" << " " << m << endl;
        cout.flush();
        int h_w; cin >> h_w;
        if(h_w != 1) l = m + 1;
        else r = m;
    }
    int a = l;
    for(int H = 2;H<=n;H++)  //对每个高度搜索最优解
    {
        cout << "?" << " " << l/H << endl;
        cout.flush();
        int h_w; cin >> h_w;
        if(h_w == H) a = min(a,h_w * (l / H)); 
    }
    cout << "!" << " " << a << endl;
    system("pause");
    return 0;
}

F1题- Array Shuffling（GOOD）-复习置换的知识(very good)

思路()

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> cnt[200001];

int main()
{
    int t;
    cin >> t;
    for(int i = 0;i<t;i++)
    {
        int n;
        cin >> n;
        int max = -1;
        int maxnum = -1;
        int d[n];
        set<int> c;
        for(int k = 0;k<n;k++) {
            int a;cin >> a;cnt[a].push_back(k);d[k]=a;
            if((int)cnt[a].size() > max) 
            {max = cnt[a].size();maxnum = a;}
            c.insert(a);
        }
        vector<int> group[max];
        int cur  =  0;
        for(int k : c)
        {
            while(cnt[k].size() > 0)
            {
                group[cur].push_back(cnt[k][cnt[k].size() - 1]);
                cnt[k].pop_back();
                cur = (cur + 1) % max;
            }   
        }
        //交换数组d
        for(int k = 0;k<max;k++)
        {
            for(int q = 0;q<group[k].size() - 1;q++)
            {
                swap(d[group[k][q]],d[group[k][q+1]]);
            }
        }
        for(int k = 0;k<n-1;k++) cout << d[k] << " ";
        cout << d[n-1]<<endl;
    }
    system("pause");
    return 0;
}

F2-Checker for Array Shuffling$VeryGOOD$

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖