A. Countdown
题意：给你一个
n
n
n 位的字符串。每位均为一个从
0
0
0 至
9
9
9 的整数（即整个字符串表示一个从
0
0
0 至
1
0
n
?
1
10^{n-1}
10n?1 的整数）。你可以执行以下操作之一任意次：
求使整个字符串转变为
0
0
0 字符串所需的最少操作数。
题目分析：最优解显然是将其它位上的数字交换至个位上再减为
0
0
0 ，除了原本就在个位上的数之外，其余各数的花费均为：
s
[
i
]
s[i]
s[i] （变
0
0
0 费用） +
1
1
1 （交换费用）。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
using ll = long long;
using namespace std;
ll solve()
{
int n;
string s;
cin >> n >> s;
ll res = 0;
for (auto x : s)
if (x - '0')
res += x - '0' + 1;
if (s[n - 1] - '0')
--res;
return res;
}
int main(int argc, char const *argv[])
{
IOS;
int T;
cin >> T;
while (T--)
cout << solve() << endl;
return 0;
}
B. Swaps
题意：给你两个长度均为
n
n
n 的序列
a
a
a 和
b
b
b 。序列
a
a
a 仅包含从
1
1
1 至
2
n
2n
2n 的每个奇数，序列
b
b
b 仅包含从
1
1
1 到
2
n
2n
2n 的每个偶数。
你可以对这两个序列执行以下操作：
- 选择两序列之一
- 选择从
1
1
1 至
n
?
1
n?1
n?1 的一个索引
i
i
i
- 交换所选序列的第
i
i
i 个和第
(
i
+
1
)
(i+1)
(i+1) 个元素
计算使序列
a
a
a 的字典序小于序列
b
b
b 所需的最小操作数。
题目分析：要使得字典序最小，显然有
a
[
1
]
<
b
[
1
]
a[1] < b[1]
a[1]<b[1] 。考虑暴力的做法，枚举每个
a
i
a_i
ai? 为首时，将符合条件的
b
i
b_i
bi? 挪至列首的总费用，时间复杂度
O
(
n
2
)
O(n^2)
O(n2) 。
如何优化？假设现在
a
[
1
]
=
x
a[1] = x
a[1]=x ，那符合条件的
b
i
b_i
bi? 必为
x
+
1
x+1
x+1 、
x
+
3
x+3
x+3 、
x
+
5
?
2
n
?
2
x+5 \cdots 2n-2
x+5?2n?2 、
2
n
2n
2n 。因此我们可以用
p
a
i
r
<
i
n
t
,
i
n
t
>
pair<int,int>
pair<int,int> 记录下每个元素的初始位置和元素大小，按值排序后用后缀和的思想预先处理出
b
b
b 序列中
[
x
+
1
,
2
n
]
[x+1,2n]
[x+1,2n] 挪至列首费用的最小值后再进行计算，时间复杂度降至
O
(
n
)
O(n)
O(n) 。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
#define pii std::pair<int, int>
#define mp std::make_pair
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int solve()
{
int n = read();
std::vector<pii> a(n + 1), b(n + 1);
std::vector<int> mn(n + 1);
rep(i, 1, n) a[i].first = read(), a[i].second = i;
rep(i, 1, n) b[i].first = read(), b[i].second = i;
std::sort(a.begin() + 1, a.begin() + n + 1);
std::sort(b.begin() + 1, b.begin() + n + 1);
mn[n] = b[n].second;
down(i, n - 1, 1) mn[i] = std::min(mn[i + 1], b[i].second);
int res = inf;
rep(i, 1, n) res = std::min(res, a[i].second + mn[i] - 2);
return res;
}
int main(int argc, char const *argv[])
{
int T = read();
while (T--)
printf("%d\n", solve());
return 0;
}
C. Book
题意：给你一本有
n
n
n 章的书。每章都有一定数量的前置章节，需要理解所有的前置章节后才能理解本章的内容。现在你将从头到尾反复阅读本书，直到你理解整本书。问你在阅读多少遍后才能啃完这本书，或读懂这本书对你来说为时尚早。
题目分析：画下样例不难发现是拓扑排序。套个拓扑排序的板子，当某章节入度为
0
0
0 入队时，若其编号大于前置章节，则该章节这一轮阅读就能读到，否则要等到下一轮，我们可以用优先队列维护当前可读章节的阅读顺序。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
#define pii std::pair<int, int>
#define mp std::make_pair
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int solve()
{
int n = read();
std::vector<int> in(n + 1);
std::vector<int> e[n + 1];
std::priority_queue<pii, std::vector<pii>, std::greater<pii>> q;
rep(i, 1, n)
{
int k = in[i] = read();
if (!in[i])
q.push(mp(1, i));
rep(j, 1, k) e[read()].push_back(i);
}
int res, cnt = 0;
while (!q.empty())
{
pii cur = q.top();
q.pop();
res = cur.first;
++cnt;
for (auto v : e[cur.second])
{
--in[v];
if (!in[v])
q.push(mp(v > cur.second ? cur.first : cur.first + 1, v));
}
}
if (cnt < n)
return -1;
return res;
}
int main(int argc, char const *argv[])
{
int T = read();
while (T--)
printf("%d\n", solve());
return 0;
}
D. Xor of 3
题意：给你一个长为
n
n
n 的
01
01
01 序列，你可以进行以下操作至多
n
n
n 次直至序列中所有元素均为
0
0
0 ：
- 从
1
1
1 到
n
?
2
n?2
n?2 中选择一个索引
i
i
i
- 令
a
i
=
a
i
+
1
=
a
i
+
2
=
a
i
⊕
a
i
+
1
⊕
a
i
+
2
a_i = a_{i+1} = a_{i+2} = a_i⊕a_{i+1}⊕a_{i+2}
ai?=ai+1?=ai+2?=ai?⊕ai+1?⊕ai+2?
判断是否有解，若有解，输出任一解决方案。
题目分析：先考虑变换前后的不变量，首先每次变换均不会改变序列的奇偶性，要么少两个
1
1
1 要么多两个
1
1
1 ，所以原序列若存在奇数个
1
1
1 则无解。
偶数个
1
1
1 情况下，考虑一段连续的
1
1
1 ：
- 如果是偶数个
1
1
1 ，由于本题序列的奇偶不变性，一定可以将这段
1
1
1 全消为
0
0
0
- 如果是奇数个
1
1
1 ，那么不能靠自己消完，所以要往后每次把两个
0
0
0 变成
1
1
1 ，直到遇到
101
101
101 这种情况，把
101
101
101 变成
000
000
000 后，前面的
1
1
1 只有偶数个，即转换为了上述情况，就可以消完了
最后特判一下
0
、
0
、
0
?
1
、
1
、
1
0、0、0 \cdots 1、1、1
0、0、0?1、1、1 情况就好，由于末尾段
1
1
1 的个数必为偶数个，所以前面只要存在
0
0
0 就可以全部消完，那么唯一无解的情况下即是序列转化为了全
1
1
1 序列（如
[
1
,
0
,
0
,
1
]
[1,0,0,1]
[1,0,0,1] ）。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void solve()
{
int n = read(), cnt = 0;
std::vector<int> a(n + 1);
std::vector<int> ans;
for (int i = 1; i <= n; ++i)
if (a[i] = read())
++cnt;
if (cnt & 1)
{
puts("NO");
return;
}
cnt = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i])
++cnt;
else if (cnt & 1)
{
if (a[i + 1])
{
a[i - 1] = a[i + 1] = 0;
for (int j = i - 1; j >= i - cnt; j -= 2)
ans.push_back(j), a[j] = a[j + 1] = 0;
cnt = 0;
}
else
{
ans.push_back(i - 1);
a[i] = a[i + 1] = 1;
++cnt;
}
}
else
{
for (int j = i - 2; j >= i - cnt; j -= 2)
ans.push_back(j), a[j] = a[j + 1] = 0;
cnt = 0;
}
}
if (cnt)
{
if (cnt == n)
{
puts("NO");
return;
}
for (int i = n - cnt; i <= n - 2; i += 2)
ans.push_back(i);
}
puts("YES");
printf("%d\n", ans.size());
for (auto x : ans)
printf("%d ", x);
if (ans.size())
puts("");
}
int main(int argc, char const *argv[])
{
int T = read();
while (T--)
solve();
return 0;
}
|