背景

重感冒,所以迟发了www

A题:Turtle and Good Strings

思路

如果字符串的开头不等于末尾,那么就可以截取n-1个作为s1,剩下1个作为s2,这样是符合题意的。反之,如果相等,那么无论怎么取都无法满足题意。这是一个对立条件,故可以直接拿来进行判断

代码

inline void solve() {
     int n; cin >> n;
     string s; cin >> s;
     s = ' ' + s;
     cout << (s[1] == s[n] ? "NO" : "YES") << endl;
	 return;
}

B题:Turtle and Piggy Are Playing a Game 2 

思路

给定一个数组,T每次可以删去选定的两个相邻元素中较小的一个,而P会删去较大的一个。

如果这么理解就清楚多了,我们贪心地想,T一定是删去最小的,而P一定是删去最大的,按题意模拟即可

这样是输出n/2+1大的元素

代码

inline void solve() {
     int n; cin >> n;
     vector<int> a(n + 1);
     for (int i = 1; i <= n; i ++ ) cin >> a[i];
     sort(a.begin() + 1, a.end());
     cout << a[n / 2 + 1] << endl;
	 return;
}

C题:Turtle and Good Pairs 

思路

众生平等构造题

显然地,如果相邻的两个元素不同的组数越多,答案越大

这样怎么构造呢?放了一个字符后,放下一个不是它的字符即可

最后可能会剩余3个d等等情况,我们还是照样放最后面,因为按照题意,它也是good的

复杂度 26n

代码

inline void solve() {
     int n; cin >> n;
     string s; cin >> s;
     s = ' ' + s;
     if (n <= 3) return cout << s.substr(1) << endl, void();
     vector<int> a(26);
     for (int i = 1; i <= n; i ++ ) a[s[i] - 'a'] += 1;
     while (true) {
        bool flag = false;
        for (int i = 0; i < 26; i ++ ) {
            if (a[i]) {
                flag = true;
                cout << char('a' + i);
                a[i] -= 1;
            }
        }
        if (!flag) break;
     }
     cout << endl;
	 return;
}

D1:Turtle and a MEX 问题 (Easy Version) 

思路

 
 

3 4

2 0 2

3 2 3 3

4 7 0 1 5

这三个数组的mex1分别为1,0,2

如果x分别与之相等的情况下,数组的mex还可以增长

可以得到mex2:    3,1,3

得到的关系为

1-3

0-1

2-3

可以抽象成一个有向无环图

0-1-3

2-3

在任意次操作下,根据mex的定义,给定的任意一个x,都可以变成mex1中的元素,然后在图中向下遍历

所以任意一个x都可以变成mex2中的最大元素

因为还可以不操作,所以我们只要将x和最大的mex2比较取大即可

这过程中用到了等差数列

代码

inline void solve() {
     int n, m; cin >> n >> m;
     int mex = 0;
     for (int i = 1; i <= n; i ++ ) {
        int num; cin >> num;
        set<int> s;
        for (int j = 1; j <= num; j ++ ) {
            int x; cin >> x;
            s.insert(x);
        }
        int cur = 0;
        bool flag = true;
        while (true) {
            if (!s.count(cur)) {
                if (flag) flag = false;
                else break;
            }
            cur += 1;
        }
        mex = max(mex, cur);
     }
     if (mex >= m) cout << (ll)mex * (m + 1) << endl;
     else cout << (ll)mex * (mex + 1) + (ll)(mex + 1 + m) * (m - mex) / 2 << endl;
	 return;
}

D2:Turtle and a MEX 问题 (Hard Version) 

思路

因为只能每个数组操作一次了,一开始我们可以定义一个默认值M,意为任意的x都可以直接变成M

对于任意的x,都可以花费一次操作到mex1中的任意元素,所以我们又可以将M定义为mex1中最大的一个元素

我们再进行分类讨论

如果x是mex1中的元素

        1:它可以继续往下遍历,成为“它可以遍历的到的最大mex2”

        2:立刻变成M

        3:不操作

如果x不是mex1中的元素

        1:立刻变成M

        2:不操作

这个M怎么求呢?

我们注意到

如果出现了

1-3

3-5

3-4

这种情况,我们先将它连成图,是

1-3-4

     -5

这个3可以前往4或者5,

因为是3-4和3-5

所以我们可以花费一次操作变成3,然后往下遍历4或者5任意一支

这样就还可以更新M了,因为要最大,所以可以更新为所有分支中的最大一个

最后还是等差数列求和,不过有些因为可以变大,所以我们可以用一个extra存其变化

此题细节较多,代码较烦,难度分2000

代码

inline void solve() {
     ll n, m; cin >> n >> m;
     map<int, vector<int>> tr;
     map<ll, ll> to;
     ll M = 0;
     for (int i = 1; i <= n; i ++ ) {
        int num; cin >> num;
        set< int > s;
        for (int j = 1; j <= num; j ++ ) {
            int x; cin >> x;
            s.insert(x);
        }
        bool flag = false;
        ll cur = 0, mex;
        while (true) {
            if (!s.count(cur)) {
                if (flag) {
                    tr[mex].push_back(cur);
                    to[cur] = cur;
                    break;
                }
                mex = cur;
                M = max(M, mex);
                flag = true;
            }
            cur += 1;
        }
     }
     for (int i = M; i >= 0; i -- ) {
        if (tr[i].size()) {
            if (tr[i].size() > 1) {
                for (int v : tr[i]) {
                    to[i] = max(to[i], to[v]);
                }
                M = max(M, to[i]);
            }else to[i] = max(to[i], to[tr[i][0]]);
        }
     }
     ll extra = 0;
     for (auto [x, y] : to) {
        if (x > m) break;
        if (x <= M) extra += max(y, M) - M;
        else extra += max({x, y, M}) - x;
     }
     if (M >= m) cout << extra + M * (m + 1) << endl;
     else cout << extra + M * (M + 1) + (M + 1 + m) * (m - M) / 2 << endl;
	 return;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部