代碼源周賽 Round 11 題解
A. [R11A]出現(xiàn)奇數(shù)次的偶數(shù)
我們開一個 map 記錄每個數(shù)的出現(xiàn)次數(shù)。
把數(shù)組遍歷一遍看一個數(shù)如果又是偶數(shù)出現(xiàn)次數(shù)又是奇數(shù)就更新答案，最后輸出即可。
預(yù)計(jì)時間 \(\le 1min\)。
B. [R11B]前三小
我們記錄二元組 \((x,y)\) 表示第 \(x\) 個數(shù)出現(xiàn)位置是 \(y\)。按照 \(x\) 排序后取前三個再按 \(y\) 排序即可。
預(yù)計(jì)時間 \(\le 2min\)。
C. [R11C]勻加速運(yùn)動
分類討論是否到達(dá)最大速度，開 double 套公式即可，注意 cout<<fixed<<setprecision(n) 可以保留 \(n\) 位小數(shù)。
D. [R11D]山谷數(shù)
同見：數(shù)位 DP 的技巧 的特別情況。
注意到答案很小。我們可以把所有符合條件的數(shù)求出來排序，再二分 \(l,r\) 內(nèi)最小和最大符合條件的數(shù)在排序后數(shù)組里的位置相減加上一即可。
具體構(gòu)造方法，先枚舉長度，然后枚舉最小的數(shù)的位置和值，然后朝兩邊 DFS 回溯決定各個位數(shù)即可，注意排除不合法狀態(tài)。
代碼：
#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
vector<int> ans;
map<int, int> ha;
int a[20];
void dfs(int u, int op, int len, int last, int gu) {
if (!u) {
int now = 0;
upp(i, 1, len) {
now *= 10;
now += a[i];
}
ans.push_back(now);
return;
}
if (!op) {
upp(i, last + 1, 9 - (len - u + 1) + 1) {
if (u != len) {
a[u] = i;
dfs(u + 1, op, len, i, gu);
} else {
if (a[gu] + gu - 1 > i) continue;
a[u] = i;
dfs(gu - 1, i, len, a[gu], gu);
}
}
} else {
upp(i, last + 1, op - u + 1) {
if (u != 1) {
a[u] = i;
dfs(u - 1, op, len, i, gu);
} else {
a[u] = op;
dfs(u - 1, op, len, op, gu);
break;
}
}
}
}
void init() {
upp(len, 1, 18) {
upp(j, 2, len - 1) {
upp(k, 0, 9) {
if (k + j - 1 > 9 || k + (len - j) > 9) continue;
a[j] = k;
dfs(j + 1, 0, len, k, j);
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
sort(ans.begin(), ans.end());
int qq;
cin >> qq;
upp(i, 1, qq) {
int l, r;
cin >> l >> r;
cout << upper_bound(ans.begin(), ans.end(), r) -
lower_bound(ans.begin(), ans.end(), l)
<< endl;
}
return 0;
}
E. [R11E]波浪數(shù)
同見：數(shù)位 DP 的技巧。
-
一個數(shù)貢獻(xiàn)的條件是為波浪數(shù)，波浪數(shù)說白了就是一上一下，記錄這次應(yīng)該是上還是下或者還未決定 \(go=1/0/2\)。如果還未決定，我們就可以填上繼續(xù) \(0\)，或者填上一個正數(shù)，然后決定上下是 \(0/1\) 各繼續(xù)計(jì)算，注意如果 \(pos=1\) 的時候，上和下都會只取到一個數(shù)，為了保證不重不漏，我們只再計(jì)算其中一種情況即可。對于之前就已經(jīng)決定是上還是下，我們直接枚舉數(shù)就行了，為了保證上下我們記錄狀態(tài) \(last\) 表示上一個填的數(shù)，沒什么好講的。
-
所有數(shù)的貢獻(xiàn)都為 \(1\)。
-
所有狀態(tài)為 \(pos,lim,go,last\)。
代碼：
#include <bits/stdc++.h>
#define int long long
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 10, X = 998244353;
int f[N][3][10], a[N];
int dfs(int pos, bool lim, int go, int last) { // 0 代表降
if (f[pos][go][last] != -1 && lim == 0) return f[pos][go][last];
if (!pos) return 1;
int res = 0, up = (lim ? a[pos] : 9);
if (go == 2) {
upp(i, 0, up) {
if (i) {
if (pos > 1)
(res += dfs(pos - 1, (lim && i == a[pos]), 1, i)) %= X;
(res += dfs(pos - 1, (lim && i == a[pos]), 0, i)) %= X;
} else
(res += dfs(pos - 1, (lim && i == a[pos]), go, last)) %= X;
}
} else if (go == 1) {
upp(i, last + 1, up) {
(res += dfs(pos - 1, (lim && i == a[pos]), 0, i)) %= X;
}
} else {
upp(i, 0, min(last - 1, up)) {
(res += dfs(pos - 1, (lim && i == a[pos]), 1, i)) %= X;
}
}
if (!lim) f[pos][go][last] = res;
return res;
}
int solve(string x) {
int len = 0;
dww(i, x.size() - 1, 0) { a[++len] = x[i] - '0'; }
return dfs(len, 1, 2, 0);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(f, -1, sizeof f);
int qq;
cin >> qq;
while (qq--) {
string l, r;
cin >> l >> r;
int ans = ((solve(r) - solve(l)) % X + X) % X;
int now = 2, flag = 1;
upp(i, 1, (int)l.size() - 1) {
if (l[i] == l[i - 1]) {
flag = 0;
break;
}
if (now == 2) {
if (l[i] > l[i - 1])
now = 0;
else
now = 1;
} else {
if (now && l[i] < l[i - 1]) {
flag = 0;
break;
}
if (!now && l[i] > l[i - 1]) {
flag = 0;
break;
}
now ^= 1;
}
}
if (flag || l.size() == 1) ans++;
cout << ans % X << endl;
}
return 0;
}
F. [R11F]二維gcd和 2
參考洛谷 P2303 [SDOI2012] Longge 的問題。這題我們可以直接枚舉對答案的貢獻(xiàn) \(\gcd\)。
具體來說，就是當(dāng)兩數(shù) \(i,j\) 的最大公約數(shù)為 \(x\) 的時候，\(\frac{i}{x}\) 和 \(\frac{j}{x}\) 互質(zhì)。因此，我們就可以枚舉這個 \(x\)，統(tǒng)計(jì)它對答案貢獻(xiàn)了多少次，就可以把原式變成下面這樣。
因?yàn)?\(i,j\) 必須為 \(k\) 的倍數(shù)，所以我們直接枚舉是 \(k\) 的幾倍，也就是 \(p,q\)，這時候 \(\frac{i}{k}=p,\frac{j}{k}=q\)。
為了把式子轉(zhuǎn)化成歐拉函數(shù)，我們做這樣的變換。
這是因?yàn)閷τ趯τ?\(p,q\) 都從 \(1\) 取到 \(n\) 的時候，一個 \((x,y)(x<y)\) 會被取兩次，即 \((p=x,q=y),(p=y,q=x)\)。而 \((x,x)\) 只會被取一次，當(dāng) \(x=1\) 時，貢獻(xiàn)為 \(1\)，否則貢獻(xiàn)為 \(0\)。
現(xiàn)在變成這樣。
很明顯，時間復(fù)雜度為調(diào)和級數(shù)，所以這個時間復(fù)雜度是 \(O(n\log n)\) 的。
發(fā)現(xiàn)我們要查詢的 \(\varphi\) 和都是一段，于是我們直接做前綴和，令 \(\displaystyle g(x)=\sum_{i=1}^{x} \varphi(i)\)。
答案表示為：
直接預(yù)處理 \(O(n)\) 即可計(jì)算。
其實(shí)注意到 \(g(x)\) 函數(shù)的自變量是一個分式，所以取值不多，我們可以數(shù)論分塊做到 \(O(\sqrt{n})\) 解決該問題，不過這題 \(O(n)\) 足矣。
代碼：
#include <bits/stdc++.h>
#define upp(a, x, y) for (int a = x; a <= y; a++)
#define dww(a, x, y) for (int a = x; a >= y; a--)
#define pb(x) push_back(x)
#define endl '\n'
#define x first
#define y second
#define PII pair<int, int>
using namespace std;
const int EU = 5e7 + 10, X = 998244353;
int st[EU], phi[EU], sumphi[EU];
int prs[EU],top;
void init(int n) {
phi[1] = 1;
upp(i, 2, n) {
if (!st[i]) {
prs[top++]=i;
phi[i] = i - 1;
}
for (int j = 0; prs[j] <= n / i; j++) {
st[i * prs[j]] = 1;
if (i % prs[j] == 0) {
phi[i * prs[j]] = prs[j] * phi[i];
break;
} else
phi[i * prs[j]] = (prs[j] - 1) * phi[i];
}
}
upp(i, 1, n) sumphi[i] = (sumphi[i - 1] + phi[i]) % X;
return;
}
int n, ans;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
init(n);
upp(k, 1, n) {
ans = ((ans + (2 * (long long)k * sumphi[n / k]) % X - k) % X + X) % X;
}
cout << ans << endl;
return 0;
}
浙公網(wǎng)安備 33010602011771號