CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
A - Jagged Swaps
解题思路:
若\(a[1] = 1\)，则可以。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
ll n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
if (a[1] == 1)
{
puts("YES");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - AB Flipping
解题思路:
从后往前遍历，累计\(B\)的数目\(cnt\)，遇到\(A\)了就累加到答案上。同时，\(B\)的累计数目重置为\(min(cnt,1)\)。继续遍历。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int cnt = 0;
int ans = 0;
for (int i = n - 1; i >= 0; i--)
{
if (s[i] == 'B')
{
cnt++;
}
else
{
ans += cnt;
cnt = min(cnt, 1);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Matching Arrays
解题思路:
贪心，尽量让大对大。
首先，将两数列排序。
然后，将\(b[x \sim 1] 和 a[n - (1 \sim x) + 1])\)按照顺序一一比较，若过程中\(b[i] \geq a[n - (x - i)]\),说明无解。否则，二者位置对应放置即可。
最后，将\(b[n \sim (x + 1)] 和 a[(n - x) \sim 1]\)，按照顺序一一比较，若过程中\(b[i] < a[n - (x - i)]\),说明无解。否则，二者位置对应放置即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n, x;
cin >> n >> x;
vector<pii> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i].fi;
a[i].se = i;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i].fi;
b[i].se = i;
}
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
vector<int> ans(n + 1);
for (int i = 1; i <= x; i++)
{
if (a[n - i + 1].fi <= b[x - i + 1].fi)
{
puts("NO");
return;
}
else
{
ans[a[n - i + 1].se] = b[x - i + 1].fi;
}
}
int idx = n;
for (int i = x + 1; i <= n; i++)
{
if (a[n - i + 1].fi > b[idx].fi)
{
puts("NO");
return;
}
else
{
ans[a[n - i + 1].se] = b[idx].fi;
idx--;
}
}
puts("YES");
for (int i = 1; i <= n; i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Ones and Twos
解题思路:
首先，对于以\(1\)为端点，\(2\)为中间段的数值段，设其总和为\(s\)，那么这个数值段的子段和一定能表示\(1 \sim s\)的所有数。
举例：
\([1,2,2,2,2]\)总和为\(9\)。\([1,3,5,7,9]\)，分别对应左端点向右扩展，\([2,4,6,8]\)用\(2\)段截取即可。中间有\(1\)同理。
所以，我们可以记录\(1\)的位置，同时更新整段的数值和。
\([2,2,1,2,2,2,1,2]\)。
我们将其划分为端点为\(1\)的子段后会发现，多出一个纯\(2\)段。我们考虑加上纯\(2\)段的情况。
首先，加上纯\(2\)段后，数值和的奇偶性不变。我们设纯\(2\)段的数值和为\(num\)
所以，设目标和\(v\),如果\(v \leq s - num\),说明我们用\(1\)为端点的段就可以得到\(v\)。
否则，说明我们可以尝试加上\(2\)段来进行构造，那么\(v,(s -num)\)的奇偶性要相同，然后就是\(v - (s - num) <= num\)。
实现注意细节：我们在提取纯\(2\)段的时候，纯\(2\)段尽量小。（方便将纯\(2\)段为空的情况进行合并)。
举例：
\([2,2,1,2,2,2,1,2]\)中的纯\(2\)段是\([2]\)而不是\([2,2]\)。
\([1,2]\)中的纯二段为\([]\)而不是\([2]\)。
如果纯二段为\([2]\),这里我们的\(num = 2,res = s - num = 1\)。我们按照上面条件的判断就会发现\(2\)这个数无法构造出来。因为奇偶性不同，而\(2\)本身其实就是答案。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
void solve()
{
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
ll s = 0;
set<int> se;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s += a[i];
if (a[i] == 1)
{
se.insert(i);
}
}
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int v;
cin >> v;
if (se.empty())
{
if (v % 2 == 0)
{
puts("YES");
}
else
{
puts("NO");
}
continue;
}
ll cnt = min(*se.begin() - 1, n - *se.rbegin());
ll res = s - 2 * cnt;
if (v <= res || ((v % 2 == res % 2) && (((v - res) / 2) <= cnt)))
{
puts("YES");
}
else
{
puts("NO");
}
}
else
{
int idx, val;
cin >> idx >> val;
if (a[idx] == 1)
{
se.erase(idx);
}
if (val == 1)
{
se.insert(idx);
}
s += val - a[idx];
a[idx] = val;
}
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}