Codeforces Round #739 (Div. 3)

A. Dislike of Threes

找到第$k$個既不是$3$的倍數，個位數上也不是$3$的數，也已預處理然后$O(1)$輸出，也可直接$for$循環暴力。

#include <bits/stdc++.h>using namespace std;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);vector<int> a;for (int i = 1; i <= 2000; i++) {if (i % 3 == 0 || i % 10 == 3) {continue;}a.push_back(i);}int T, n;cin >> T;while (T--) {cin >> n;cout << a[n - 1] << "\n";}return 0; }

B. Who’s Opposite?

由$2\times n$個數按照順序構成一圈，$i$的對立是$i+n$，給定兩個對立的$a,b$，求$c$的對立是誰。

容易發現$abs(a?b)=n$，所以只要判斷$a,b,c$是否合法$\le 2\times n$，然后判斷$c$在前半圈還是后半圈即可。

#include <bits/stdc++.h>using namespace std;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int T;cin >> T;while (T--) {int a, b, c;cin >> a >> b >> c;if (a > b) {swap(a, b);}int haf = b - a;if (c > haf * 2 || a > haf * 2 || b > haf * 2) {puts("-1");}else {if (c > haf) {printf("%d\n", c - haf);}else {printf("%d\n", c + haf);}}}return 0; }

C. Infinity Table

可以得到，第$i$次書寫，有$2\times i?1$個數字，所以直接模擬即可，復雜度$T\sqrt{k}$，當然也可以預處理一下，然后二分$O(\sqrt{k}+T\log k)$。

#include <bits/stdc++.h>using namespace std;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int T;cin >> T;while (T--) {int n;cin >> n;for (int i = 1; ; i++) {int cur = 2 * i - 1;if (n > cur) {n -= cur;}else {if (n <= i) {printf("%d %d\n", n, i);}else {n -= i;printf("%d %d\n", i, i - n);}break;}}}return 0; }

D. Make a Power of Two

給定一個數字字符串，可以移走其中任意數字，或者在末尾添加任意數字，要求在最少的步驟將其變為$2$的冪次。

考慮得到$2^{60}$以內所有$2$的冪次數字的字符串，讓給定字符串在上面按照順序匹配，

找到能匹配上的一個最大子序列，然后計算操作次數，不斷取最小值即可，整體復雜度$O(60\times 10\times T)$。

#include <bits/stdc++.h>using namespace std;string a[60];void init() {for (int i = 0; i < 60; i++) {long long cur = 1ll << i;while (cur) {a[i] += char(cur % 10 + '0');cur /= 10;}reverse(a[i].begin(), a[i].end());} }int f(string str) {int ans = 0x3f3f3f3f;for (int i = 0; i < 60; i++) {int sum = 0, p1 = 0, p2 = 0, n = str.size(), m = a[i].size();while (p1 < n && p2 < m) {if (str[p1] == a[i][p2]) {p1++, p2++, sum++;}else {p1++;}}ans = min(ans, n - sum + m - p2);}return ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);init();int T;cin >> T;while (T--) {string str;cin >> str;cout << min(f(str), (int)str.size() + 1) << "\n";}return 0; }

E. Polycarp and String Transformation

考慮對串從后往前開始做，不難得到刪除字母的順序，我們再對字母的個數統計一下，加入字母$c$是在第$k$次刪除，總共出現了$x$次，

那么我們可以得出字母$c$在原串中出現的次數就是$\frac{x}{k}$次，通過這個，我們可以統計出原串的長度，

然后再對原串$O(不同字母個數\times lenth)$，統計模擬一下即可得到一個新的串，然后與給定串對比一下是否一樣即可。

#include <bits/stdc++.h>using namespace std;const int N = 5e5 + 10;int num[30], vis[N], len, cnt, n;char str[N];bool judge(int len) {string s;for (int i = 1; i <= len; i++) {s += str[i];}string ans = s;for (int i = 1; i <= cnt; i++) {string cur = "";for (auto it : s) {if (vis[i] == it - 'a') {continue;}cur += it;}ans += cur;s = cur;}if (n != ans.size()) {return false;}for (int i = 1; i <= n; i++) {if (str[i] != ans[i - 1]) {return false;}}return true; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int T;scanf("%d", &T);while (T--) {scanf("%s", str + 1);n = strlen(str + 1);for (int i = n; i >= 1; i--) {num[str[i] - 'a']++;if (num[str[i] - 'a'] == 1) {vis[++cnt] = str[i] - 'a';}}len = 0;reverse(vis + 1, vis + 1 + cnt);for (int i = 1; i <= cnt; i++) {len += num[vis[i]] / i;}if (judge(len)) {for (int i = 1; i <= len; i++) {putchar(str[i]);}putchar(' ');for (int i = 1; i <= cnt; i++) {putchar(char(vis[i] + 'a'));}puts("");}else {puts("-1");}for (int i = 0; i < 26; i++) {num[i] = 0;}cnt = 0;}return 0; }

F. Nearest Beautiful Number

$easyhard$的做法都是一樣的，考慮數位$dp$：

我們定義$f[i][j][k]$，表示第$i$位前已用數字的狀態是$j$，后面還剩下$k$位不同的數字可用，$j$是一個最大值為$2^{10}?1$的二進制數。

通過定義可以發現這個狀態對于不同的給定的$K$都是沒有影響的，所以可以不用每次做都去$memset$，直接$dp$即可。

或者我們可以考慮定義$f[i][j][k]$，表示第$i$位前醫用數字的狀態是$j$，總的可用的不同數位是$k$，然后根據不同的$K$去轉移也可。

最后，對于給定的$n,K$，我們先數位$dp$得到$x\le n?1$，且最多有$K$位不同的數字有多少個，然后二分數位$dp$去檢驗答案。

整體復雜度$O(T\times 10\times \log n+10\times 1024\times 10)$。

#include <bits/stdc++.h>using namespace std;int f[15][1050][15], p[15], tot, n, k;int dfs(int pos, int cur, int last, int flag, int lim) {if (last < 0) {return 0;}if (!pos) {return !lim;}if (!flag && !lim && f[pos][cur][last] != -1) {return f[pos][cur][last];}int ans = 0, nex = flag ? p[pos] : 9;for (int i = 0; i <= nex; i++) {if (lim) {if (i == 0) {ans += dfs(pos - 1, cur, last, 0, 1);}else {int mins = cur >> i & 1 ? 0 : 1;ans += dfs(pos - 1, cur | (1 << i), last - mins, flag && i == nex, 0);}}else {int mins = cur >> i & 1 ? 0 : 1;ans += dfs(pos - 1, cur | (1 << i), last - mins, flag && i == nex, 0);}}if (!flag && !lim) {f[pos][cur][last] = ans;}return ans; }int calc(int x) {tot = 0;while (x) {p[++tot] = x % 10;x /= 10;}return dfs(tot, 0, k, 1, 1); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);memset(f, -1, sizeof f);int T;scanf("%d", &T);while (T--) {scanf("%d %d", &n, &k);int cur = calc(n - 1);int l = n, r = 2000000000;while (l < r) {int mid = 1ll * l + r >> 1;if (calc(mid) > cur) {r = mid;}else {l = mid + 1;}}printf("%d\n", l);}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #739 (Div. 3)（AK实况）的全部內容，希望文章能夠幫你解決所遇到的問題。

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