首页 💻 数据结构,📝 算法学习

解题情况:
solved:(5 / 7)
涉及知识点:
A题:数学
B题:贪心
C题:暴力
D题:思维
E题:数据结构(优先队列)
F题:找规律
G题:枚举


Problem A: Strange Table

题目传送门: https://codeforces.ml/contest/1506/problem/A

解题思路:

首先把按行编号的坐标(位置)找到,然后进行列编号即可。

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, x, l, r;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n >> m >> x;
        l = x / n;
        r = x % n;
        if(x % n == 0) r = n;
        else l++;
        cout << (r - 1) * m + l << endl;
    }

    return 0;
}

Problem B: Partial Replacement

题目传送门: https://codeforces.ml/contest/1506/problem/B

解题思路:

首先找到第一个和最后一个*的位置,从第一个*开始,把它变成$x$,然后尽可能找到最靠右的满足距离不超过$k$的*,然后把它也变成$x$,直到它到最后一个的距离也不超过$k$为止。
找最后一个距离它不超过$k$的*我们可以用类似并查集的方式记录下每个*右边第一个*的位置,然后通过while循环找到。

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, k, x, y;
string s;
ll b[105];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        memset(b, -1, sizeof(b));
        ll h, o, cnt = 0, ans = 2;
        cin >> n >> k >> s;
        for(ll i = 0; i < s.size(); i++){
            if(s[i] == '*') s[i] = 'x', cnt++;
        }
        if(cnt == 1 || cnt == 2){cout << cnt << endl; continue;}
        for(ll i = 0; i < s.size(); i++){
            if(s[i] == 'x'){x = i; break;}
        }
        for(ll i = s.size() - 1; i >= 0; i--){
            if(s[i] == 'x'){y = i; break;}
        }
        h = y;
        for(ll i = y - 1; i >= x; i--){
            if(s[i] == 'x') b[i] = h, h = i;
        }
        h = 0, o = x;
        for(ll i = x; i < y; i++){
            while(b[o] != -1 && b[o] - i <= k){
                o = b[o];
            }
            if(b[o] != -1){
                i = o - 1;
                ans++;
            }
            else if(b[o] == -1) break;
        }
        cout << ans << endl;
    }

    return 0;
}

Problem C: Double-ended Strings

题目传送门: https://codeforces.ml/contest/1506/problem/C

解题思路:

题目等价于对于两个子串分别找到一个最长的子串使得他们相等,暴力枚举子串长度,起点,暴力判断相等。

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1, s2;
ll t, ans, op;
bool flag;

bool judge(ll x, ll y, ll len){
    if(len == 0) return true;
    string k1 = "", k2 = "";
    for(ll i = x; i < x + len; i++) k1 += s1[i];
    for(ll i = y; i < y + len; i++) k2 += s2[i];
    return k1 == k2;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> s1 >> s2; flag = false; op = 0, ans = 0;
        ll s = min(s1.size(), s2.size());
        for(ll len = s; len >= 0; len--){ // 枚举长度
            for(ll i = 0; i + len - 1 < s1.size(); i++){ // 枚举s1起点
                for(ll j = 0; j + len - 1 < s2.size(); j++){ // 枚举s2起点
                    if(judge(i, j, len)){
                        op = len; flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
        }
        ans = s1.size() - op + s2.size() - op;
        cout << ans << endl;
    }

    return 0;
}

Problem D: Epic Transformation

题目传送门: https://codeforces.ml/contest/1506/problem/D

解题思路:

思维题,如果一个数出现次数超过$n$/2个则答案是超过的部分*2,统计答案注意判断下奇偶数。
(PS:这题会卡unordered_map,呜呜呜)

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
ll t, n, k, a[maxn];
map<ll, ll> mp;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n; mp.clear(); k = 0;
        for(ll i = 1; i <= n; i++) cin >> a[i], mp[a[i]]++;
        for(auto it : mp){
            if(it.second > ll(n / 2)){
                k = it.second - ll(n / 2);
                break;
            }
        }
        if(k == 0 && n % 2 == 0) cout << 0 << endl;
        else if(k == 0 && n % 2 != 0) cout << 1 << endl;
        else if(n & 1) cout << k * 2 - 1 << endl;
        else if(n % 2 == 0) cout << k * 2 << endl;
    }

    return 0;
}

Problem E: Restoring the Permutation

题目传送门: https://codeforces.ml/contest/1506/problem/E

解题思路:

当a[i]!=a[i-1]时,p[i]=a[i];
当a[i]==a[i-1]时,如果找字典序最小的,就用升序优先队列维护下比a[i]小并没出现过的最小的数;如果找字典序最大的,就用降序优先队列维护下比a[i]小并没出现过的最大的数。

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
ll t, n, a[maxn];
priority_queue<ll> q1;
priority_queue<ll, vector<ll>,greater<ll> > q2;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n; ll x = 0;
        while(!q1.empty()) q1.pop();
        while(!q2.empty()) q2.pop();
        for(ll i = 1; i <= n; i++) cin >> a[i];
        for(ll i = 1; i <= n; i++){
            if(a[i] != a[i - 1]){
                cout << a[i] << " ";
                for(ll j = x + 1; j < a[i]; j++) q2.push(j);
                x = a[i];
            }
            else{
                cout << q2.top() << " ";
                q2.pop();
            }
        }
        cout << endl; x = 0;
        for(ll i = 1; i <= n; i++){
            if(a[i] != a[i - 1]){
                cout << a[i] << " ";
                for(ll j = x + 1; j < a[i]; j++) q1.push(j);
                x = a[i];
            }
            else{
                cout << q1.top() << " ";
                q1.pop();
            }
        }
        cout << endl;
    }
 
    return 0;
}

(PS: 下面两题借鉴了滑稽聚聚的题解)

Problem F: Triangular Paths

题目传送门: https://codeforces.ml/contest/1506/problem/F

解题思路:

数据保证有解的话我们假设某个点坐标为$(x,y)$,从上往下走$x$必然是递增的,由于两条边要么是$(x+1,y)$不变,要么是$(x+1,y+1)$,所以$y$的增幅必然小于等于$x$的增幅
可以发现在$x−y$为奇数时可以一直往右下方向走,为偶数时想往右下方向走就需要修改路径上每一条边,如果想往下走需要打通一些向下的通。

代码如下:
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
const ll maxn = 2e5 + 5;
ll t, n, res; PII e[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> n; res = 0;
        for(ll i = 1; i <= n; i ++) cin >> e[i].x;
        for(ll i = 1; i <= n; i ++) cin >> e[i].y;
        e[0].x = e[0].y = 1;
        sort(e + 1, e + n + 1);
        for(ll i = 1; i <= n; i ++){
            ll dx = e[i].x - e[i - 1].x, dy = e[i].y - e[i - 1].y;
            ll t = dx - dy;
            if(!t){
                if((e[i].x - e[i].y) % 2 == 0)  res += dx;
            }
            else{
                if((e[i - 1].x - e[i - 1].y) % 2)  res += t + 1 >> 1;
                else  res += t >> 1;
            }
        }
        cout << res << endl;
    }

    return 0;
}

Problem G: Maximize the Remaining String

题目传送门: https://codeforces.ml/contest/1506/problem/G

解题思路:

最后留下的字符串长度一定不超过26,可以从前往后枚举留下的字符串的第几个字符应该可以填的最大的字母,要保证填上这个字母之后,后面依然有数量足够的字母可以填。

代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll t, n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> s;
        n = s.size();
        vector<vector<ll>> pos(26);
        set<ll, greater<>> ch;
        for (ll i = 0; i < n; i++) {
            pos[s[i] - 'a'].push_back(i);
            ch.insert(s[i] - 'a');
        }
        vector<ll> ptr(26);
        string ans;
        while (!ch.empty()) {
            for (ll i : ch) {
                bool can_take = true;
                for (ll j : ch) {
                    can_take &= pos[j].back() >= pos[i][ptr[i]];
                }
                if (can_take) {
                    ch.erase(i);
                    for (ll j : ch) {
                        while (pos[j][ptr[j]] <= pos[i][ptr[i]]) {
                            ptr[j] += 1;
                        }
                    }
                    ans += 'a' + i;
                    break;
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}



文章评论

    wangbingbing 访客ChromeWindows
    2021-03-27 17:31   回复

    针不戳