Codeforces Round 924 (Div. 2)
Codeforces Round 924 (Div. 2)
A. Rectangle Cutting
题意：给出a*b的矩形，沿着其中一个边恰好一分为二后可以组成一个新的矩形
思路：判断其中一个边是否可以被2整除以及二分后是否等于另一个边即可
AC code：
void solve() {
int a, b; cin >> a >> b;
if (a % 2 == 0 && a / 2 != b || b % 2 == 0 && b / 2 != a) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
B. Equalize
题意：给出长度为n的整数数组a，将1到n的数分别加到数组元素中，数组众数最大是多少
思路：
- 去重，因为每个数一定会加上一个不同的数，原本重复的元素一定不会贡献比1更大的答案
- 排序后找到区间极值小于n的最长连续子序列，该长度就是答案(二分or双指针均可)
AC code：
- 双指针
void solve() {
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int sz = a.size();
int l = 0, r = 0, ans = 1;
while (l <= r) {
while (a[r] - a[l] < n && r < sz) r ++;
ans = max(ans, r - l);
l ++;
}
cout << ans << endl;
}
- 二分
bool check(const vector<int> &a, int x, int len) {
for (int i = 0; i <= len - x; i ++)
if (a[i + x - 1] - a[i] < n) return true;
return false;
}
void solve() {
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
int sz = a.size();
int l = 1, r = sz;
while (l < r) {
int mid = l + r + 1 >> 1;
if(check(a, mid, sz)) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
C. Physical Education Lesson
题意：额
-
有长度为n的一排队伍，队伍的序号有个标准值k，每2*k-2重置一次序号，每段为(1,2…k,k-1,k-2…2)这样的；
-
现在当前队尾序号为x，有多少种可能的k
思路：
-
将每组2k-2看成一段上坡一段下坡，分答案在上坡和下坡的情况
-
上坡：首先最后一段一定是1~x为结尾，而前面我们假设有Y段(2k-2)，总长度为n，所以可以得到：
Y * (2 * k - 2) + x = n，即(n - x) % (2k-2) == 0 -
下坡：同理我们可以得到：
Y * (2 * k - 2) - x + 2 = n，即(n + x - 2) % (2*k-2) == 0
-
-
然后根据情况枚举因子即可，注意枚举过程可能会出现重复，所以用set来统计答案方便去重
AC code：
void solve() {
cin >> n >> x;
set<int> st;
int fr = n - x;//上坡
for (int i = 1; i <= fr / i; i ++) {
if (fr % i == 0) {
if (i % 2 == 0) {
int k = (i + 2) / 2;
if (k >= x) st.insert(k);
}
int j = fr / i + 2;
if (j % 2 == 0) {
int k = j / 2;
if (k >= x) st.insert(k);
}
}
}
int ba = n + x - 2;//下坡
for (int i = 1; i <= ba / i; i ++) {
if (ba % i == 0) {
if (i % 2 == 0) {
int k = (i + 2) / 2;
if (k >= x) st.insert(k);
}
int j = ba / i + 2;
if (j % 2 == 0) {
int k = j / 2;
if (k >= x) st.insert(k);
}
}
}
cout << st.size() << endl;
}
