Codeforces Round 908 (Div. 2)
A - Secret Sport
解题思路:
有一说一，没看很懂，感觉最后赢的就是赢了。。。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
s = ' ' + s;
cout << s.back() << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Two Out of Three
解题思路:
选取两个不同的数字，分别满足\((1,2),(1,3)\)对，其余全部设为\(1\).
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), cnt(100 + 10);
vector<vector<int>> pos(100 + 1, vector<int>());
for (int i = 1; i <= n; i++)
{
cin >> a[i];
cnt[a[i]]++;
pos[a[i]].push_back(i);
}
int num = 0;
for (int i = 1; i <= 100; i++)
{
if (cnt[i] > 1)
{
num++;
}
}
if (num < 2)
{
cout << -1 << "\n";
return;
}
vector<int> ans(n + 1);
int t = 3;
for (int i = 1; i <= 100; i++)
{
if (cnt[i] > 1)
{
int len = pos[i].size();
for (int j = 0; j < len; j++)
{
if (j == 0)
{
ans[pos[i][j]] = 1;
}
else
{
ans[pos[i][j]] = t;
}
}
if (t == 3)
{
t = 2;
}
else
{
t = 0;
}
}
if (t == 0)
{
break;
}
}
for (int i = 1; i <= n; i++)
{
if (!ans[i])
{
ans[i] = 1;
}
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " \n"[i == n];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Anonymous Informant
解题思路:
正着想没头绪，思考反向操作。
发现反向操作模拟方便，如果能够反向操作\(n\)次，那么一定能形成一个循环操作(可能不到\(n\)次就开始循环了)。
所以，对于\(k < n\)，我们可以直接模拟\(k\)次反向操作是否合法。
对于\(k \geq n\),如果\(n\)次合法，那么一定可以无限操作，\(k\)也合法。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int cur = n;
for (int i = 1; i <= min(k, n + 1); i++)
{
if (a[cur] > n)
{
cout << "NO\n";
return;
}
cur = (cur - 1 - a[cur] + n) % n + 1;
}
cout << "YES\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Neutral Tonality
解题思路:
新序列的\(LIS\)一定大于等于原序列\(LIS\),我们的目的就是尽量让\(LIS\)保持不变。
先将\(b\)进行降序排序。
对于将大于\(a_1\)的元素降序插入到\(a_1\)之前。
- 如果原\(LIS\)包括\(a_1\)，那么首位降序插入的元素最多选一个替代\(a_1\)，\(LIS\)不会增长。
- 如果原\(LIS\)不包括\(a_1\)，那么\(a_1\)一定大于等于原\(LIS\)的首位，插入的元素也一定大于等于原\(LIS\)首位，那么首位降序插入的元素最多选一个替代\(a_1\)，\(LIS\)不会增长。
将剩余的元素降序插入到\(a_n\)之后。
- 如果原\(LIS\)包括\(a_1\)，那么最后降序插入的元素都小于\(a_1\)，同样最多选一个进行替换，\(LIS\)不会增长。
- 如果原\(LIS\)不包括\(a_1\)，那么\(a_1\)一定大于等于原\(LIS\)的首位，同理。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int mod = 998244353;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
}
sort(b.begin() + 1, b.end());
vector<int> ans;
int j = m;
for (int i = 1; i <= n; i++)
{
while (j > 0 && b[j] >= a[i])
{
cout << b[j--] << ' ';
}
cout << a[i] << ' ';
}
while (j > 0)
{
cout << b[j--] << ' ';
}
cout << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}