GoodBye 2018(a.k.a Codeforces 1091) A~E
0000 先bb幾句
幾個大作業一寫，各種網課一補，又是一個月沒做題……cf換了新號，其實已經打了兩場比賽了，但是由於時間的因素，就從2018年的最後一場比賽開始補題吧。1月17號LoliconAutomaton的期末考試就結束了，，，
0001 Problem - A - Codeforces
題意：給你黃藍紅三種顏色的材料，分別有 個。要求最後選出來的顏色
，
，然後最大化
題解：打比賽的時候日常智熄想寫非常多個if-else，直接導致別人一分鐘過的sb題我八分鐘才過……其實就是取min，然後判斷一下就可以了
#include <bits/stdc++.h>
#define N 100100
#define eps 1e-6
using namespace std;
typedef long long ll;
int y, b, r;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> y >> b >> r;
int ret = r;
if (ret > b + 1) ret = b + 1;
else b = ret - 1;
if (b > y + 1) b = y + 1;
else y = b - 1;
if (ret > b + 1) ret = b + 1;
else b = ret - 1;
ret += b + y;
cout << ret << endl;
return 0;
}
0010 Problem - B - Codeforces
題意：沒看懂，給一堆向量，然後幹啥啥的
題解：雖然我沒看懂題目，但是我注意到答案就是所有坐標和/n，然後……
居然活到了system test……我那個room的選手怕是都和我一樣智熄了
在等rating change的時候翻看vfk的《一場cf的臺前幕後》，看到了下面這段：
「
Codeforces出題人的自我修養：
1. .......
17.如果需要long long，請確保不開long long的人不能pretest passed
」
覺得那個時候的cf真友好……後來聽說只有這一種做法要開long long……早知道給自己改個和fst有關的名字了
#include <bits/stdc++.h>
#define N 1000100
#define eps 1e-6
#define pmod 998244353
using namespace std;
typedef long long ll;
int n;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
ll sum_x = 0, sum_y = 0;
for (int i = 1; i <= (n << 1); ++i) {
long long x, y;
cin >> x >> y;
sum_x += x, sum_y += y;
}
sum_x /= (1LL * n), sum_y /= (1LL * n);
cout << sum_x << " " << sum_y << endl;
return 0;
}
0011 Problem - C - Codeforces
題意：給你一個環，現在以步長 在環上跳躍，得到
，然後把經過的所有的數加起來，得到一個和，最後輸出所有不同的和
題解：能跳回 的所有不同的步長肯定是
的約數（和別人py了一波BC，逃），然後我再次智熄，直接寫了個模擬T了還以為是分解因數複雜度大了……因為是約數，所以肯定是恰好轉一週回到
的，那麼用等差數列求和就行了……然後推公式推了10min……令人智熄的cf
#include <bits/stdc++.h>
#define N 100100
#define eps 1e-6
using namespace std;
typedef long long ll;
int n;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<ll> fact, ans;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
if (i * i == n)
fact.emplace_back(i);
else {
fact.emplace_back(i);
fact.emplace_back(n / i);
}
}
}
for (auto x : fact) {
ll num = (n - 1) / x;
ll lst = 1 + 1LL * num * x;
ll ret = 1LL * (1 + lst) * (num + 1) / 2;
ans.emplace_back(ret);
}
sort(ans.begin(), ans.end());
for (auto x : ans) cout << x << " ";
cout << endl;
return 0;
}
0100 Problem - D - Codeforces
題意：把 的所有排列按照字典序寫在一起，問你有多少段長度是
的區間恰好是
的一個排列
題解：再次死於數學差……樣例二就走眼了沒數出來，後來對著 的表看了20min沒找出規律，看了一眼題解提到一個遞推公式
很不幸的發現當時我一直沒有湊出來的那一項是
，，，然後NWPU_zhaoyiping也打了一張表
告訴我了一個很神奇的東西……另外xyz大爺也給出了他的公式（硬核啊……）：
出題人給的公式是求了答案的補集：
#include <bits/stdc++.h>
#define N 1000100
#define eps 1e-6
#define pmod 998244353
using namespace std;
typedef long long ll;
int n;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
if (n == 1) {
cout << 1 << endl;
return 0;
}
ll minus = 2, fact = 1;
for (int i = 1; i <= n; ++i) fact = fact * i % pmod;
for (int i = 3; i <= n; ++i) minus = 1LL * i * (minus + 1) % pmod;
ll ret = (fact * n % pmod - minus + pmod) % pmod;
cout << ret << endl;
return 0;
}
0101 Problem - E - Codeforces
題意：有一張 個點的圖，給你另外
個點的度數，問你第
個點度數所有可能的取值
題解：出題人把題解放進了題目裏給的鏈接……
Erd?s-Gallai theorem核心是定理中的公式： ，這個公式直接去計算是
的，因此我們需要想個快速維護的方法
事實上我們注意到左邊可以用前綴和快速維護，而右邊的求和一定是後綴和加上一段連續的 ，位置可以利用二分查找得到。然後那天_rqy在UOJ羣裏說了一下做法，大概就是枚舉每一個位置，然後可以求出一個上下界，合併這些上下界，然後答案要麼就全都是奇數要麼就全都是偶數（定理內容），直接枚舉就可以了。也就是：
#include <bits/stdc++.h>
#define N 500100
#define eps 1e-6
#define pmod 998244353
using namespace std;
typedef long long ll;
struct cmp { inline bool operator()(const int& a, const int& b) const { return a > b; } };
int n, d[N], inc[N];
ll pre[N], suf[N], low[N], high[N];
inline ll calc(int i, int k) {
int x = upper_bound(inc + 1, inc + n + 1, k) - inc;
int p = max(i, n - x + 2);
return 1LL * (p - i) * k + suf[p];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> d[i];
inc[i] = d[i];
}
sort(inc + 1, inc + n + 1);
sort(d + 1, d + n + 1, cmp());
pre[0] = suf[n + 1] = 0;
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + d[i];
for (int i = n; i; --i) suf[i] = suf[i + 1] + d[i];
for (int i = 1; i <= n; ++i) {
low[i] = pre[i] - 1LL * i * (i - 1) - calc(i + 1, i);
high[i] = 1LL * i * (i + 1) + calc(i + 1, i + 1) - pre[i];
}
low[0] = 0, high[n + 1] = n + 1;
for (int i = 1; i <= n; ++i) low[i] = max(low[i] ,low[i - 1]);
for (int i = n; i; --i) high[i] = min(high[i], high[i + 1]);
vector<int> ret;
int deg;
if (pre[n] & 1) deg = 1;
else deg = 0;
for (int candidate = deg; candidate <= n; candidate += 2) {
int x = upper_bound(inc + 1, inc+ n + 1, candidate) - inc;
int p = n - x + 2;
if (low[p - 1] > candidate) continue;
if (high[p] < candidate) continue;
if (pre[p - 1] + candidate > 1LL * p * (p - 1) + calc(p, p)) continue;
ret.emplace_back(candidate);
}
if (ret.empty()) cout << -1 << endl;
else {
for (auto x : ret) cout << x << " ";
cout << endl;
}
return 0;
}
看_rqy的題解好像還能處理地更精細一點
0110 再bb幾句
後面幾個題佔坑待補吧，主要是F題沒看懂出題人的貪心策略，然後聽說G是個交互，之前UOJ Easy Round #8被那個交互題噁心到了……實在是不想做
感想的話就是 死 於 數 學 差，以及各種智熄
推薦閱讀：
