2020 CCPC Wannafly Winter Camp Day1

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$ 遍历所有区间，两个区间形成逆序对的概率为$\frac{1}{len_1}\cdot \sum_{i=l_1}^{r_1}\frac{g(i)}{len_2}$

其中 $g(i)$ 为 区间2 中小于 $i$ 的部分的长度，这里就是要分类讨论的地方了。

$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$

#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加密，所以直接倒着解密即可。

#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$，$K$ 从 $l$ 到 $r$。$g(n,k)$ 表示共 $n$ 个点，可 $k$ 染色的图的最多边数。求 $\sum_{k=l}^r g(n,k)$。

先考虑 $k$ 固定的情况，则把所有点平均分为 $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)]$

设 $x=\lfloor\frac{n}{k}\rfloor$

化简为 $g(n,k)=\frac{1}{2}[(n-kx)\cdot x\cdot (n-x)+(k-n+kx)\cdot x\cdot (n-x)]$

再从 $l$ 到 $r$ 求和。

又要用到除法分块，之前之所以全都化为 $\lfloor\frac{n}{k}\rfloor$ 就是为了这一步把所有 $\lfloor\frac{n}{k}\rfloor$ 相等的 $k$ 都合并到一起算，用乘法加速加法。

#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)$ 地求出，考虑如何转移。

对一条路径而言，若两个点并不是都在这条路径上，则转移后这条路径对这两点地贡献相同；若两点在一条路径上，假设向左转移，原先路径为 $L\cdot R$，变为 $A_1=(L-1)\cdot (R+1)=L\cdot R+(L-R-1)=A_0+(L-R-1)$，假设再向左转移，变为 $(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)$。

以此类推，转移方程 $A_j=A_i+g(j)$，其中 $g(j)$ 又是一个等差数列，公差为 $2$.

所以先把 $2$ 加入差分，再把 $L-R-1$ 加入差分，最后对 $2$ 求两次前缀和，得到 $2,4,6,\cdots$ 的等差数列，加上 $L-R-1$ 的前缀和，得到 $g(i)$ ，这样就可以转移了。

调了半天，结果是求LCA前的dfs2(1,1)传成了dfs2(1,0)。

#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);
	}
	//cout << B[0] << A[0] << endl;
	dfs3(1, 0);
	for (int i = 1; i <= n; i++)B[i] += tmp[i];
	//cout << B[0] << A[0] << endl;
	dfs(1, 0);
	//cout << B[0] << A[0] << endl;
	dfs4(1, 0);
	for (int i = 1; i <= n; i++) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}

 

F. 乘法

 

题意：给出一个长度为 $n$ 的数列和一个长度为 $m$ 的数列，相乘得到 $n\cdot m$ 的矩阵，求矩阵中第 $K$ 大的数。

二分答案。

每次check时，遍历第一个数组，二分找到第二个数组中与该值相乘大于等于mid的数的个数。

由于给出的数组可能有正有负还有零，所以特判零，再取 $tmp$ 为第一个 $tmp\cdot a[i]\geq mid$ 的数，不用再分类讨论，只要找到 $tmp\cdot a[i]$ 仍大于等于 $mid$ 的那一边即可。

#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$ 到 $n$ 中挑出了一个数 $x$，现在要你从正整数集中选出一个数，它与挑出的数 $x$ 的最大公因数是它与 $1$ 到 $n$ 中所有数的最大公因数中独一无二的，且这个数要最小。

把 $1$ 到 $n$ 中所有 $x$ 的倍数都找出来，构造出的数应该在 $x$ 的基础上乘以所有它的倍数包含的质数，且每个质数最多乘一次。

最终的数比较大。可以用python

#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标记

以 $\sqrt n$ 分为一块。

更新答案时，整块的直接更新lazy，两边的暴力更新。

查询时，二分答案，整块的若laz小于等于mid则直接加上块大小，否则内部排序后二分找到小于等于mid的个数，两边暴力查找。

#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;
}