2022”杭电杯“中国大学生算法设计超级联赛(9)1 3 7题解
1001-Arithmetic Subsequence
题目大意:
对给定的序列进行重排,使得任意一个长度大于等于3的子序列不构成等差数列。
思路:
如果一个数出现3次以上就无解。
下面讨论有解的情况:
奇 偶 偶 或是 偶 偶 奇 这种排列一定是构不成等差数列的。
所以把奇数全部放到一端,偶数全部放到另一端。
但是这样只能保证奇数和偶数不会构成等差数列,奇数和奇数之间(或是偶数和偶数之间)仍然会构成等差数列。
因此对于全部是奇数的一端,将每个数字减1后除2,不改变等差的性质,但是会出现奇数和偶数,就可以继续用上面的方法进行分治。
对于全是偶数的一端,将每个数字除2,同样可以用上面的方法进行分治。
#include <bits/stdc++.h>
const int N = 5e3 + 5;
using namespace std;
struct node
{
int num, x;
} a[N];
vector<node> odd, even;
void dfs(int l, int r)
{
if (r - l <= 1) return; //区间长度小于3的时候就退出,防止因为两个0进入无限循环
odd.clear(), even.clear();
for (int i = l; i <= r; i++)
{
if (a[i].x & 1)
odd.push_back(a[i]);
else
even.push_back(a[i]);
}
for (int i = 0; i < odd.size(); i++)
odd[i].x /= 2;
for (int i = 0; i < even.size(); i++)
even[i].x /= 2;
for (int i = 0; i < odd.size(); i++)
a[i + l] = odd[i];
for (int i = 0; i < even.size(); i++)
a[r - i] = even[i];
int r2 = l + odd.size() - 1, l2 = l + odd.size();
dfs(l, r2);
dfs(l2, r);
}
void solve()
{
int n, flag = 1;
unordered_map<int, int> cnt;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].num;
a[i].x = a[i].num;
if (cnt[a[i].num] == 2)
flag = 0;
else
cnt[a[i].num] = cnt[a[i].num] + 1;
}
if (flag)
{
dfs(1, n);
cout << "YES\n";
for (int i = 1; i <= n; i++)
cout << a[i].num << " ";
}
else
cout << "NO";
cout << "\n";
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
1003-Fast Bubble Sort
题目大意:
给定任何一个长度为𝑁的数组𝐴 = (𝑎1, 𝑎2, . . . , 𝑎𝑛),令𝐵(𝐴)表示对𝐴进行一次冒泡排序之后得到的数组。令𝑛𝑢𝑚(𝐴)表示从𝐴到𝐵(𝐴)最少需要移动元素(数组区间循环移位)的次数。给定一个1 − 𝑛的排列𝑃以及𝑞组1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛,求𝑛𝑢𝑚(𝑃 [𝑙, 𝑟])
思路:
对于一个位置l,al 会被移动到在它之后的第一个大于al的位置r之前(记这个数字为极点)。相当于对区间[l,r-1]进行了一次循环左移。
因此只要求出每个数字的极点,同时用倍增来预处理每个数字之后第2n个非连续极点位置。因为一个数的极点如果就是下一个数,那么这个数的极点和下一个数的极点是相同的,因为极点构成了一个连续的区间,根据冒泡排序的原理,只需要循环移位一次。
对于一个区间的右侧剩余位置,如果存在降序子序列,那么还需要循环移位一次,因此还需要预处理每个数字之后第一个降序的位置。
求每个数字的极点可以用一个单调栈来实现。
AC代码:
#include <bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;
// st[i][k]记录ai之后的第2^k个极点位置,f[i]记录i之后第一个降序的位置
int a[N], f[N], st[N][20];
int num[N], pos[N], cnt;
void solve()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
cnt = 0;
for (int i = n; i >= 1; i--) //通过单调栈来找出每个数字的极点位置
{
while (cnt && num[cnt] < a[i])
cnt--;
if (!cnt)
st[i][0] = n + 1;
else
st[i][0] = pos[cnt];
num[++cnt] = a[i];
pos[cnt] = i;
}
st[n + 1][0] = n + 1;
f[n] = n + 1;
for (int i = n - 1; i >= 1; i--)
{ //如果一个数的极点就是下一个数,那么就将这个数的极点位置改为下一个数的极点位置
if (st[i][0] == i + 1)
{
st[i][0] = st[i + 1][0];
f[i] = f[i + 1];
}
else
f[i] = i + 1;
}
for (int k = 1; k < 20; k++)
for (int i = 1; i <= n + 1; i++)
st[i][k] = st[st[i][k - 1]][k - 1];
while (q--)
{
int l, r, ans = 0;
cin >> l >> r;
for (int i = 19; i >= 0 && l < r; i--)
{
if (st[l][i] <= r)
{
l = st[l][i];
ans += 1 << i;
}
}
if (f[l] <= r) ans++; //如果剩余的区间存在降序,则还要进行一次移位
cout << ans << "\n";
}
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
1007-Matryoshka Doll
题目链接
题目大意:
将n个数字分成k组,使得每一组中的数字之间差值不小于r,求出方案的数量(一组可以只有一个数字)。
思路:
首先把数字按升序排,对结果不会有影响。
如果已经求出前i个数字分成k组的方案数了,对于第i+1个数字,有两种选择:
- 单独成一组,相当于求前i个数字分成k-1组的方案
- 加入到前面的k组中,这时候要求出有多少组是可以加入的。
题目的限制条件: 相差不能小于r。
因此先找出有多少数字是小于第i个数字的,含有这些数字的组肯定是不能加入的。
然后发现这些数字之间的差也是小于r的,因此这些数字也不能位于同一组中,因此问题就好求了,只要将k减去这些数字的数量就是第i个数字能加入的组数。
用dp[i][j]表示把前i个数字分成j组的方案数
状态转移方程如下:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] * max(0, j - f(a[i]))
1.dp[i-1][j-1]表示第i个数字单独成一组的方案数
2.dp[i-1][j] * max(0, j - f(a[i]))表示第i个数字加到前面的j组中的方案数
f(x)表示在x之前,与x相差小于r的数字数量。
AC代码:
#include <bits/stdc++.h>
const int N = 5e3 + 5;
const int mod = 998244353;
using namespace std;
int n, k, r, a[N], f[N];
long long dp[N][N];
void solve()
{
cin >> n >> k >> r;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 2; i <= n; i++)
{
int *l = upper_bound(a + 1, a + i, a[i] - r);
f[i] = &a[i] - l;
}
for (int i = 1; i <= k; i++)
{
dp[i][i] = 1;
for (int j = i + 1; j <= n; j++)
dp[j][i] = (dp[j - 1][i - 1] + dp[j - 1][i] * max(0, i - f[j])) % mod;
}
cout << dp[n][k] << endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}