小明の雜貨鋪

發表於2024-12-03|更新於2024-12-03|日記主机註記|小明•主机

第 43 周主机註記月曜日 (Dec.2) 火曜日 (Dec.3) 水曜日 (Dec.4) 木曜日 (Dec.5) 金曜日 (Dec.6) 土曜日 (Dec.7) 日曜日 (Dec.8)

發表於2024-12-03|更新於2024-12-03|筆記練習賽|ACM•算法•筆記•題解•練習賽

2042A - Greedy Monocarp 123456789101112131415161718192021222324252627282930#include <bits/stdc++.h>using namespace std;int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end(), greater<>()); for (int i = 0; i < n; i++) { if (a[i] <= k)...

Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)

發表於2024-12-02|更新於2024-12-02|筆記練習賽|ACM•算法•筆記•題解•練習賽

2034A - King Keykhosrow’s Mystery 虽然是 A 题，也简单写个证明：由题意，m mod a=m mod bm \bmod a = m \bmod bmmoda=mmodb，设 m=ta+r=kb+rm = ta + r = kb + rm=ta+r=kb+r，则 ta=kbta = kbta=kb。希望 t,k,rt,k,rt,k,r 尽可能小，则 r=0r = 0r=0。再设 gcd⁡(a,b)=d, a=a0d, b=b0d\gcd(a,b) = d,\ a = a_{0}d,\ b = b_{0}dgcd(a,b)=d, a=a0d, b=b0d，则 ta0=kb0ta_{0} = kb_{0}ta0=kb0，由于 a0,b0a_{0},b_{0}a0,b0 互素，只能取 t=b0t = b_{0}t=b0，此时 m=ta=b0a=lcm⁡(a,b)m = ta = b_{0}a = \operatorname{lcm}(a, b)m=ta=b0a=lcm(a,b)。不要按题意暴力，会...