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; }
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; }
尺取, 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; }
枚举终点, 用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; }
排序, 把一条边用到极致,
以\(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; }