https://ac.nowcoder.com/acm/contest/5671

B - Binary Vector

 

题意：n 维的 01 向量空间，每次随机选一个向量，问 n 次后所有向量线性无关的概率。

假设已选出 i 个向量，则这 i 个向量构成的向量空间包含 2i2^i 个向量：其实就是 i 个向量的线性组合，也就是子集大小。

则下一个要选的向量必须不在这个空间内，已知 n 维向量空间中所有向量总数为 2n2^n，则所选向量的概率为 2n−2i2n\frac{2^n-2^i}{2^n}。对于每一步选择，即每一个 i 都有上面的要求，所以最终概率为 ∏i=0n−12n−2i2n\prod_{i=0}^{n-1}\frac{2^n-2^i}{2^n}。

fn=∏i=0n−12n−2i2n=∏i=0n−12n−i−12n−i=∏i=1n2i−12i⇓fn=fn−1⋅(2n−12n)=fn−1⋅(1−12n)\begin{align} f_n&=\prod_{i=0}^{n-1}\frac{2^n-2^i}{2^n}\\ &= \prod_{i=0}^{n-1}\frac{2^{n-i}-1}{2^{n-i}}\\ &= \prod_{i=1}^{n}\frac{2^i-1}{2^i}\\ &\Downarrow\\ f_n &= f_{n-1}\cdot(\frac{2^n-1}{2^n})\\ &= f_{n-1}\cdot(1-\frac{1}{2^n})\\ \end{align} 

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e7 + 10;
const ll mod = 1e9 + 7;
int T;
ll f[N];
int main() {
    scanf("%d", &T);
    ll inv2 = 500000004;
    ll tmp = inv2;
    f[1] = inv2;
    for (int n = 2; n < N; n++) {
        tmp = tmp * inv2%mod;
        f[n] = f[n - 1] * (1 + mod - tmp) % mod;
    }
    for (int i = 2; i < N; i++) {
        f[i] ^= f[i - 1];
    }
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", f[n]);
    }
    return 0;
}

 

K - K-Bag

 

题意：定义k-bag为几个由k的排列按顺序拼成的数列，给定一个数列，问是不是某个k-bag的子区间。

把给定数列分成几块，每块里面对于 1 到 k 中每个数最多包含一次。

所以对于数 a[i]，它之前最近出现的位置 pre[i] 与 i 直接必须要有一个分界线。而一旦确定了某一个分界线，其实所有分界线也就都确定了，所以把这个限制都映射为对第一个分界线的限制以便统计。

[pre[a[i]],i)[pre[a[i]],i) 之间存在一个分界线，则第一个分界线必定要在 [pre[a[i]]%k,i%k)[pre[a[i]]\%k,i\%k) 之间，这里还要注意如果 pre[a[i]]%k>i%kpre[a[i]]\%k>i\%k，则映射到 [0,k)[0,k) 应该是两部分 [0,i%k)⋃][pre[a[i]]%k,k)[0,i\%k)\bigcup ][pre[a[i]]\%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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int T;
int n, k;
int a[N], sum[N], pre[N];
vector<int>vc;
bool ck() {
	for (int i = 0; i < n; i++)if (a[i] > k)return false;
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++)scanf("%d", &a[i]);
		if (!ck()) {
			puts("NO");
			continue;
		}
		if (k > n) {
			vc.clear();
			for (int i = 0; i < n; i++)vc.push_back(a[i]);
			sort(vc.begin(), vc.end());
			vc.erase(unique(vc.begin(), vc.end()), vc.end());
			k = (int)vc.size();
			for (int i = 0; i < n; i++)a[i] = lower_bound(vc.begin(), vc.end(), a[i]) - vc.begin() + 1;
		}
		int cnt = 0;
		fill(pre, pre + n + 1, -INF);
		fill(sum, sum + n + 1, 0);
		for (int i = 0; i < n; i++) {
			if (i - pre[a[i]] >= k) {
				pre[a[i]] = i;
				continue;
			}
			cnt++;
			int l = pre[a[i]] % k, r = i % k;
			if (l <= r)sum[l]++, sum[r]--;
			else {
				sum[0]++;
				sum[r]--;
				sum[l]++;
				sum[k]--;
			}
			pre[a[i]] = i;
		}
		bool flg = 0;
		for (int i = 1; i < k; i++)sum[i] += sum[i - 1];
		for (int i = 0; i < k; i++) {
			if (sum[i] == cnt)flg = 1;
		}
		puts(flg ? "YES" : "NO");
	}
	return 0;
}

 

H - Harmony Pairs

 

题意：定义 S(A)S(A) 为 A 的每位上数字之和。问有几个数对 (A,B)(A,B) 满足 1≤A<B≤N1\le A<B\le N 且 S(A)>S(B)S(A)>S(B)。

数位dp

竟然是第一次做的数位dp

数位dp大概来说就是枚举数位的记忆化搜索，比较特别的点就在于 limit ，它限定了每一位的数字范围；以及还有一维常常用来记录需要的状态，这一维也就和普通的dp比较相似了。

考虑如果记录 S(A)S(A) 以及 S(B)S(B) 则空间不够（时间应该还是够的），但是由于只需要这两者的大小关系，所以可以用 S(A)−S(B)S(A)-S(B) 来代替。如果递归到最后一位时 S(A)−S(B)>0S(A)-S(B)>0，则满足条件。

再看另一个条件 1≤A<B≤N1\le A<B\le N，如果只有 B<NB<N ，那就和普通的数位dp一样了，只需要一个 limit 记录即可，而这里多了一个，所以还要再来一个 limit2。

dp[pos][d][lim1][lim2]dp[pos][d][lim1][lim2] 表示枚举到第 pos 位，S(A)−S(B)=dS(A)-S(B)=d，B 是/否 达到 N 的limit1，A 是/否 达到 B 的limit2。

两层循环，第一层枚举 B 的第 pos 位，受到 limit1 限制；第二层枚举 A 的第 pos 位，受到 limit2 的限制。

很多时候 dp 数组只记忆化 非limit 时的结果，因为 是否limit 时结果很可能不同，且 limit 的情况又很少。但是本题必须对有 limit 时也要记忆，因为两个 limit 情况比较多，否则会 T。

总的来说本题是比较好的数位dp入门题。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
char s[N];
ll dp[101][2000][2][2];
int base = 1000;
ll dfs(int pos, int d, int lim1, int lim2) {
	if (pos == -1)return d > base;
	if (~dp[pos][d][lim1][lim2])return dp[pos][d][lim1][lim2];
	int up1 = (lim1 ? s[pos] - '0' : 9);
	ll res = 0ll;
	for (int i = 0; i <= up1; i++) {
		int up2 = (lim2 ? i : 9);
		for (int j = 0; j <= up2; j++) {
			res = (res + dfs(pos - 1, d + j - i, lim1 && (i == s[pos] - '0'), lim2 && (j == i))) % mod;
		}
	}
	return dp[pos][d][lim1][lim2] = res;
}
int main() {
	scanf("%s", s);
	int n = strlen(s);
	reverse(s, s + n);
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", dfs(n - 1, base, 1, 1));
	return 0;
}

 

G - Grid Coloring

 

题意：有一个 n∗nn*n 的网格，kk 种颜色，要求对边染色，使得每种颜色出现次数相同，且没有纯色的环，且每行与每列都至少有两种颜色。

构造

题解的构造方法挺复杂，找了其它大佬的构造方法。

从上到下，从左到右循环使用 1−k1-k 染色，染完一行染一列，再染一行，再染一列，以此类推。

这样第一第三个条件必定已经满足。而对于边长大于 1 的环也必定已经满足，对于 1∗11*1 的环，两列是相邻顺序染色的，所以颜色必定不同。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, k;
int a[210][210], b[210][210];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		if (n == 1 || k == 1) {
			puts("-1");
			continue;
		}
		if (2 * n*(n + 1) % k) {
			puts("-1");
			continue;
		}
		int p = 0;
		int flg = 0, x1 = 1, y1 = 1, x2 = 1, y2 = 1;
		for (int t = 1; t <= 2 * n*(n + 1); t++) {
			if (!flg) {
				a[x1][y1] = p + 1;
				y1++;
				if (y1 == n + 1)y1 = 1, x1++, flg ^= 1;
			}
			else {
				b[x2][y2] = p + 1;
				y2++;
				if (y2 == n + 2)y2 = 1, x2++, flg ^= 1;
			}
			p = (p + 1) % k;
		}
		for (int i = 1; i <= n + 1; i++)for (int j = 1; j <= n; j++)printf("%d%c", a[i][j], " \n"[j == n]);
		for (int i = 1; i <= n + 1; i++)for (int j = 1; j <= n; j++)printf("%d%c", b[j][i], " \n"[j == n]);
	}
	return 0;
}

 

J - Josephus Transform

 

题意：有一个排列 PP 初始为 {1,2,⋯ ,n}\{1,2,\cdots,n\}，定义 k−k-约瑟夫变换：数到 kk，把该数删除并加入新排列末尾，继续数，知道所有数都到新排列中。多次操作，每次操作执行 xx 次 k−k-约瑟夫变换，问最终排列。

线段树

对于一次 k−k-约瑟夫变换，每次选择的数是可以知道的，设从第 pospos 个数开始数，当前剩余 cntcnt 个数，则选择的是当前剩余数中的第 (pos−1+k−1)%cnt+1(pos-1+k-1)\%cnt+1 个，并将 pospos 变为 ((pos−1+k−1)%(n−i+1)%(n−i))+1((pos - 1 + k - 1) \% (n - i + 1) \% (n - i)) + 1，选择当前剩余数中第 xx 个可以在线段树上二分做到。

得到了一次变换后，就可以通过环得到 xx 次变换。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2];
void up(int rt) {
	tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void build(int l, int r, int rt) {
	if (l == r) {
		tr[rt] = 1;
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
int qry(int k, int l, int r, int rt) {
	if (l == r) {
		tr[rt] = 0;
		return l;
	}
	int ans;
	if (k <= tr[rt << 1])ans = qry(k, lson);
	else ans = qry(k - tr[rt << 1], rson);
	up(rt);
	return ans;
}
int p[N], a[N], tmp[N];
vector<int>vc;
int vis[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)a[i] = i;
	while (m--) {
		int k, x;
		scanf("%d%d", &k, &x);
		build(1, n, 1);
		int pos = 1;
		for (int i = 1; i <= n; i++) {
			p[i] = qry((pos - 1 + k - 1) % (n - i + 1) + 1, 1, n, 1);
			if (n != i)pos = ((pos - 1 + k - 1) % (n - i + 1) % (n - i)) + 1;
		}
		fill(vis, vis + n + 1, 0);
		for (int i = 1; i <= n; i++) {
			if (vis[i])continue;
			vc.clear();
			int u = p[i];
			while (!vis[u]) {
				vis[u] = 1;
				vc.push_back(u);
				u = p[u];
			}
			for (int j = 0; j < (int)vc.size(); j++) {
				p[vc[j]] = vc[(j + x) % (int)vc.size()];
			}
		}
		for (int i = 1; i <= n; i++)tmp[i] = a[p[i]];
		for (int i = 1; i <= n; i++)a[i] = tmp[i];
	}
	for (int i = 1; i <= n; i++)printf("%d%c", a[i], " \n"[i == n]);
	return 0;
}