CF2178 Goodbye 2025 个人题解

再见 2025

A

限制是不能合并两个相邻的Y。

两个N合并后还是N，但如果是一个Y一个N，结果就是Y。

所以，合并过程中Y不会消失，一旦有超过一个Y，最后一定无法合并。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int T;
25
string s;
26
void solve() {
27
    cin >> s;
28
    int cnt = 0;
29
    for(auto x : s) if(x == 'Y') cnt++;
30
    if(cnt > 1) puts("NO");
31
    else puts("YES");
32
}
33
signed main() {
34
    ios::sync_with_stdio(0);
35
    cin.tie(0);
36
    cout.tie(0);
37
    cin >> T;
38
    while(T--) solve();
39
    return 0;
40
}

B

显然首尾的u必须改掉。

以下是场上胡乱猜的做法：

从左往右扫一遍，维护 $lst$ 表示当前位置左边最近的s。
如果当前位置为s，更新 $lst$ 。
否则根据 $lst$ 计算右边对称的位置，如果其为u，将其更新为 s。

没想到竟然通过了。

怎么证明呢？

首先我们的原则是能不改就不改。

对于一个u，令其满足条件（更新右边的对称位置）代价为 1，改掉它代价也是 1。

因为我们提前改掉了首尾，所以每个u都会面临这样的抉择。

选择前者，以后扫到改的那个点时可以一定不必额外花费代价，后者则可能还有代价。

好像证出来了？

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, pos[N];
26
string s;
27
void solve() {
28
    cin >> s;
29
    n = s.size();
30
    s = " " + s;
31
    int ans = 0;
32
    if(s[1] == 'u') s[1] = 's', ans++;
33
    if(s[n] == 'u') s[n] = 's', ans++;
34
    int lst = 0;
35
    for(int i = 1;i <= n;i++) {
36
        if(s[i] == 'u') {
37
            if(lst) {
38
                if(s[i + i - lst] != 's') {
39
                    ans++;
40
                    s[i + i - lst] = 's';
41
                }
42
            }
43
        } else lst = i;
44
    }
45
    cout << ans << endl;
46
}
47
signed main() {
48
    ios::sync_with_stdio(0);
49
    cin.tie(0);
50
    cout.tie(0);
51
    cin >> T;
52
    while(T--) solve();
53
    return 0;
54
}

C

观察一下先。

$a_1$ 的贡献只能是 $a_1$ 。
无论怎么操作，一定存在一个 $i \in [2, n]$ ，满足 $a_{i + 1}$ 到 $a_n$ 的贡献是 $- \sum_{j = i + 1}^n a_j$ 。因为最后肯定是先留着一个元素，然后用若干 $2$ 操作（可以是 $0$ 个）干掉那个元素后面的，最后 $1$ 操作干掉它。
关键在于中间的情况。我们考虑对于第二个元素，如果它是正数，可以跟着 $a_1$ 用 $1$ 操作干掉，如果是负数，则可以先用 $2$ 操作干掉它。这两个过程中，第三个数会到第二个位置，第一个位置上可能是 $a_1$ 或 $a_2$ ，但 $a_2$ 最终一定能贡献出其绝对值。归纳一下，我们断定，中间的一段肯定可以贡献出每个元素的绝对值。

所以我们枚举贡献绝对值的间断点，其最后一个元素就可以作为 2 里提到的留着的那个元素，答案就是

\max_{i = 2} \Big\{ a_1 + \sum_{j = 2}^i |a_j|- \sum_{j = i + 1}^{n} a_j \Big \}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, a[N];
26
ll s[N], sa[N];
27
void solve() {
28
    cin >> n;
29
    for(int i = 1;i <= n;i++) {
30
        cin >> a[i];
31
        s[i] = s[i - 1] + a[i];
32
        sa[i] = sa[i - 1] + abs(a[i]);
33
    }
34
    ll ans = s[1] - s[n];
35
    for(int i = 2;i <= n;i++) {
36
        ll res = a[1] + sa[i - 1] - sa[1] + s[i] - s[n];
37
        ans = max(ans, res);
38
    }
39
    cout << ans << endl;
40
}
41
signed main() {
42
    ios::sync_with_stdio(0);
43
    cin.tie(0);
44
    cout.tie(0);
45
    cin >> T;
46
    while(T--) solve();
47
    return 0;
48
}

D

构造题，我们尝试去找到一些普遍的方法。

先给 $\{a\}$ 递增排个序。

考虑一个长度为 $n$ 并且攻击力递增的序列，第 $i$ 次操作让 $i + 1$ 攻击 $i$ ，这样就能用 $n - 1$ 次操作留下 $1$ 个元素且合法。

然后，再写这篇题解的时候，我突然想到可以在序列里 $k$ 个位置都进行这样的操作，这样肯定就能留下 $k$ 个了，有 $2k \le n$ 。但当时不知道为什么，我想到的是枚举一个点，这个点一边进行这种操作留下 $1$ 个，然后另一边不断让相邻两个里较大的干掉较小的，然后也能算出干掉的个数，范围和上面其实是一样的。

每进行一次操作，会且仅会干掉一个，次数容易计算且合法。

问题在于，当 $m = 0$ 时该怎么做。这也是场上卡我巨多时间的点。

其实就是最大的那个数怎么办的问题。

如果其他所有数的和还小于最大的数，那么肯定做不到。否则还是有希望的，然后我们就要寻找一个 $k$ ，先让最大值被一堆炮灰送死 + 消耗，然后在 $[1, k]$ 里面进行只存活一人的自相残杀，最后让 $k$ 干死大魔王，同时自己也受到反作用力而死。

那么这个 $k$ 就要满足 $a_k \le a_n - \sum_{i = k + 1}^{n - 1} a_i$ 并且 $a_n > \sum_{i = k + 1}^{n - 1} a_i$ 。

如果找不到这样的 $k$ ，那么无解。这个是否充要我不好说（雾

否则输出操作序列即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, m, d, td;
26
ll s[N];
27
PII a[N];
28
void print(int x) {
29
    for(int i = 1;i < x;i++) {
30
        cout << a[i + 1].se << " " << a[i].se << endl;
31
    }
32
    for(int i = n;i > x;i -= 2) {
33
        cout << a[i].se << " " << a[i - 1].se << endl;
34
    }
35
}
36
void solve() {
37
    cin >> n >> m;
38
    d = n - m;
39
    td = 0;
40
    for(int i = 1;i <= n;i++) {
41
        int x = 0;
42
        cin >> x;
43
        a[i] = {x, i};
44
    }
45
    if(n == m) {
46
        cout << -1 << endl;
47
        return;
48
    }
49
    sort(a + 1, a + n + 1);
50
    if(m == 0) {
51
        if(n == 2) {
52
            cout << -1 << endl;
53
            return;
54
        }
55
        for(int i = 1;i <= n;i++) {
56
            s[i] = s[i - 1] + a[i].fi;
57
        }
58
        if(s[n - 1] < a[n].fi) {
59
            cout << -1 << endl;
60
            return;
61
        }
62
        int p = 0;
63
        for(int i = 1;i < n;i++) {
64
            if(a[i].fi >= a[n].fi - (s[n - 1] - s[i]) && a[n].fi - (s[n - 1] - s[i]) > 0) {
65
                p = i;
66
                break;
67
            }
68
        }
69
        if(!p) {
70
            cout << -1 << endl;
71
            return;
72
        }
73
        cout << n - 1 << endl;
74
        for(int i = 1;i < p;i++) {
75
            cout << a[i + 1].se << " " << a[i].se << endl;
76
        }
77
        for(int i = p + 1;i < n;i++) {
78
            cout << a[i].se << " " << a[n].se << endl;
79
        }
80
        cout << a[n].se << " " << a[p].se << endl;
81
        return;
82
    }
83
    if(n % 2 == 0) {
84
        if(d == n / 2) {
85
            cout << d << endl;
86
            for(int i = 1;i < n;i += 2) {
87
                cout << a[i + 1].se << " " << a[i].se << endl;
88
            }
89
            return;
90
        }
91
    }
92
    for(int i = 2;i <= n;i++) {
93
        int t = i - 1 + (n - i + 1) / 2;
94
        if(t == d) {
95
            cout << t << endl;
96
            print(i);
97
            return;
98
        }
99
    }
100
    cout << "-1" << endl;
101
}
102
signed main() {
103
    ios::sync_with_stdio(0);
104
    cin >> T;
105
    while(T--) solve();
106
    return 0;
107
}

E

待补

Nanami^2

A

B

C

D

E

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

觉得这篇文章怎么样？

分享这篇文章

评论区