https://ac.nowcoder.com/acm/contest/3979
题解 https://ac.nowcoder.com/discuss/363319?type=101&order=0&pos=18&page=1
A. 期望逆序对
题意:有n个随机数,给出各自的随机区间,现在要求对这些区间重新排列,使得这些随机数形成的逆序对期望最小,求期望值。
按照中点从小到大排序后,n 2 n^2 n 2 遍历所有区间,两个区间形成逆序对的概率为1 l e n 1 ⋅ ∑ i = l 1 r 1 g ( i ) l e n 2 \frac{1}{len_1}\cdot \sum_{i=l_1}^{r_1}\frac{g(i)}{len_2} l e n 1 1 ⋅ ∑ i = l 1 r 1 l e n 2 g ( i )
其中 g ( i ) g(i) g ( i ) 为 区间2 中小于 i i i 的部分的长度,这里就是要分类讨论的地方了。
g ( i ) = ∑ i = m a x ( l 1 , l 2 ) m i n ( r 1 , r 2 ) ( i − l 2 ) + ∑ i = m i n ( r 1 , r 2 ) r 2 l e n 2 g(i)=\sum_{i=max(l_1,l_2)}^{min(r_1,r_2)}(i-l_2)+\sum_{i=min(r_1,r_2)}^{r_2}len_2 g ( i ) = ∑ i = ma x ( l 1 , l 2 ) min ( r 1 , r 2 ) ( i − l 2 ) + ∑ i = min ( r 1 , r 2 ) r 2 l e n 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<ll, ll> pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 10 ;const int mod = 998244353 ;int n;pii a[maxn]; bool cmp (const pii& a, const pii& b) { return (a.first + a.second)*0.5 < (b.first + b.second)*0.5 ; } inline ll ksm (ll a, ll b) { ll ret = 1 ; a %= mod; while (b) { if (b & 1 )ret = (ret*a) % mod; a = (a*a) % mod; b >>= 1 ; } return ret; } ll ans; ll inv[maxn]; int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%lld%lld" , &a[i].first, &a[i].second); sort (a + 1 , a + n + 1 , cmp); for (int i = 1 ; i <= n; i++) inv[i] = ksm (a[i].second - a[i].first + 1 , mod - 2 ); for (int i = 1 ; i <= n; i++) { for (int j = i + 1 ; j <= n; j++) { if (a[i].second <= a[j].first)continue ; ll tmp = inv[i] * inv[j] % mod; ll l = max (a[i].first, a[j].first), r = min (a[i].second, a[j].second); ll res = (l - a[j].first + r - a[j].first)*(r - l + 1 ) / 2 % mod; res = (res + (a[i].second - r)*(a[j].second - a[j].first + 1 ) % mod) % mod; res = res * tmp % mod; ans = (ans + res) % mod; } } printf ("%lld\n" , ans); return 0 ; }
B. 密码学
题意:给出一些字符串,每次用一个字符串加密另一个,给出每次操作和最终的字符串。要求还原字符串。
由于是取mod加密,所以直接倒着解密即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 3e5 + 10 ;int n, m;string s[maxn]; stack<pii>st; int id (char c) { return c <= 'Z' ? (26 + c - 'A' ) : (c - 'a' ); } char ck (int x) { return x < 26 ? ('a' + x) : ('A' + x - 26 ); } int main () { scanf ("%d%d" , &n, &m); for (int i = 0 ; i < m; i++) { int x, y; scanf ("%d%d" , &x, &y); st.push (pii (x, y)); } for (int i = 1 ; i <= n; i++)cin >> s[i]; while (!st.empty ()) { int x = st.top ().first, y = st.top ().second; st.pop (); int p = s[x].length (), q = s[y].length (); for (int i = 0 ; i < q; i++) { s[y][i] = ck ((id (s[y][i]) + 52 - id (s[x][i%p])) % 52 ); } } for (int i = 1 ; i <= n; i++)cout << s[i] << endl; return 0 ; }
C. 染色图
题意:假设一张图是K可染色的,即点染色为1到K,相邻点颜色不同。现在给出点个数 n n n ,K K K 从 l l l 到 r r r 。g ( n , k ) g(n,k) g ( n , k ) 表示共 n n n 个点,可 k k k 染色的图的最多边数。求 ∑ k = l r g ( n , k ) \sum_{k=l}^r g(n,k) ∑ k = l r g ( n , k ) 。
先考虑 k k k 固定的情况,则把所有点平均分为 k k k 个点集,所有不在同一点集的点两两连边,这样的边数一定是最多的。
可以得到 g ( n , k ) = 1 2 [ ( n % k ) ⋅ ⌈ n k ⌉ ⋅ ( n − ⌈ n k ⌉ ) + ( k − n % k ) ⋅ ⌊ n k ⌋ ⋅ ( n − ⌊ n k ⌋ ) ] g(n,k)=\frac{1}{2}[(n\%k) \cdot \lceil\frac{n}{k}\rceil \cdot (n-\lceil\frac{n}{k}\rceil)+(k-n\%k) \cdot \lfloor\frac{n}{k}\rfloor \cdot (n-\lfloor\frac{n}{k}\rfloor)] g ( n , k ) = 2 1 [( n % k ) ⋅ ⌈ k n ⌉ ⋅ ( n − ⌈ k n ⌉) + ( k − n % k ) ⋅ ⌊ k n ⌋ ⋅ ( n − ⌊ k n ⌋)]
设 x = ⌊ n k ⌋ x=\lfloor\frac{n}{k}\rfloor x = ⌊ k n ⌋
化简为 g ( n , k ) = 1 2 [ ( n − k x ) ⋅ x ⋅ ( n − x ) + ( k − n + k x ) ⋅ x ⋅ ( n − x ) ] g(n,k)=\frac{1}{2}[(n-kx)\cdot x\cdot (n-x)+(k-n+kx)\cdot x\cdot (n-x)] g ( n , k ) = 2 1 [( n − k x ) ⋅ x ⋅ ( n − x ) + ( k − n + k x ) ⋅ x ⋅ ( n − x )]
再从 l l l 到 r r r 求和。
又要用到除法分块 ,之前之所以全都化为 ⌊ n k ⌋ \lfloor\frac{n}{k}\rfloor ⌊ k n ⌋ 就是为了这一步把所有 ⌊ n k ⌋ \lfloor\frac{n}{k}\rfloor ⌊ k n ⌋ 相等的 k k k 都合并到一起算,用乘法加速加法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 10 ;const ll mod = 998244353 ;const ll inv2 = (mod + 1 ) / 2 ;int T;ll n, l, r; ll solve (ll l, ll r) { ll L = l, R; ll tot = 0 ; while (L <= r) { ll x = n / L; R = min (r, n / (n / L)); tot = (tot + ((n*n%mod) - n - 2 * n%mod*x) % mod*(R - L + 1 ) % mod) % mod; tot = (tot + (x * (x + 1 ) % mod)*((L + R)*(R - L + 1 ) / 2 % mod)) % mod; L = R + 1 ; } tot = (tot + mod) % mod; return tot; } int main () { scanf ("%d" , &T); while (T--) { scanf ("%lld%lld%lld" , &n, &l, &r); ll ans = solve (l, r); ans = ans * inv2%mod; cout << ans << endl; } return 0 ; }
E. 树与路径
题意:给出一棵树,重新定义两点之间的路径为 u 到 lca 的距离乘以 v 到 lca 的距离。给出 m 对点,求以树上各个点为根时,所有 m 对点的路径值之和。
树上差分
以固定点为根时,可以 O ( m log n ) O(m\log n) O ( m log n ) 地求出,考虑如何转移。
对一条路径而言,若两个点并不是都在这条路径上,则转移后这条路径对这两点地贡献相同;若两点在一条路径上,假设向左转移,原先路径为 L ⋅ R L\cdot R L ⋅ R ,变为 A 1 = ( L − 1 ) ⋅ ( R + 1 ) = L ⋅ R + ( L − R − 1 ) = A 0 + ( L − R − 1 ) A_1=(L-1)\cdot (R+1)=L\cdot R+(L-R-1)=A_0+(L-R-1) A 1 = ( L − 1 ) ⋅ ( R + 1 ) = L ⋅ R + ( L − R − 1 ) = A 0 + ( L − R − 1 ) ,假设再向左转移,变为 ( L − 2 ) ⋅ ( R + 2 ) = L ⋅ R + 2 L − 2 R − 4 = L ⋅ R + ( L − R − 1 ) + ( L − R − 3 ) = A 1 + ( L − R − 3 ) (L-2)\cdot (R+2)=L\cdot R +2L-2R-4=L\cdot R+(L-R-1)+(L-R-3)=A_1+(L-R-3) ( L − 2 ) ⋅ ( R + 2 ) = L ⋅ R + 2 L − 2 R − 4 = L ⋅ R + ( L − R − 1 ) + ( L − R − 3 ) = A 1 + ( L − R − 3 ) 。
以此类推,转移方程 A j = A i + g ( j ) A_j=A_i+g(j) A j = A i + g ( j ) ,其中 g ( j ) g(j) g ( j ) 又是一个等差数列,公差为 2 2 2 .
所以先把 2 2 2 加入差分,再把 L − R − 1 L-R-1 L − R − 1 加入差分,最后对 2 2 2 求两次前缀和,得到 2 , 4 , 6 , ⋯ 2,4,6,\cdots 2 , 4 , 6 , ⋯ 的等差数列,加上 L − R − 1 L-R-1 L − R − 1 的前缀和,得到 g ( i ) g(i) g ( i ) ,这样就可以转移了。
调了半天,结果是求LCA前的dfs2(1,1)传成了dfs2(1,0)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 #include <bits/stdc++.h> using namespace std;#define ll long long const int maxn = 1e6 + 10 ;const int INF = 0x3f3f3f3f ;int n, m;vector<int >G[maxn]; int dep[maxn], fa[maxn], son[maxn], siz[maxn];void dfs1 (int x, int _fa) { siz[x] = 1 ; fa[x] = _fa; for (int v : G[x]) { if (v == _fa)continue ; dep[v] = dep[x] + 1 ; dfs1 (v, x); siz[x] += siz[v]; if (siz[v] > siz[son[x]])son[x] = v; } } int topf[maxn];void dfs2 (int x, int topfa) { topf[x] = topfa; if (!son[x])return ; dfs2 (son[x], topfa); for (int v : G[x]) { if (!topf[v])dfs2 (v, v); } } int LCA (int u, int v) { while (topf[u] ^ topf[v]) dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]]; return dep[u] < dep[v] ? u : v; } ll A[maxn], B[maxn]; ll ans[maxn]; void dfs3 (int u, int _fa) { for (int v : G[u]) { if (v == _fa)continue ; dfs3 (v, u); B[u] += B[v]; A[u] += A[v]; } } void dfs (int u, int _fa) { for (int v : G[u]) { if (v == _fa)continue ; dfs (v, u); B[u] += B[v]; } A[u] += B[u]; } void dfs4 (int u, int _fa) { for (int v : G[u]) { if (v == _fa)continue ; ans[v] = ans[u] + A[v]; dfs4 (v, u); } } inline int read () { char ch = getchar (); int x = 0 , f = 1 ; while (ch < '0' || ch > '9' ) { if (ch == '-' ) f = -1 ; ch = getchar (); } while ('0' <= ch && ch <= '9' ) { x = x * 10 + ch - '0' ; ch = getchar (); } return x * f; } ll tmp[maxn]; int main () { scanf ("%d%d" , &n, &m); for (int i = 1 ; i < n; i++) { int u, v; u = read (); v = read (); G[u].push_back (v); G[v].push_back (u); } dfs1 (1 , 0 ); dfs2 (1 , 1 ); for (int i = 0 ; i < m; i++) { int u, v; u = read (); v = read (); int lca = LCA (u, v); B[u] += 2 ; B[v] += 2 ; B[lca] -= 2 ; B[fa[lca]] -= 2 ; ll L = dep[u] - dep[lca], R = dep[v] - dep[lca]; tmp[fa[lca]] -= (L + R + 1 ) * 2 ; ans[1 ] += L * R; A[u] += L - R - 1 - 2 * L; A[v] += R - L - 1 - 2 * R; A[fa[lca]] -= (-2 - 2 * L - 2 * R); } dfs3 (1 , 0 ); for (int i = 1 ; i <= n; i++)B[i] += tmp[i]; dfs (1 , 0 ); dfs4 (1 , 0 ); for (int i = 1 ; i <= n; i++) { printf ("%lld\n" , ans[i]); } return 0 ; }
F. 乘法
题意:给出一个长度为 n n n 的数列和一个长度为 m m m 的数列,相乘得到 n ⋅ m n\cdot m n ⋅ m 的矩阵,求矩阵中第 K K K 大的数。
二分答案。
每次check时,遍历第一个数组,二分找到第二个数组中与该值相乘大于等于mid的数的个数。
由于给出的数组可能有正有负还有零,所以特判零,再取 t m p tmp t m p 为第一个 t m p ⋅ a [ i ] ≥ m i d tmp\cdot a[i]\geq mid t m p ⋅ a [ i ] ≥ mi d 的数,不用再分类讨论,只要找到 t m p ⋅ a [ i ] tmp\cdot a[i] t m p ⋅ a [ i ] 仍大于等于 m i d mid mi d 的那一边即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 50 ;int n, m;ll k; ll a[maxn], b[maxn]; bool check (ll mid) { ll cnt = 0 ; for (int i = 1 ; i <= n; i++) { if (a[i] == 0 ) { if (mid <= 0 )cnt += m; continue ; } ll tmp = mid / a[i]; if (tmp*a[i] < mid) { if ((tmp + 1 )*a[i] >= mid)tmp++; else tmp--; } if ((tmp + 1 )*a[i] >= mid) cnt += m + 1 - (lower_bound (b + 1 , b + m + 1 , tmp) - b); else cnt += upper_bound (b + 1 , b + m + 1 , tmp) - b - 1 ; } return cnt >= k; } int main () { scanf ("%d%d%lld" , &n, &m, &k); for (int i = 1 ; i <= n; i++)scanf ("%lld" , &a[i]); for (int i = 1 ; i <= m; i++)scanf ("%lld" , &b[i]); sort (a + 1 , a + n + 1 ); sort (b + 1 , b + m + 1 ); ll L = -1e12 , R = 1e12 ; ll ans = L; while (L <= R) { ll mid = (L + R) / 2 ; if (check (mid)) { ans = mid; L = mid + 1 ; } else R = mid - 1 ; } cout << ans << endl; return 0 ; }
H. 最大公因数
题意:从 1 1 1 到 n n n 中挑出了一个数 x x x ,现在要你从正整数集中选出一个数,它与挑出的数 x x x 的最大公因数是它与 1 1 1 到 n n n 中所有数的最大公因数中独一无二的,且这个数要最小。
把 1 1 1 到 n n n 中所有 x x x 的倍数都找出来,构造出的数应该在 x x x 的基础上乘以所有它的倍数包含的质数,且每个质数最多乘一次。
最终的数比较大。可以用python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 50 ;int prime[maxn];bool is_prime[maxn];int sieve (int n) { int p = 0 ; memset (is_prime, true , sizeof (is_prime)); is_prime[0 ] = is_prime[1 ] = false ; for (int i = 2 ; i <= n; i++) { if (is_prime[i]) { prime[p++] = i; for (int j = 2 * i; j <= n; j += i) { is_prime[j] = false ; } } } return p; } int vis[maxn];int T, n, k;ll gcd (ll a, ll b) { if (a < b)swap (a, b); return b == 0 ? a : gcd (b, a%b); } int main () { int N = sieve (500 ); scanf ("%d" , &T); while (T--) { scanf ("%d%d" , &n, &k); fill (vis, vis + n + 1 , 0 ); for (int i = 1 ; i <= n; i++) { if (i != k && i%k == 0 ) { int tmp = i / k; for (int j = 0 ; j < N; j++) { if (tmp%prime[j] == 0 )vis[prime[j]] = 1 ; } } } BigInteger ans = k; for (int i = 1 ; i <= n; i++)if (vis[i])ans = ans * i; cout << ans << endl; } return 0 ; }
I. K小数查询
题意:给出一个数组,两种操作每次选一个区间,第一种操作把区间中所有数与给定数x取最小值,第二种操作求区间中第k小的数。
分块+lazy标记
以 n \sqrt n n 分为一块。
更新答案时,整块的直接更新lazy,两边的暴力更新。
查询时,二分答案,整块的若laz小于等于mid则直接加上块大小,否则内部排序后二分找到小于等于mid的个数,两边暴力查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <bits/stdc++.h> using namespace std;#define ll long long typedef pair<int , int > pii;const int INF = 0x3f3f3f3f ;const int maxn = 1e5 + 10 ;int n, m;int tot, siz;int a[maxn];vector<int >vc[maxn]; int laz[maxn];void change (int id, int l, int r, int x) { int N = (int )vc[id].size (); vc[id].clear (); for (int i = 0 ; i < N; i++) { int j = i + id * siz; if (l <= j && j <= r)a[j] = min (a[j], min (laz[id], x)); else a[j] = min (a[j], laz[id]); vc[id].push_back (a[j]); } laz[id] = max (x, laz[id]); sort (vc[id].begin (), vc[id].end ()); } void update (int l, int r, int x) { int L = l / siz, R = r / siz; change (L, l, r, x); if (L != R)change (R, l, r, x); for (int i = L + 1 ; i < R; i++)laz[i] = min (laz[i], x); } int sol (int l, int r, int id, int mid) { int res = 0 ; int L = max (id * siz, l), R = min (r, id*siz + (int )vc[id].size () - 1 ); for (int i = L; i <= R; i++) { if (min (laz[id], a[i]) <= mid)res++; } return res; } int check (int l, int r, int mid) { int L = l / siz, R = r / siz; int res = 0 ; res += sol (l, r, L, mid); if (L != R)res += sol (l, r, R, mid); for (int i = L + 1 ; i < R; i++) { if (laz[i] <= mid)res += (int )vc[i].size (); else res += upper_bound (vc[i].begin (), vc[i].end (), mid) - vc[i].begin (); } return res; } int query (int l, int r, int k) { int L = 0 , R = n; while (L < R) { int mid = (L + R) / 2 ; if (check (l, r, mid) >= k)R = mid; else L = mid + 1 ; } return L; } int main () { scanf ("%d%d" , &n, &m); for (int i = 0 ; i < n; i++)scanf ("%d" , &a[i]); siz = sqrt (n); tot = ceil (1.0 *n / siz); for (int i = 0 ; i < n; i++)vc[i / siz].push_back (a[i]); for (int i = 0 ; i < tot; i++)sort (vc[i].begin (), vc[i].end ()); memset (laz, 0x3f , sizeof (laz)); int op, l, r, x; while (m--) { scanf ("%d%d%d%d" , &op, &l, &r, &x); l--; r--; if (op == 1 )update (l, r, x); else printf ("%d\n" , query (l, r, x)); } return 0 ; }