2019 ICPC Asia Yinchuan Regional

A - Girls Band Party（分組背包）

每個物品有兩個標簽，名字，顏色，當名字是設置為獎賞時會對整體加上0.1 的貢獻，如果顏色符合要求時 會對整體加上 0.2 的的貢獻

但是有一個限制，相同名字的只能選一次，我們的目的是要選出 5 個物品使得總價值最大，map 映射一下，然后做分組背包就好了，

定義$f[i][j]$為裝了$i$個物品，附加值是$\frac{j}{10}$時，最大的價值，最后再遍歷一遍數組統計一下答案即可，整體復雜度$5\times 15\times n\times T$。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;string name[N], col[N];int power[N], f[10][20], n, tot;vector<pair<int, int>> a[N];map<string, int> mp, mp1;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {cin >> n;memset(f, -1, sizeof f), tot = 0;mp1.clear(), mp.clear();for (int i = 1; i <= n; i++) {cin >> name[i] >> col[i] >> power[i];if (!mp.count(name[i])) {mp[name[i]] = ++tot;a[tot].clear();}}for (int i = 1; i <= 5; i++) {string str;cin >> str;mp1[str] = 1;}string b_col;cin >> b_col;for (int i = 1; i <= n; i++) {int cur = 0;if (mp1.count(name[i])) {cur += 1;}if (col[i] == b_col) {cur += 2;}a[mp[name[i]]].push_back({power[i], cur});}f[0][0] = 0;for (int i = 1; i <= tot; i++) {for (int j = 5; j >= 1; j--) {for (int k = 15; k >= 0; k--) {for (auto it : a[i]) {if (k >= it.second && f[j - 1][k - it.second] != -1) {f[j][k] = max(f[j][k], f[j - 1][k - it.second] + it.first);}}}}}int ans = 0;for (int i = 1; i <= 5; i++) {for (int j = 0; j <= 15; j++) {ans = max(ans, f[i][j] * (10 + j) / 10);}}cout << ans << "\n";}return 0; }

B - So Easy（模擬，簽到）

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 10;int a[N][N], r[N], n, x, y;;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d", &n);for (int i = 1; i <= n; i++) {int minn = 0x3f3f3f3f;for (int j = 1; j <= n; j++) {scanf("%d", &a[i][j]);if (a[i][j] == -1) {a[i][j] = 0x3f3f3f3f;x = i, y = j;}minn = min(minn, a[i][j]);}r[i] = minn;for (int j = 1; j <= n; j++) {a[i][j] -= minn;}}int minn = 0x3f3f3f3f;for (int i = 1; i <= n; i++) {minn = min(minn, a[i][y]);}printf("%d\n", r[x] + minn);return 0; }

D - Easy Problem（莫比烏斯）

定義一個序列是$(n,m,d)$ - good，當且僅當$1\le a_i\le m$，$\gcd (a_1,a_2,\dots ,a_n)=d$，

$f(q,k)$是對于給定的$(n,m,d)$序列$q$，$f((a_1,a_2,\dots ,a_n),k)=(a_1{a}_2\dots a_n{)}^k$，給定$n,m,d,k$要求所有的$f(q,k)$的和。
$$\begin{gathered} \sum _{a_1=1}^m\sum _{a_2=1}^m?\sum _{a_n=1}^m(a_1{a}_2\dots a_n{)}^K[\gcd (a_1,a_2,\dots ,a_n)=d] \\ {d}^{Kn}\sum _{a_1=1}^{\frac{m}{d}}\sum _{a_2=1}^{\frac{m}{d}}?\sum _{a_n=1}^{\frac{m}{d}}(a_1{a}_2\dots a_n{)}^K[\gcd (a_1,a_2,\dots ,a_n)=1] \\ {d}^{kn}\sum _{k=1}^{\frac{m}{d}}{k}^{Kn}\mu (k)(\sum _{i=1}^{\frac{m}{kd}}{i}^k{)}^n \end{gathered}$$

之后只要歐拉降冪搞一搞就行了，整體復雜度$O(\sqrt{m}\log m)$，但是好像沒必要，直接$O(m\log m)$做就行了。

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e5 + 10, mod = 59964251, phi = 59870352;int mu[N], prime[N], cnt;ll m, d, k, n, sum[N];bool st[N];char str[N];ll quick_pow(ll a, int n, int mod = 59964251) {ll ans = 1;while(n) {if(n & 1) ans = ans * a % mod;a = a * a % mod;n >>= 1;}return ans; }void init() {memset(st, 0, sizeof st);cnt = 0;mu[1] = 1, sum[1] = 1;for(int i = 2; i < N; i++) {if(!st[i]) {mu[i] = -1;prime[cnt++] = i;sum[i] = quick_pow(i, k);}for(int j = 0; j < cnt && i * prime[j] < N; j++) {st[i * prime[j]] = 1;sum[i * prime[j]] = sum[i] * sum[prime[j]] % mod;if(i % prime[j] == 0) break;mu[i * prime[j]] = -mu[i];}}for(int i = 1; i < N; i++) {sum[i] = (sum[i] + sum[i - 1]) % mod;} }ll solve(ll m) {ll ans = 0;for (ll i = 1; i <= m; i++) {ans = ans + 1ll * mu[i] * quick_pow(i, k * n % phi + phi) % mod * quick_pow(sum[m / i], n + phi) % mod;}return (ans % mod + mod) % mod; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int T;scanf("%d", &T);while (T--) {scanf("%s %lld %lld %lld\n", str + 1, &m, &d, &k);init();int len = strlen(str + 1);n = 0;for (int i = 1; i <= len; i++) {n = n * 10 + str[i] - '0';n %= phi;}ll ans = quick_pow(d, k * n % phi + phi) * solve(m / d) % mod;printf("%lld\n", ans);}return 0; }

E - XOR Tree（長鏈剖分）

給定一顆根節點為$1$的有$n$個節點的樹點有點權$a_i$，$d(x,y)$表示$x,y$之間的邊數，集合$P(x,k)=\{a_y\mid yisthesubtreeofxandd(x,y)\le k\}$，$a_x\in P(x,k)$

定義一個集合的價值為，加入給定一個集合$\{1,1,2,3\}$，則其價值為$(1\oplus 1{)}^2+(1\oplus 2{)}^2+(1\oplus 3{)}^2+(1\oplus 2{)}^2+(1\oplus 3{)}^2+(2\oplus 3{)}^2=27$。

給定$k$，要我們求出$P(i,k),i\in [1,n]$，答案對$2^{64}$取膜。

題目大概是要我們算這樣一個東西：
$$\sum _{i=1}^n\sum _{j=i+1}^n(a_i\oplus a_j{)}^2$$
對二進制拆位后算貢獻：
$$\begin{gathered} \sum _{i=1}^n\sum _{j=i+1}^n{\left((a_{i,0}\oplus a_{j,0})2^0+(a_{i,1}\oplus a_{j,1})2^1+?+(a_{i,29}\oplus a_{j,29})2^{29}\right)}^2 \\ \sum _{i=1}^n\sum _{j=i+1}^n\sum _{k1=0}^{29}\sum _{k2=0}^{29}(a_{i,k_1}\oplus a_{j,k1})(a_{i,k2}\oplus a_{j,k2})2^{k1+k2} \\ \sum _{k1=0}^{29}\sum _{k2=0}^{29}{2}^{k1+k2}\sum _{i=1}^n\sum _{j=k+1}^n[a_{i,k1}=a_{j,k1}][a_{i,k2}=a_{j,k2}] \end{gathered}$$

F - Function!（分類討論）

$f_a(x)=a^x(a>0,a=1)$，我們要求$\sum _{a=2}^n\left(a\sum _{b=a}^n?f_a^{?1}(b)??f_b^{?1}(a)?\right)$。
$$\begin{gathered} \sum _{a=2}^n\left(a\sum _{b=a}^n?f_a^{?1}(b)??f_b^{?1}(a)?\right) \\ \sum _{a=2}^n\left(a\sum _{b=a}^n?{\log }_{a}b??{\log }_{b}a?\right) \\ b\ge a，則有?{\log }_{b}a?=1 \\ \sum _{a=2}^n\left(a\sum _{b=a}^n?{\log }_{a}b?\right) \end{gathered}$$

且容易發現，當$a\times a>n$時，有$?{\log }_{a}b?$恒為$1$，所以可以單獨用公式計算。

#include <bits/stdc++.h>using namespace std;const int mod = 998244353, inv2 = mod + 1 >> 1, inv6 = (mod + 1) / 6;typedef long long ll;ll calc1(ll l, ll r) {return (l + r) % mod * ((r - l + 1) % mod) % mod * inv2 % mod; }ll calc2(ll n) {n %= mod;return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ll a, n, ans = 0;cin >> n;for (a = 2; a * a <= n; a++) {for (ll l = a, r, k = 1; l <= n; l = r + 1, k++) {r = min(l * a - 1, n);int tot = (r - l + 1) % mod;ans = (ans + a * tot % mod * k % mod) % mod;}}// for (; a <= n; a++) {//原本我們是這樣算的，當時這里可以變成，自然冪次求和的形式，所以可以快速算出來。// ans = (ans + a * (n - a + 1) % mod) % mod;// }ans = (ans + (n + 1) % mod * calc1(a, n) % mod) % mod;ans = ((ans - calc2(n) + calc2(a - 1)) % mod + mod) % mod;cout << ans << "\n";return 0; }

G - Pot!!（區間最大值）

#include <bits/stdc++.h> #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;const int N = 1e5 + 10;struct Res {int a[N << 2], lazy[N << 2];void push_up(int rt) {a[rt] = max(a[ls], a[rs]);}void push_down(int rt) {if (lazy[rt]) {a[ls] += lazy[rt], a[rs] += lazy[rt];lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];lazy[rt] = 0;}}void update(int rt, int l, int r, int L, int R, int v) {if (l >= L && r <= R) {lazy[rt] += v;a[rt] += v;return ;}push_down(rt);if (L <= mid) {update(lson, L, R, v);}if (R > mid) {update(rson, L, R, v);}push_up(rt);}int query(int rt, int l, int r, int L, int R) {if (l >= L && r <= R) {return a[rt];}push_down(rt);int ans = 0;if (L <= mid) {ans = max(ans, query(lson, L, R));}if (R > mid) {ans = max(ans, query(rson, L, R));}return ans;} }a[20];int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int n, m;scanf("%d %d", &n, &m);char op[10];for (int i = 1, l, r, x; i <= m; i++) {scanf("%s %d %d", op, &l, &r);if (op[1] == 'A') {printf("ANSWER %d\n", max({a[2].query(1, 1, n, l, r), a[3].query(1, 1, n, l, r), a[5].query(1, 1, n, l, r), a[7].query(1, 1, n, l, r)}));}else {scanf("%d", &x);int v = 0;while (x % 2 == 0) {x /= 2;v++;}if (v) {a[2].update(1, 1, n, l, r, v);}v = 0;while (x % 3 == 0) {x /= 3;v++;}if (v) {a[3].update(1, 1, n, l, r, v);}v = 0;while (x % 5 == 0) {x /= 5;v++;}if (v) {a[5].update(1, 1, n, l, r, v);}v = 0;while (x % 7 == 0) {x /= 7;v++;}if (v) {a[7].update(1, 1, n, l, r, v);}}}return 0; }

I - Base62（進制轉換）

import java.math.BigInteger; import java.util.Stack; import java.util.Scanner;public class Main {private static final String TARGET_STR = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";private static final char[] chs = TARGET_STR.toCharArray();private static final BigInteger INTEGER0 = new BigInteger("0");public static String numToRadix(String number, int radix) {if(radix < 0 || radix > TARGET_STR.length()){radix = TARGET_STR.length();}BigInteger bigNumber = new BigInteger(number);BigInteger bigRadix = new BigInteger(radix + "");Stack<Character> stack = new Stack<>();StringBuilder result = new StringBuilder(0);while (!bigNumber.equals(INTEGER0)) {stack.add(chs[bigNumber.remainder(bigRadix).intValue()]);bigNumber = bigNumber.divide(bigRadix);}for (; !stack.isEmpty(); ) {result.append(stack.pop());}return result.length() == 0 ? "0" : result.toString();}public static String radixToNum(String number, int radix){if(radix < 0 || radix > TARGET_STR.length()){radix = TARGET_STR.length();}if (radix == 10) {return number;}char ch[] = number.toCharArray();int len = ch.length;BigInteger bigRadix = new BigInteger(radix + "");BigInteger result = new BigInteger("0");BigInteger base = new BigInteger("1");for (int i = len - 1; i >= 0; i--) {BigInteger index = new BigInteger(TARGET_STR.indexOf(ch[i]) + "");result = result.add(index.multiply(base)) ;base = base.multiply(bigRadix);}return result.toString();}public static String transRadix(String num, int fromRadix, int toRadix) {return numToRadix(radixToNum(num, fromRadix), toRadix);}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int x = cin.nextInt();int y = cin.nextInt();String s = cin.next(); System.out.println(Main.transRadix(s, x, y));} }

K - Largest Common Submatrix（懸線 DP）

給定兩個$n\times m$的矩陣，找到一個矩陣，在這兩個矩陣中都出現過，輸出這個矩陣的最大值。

矩陣匹配問題，容易想到用懸線 DP，三個數組$l[i][j],r[i][j],up[i][j]$，分別記錄，從$(i,j)$點向左能到哪個位置，向右能到哪個位置，向上能拓展多少格。

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 10;int a[N][N], b[N][N], l[N][N], r[N][N], up[N][N], X[N * N], Y[N * N], n, m;int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &a[i][j]);l[i][j] = r[i][j] = j, up[i][j] = 1;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &b[i][j]);X[b[i][j]] = i, Y[b[i][j]] = j;}}for (int i = 1; i <= n; i++) {for (int j = 2; j <= m; j++) {if (a[i][j - 1] == b[X[a[i][j]]][Y[a[i][j]] - 1]) {l[i][j] = l[i][j - 1];}}for (int j = m - 1; j >= 1; j--) {if (a[i][j + 1] == b[X[a[i][j]]][Y[a[i][j]] + 1]) {r[i][j] = r[i][j + 1];}}}int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (i > 1 && a[i - 1][j] == b[X[a[i][j]] - 1][Y[a[i][j]]]) {up[i][j] = up[i - 1][j] + 1;l[i][j] = max(l[i][j], l[i - 1][j]);r[i][j] = min(r[i][j], r[i - 1][j]);}ans = max(ans, (r[i][j] - l[i][j] + 1) * up[i][j]);}}printf("%d\n", ans);return 0; }

N - Fibonacci Sequence（簽到）

#include <bits/stdc++.h>using namespace std;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);puts("1 1 2 3 5");return 0; }

總結

以上是生活随笔為你收集整理的2019 ICPC Asia Yinchuan Regional（9 / 13）的全部內容，希望文章能夠幫你解決所遇到的問題。

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