网站开发与客户交流,邯郸最新工程项目公示,wordpress博客文章美化,常德红网官网网站2019 ICPC Asia Yinchuan Regional
A - Girls Band Party#xff08;分组背包#xff09;
每个物品有两个标签#xff0c;名字#xff0c;颜色#xff0c;当名字是设置为奖赏时会对整体加上0.1 的贡献#xff0c;如果颜色符合要求时 会对整体加上 0.2 的的贡献
但是有…2019 ICPC Asia Yinchuan Regional
A - Girls Band Party分组背包
每个物品有两个标签名字颜色当名字是设置为奖赏时会对整体加上0.1 的贡献如果颜色符合要求时 会对整体加上 0.2 的的贡献
但是有一个限制相同名字的只能选一次我们的目的是要选出 5 个物品使得总价值最大map 映射一下然后做分组背包就好了
定义f[i][j]f[i][j]f[i][j]为装了iii个物品附加值是j10\frac{j}{10}10j时最大的价值最后再遍历一遍数组统计一下答案即可整体复杂度5×15×n×T5 \times 15 \times n \times T5×15×n×T。
#include bits/stdc.husing namespace std;const int N 1e5 10;string name[N], col[N];int power[N], f[10][20], n, tot;vectorpairint, int a[N];mapstring, 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.husing 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)(n, m, d)(n,m,d) - good当且仅当1≤ai≤m1 \leq a_i \leq m1≤ai≤mgcd(a1,a2,…,an)d\gcd(a_1, a_2, \dots, a_n) dgcd(a1,a2,…,an)d
f(q,k)f(q, k)f(q,k)是对于给定的(n,m,d)(n, m, d)(n,m,d)序列qqqf((a1,a2,…,an),k)(a1a2…an)kf((a_1, a_2, \dots, a_n), k) (a_1a_2 \dots a_n) ^ kf((a1,a2,…,an),k)(a1a2…an)k给定n,m,d,kn, m, d, kn,m,d,k要求所有的f(q,k)f(q, k)f(q,k)的和。 ∑a11m∑a21m⋯∑an1m(a1a2…an)K[gcd(a1,a2,…,an)d]dKn∑a11md∑a21md⋯∑an1md(a1a2…an)K[gcd(a1,a2,…,an)1]dkn∑k1mdkKnμ(k)(∑i1mkdik)n\sum_{a_1 1} ^{m} \sum_{a_2 1} ^{m} \dots \sum_{a_n 1} ^{m} (a_1 a_2 \dots a_n) ^ K[\gcd(a_1, a_2, \dots, a_n) d]\\ d ^ {K n} \sum_{a_1 1} ^{\frac{m}{d}} \sum_{a_2 1} ^{\frac{m}{d}} \dots \sum_{a_n 1} ^{\frac{m}{d}}(a_1a_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\\ a11∑ma21∑m⋯an1∑m(a1a2…an)K[gcd(a1,a2,…,an)d]dKna11∑dma21∑dm⋯an1∑dm(a1a2…an)K[gcd(a1,a2,…,an)1]dknk1∑dmkKnμ(k)(i1∑kdmik)n
之后只要欧拉降幂搞一搞就行了整体复杂度O(mlogm)O(\sqrt m \log m)O(mlogm)但是好像没必要直接O(mlogm)O(m \log m)O(mlogm)做就行了。
#include bits/stdc.husing 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长链剖分
给定一颗根节点为111的有nnn个节点的树点有点权aia_iaid(x,y)d(x, y)d(x,y)表示x,yx, yx,y之间的边数集合P(x,k){ay∣yisthesubtreeofxandd(x,y)≤k}P(x, k) \{a_y \mid y\ is\ the\ subtree\ of\ x\ and\ d(x, y) \leq k \}P(x,k){ay∣y is the subtree of x and d(x,y)≤k}ax∈P(x,k)a_x \in P(x, k)ax∈P(x,k)
定义一个集合的价值为加入给定一个集合{1,1,2,3}\{1, 1, 2, 3\}{1,1,2,3}则其价值为(1⊕1)2(1⊕2)2(1⊕3)2(1⊕2)2(1⊕3)2(2⊕3)227(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(1⊕1)2(1⊕2)2(1⊕3)2(1⊕2)2(1⊕3)2(2⊕3)227。
给定kkk要我们求出P(i,k),i∈[1,n]P(i, k), i \in [1, n]P(i,k),i∈[1,n]答案对2642 ^ {64}264取膜。
题目大概是要我们算这样一个东西 ∑i1n∑ji1n(ai⊕aj)2\sum_{i 1} ^{n} \sum_{j i 1} ^{n} (a_i \oplus a_j) ^ 2\\ i1∑nji1∑n(ai⊕aj)2 对二进制拆位后算贡献 ∑i1n∑ji1n((ai,0⊕aj,0)20(ai,1⊕aj,1)21⋯(ai,29⊕aj,29)229)2∑i1n∑ji1n∑k1029∑k2029(ai,k1⊕aj,k1)(ai,k2⊕aj,k2)2k1k2∑k1029∑k20292k1k2∑i1n∑jk1n[ai,k1≠aj,k1][ai,k2≠aj,k2]\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 \dots (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} \neq a_{j, k1}][a_{i, k2} \neq a_{j, k2}]\\ i1∑nji1∑n((ai,0⊕aj,0)20(ai,1⊕aj,1)21⋯(ai,29⊕aj,29)229)2i1∑nji1∑nk10∑29k20∑29(ai,k1⊕aj,k1)(ai,k2⊕aj,k2)2k1k2k10∑29k20∑292k1k2i1∑njk1∑n[ai,k1aj,k1][ai,k2aj,k2] F - Function!分类讨论
fa(x)ax(a0,a≠1)f_a(x) a ^ x(a 0, \ a \neq 1)fa(x)ax(a0, a1)我们要求∑a2n(a∑ban⌊fa−1(b)⌋⌈fb−1(a)⌉)\sum\limits_{a 2} ^{n} \left(a \sum\limits_{b a} ^{n} \lfloor f_a ^{-1}(b) \rfloor \lceil f_b ^{-1}(a) \rceil \right)a2∑n(aba∑n⌊fa−1(b)⌋⌈fb−1(a)⌉)。 ∑a2n(a∑ban⌊fa−1(b)⌋⌈fb−1(a)⌉)∑a2n(a∑ban⌊logab⌋⌈logba⌉)b≥a则有⌈logba⌉1∑a2n(a∑ban⌊logab⌋)\sum\limits_{a 2} ^{n} \left(a \sum\limits_{b a} ^{n} \lfloor f_a ^{-1}(b) \rfloor \lceil f_b ^{-1}(a) \rceil \right)\\ \sum_{a 2} ^{n} \left( a \sum_{b a} ^{n} \lfloor \log_a b \rfloor \lceil \log_b a \rceil \right)\\ b \geq a则有 \lceil \log _b a \rceil 1\\ \sum_{a 2} ^{n} \left( a \sum_{b a} ^{n} \lfloor \log_a b \rfloor\right)\\ a2∑n(aba∑n⌊fa−1(b)⌋⌈fb−1(a)⌉)a2∑n(aba∑n⌊logab⌋⌈logba⌉)b≥a则有⌈logba⌉1a2∑n(aba∑n⌊logab⌋)
且容易发现当a×ana \times a na×an时有⌊logab⌋\lfloor \log _a b \rfloor⌊logab⌋恒为111所以可以单独用公式计算。
#include bits/stdc.husing 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 );StackCharacter 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×mn \times mn×m的矩阵找到一个矩阵在这两个矩阵中都出现过输出这个矩阵的最大值。
矩阵匹配问题容易想到用悬线 DP三个数组l[i][j],r[i][j],up[i][j]l[i][j], r[i][j], up[i][j]l[i][j],r[i][j],up[i][j]分别记录从(i,j)(i, j)(i,j)点向左能到哪个位置向右能到哪个位置向上能拓展多少格。
#include bits/stdc.husing 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.husing namespace std;int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);puts(1 1 2 3 5);return 0;
}
