Codeforces Round #643 (Div. 2)

Sequence with Digits

思路

一道暴力題，猜想在某一步一定會出現0，于是懷著忐忑提交了代碼，結果還真的是這樣。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;ll judge(ll x) {int minn = x % 10, maxn = x % 10;ll temp = x;temp /= 10;while(temp) {minn = min(int(temp % 10), minn);maxn = max(int(temp % 10), maxn);temp /= 10;}return x + minn * maxn; }int main() {// freopen("in.txt", "r", stdin);int t;scanf("%d", &t);while(t--) {ll ans, n;scanf("%lld %lld", &ans, &n);for(ll i = 0; i < n - 1; i++) {ll temp = judge(ans);if(temp == ans) break;ans = temp;}printf("%lld\n", ans);}return 0; }

Young Explorers

思路

應該是一個貪心吧。

題意是對于一個分數為$e$的選手，只能加入人數大于等于$e$的組里，所以我們取每一組的最大值剛好等于其人數，這樣就最大化的利用了所有的人，當然進行這一步之前必須得先排序。

代碼

#include <bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long ll;const int N = 2e5 + 10;int a[N];int main() {// freopen("in.txt", "r", stdin);IOS;int t;cin >> t;// scanf("%d", &t);while(t--) {int n;cin >> n;for(int i = 0; i < n; i++)cin >> a[i];int sum = 0, ans = 0;sort(a, a + n);for(int i = 0; i < n; i++) {sum++;if(a[i] <= sum) {sum = 0;ans++;}}cout << ans << "\n";}return 0; }

Count Triangles

思路

這題是看了別人的思路才寫出來的，我一開始一直在枚舉$z$邊試圖去找另外兩條邊的范圍，但是一直wa。

• 我們考慮枚舉$x+y$的范圍， $min(c+1,a+b)<=i<=b+c$。
• 通過x的最大值我們可以確定y的最小值，同時我們也可以通過x的最小值確定y的最大值。

當$x=a$，最大的$y_{max}=min(i?a,c)$，當$y=b$，最大的$x_{max}=min(i?b,b)$

通過這個我們可以鎖定任意的真正的最小的$x||y$，我們$x_{min}=i?y_{max}$，$y_{min}=i?x_{max}$

這里我們可以得到任意的一段符合條件的x，y的組合，$num=(x_{max}?x_{min}+1)=(y_{max}?y_{min}+1)$

然后$z$的取值區間長度是$long=min(d?c+1,i?c)$。

我們每次枚舉的區間答案就是$ans+=num?long$

代碼

#include <bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long ll;int main() {// freopen("in.txt", "r", stdin);IOS;ll a, b, c, d, ans = 0;cin >> a >> b >> c >> d;for(int i = max(a + b, c + 1); i <= b + c; i++) {int x = min(i - b, b), y = min(i - a, c);x = i - x;ll l = min(i - c, d - c + 1);ans += l * (y - x + 1);}cout << ans << "\n";return 0; }

Game With Array

思路

一道構造題，這題應該是比較好想的，當$2?n>s$的時候，我們至少會出現兩個一，然后剩下的全是2，這里我們顯然可以得到我們所需要的和為$s$的所有二進制數，所以這個是侯一定是不可能有解的。

當$2?n<=s$的時候我們如何構造，只需要取$n?1$個一，然后最后一個數是$s?n+1$就行了，最后的$k$取$n$這樣就可以保證答案的有解性。

代碼

#include <bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) typedef long long ll;int main() {// freopen("in.txt", "r", stdin);IOS;int n, s;cin >> n >> s;if(2 * n > s) cout << "NO\n";else {cout << "YES\n";for(int i = 0; i < n - 1; i++)cout << "1 ";cout << s - (n - 1) << "\n";cout << n << "\n";}// int t;// cin >> t;// // scanf("%d", &t);// while(t--) {// }return 0; }

Restorer Distance

思路

因為push和move這兩個操作，我們比較容易發現這兩個操作好像在最大值最小值兩頭是等價的，因此當在最大最小值中間可能存在一個最優值，使操作成本最低。

通過上面的分析我們可以大致的得到這是一個凹函數，并且存在最極小值，因此我們可以考慮三分去的到這個最小值。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10;int a[N], n, A, R, M;ll f(int x) {ll sum1 = 0, sum2 = 0;//分別記錄大于當前值的數量，和小于當前值的數量。for(int i = 1; i <= n; i++) {if(a[i] > x) sum1 += a[i] - x;else if(a[i] < x) sum2 += x - a[i];}ll ans = 0;ll mid = min(sum2, sum1);ans += mid * M;sum1 -= mid, sum2 -= mid;//優先考慮從一個移到另一個上。if(sum1) ans += sum1 * R;if(sum2) ans += sum2 * A;return ans; }int main() {// freopen("in.txt", "r", stdin);scanf("%d %d %d %d", &n, &A, &R, &M);M = min(M, A + R);//這個操作可以等同是前兩個操作的和，取一個最小值。for(int i = 1; i <= n; i++)scanf("%d", &a[i]);int l = 0, r = 1e9;while(l < r) {int lmid = l + (r - l) / 3;int rmid = r - (r - l) / 3;if(f(lmid) >= f(rmid)) l = lmid + 1;else r = rmid - 1;}printf("%lld\n", min(f(l), f(r)));return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #643 (Div. 2)(A, B, C, D, E)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。