Codeforces Round 924(Div.2) A~E

A.Rectangle Cutting (模拟)

题意：

给出一个长方形，通过平行于原始矩形的一条边进行切割，将该矩形切割成两个边长为整数的矩形。询问是否能通过旋转和移动这两个矩形，得到新的矩形。

分析：

可以发现拼成的新长方形一定是原长方形的一条边减半，一条边翻倍，只要判断平分切开再拼接不会是正方形即可。

代码：

#include <bits/stdc++.h>using namespace std;void solve() {int n, m;cin >> n >> m;if ((n % 2 == 0 && n / 2 != m) || (m % 2 == 0 && m / 2 != n))cout << "Yes" << endl;elsecout << "No" << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

B.Equalize (双指针)

题意：

给出一个长度为$n$的数组$a$，将一个排列加到$a$数组上之后，统计所有数字的出现次数，问怎样添加排列可以使得所有数字出现的次数中的最大值尽可能大。输出这个最大值。

分析：

元素之间差值小于$n$可以通过加上一个排列变成相同的值，将题目转化成有多少不同元素满足它们之间的差值都小于$n$。利用双指针快速计算。

代码：

#include <bits/stdc++.h>using namespace std;
set<int> s;
vector<int> a;void solve() {int n;cin >> n;s.clear();a.clear();for (int i = 0; i < n; i++) {int x;cin >> x;s.insert(x);}for (auto tmp: s)a.push_back(tmp);int maxval = 1, ans = 1, pos = 0;for (int i = 1; i < a.size(); i++) {if (a[i] - a[pos] >= n) {maxval = max(maxval, ans);while (pos < i && a[i] - a[pos] >= n)pos++;ans = i - pos + 1;} elseans++;}maxval = max(maxval, ans);cout << maxval << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

C. Physical Education Lesson (思维)

题意：

定义一个数组$a$，$a_1=1,a_2=2\dots a_k=k,a_{k+1}=k-1,a_{k+2}=k-2,\dots ,a_{2k-2}=2$，以$2k-2$为一组重复。给定$n,x$，询问使得$a[n]=x$的$k$有多少个。

分析：

$n$只有两种情况，在递增的序列上和递减的序列上，如果是递增序列那么$n-x$是$2\times k-2$的倍数，如果是递减序列，那么$n+x-2$是$2\times k-2$的倍数，求出所有可能的$k$，判断第$n$个数是否为$x$即可。

代码：

#include <bits/stdc++.h>using namespace std;void solve() {int n, x;cin >> n >> x;int l = n + x - 2;int r = n - x;set<int> s;for (int i = 1; i <= l / i; i++)if (l % i == 0) {if (i % 2 == 0 && (i + 2) / 2 >= x)s.insert(i);if ((l / i) % 2 == 0 && (l / i + 2) / 2 >= x)s.insert(l / i);}for (int i = 1; i <= r / i; i++)if (r % i == 0) {if (i % 2 == 0 && (i + 2) / 2 >= x)s.insert(i);if ((r / i) % 2 == 0 && (r / i + 2) / 2 >= x)s.insert(r / i);}cout << s.size() << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

D.Lonely Mountain Dungeons (思维)

题意：

有$n$个种族，每个种族数量为$c_i$。现在要组建军队，每对处于不同小队的同一种族的生物，都会为军队的总兵力增加$b$个单位，然而小队越多，越不好管理，$k$个小队组成的军队总兵力会减少$(k-1)\times x$。询问怎样组建军队能使得总兵力最大。

分析：

假设当前有$k$队，某个种族有$x$人，当$x\le k$时，战力会增加$C(x,2)$，当$x>k$时，会存在同一种族的人在相同的队伍中，假设有$y$人，那么需要减去$C(y,2)$。考虑到种族数量加起来为$2e5$，所以考虑暴力枚举$k$。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
const int MAXN = 2e5 + 5;
vector<LL> num(MAXN, 0);void solve() {LL n, b, x;cin >> n >> b >> x;num.clear();map<LL, LL> map1;LL maxval = 0;for (int i = 0; i < n; i++) {cin >> num[i];maxval = max(maxval, num[i]);map1[num[i]]++;}LL ans = 0;for (int i = maxval; i >= 1; i--) {LL sum = 0;for (auto tmp: map1) {LL x = tmp.first / i;LL cnt = tmp.first % i;sum += (tmp.first * (tmp.first - 1) / 2 - (cnt * (x + 1) * x / 2 + (i - cnt) * x * (x - 1) / 2)) *tmp.second;}LL tmp1 = b * sum;tmp1 -= (i - 1) * x;ans = max(ans, tmp1);}cout << ans << endl;
}int main() {int t;cin >> t;while (t--) {solve();}return 0;
}

E.Modular Sequence (dp)

题意：

给出两个整数$x,y$，询问是否存在一个序列$a$，满足$a_1=x$，$a_i=a_{i-1}+y$或者$a_i=a_{i-1}\%y$。再给定$n$和$s$，询问序列$a$的前$n$项和是否等于$s$。

分析：

可以发现序列$a$中所有数的余数都是一个固定的数字，$s$先减去这个余数，如果$s$是合法的，那么$s$一定是$y$的倍数，将$s/=y$将问题转化成$a_1=x/y,a_i=a_{i-1}+1$或者$a_i=0$。设$dp[i]$表示总和为$i$，需要的最短长度。$dp$可以用完全背包进行预处理。由于$a_1$不一定为$0$，所以需要枚举$a_1$往后加了多少位的$1$。再用$dp$判断是否有解。

代码：

#include <bits/stdc++.h>using namespace std;
const int MAXN = 2e5 + 5;
vector<int> dp(MAXN + 1, 1e9);void init() {dp[0] = 0;for (int i = 1;; i++) {int t = i * (i + 1) / 2;if (t > MAXN)break;for (int j = t; j <= MAXN; j++) {dp[j] = min(dp[j], dp[j - t] + i + 1);}}
}void solve() {int n, x, y, s;cin >> n >> x >> y >> s;int r = x % y;if (1LL * r * n > s) {cout << "NO" << endl;return;}s -= r * n;if (s % y != 0) {cout << "NO" << endl;return;}s /= y;vector<int> a(n + 1);a[1] = x / y;int pos = -1;int sum = a[1], k = a[1];for (int i = 1; i <= n && sum <= s; i++) {if (dp[s - sum] <= n - i) {pos = i;break;}k += 1;sum += k;}if (pos == -1) {cout << "NO" << endl;return;}for (int i = 2; i <= pos; i++) {a[i] = a[i - 1] + 1;}s -= sum;int minval = dp[s];for (int i = 1; s > 0; i++) {int t = i * (i + 1) / 2;while (s > 0 && dp[s - t] + i + 1 == minval) {s -= t;minval -= i + 1;for (int j = 0; j <= i; j++) {pos++;a[pos] = j;}}}cout << "YES" << endl;for (int i = 1; i <= n; i++) {cout << a[i] * y + r << " ";}cout << endl;
}int main() {init();int t;cin >> t;while (t--) {solve();}return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。