2023/11/9
Codeforces Round 908 (Div. 2) 补题
A. Secret Sport
简单签到，一个思路就是比赛结束总是在刚刚得出胜者的时候，所以最后一个人总是获胜的
B. Two Out of Three
签到
C. Anonymous Informant （补）
思路：逆推，因为每次左移的时候，选择的数总是会到最后一位，那么我们就可以看当前最后一位数是谁，就可以知道上一轮选了谁，那么当进入循环或者k次结束时，最后一位数都没有大于n，那么就是合法的。否则，就是不合法
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
map<int, int> mp;
vector<int> alls;
const int N = 201010;
int a[N];
int vis[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
vis[i] = 0;
}
int pos = n;
vis[pos] = 1;
if (a[n] > n)
{
cout << "No\n";
return;
}
while (k--)
{
if (a[pos] > n)
{
cout << "No\n";
return;
}
vis[pos] = 1;
pos = (pos - a[pos] + n) % n;
if (pos == 0)
pos = n;
if (vis[pos])
{
cout << "Yes\n";
return;
}
}
cout << "Yes\n";
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
D - Neutral Tonality（补）
题意：让我们往只有的序列里面加数，使最后的LIS最小。
这个其实是自己写的，赛时被C卡了没时间。
思路：我们加数的时候就和原来的a数组里的数比较，对于一个a[i]我们让选a[i]是优于我们加进去的数就行，这样我们就可以让LIS最小，对于一个a[i],我们若在他前面降序加入大于等于a[i]的数，那么肯定是选a[i]更优的。因为这lis同等长度结尾更小，自然更优。 若遍历a[n]结束，b还没填完，说明有一部分数太小了，比a中任何一个数都小，那个自然加到末尾就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
vector<int> alls;
void solve()
{
alls.clear();
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int j = 1; j <= m; j++)
cin >> b[j], alls.push_back(b[j]);
sort(alls.begin(), alls.end());
for (int i = 1; i <= n; i++)
{
int x = alls.size() - 1;
for (int j = x; j >= 0; j--)
{
if (alls[j] >= a[i])
{
cout << alls[j] << " ";
alls.pop_back();
}
else
break;
}
cout << a[i] << " ";
}
for (int j = alls.size() - 1; j >= 0; j--)
{
cout << alls[j] << " ";
}
cout << endl;
}
signed main()
{
Acode;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}