A. Simply Strange Sort
题意：给出n的一个排列（n为奇数），进行t轮如下操作，当前轮数为奇数，检查所有奇数位置(没有第n项)，使得a[i] < a[i+1],不是就进行交换；当前轮数为偶数，就检查所有偶数位置，问使得n为递增序列的t最小值
分析：暴力，因为n数据小，也就1000次，大体估计，t的轮次不会超过2n，每个物品都会往自己的方向移动最多n次，被挡出最多n-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 = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], g[N], dp[N];
bool judge()
{
for (int i = 1; i <= n; i++)
if (s[i] != i)
return true;
return false;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
int cnt = 0;
while (judge())
{
cnt++;
if (cnt & 1)
{
for (int i = 1; i <= n - 2; i += 2)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
}
else
{
for (int i = 2; i <= n - 1; i += 2)
if (s[i] > s[i+1])
swap(s[i], s[i+1]);
}
}
cout << cnt << endl;
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
B. Charmed by the Game
题意：这题读的不是很明白，按我的理解说，双方轮流发球，发球顺序不变，但是不知道最初是谁发的，现在Alice发了a个球，Bob发了b个球，问双方可能的抢发次数
分析：分奇偶进行研究，按偶数来说，双方都应该发（a+c）/2个，所以最少的抢发次数就是跟中间值的差值，当少的一方抢一次时，多的一方就必然会再抢一次，而最多少的一方不会抢超过自己数值的次数，设n<m，答案就是从（m-n）/2到（m+3n）/2，差值为2，而奇数的话，因为最初不知道双方谁发球，所以就比较宽泛，在少的一方抢一次时，多的一方就不一定会再抢了，我们可以理解为初始发球方的交换，所以答案就是从（m-n）/2到（m+3n）/2，差值为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 = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], g[N], dp[N];
void solve()
{
cin >> n >> m;
if (n > m) swap(n, m);
if ((n + m) % 2 == 0)
{
printf("%d\n", n + 1);
for (int i = (m - n) / 2, j = 0; j <= n; j++)
printf("%d%c", j * 2 + i, j == n ? ‘\n‘ : ‘ ‘);
}
else
{
printf("%d\n", 2 * n + 2);
for (int i = (m - n) / 2, j = 0; j <= 2 * n + 1; j++)
printf("%d%c", j + i, j == 2 * n + 1 ? ‘\n‘ : ‘ ‘);
}
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
C. Deep Down Below
题意：有n个关卡，每一关有n个boss，在每一关勇者必须按顺序挑战这n个boss，只要勇者的攻击力严格大于boss的护甲，勇者就一定会无伤打赢，且攻击力+1，否则必败，n个关卡的挑战顺序可以随意，问勇者无伤打完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 = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], g[N], dp[N];
PII a[N];
bool judge(int u)
{
for (int i = 1; i <= n; i++)
if (u < a[i].x)
return false;
else u += a[i].y;
return true;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> m;
cin >> s[1];
int maxn = s[1] + 1;
for (int j = 2; j <= m; j++)
{
cin >> s[j];
maxn = max(maxn, s[j] + 2 - j);
}
a[i] = {maxn, m};
}
sort(a + 1, a + n + 1);
int l = 1, r = mod;
while (l < r)
{
int mid = l + r >> 1;
if (judge(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}
D1. Up the Strip (simplified version)
题意：给定n和p，答案对p取余，对于一个数n，我们可以进行如下操作，1.选择1到n-1的数，变成那个数。 2.选择2到n的数m，变成\(\left \lfloor \frac{n}{m} \right \rfloor\),问从n变成1有多少种不同方式，d1题中n的范围为2e5
分析：对于2e5的数据，我们可以算出前n项所有的值，此时，对于第一种操作，我们可以统计前缀和对于每一个i位置，都可以O(1)统计，对于第二种操作\(\sum_{j=2}^{i} s[\left \lfloor \frac{i}{j} \right \rfloor]\),这是一个很显然的整除方块问题，可以优化为O(\(\sqrt{n}\)),总时间复杂度就是O(n\(\sqrt{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 = 2e5 + 10, mod = 1e9 + 7;
int n, m, t, k, p;
int s[N], g[N], dp[N];
void solve()
{
cin >> n >> p;
int m = 1;
s[1] = 1;
for (int i = 2; i <= n; i++)
{
s[i] = m;
for (int l = 2, r; l <= i; l = r + 1)
{
r = min(i, i / (i / l));
s[i] = (1ll * s[i] + 1ll * (r - l + 1) * s[i / l]) % p;
}
m = (1ll * m + s[i]) % p;
}
cout << s[n] << endl;
}
int main()
{
t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
D2. Up the Strip
题意：同D1，n范围4e6
分析：考虑实际，每个数对于后续的影响，从后往前推，对于该数，一共会被后面的数用几次，对于第一种情况，计算后缀和，对于第二种情况，考虑什么时候会被后面的数计算，设该位置为 i，那么i * j一定可以通过除以 j 到达 i 的位置，在下取整得意义下，一直到 i * j + j - 1 都可以通过除以 j 到达 i 的位置，而 i * j + j 以后，除以 j 就会至少也是 i + 1 了，对于 j 这个数进行枚举，这个复杂度是O(logn)级别的，总时间复杂度就是O(nlogn)
代码：
#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 = 8e6 + 10, mod = 1e9 + 7;
int n, m, t, k, p;
int s[N], g[N], dp[N];
void solve()
{
cin >> n >> p;
s[n] = 1;
int u;
for(int i = n - 1 ; i >= 1; i--)
{
u = s[i + 1];
for (int j = 2; i * j <= n; j++)
u = ((1ll * u + s[i * j] - s[i * j + j]) % p + p) % p;
s[i] = (s[i + 1] + u) % p;
}
cout << u << endl;
}
int main()
{
t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
E. Bottom-Tier Reversals
题意：多组输入，给出n个数n为奇数，进行不超过\(\frac{5n}{2}\)的操作，使得原数组递增，不需要最小化次数，操作指的是进行初始位置为第一个元素，长度为奇数的翻转，如果不可能实现，输出-1，可能实现，输入次数，每次操作的长度
分析：思维题，操作几次后发现，偶数位置绝对不会跑到奇数位置，奇数位置也绝对不会去偶数位置，所以所有偶数必须都在偶数位置上，奇数位置同理，不符合输出-1，之后考虑，题目给出不超过\(\frac{5n}{2}\)的交换，那就代表考虑两轮五次，每次同时进行两个数的调换，使得操作从考虑n的操作答案变成考虑n-2的操作答案，方式很多，现给出一种，思路是考虑将i和i-1的位置放一起，就可以通过两次翻转到它们的位置上去，因为保证了n为奇数，所以可以基本上定位改变i的位置，先找见i的位置pos，交换到1号位置，找到i-1的位置pos2，将i翻转到pos2-1的位置，再将两数翻转到2,3位置，再交换到1,2位置，再换到i-1，i的位置，一共5次
代码：
#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 = 1e5 + 10, mod = 1e9 + 7;
int n, m, t, k;
int s[N], g[N], dp[N];
vector<int> vec;
int find(int x, int u)
{
for (int i = 1; i <= u; i++)
if (s[i] == x)
return i;
return -1;
}
void solve()
{
vec.clear();
cin >> n;
for (int i = 1; i <= n; i++)
cin >> s[i];
for (int i = 1; i <= n; i++)
if (s[i] % 2 != i % 2)
{
puts("-1");
return;
}
for (int i = n; i > 1; i -= 2)
{
int pos = find(i, i);
vec.push_back(pos);
reverse(s + 1, s + 1 + pos);
pos = find(i - 1, i);
vec.push_back(pos - 1);
reverse(s + 1, s + pos);
vec.push_back(pos + 1);
reverse(s + 1, s + pos + 2);
vec.push_back(3);
reverse(s + 1, s + 4);
vec.push_back(i);
reverse(s + 1, s + 1 + i);
}
printf("%d\n", vec.size());
for (int i = 0; i < vec.size(); i++)
printf("%d%c", vec[i], i == vec.size() - 1 ? ‘\n‘ : ‘ ‘);
}
int main()
{
t = 1;
cin >> t;
while(t--)
solve();
return 0;
}