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;
}