AtCoder Beginner Contest 210
A - Cabbages
int main() {
IOS;
ll n, a, x, y, ans = 0;
cin >> n >> a >> x >> y;
if (n > a)
ans = a * x + (n - a) * y;
else
ans = n * x;
cout << ans;
return 0;
}
B - Bouzu Mekuri
int main() {
IOS;
cin >> n;
string s; cin >> s;
for (int i = 0; i < n; ++i)
if (s[i] == '1')
return cout << (i & 1 ? "Aoki" : "Takahashi"), 0;
return 0;
}
C - Colorful Candies
尺取, set维护
int main() {
IOS;
cin >> n >> k;
VI a(n);
map<int, int> st;
for (int i = 0, j = 0; i < n; ++i) {
cin >> a[i];
++st[a[i]];
if (i - j + 1 > k) {
--st[a[j]];
if (!st[a[j]])
st.erase(a[j]);
++j;
}
umax(m, st.size());
}
cout << m;
return 0;
}
D - National Railway
枚举终点, 用multiset维护已经枚举过的点(用来当起点)
int main() {
IOS;
ll ans = 2e17;
cin >> n >> m >> k;
vector<ll> a(m, 1e15);
for (int i = 0; i < n; ++i) {
multiset<ll> x, y;
for (int j = 0; j < m; ++j) {
a[j] += k;
y.insert(a[j] + (ll)j * k);
}
for (int j = 0; j < m; ++j) {
ll cur; cin >> cur;
if (x.empty())
umin(ans, cur + *y.begin() - (ll)j * k);
else
umin(ans, min(*y.begin() - (ll)j * k, *x.begin() - (ll)(m - j) * k) + cur);
y.erase(y.find(a[j] + (ll)j * k));
umin(a[j], cur);
x.insert(a[j] + (ll)(m - j) * k);
}
}
cout << ans;
return 0;
}
E - Ring MST
排序, 把一条边用到极致,
以\(0, 1, 2, 3, ...\)为根, 找模\(a_i\)的群即可, 也就是点集
\({x, (k + a_i) \ mod c_i, (x + 2 \times a_i) \ mod c_i, ..., (x + (k - 1) \times a_i) \ mod c_i}\)
其中\((x + k \times c_i) \ mod = x\)
每次将剩下的点, 用边\(i\)分割成以\(0, 1, 2, 3,..\) 为首的群, 每个群以\(1,2,3,...\) 点代表
一直循环, 直到边用完,
最后剩下的代表点只剩下一个, 即可成功
int main() {
IOS;
ll n, m, ans = 0;
cin >> n >> m;
vector<pair<ll, ll>> p(m);
for (auto &i : p)
cin >> i.second >> i.first;
sort(p.begin(), p.end());
for (auto &i : p) {
ll tmp = __gcd(n, i.second);
ans += (n - tmp) * i.first;
n = tmp;
}
cout << (n ^ 1 ? -1 : ans);
return 0;
}