[Codeforces] combinatorics (R1200) Part.2

[Codeforces] combinatorics (R1200) Part.2

题单:https://codeforces.com/problemset?tags=combinatorics,0-1200

1543B. Customising the Track

原题指路:https://codeforces.com/problemset/problem/1543/B

题意

给定一个长度为$n$的序列$a_1,\cdots ,a_n$.现有操作:选择两个下标$i,j(1\le i,j\le n,i\ne j)$,令$a_i--,a_j++$.求经过若干次(可能为$0$次)操作后$\sum _{i=1}^n\sum _{j=i+1}^n|a_i-a_j|$的最小值.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 2\mathrm{e}5)$.第二行输入$n$个整数$a_1,\cdots ,a_n(0\le a_i\le 1\mathrm{e}9)$.数据保证所有测试数据的$n$之和不超过$2\mathrm{e}5$.

思路

$ans=\sum _{i=1}^n\sum _{j=i+1}^n|a_i-a_j|$描述序列$a[]$的波动情况,欲使其最小,应尽量让$a[]$均匀分布.设$a[]$中元素之和为$sum$,则$n$个元素每个先分$\lfloor \frac{sum}{n}\rfloor$,这一部分不会对$ans$有贡献.剩下的$sum\%n$放在前$sum\%n$个元素上,此时前$sum\%n$个为$1$的元素会与后面的$(n-sum\%n)$个为$0$的元素每对产生$1$点贡献,故$ans=(sum\%n)(n-sum\%n)$.

代码

void solve() {
	int n; cin >> n;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        sum += a;
    }

    cout << (ll)(sum % n) * (n - sum % n) << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

---

1574B. Combinatorics Homework

原题指路:https://codeforces.com/problemset/problem/1574/B

题意 ($2\mathrm{s}$)

给定四个整数$a,b,c,m$,判断是否存在满足下列条件的字符串:①包含$a$个字符’A’,$b$个字符’B’,$c$个字符’C’;②不存在其他字符;③有恰好$m$对相邻相同的字符,若存在则输出"YES";否则输出"NO".

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据输入四个整数$a,b,c,m(1\le a,b,c\le 1\mathrm{e}8,0\le m\le 1\mathrm{e}8)$.

思路

考虑对给定的$a,b,c$,求合法的$m$的范围.

①最大值:显然将所有’A’、‘B’、'C’分别放一起时取得最大值,此时$m=(a-1)+(b-1)+(c-1)=a+b+c-3$.

②最小值:因字符’A’、‘B’、'C’地位等价,不妨设$a\le b\le c$.

​ 考虑构造"CACACA…CBCBCB…CCC…"的字符串,即用$(a+b)$个字符’C’隔开相邻的’A’和’B’,

​ 此时剩下的$c-(a+b)$个字符’C’会组成$(c-a-b-1)$对相邻相同的字符.

综上,$m\in [c-a-b-1,a+b+c-3]$.

$m$可取到$[c-a-b-1,a+b+c-3]$中的任意整数.

[证] 当$m>0$时,取走一个出现次数最多的字符,并使得$m--$,直至$m=0$.

考虑将取走的字符放回$m=0$的字符串中对应字符最后一次出现的位置之后,

​ 显然这样使得该字符的出现次数$++$,同时$m++$.

代码

void solve() {
	int tmpa, tmpb, tmpc, m; cin >> tmpa >> tmpb >> tmpc >> m;

   int a = min({tmpa, tmpb, tmpc}), c = max({tmpa, tmpb, tmpc}), b = tmpa + tmpb + tmpc - a - c;
   int low = c - a - b - 1, high = a + b + c - 3;
   cout << (low <= m && m <= high ? "YES" : "NO") << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12

---

---

1581A. CQXYM Count Permutations

原题指路:https://codeforces.com/problemset/problem/1581/A

题意

求满足如下条件的长度为$2n$的$1\sim 2n$的排列的个数,答案对$1\mathrm{e}9+7$取模:满足$p_i<p_{i+1}$的下标$i$的个数不少于$n$.

有$t$组测试数据.每组测试数据输入一个整数$n(1\le n\le 1\mathrm{e}5)$.数据保证所有测试数据的$n$之和不超过$1\mathrm{e}5$.

思路

称一个排列的值为满足$p_i<p_{i+1}$的下标$i$的个数.将一个值为$i$的排列倒序可得值为$(2n-i)$的排列,则所有值$<n$的排列构成的集合与所有值$\le n$的排列构成的集合间存在双射,则答案为每个集合的大小,即$ans=\frac{1}{2}\cdot (2n)!$.

代码

const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
int fac[MAXN], ifac[MAXN];

void init() {
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
  ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
  for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
}

void solve() {
	init();

  CaseT {
    int n; cin >> n;
    cout << (ll)fac[2 * n] * qpow(2, MOD - 2, MOD) % MOD << endl;
  }
} 

int main() {
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

---

1582B. Luntik and Subsequences

原题指路:https://codeforces.com/problemset/problem/1582/B

题意

给定一个长度为$n$的序列$a_1,\cdots ,a_n$,令$s=\sum _{i=1}^n{a}_i$.称$a[]$的一个非空子列是好的,如果其中的元素之和为$s-1$,求$a[]$的非空子列中好的子列的个数.

有$t(1\le t\le 1000)$组测试数据.每组测试数据第一行输入一个整数$n(1\le n\le 60)$.第二行输入$n$个整数$a_1,\cdots ,a_n(0\le a_i\le 1\mathrm{e}9)$.

思路

先不考虑$a[]$中值为$0$的元素,显然一个子列是好的当且仅当它是$a[]$删除一个值为$1$的元素得到的子列,而值为$0$的元素可删可不删,设值为$0$、$1$的元素的个数分别为$cn{t}_0$、$cn{t}_1$,则$ans=cn{t}_1\cdot 2^{cn{t}_0}$.

代码

void solve() {
	int n; cin >> n;
  int cnt0 = 0, cnt1 = 0;
  vi a(n);
  for (auto& ai : a) {
    cin >> ai;
    cnt0 += ai == 0, cnt1 += ai == 1;
  }

  cout << (ll)cnt1 * ((ll)1 << cnt0) << endl;
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

---

1658B. Marin and Anti-coprime Permutation

原题指路:https://codeforces.com/problemset/problem/1658/B

题意

定义一个长度为$n$的排列$p_1,\cdots ,p_n$是好的,如果$\gcd (1\cdot p_1,2\cdot p_2,\cdots ,n\cdot p_n)>1$.求$1\sim n$的排列中好的排列的个数,答案对$998244353$取模.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入一个$n(1\le n\le 1000)$.

思路

令$g=\gcd (1\cdot p_1,2\cdot p_2,\cdots ,n\cdot p_n)$,则$g\le 2$.

[证] ①$g>2$时,若$\exists$素数$p>2s.t.p\mid g$,因$1\sim n$中有$\lfloor \frac{n}{p}\rfloor$个$p$的倍数,则至多能匹配$2\lfloor \frac{n}{p}\rfloor <n$个数.

②$g\le 2$时,可将值为奇数的数放在偶数下标的位置,将值为偶数的数放在奇数下标的位置.$1\sim n$中有$\frac{n}{2}$个奇数和$\frac{n}{2}$个偶数,故$ans={\left[\left(\frac{n}{2}\right)!\right]}^2$.

代码

const int MAXN = 1005;
const int MOD = 998244353;
int fac[MAXN], ifac[MAXN];

void init() {
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
  ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
  for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
}

void solve() {
	init();

  CaseT {
    int n; cin >> n;
    cout << (n & 1 ? 0 : (ll)fac[n / 2] * fac[n / 2] % MOD) << endl;
  }
} 

int main() {
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

---

1674B. Dictionary

原题指路:https://codeforces.com/problemset/problem/1674/B

题意 $(2\mathrm{s})$

将两相异的小写英文字母组成一个单词,将所有单词按字典序排序,下标从$1$开始.给定一个单词,求其下标.

有$t(1\le t\le 650)$组测试数据.每组测试数据输入一个长度为$2$的、只包含两相异的小写英文字母的单词.

思路

预处理出所有单词即可.

代码

umap mp;

void init() {
  for (char fi = 'a'; fi <= 'z'; fi++) {
    for (char se = 'a'; se <= 'z'; se++) {
      if (fi == se) continue;

      string word(2, ' ');
      word[0] = fi, word[1] = se;
      mp[word] = mp.size() + 1;
    }
  }
}

void solve() {
	init();

  CaseT{
    string s; cin >> s;
    cout << mp[s] << endl;
  }
} 

int main() {
	solve();
}
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

---

---

1674C. Infinite Replacement

原题指路:https://codeforces.com/problemset/problem/1674/C

题意 ($2\mathrm{s}$)

给定一个只包含字符’a’的字符串$s$和只包含小写英文字母的字符串$t$.现有操作:将$s$中的一个字符’a’替换为字符串$t$.求若干次(含零次)操作后能得到的不同字符串的数量.

有$t(1\le t\le 1\mathrm{e}4)$组测试数据.每组测试数据第一行输入长度不超过$50$的只包含字符’a’的字符串$s$.第二行输入长度不超过$50$的只包含小写英文字母的字符串$t$.

对每组测试数据,若能得到无穷多种的不同字符串,输出$-1$;否则输出能得到的不同字符串的数量.

思路

①若$t$为"a",则操作后不改变原串,$ans=1$.

②若$t$的长度$\ge 2$且包含字符’a’,则每次操作后$s$中’a’的数量不减,$ans=INF$.

③若$t$的长度$\ge 2$且不包含字符’a’,则每次操作后$s$中’a’的数量$-1$.

​ $s$中每个字符’a’都可选择替换或不替换,$ans=2^{len}$,其中$len$为$s$的长度.

代码

void solve() {
	string s, t; cin >> s >> t;

  if (t == "a") cout << 1 << endl;
  else {
    bool ok = false;
    for (auto ch : t) ok |= ch == 'a';

    if (ok) cout << -1 << endl;
    else cout << ((ll)1 << s.length()) << endl;
  }
} 

int main() {
	CaseT  // 单测时注释掉该行
	solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

---

截至2022.09.14,无新题目