Codeforces Round 874 (Div. 3)(A~D题)
A. Musical Puzzle
思路:
用最少的长度为2的字符串按一定规则拼出s。规则是：前一个字符串的尾与后一个字符串的首相同。统计s中长度为2的不同字符串数量。
代码:
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define N 200010
typedef long long ll;
typedef unsigned long long ull;
ll n, m, h, k, t, x, y, z;
ll a, b, c, d, mod = 998244353;
ll ans, num, sum1 = 0, sum, sum2 = 0, maxx, minn = 1e9;
ll f1[N], f2[N], dp[N], an[N], cnt[N];
bool flag, vis[N];
string s, s1, s2;
map<string, ll>mp;
bool cmp(ll x, ll y) {return x > y;
}
void solve() {cin >> n;cin >> s;ans = 0;mp.clear();for (int i = 0; i < s.size()-1; i++) {s1 = s.substr(i,2);if (!mp[s1]) {mp[s1] = 1;ans++;}}cout << ans << endl;
}
int main()
{cin >> t;while (t--) {solve();}return 0;
}B. Restore the Weather
思路:
将a和b分别按从小到大的顺序匹配便是最优的，一定能满足|ai−bi|≤k成立。只需注意要恢复原来的顺序输出。
代码:
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define N 200010
typedef long long ll;
typedef unsigned long long ull;
//ll n, m, h, k, t, x, y, z;
//ll a, b, c, d, mod = 998244353;
//ll ans, num, cnt,sum, maxx, minn = 1e9;
//ll f1[N], f2[N], dp[N], an[N];
//bool flag, vis[N];
//string s, s1, s2;
//map<ll, ll>mp;
struct tem {ll d, t;
}a[114514];
ll b[114514];
bool cmp1(tem a, tem b) { return a.t < b.t; }
bool cmp2(tem a, tem b) { return a.d < b.d; }
signed main()
{ll t;cin >> t;while (t--) {ll n, k;cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i].t;a[i].d = i;}for (int i = 1; i <= n; i++)cin >> b[i];sort(a + 1, a + 1 + n, cmp1);sort(b + 1, b + 1 + n);for (int i = 1; i <= n; i++)a[i].t = b[i];sort(a + 1, a + 1 + n, cmp2);for (int i = 1; i <= n; i++)cout << (a[i].t) << " ";cout << "\n";}return 0;
}
C. Vlad Building Beautiful Array
思路:
2只有减奇数才能改变奇偶性。值得注意的是，根据题目要求我们无法将一个奇数序列变成偶数序列，因此只有以下三种情况：
①原本全是奇数
②原本全是偶数
③有奇有偶：这时只能将偶序列变成奇序列。我们将每一个偶数与最小的奇数消减，只要最后的结果全为正数则有解，否则无解。
代码:
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define N 200010
typedef long long ll;
typedef unsigned long long ull;
ll n, m, h, k, t, x, y, z;
ll a, b, c, d, mod = 998244353;
ll ans, num, sum1 = 0, sum, sum2 = 0, maxx, minn = 1e9;
ll f1[N], f2[N], dp[N], an[N], cnt[N];
bool flag, vis[N];
string s, s1, s2;
map<ll, ll>mp;
void solve() {cin >> n;minn = 1e9;for (int i = 1; i <= n; i++) {cin >> dp[i];minn = min(minn, dp[i]);}if (minn % 2 == 0) {for (int i = 1; i <= n; i++) {if (dp[i] % 2 != 0) {cout << "NO" << endl;return;}}cout << "YES" << endl;return;}else {cout << "YES" << endl;return;}}
int main()
{ios_base::sync_with_stdio(false);cin >> t;while (t--) {solve();}return 0;
}
D. Flipper
思路:
在解空间中，以n/n-1开头的排列字典序比其他可行解大，因此最优解在以n/n-1开头的解空间里。
所以本题右端点是固定的，若元素n不在开头，则r在元素n所在的位置，若n在开头，则r在元素n - 1所在的位置。固定了r后我们再去枚举左端点l，在所有可行解中取字典序最大的那个排列即可。
代码:
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define N 200010
typedef long long ll;
typedef unsigned long long ull;
ll n, m, h, k, t, x, y, z;
ll a, b, c, d, mod = 998244353;
ll ans, num, cnt,sum, maxx, minn = 1e9;
ll f1[N], f2[N], dp[N], an[N];
bool flag, vis[N];
string s, s1, s2;
map<ll, ll>mp;
void solve() {cin >> n;for (int i = 1; i <= n; i++)cin >> dp[i];if (n == 1) {cout << dp[1] << endl;return;}maxx = 0;for (int i = 2; i <= n; i++) {if (dp[i] >= maxx) {maxx=dp[i];cnt = i;}}if (cnt == n) {num = cnt;for (int i = cnt - 1; i >= 2; i--) {if (dp[i] > dp[1]) {num = i;}elsebreak;}cout << dp[cnt] << " ";for (int i = cnt - 1; i >= num; i--)cout << dp[i] << " ";for (int i = 1; i < num; i++)cout << dp[i] << " ";cout << endl;}else {num = cnt - 1;for (int i = cnt-2; i >= 2; i--) {if (dp[i] > dp[1]) {num = i;}elsebreak;}for (int i = cnt; i <= n; i++)cout << dp[i] << " ";for (int i = cnt - 1; i >= num; i--)cout << dp[i] << " ";for (int i = 1; i < num; i++)cout << dp[i] << " ";cout << endl;}
}
int main()
{ios_base::sync_with_stdio(false);cin >> t;while (t--) {solve();}return 0;
}