A. Countdown
题意：只能进行两步操作，-1和对任意两个位置交换值，问最少多少步可以变成0，允许前导0的存在
分析：每个有值的位置都与个位进行交换，清0
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], dp[N], f[N];
char g[N];
string str;
vector<int> vec;
void solve()
{
int ans = 0;
cin >> n >> str;
reverse(str.begin(), str.end());
for (int i = 0; i < n; i++)
{
ans += str[i] - '0';
if (i > 0)
ans += str[i] != '0';
}
cout << ans << endl;
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
B. Swaps
题意：只能进行相邻值的交换，第一个数组为1到2n的所有奇数，随机排列，第二个数组是1到2n的所有偶数随机排列询问最少交换多少次，使得第一个数组的值比第二个数组的值小
分析：因为两个数组的任意数均不同，并且无重复的1到2n，所以可以分别对应记录第i个数在原数组中换几次可以到第一个位置，那么可以去这个数组中从大到小一边维护奇数比i大的值最小换几次，一边算偶数取到i-1时，答案为多少，答案取遍历完所有偶数值后的最小值
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], dp[N], f[N];
char g[N];
string str;
vector<int> vec;
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> k;
f[k] = i;
}
for (int i = 1; i <= n; i++)
{
cin >> k;
f[k] = i;
}
dp[2 * n + 2] = mod;
int res = mod;
for (int i = 2 * n; i >= 1; i--)
if (i & 1)
res = min(res, f[i] - 1 + dp[i+1] - 1);
else
dp[i] = min(dp[i+2], f[i]);
cout << res << endl;
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
C. Book
题意：每次读书从头到尾的读，理解某些章节需要理解彻底理解其他前驱章节的内容，问读几次能读懂整本书，或者他永远不会理解某些章节
分析：如果说存在不理解的章节，那必定成环了，这个图建起来是一棵树，因为要从小到大按顺序读，所以存放进优先队列中，存负值，就可以实现了，每一轮以此取出值，当前目录理解后对子节点的章节前置-1，把这一轮解锁的新章节（前置为0）先放入q2，在遍历完q的时候，如果q2有值，就交换优先队列q和q2，进行下一轮的读书，事先记录每一个章节的前置有多少，解锁一次少一个，前置为0代表当前这章彻底理解，以此往复。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], dp[N], f[N];
char g[N];
string str;
vector<int> vec[N];
void solve()
{
priority_queue<int> q,q2;
cin >> n;
for (int i = 1; i <= n; i++)
vec[i].clear();
for (int i = 1; i <= n; i++)
{
cin >> m;
s[i] = m;
for (int j = 1; j <= m; j++)
{
cin >> k;
vec[k].push_back(i);
}
if (!s[i]) q.push(-i);
}
m = n;
int lst = 0, res = 0;
while (q.size())
{
lst = 0, res++;
while (q.size())
{
int xx = -q.top();
q.pop();
if (xx < lst) q2.push(-xx);
else
{
lst = xx;
m--;
for (auto i : vec[xx])
{
if (!s[i]) continue;
s[i]--;
if (!s[i]) q.push(-i);
}
}
}
if (q2.size()) swap(q, q2);
}
if (m) puts("-1");
else printf("%d\n", res);
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
D. Xor of 3
题意：给出一个01序列，每回操作从1到n-2中选择i，选择后将s[i],s[i+1],s[i+2]同步修改成s[i]s[i+1]s[i+2],问是否可以在不超过n的操作次数内，将数组清0，输出NO或YES，YES的时候需要输出如何操作
分析：思路我一点想不到，看的排行榜代码，数组中1的个数的奇偶性是不变的，所以奇数个1时直接NO，对于奇偶位有些关系，假设对于所有的奇数位都进行一次操作，那么对于第i位和第i+1位的一定相等，不管如何操作，这时候如果第一位为0，在对所有的奇数位刷一次的话就成立了，所以第一次要试着找一个位置，使得第一轮交换后，第一个位置变成0，所以我们刷前i位异或和，找到奇数位上任意一个为0的情况，因为这意味着到这个数前有偶数个位置，偶数个1，往前两个两个走一遍，第一个位置就是0了，对于这个数之后的位置，就正常刷，每次跳两个位置，第一轮操作完后，所有的奇数位置就都和对应偶数位置的值相同了，所以再去拿所有奇数位走一遍就能将数组清零，n为奇数时不刷最后一个位置，因为不合法。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int cnt = 0;
int s[N], dp[N], f[N];
char g[N];
string str;
vector<int> vec;
void solve()
{
vec.clear();
cin >> n;
for (int i = 1; i <= n; i++)
{
int a;
cin >> a;
s[i] = s[i-1] ^ a;
}
int flag = 0;
for (int i = 0; i <= n; i++)
if (i % 2 == 1 && !s[i])
{
int j = i;
while (j + 3 <= n)
{
vec.push_back(j + 1);
s[j + 2] = 0;
s[j + 1] = s[j + 3];
j += 2;
}
j = i;
while (j - 2 > 0)
{
vec.push_back(j - 2);
s[j - 2] = 0;
s[j - 1] = s[j - 3];
j -= 2;
}
flag = 1;
break;
}
if (!flag || s[n])
{
puts("NO");
}
else
{
for (int i = 1; i + 2 <= n; i += 2) vec.push_back(i);
puts("YES");
cout << vec.size() << endl;
if (vec.size() == 0) return;
for (int i = 0; i < vec.size(); i++)
{
if (i) printf(" ");
printf("%d", vec[i]);
}printf("\n");
}
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}