[Codeforces] combinatorics (R1200) Part.1

[Codeforces] combinatorics (R1200) Part.1

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

535B. Tavas and SaDDas

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

题意

称只含数码$4$和$7$的数字为幸运数字,如$47,744,4$.将所有幸运数字升序排列,下标从$1$开始.给定幸运数字$n(1\le n\le 1\mathrm{e}9)$,求其下标.

思路I

暴力预处理出$1\mathrm{e}9$内的幸运数字,再lower_bound即可.

代码I

vl ans;

void init(ll x) {
	if (x > 1e9) return;

	ans.push_back(x);
	init(x * 10 + 4), init(x * 10 + 7);
	sort(all(ans));
	ans.erase(unique(all(ans)), ans.end());
}

void solve() {
	init(0);

	int n; cin >> n;
	cout << lower_bound(all(ans), n) - ans.begin();
}

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

---

思路II

设$n$的十进制表示有$x$位,$f(i)$表示二进制数$i$的十进制表示.构造一个长度为$x$的二进制串,它的第$i$位为$0$当且仅当$n$的第$i$位为$4$.$ans=2^1+2^2+\cdots +2^{x-1}+f(m)+1$.时间复杂度$O(\log n)$.

代码II

string get(string s) {  // 转化为对应的二进制串
	for (int i = 0; i < s.size(); i++)
		s[i] = (char)(s[i] == '4' ? '0' : '1');
	return s;
}

void solve() {
	string n; cin >> n;
	n = get(n);

	ll ans = 0;
	for (int i = 0; i < n.size(); i++) ans = 2 * ans + n[i] - '0';
	ans += ((ll)1 << n.size()) - 1;
	cout << ans;
}

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

---

---

610A. Pasha and Stick

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

题意

给定一段长度为整数$n(1\le n\le 2\mathrm{e}9)$的木棒,切三下将其变为四段长度都为整数的木棒.问有多少种切割方式,使得得到的四根木棒能拼成一个非正方形的长方形.

思路

显然拼出的长方形的周长只能是偶数,则$n$为奇数时无解.

$n$为偶数时,只考虑长方形两条相邻边之和$m=\frac{n}{2}$,有$(1,m-1),(2,m-2),\cdots$,共$\lfloor \frac{m}{2}\rfloor$种分割方法.注意$2\mid m$,即$4\mid n$时,有一种分割方法是正方形,方案数要$-1$.

代码

void solve() {
	int n; cin >> n;
    cout << (n & 1 ? 0 : n / 4 - (n % 4 == 0));
}

int main() {
	solve();
}
1
2
3
4
5
6
7
8

---

---

629A. Far Relative’s Birthday Cake

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

题意

给定一个$n\times n(1\le n\le 100)$的只包含字符’.‘和’C’的字符矩阵,求在同一行的’C’的对数$+$在同一列的’C’的对数.注意在每行或每列中,每个’C’至多只能属于一对’C’.

思路

设第$i$行、第$j$列中’C’的个数分别为$row[i]$、$col[j]$,则$ans=\sum _{i=1}^n{C}_{row[i]}^2+\sum _{i=1}^n{C}_{col[i]}^2$.

代码

const int MAXN = 105;
int row[MAXN], col[MAXN];  // row[i]、col[i]分别表示第i行、第i列中'C'的个数

ll C(int n) { return (ll)n * (n - 1) / 2; }  // C(n,2)

void solve() {
	int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char ch; cin >> ch;
            row[i] += ch == 'C', col[j] += ch == 'C';
        }
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) ans += C(row[i]);
    for (int i = 0; i < n; i++) ans += C(col[i]);
    cout << ans;
} 

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

---

---

630C. Lucky Numbers

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

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

称一个整数是好的,如果它只包含数码$7$、$8$.给定整数$n(1\le n\le 55)$,求长度为$n$的十进制数中好的数的个数.

思路

有$7$和$8$两个长度为$1$的好的数字.注意到在每个好的数字之后接上$7$或$8$即可得到长度$+1$的好的数字,故$ans=2^1+2^2+\cdots +2^n=2^{n+1}-2$.

代码

void solve() {
	int n; cin >> n;
    cout << ((ll)1 << n + 1) - 2;
} 

int main() {
	solve();
}
1
2
3
4
5
6
7
8

---

---

1166A. Silent Classroom

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

题意

给定$n(1\le n\le 100)$个学生的名字(只包含小写英文字母的、长度不超过$20$的字符串),将他们分在两个教室(未必每个教室都有学生),使得名字首字母相同的学生的对数最小,输出最小对数.注意学生可能有重名,$(a,b)$与$(b,a)$只统计一次.

思路

显然可分别统计每个字母开头的名字对答案的贡献.

最优策略:将名字首字母相同的学生尽量平均地分在两个教室.

[证] 设所有学生名字首字母相同,两教室分别有$a$、$b$个学生,且$a>b+1$.

将第一个教室的一个学生移动到第二个教室可减少$(a-1)$对名字首字母相同的学生,

​ 同时增加$b$对名字首字母相同的学生,净减少$(a-1)-b>0$对名字首字母相同的学生.

重复该过程,直至$|a-b|\le 1$,即将名字首字母相同的学生尽量平均地分在两个教室.

设姓名首字母为$a$的学生数为$cn{t}_a$,则第一个教室分$\lfloor \frac{cn{t}_a}{2}\rfloor$人,第二个教室分$\lceil \frac{cn{t}_a}{2}\rceil$人,每个教室中任选两个姓名首字母相同的学生组成一对,故该首字母对答案的贡献为$\left(\begin{array}{c}\lfloor \frac{cn{t}_a}{2}\rfloor \\ 2\end{array}\right)+\left(\begin{array}{c}\lceil \frac{cn{t}_a}{2}\rceil \\ 2\end{array}\right)$.

代码

umap cnt;

int C(int n) {  // C(n,2)
    if (n < 2) return 0;
    else return n * (n - 1) / 2;
}

void solve() {
	int n; cin >> n;
    while (n--) {
        string s; cin >> s;
        cnt[s[0]]++;
    }

    int ans = 0;
    for (char ch = 'a'; ch <= 'z'; ch++) ans += C(cnt[ch] / 2) + C((cnt[ch] + 1) / 2);
    cout << ans;
}

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

---

---

1272C. Yet Another Broken Keyboard

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

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

键盘只能打出$c_1,\cdots ,c_k$的$k$个不同的字母.给定一个长度为$n$的字符串,问能打出它的多少个子串.

第一行输入两个整数$n,k(1\le n\le 2\mathrm{e}5,1\le k\le 26)$.第二行输入一个长度为$n$的、只包含小写英文字母的字符串$s$.第三行输入$k$个相异的英文字母$c_1,\cdots ,c_k$.

思路

注意到不在字符集(键盘能打出的字母)中的字母可视为一类,记作$0$;在字符集中的字母可视为另一类,记作$1$,问题转化为求$s$中所有连续的$1$对答案的贡献,用双指针找连续的$1$即可.设连续的$1$的长度为$m$,则它对答案的贡献为$\frac{m(m+1)}{2}$.

代码

ll cal(int n) {
    return (ll)n * (n + 1) / 2;
}

void solve() {
	int n, k; cin >> n >> k;
    string str; cin >> str;
    uset s;
    while (k--) {
        char ch; cin >> ch;
        s.insert(ch);
    }

    for (auto& ch : str) ch = s.count(ch) + '0';

    ll ans = 0;
    int i = 0, j = 0;
    while (i < n && j < n) {
        while (i < n && str[i] == '0') i++;
        j = i;
        while (j < n && str[j] == '1') j++;
        ans += cal(max(0, j - i));
        i = j;
    }
    cout << ans;
}

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
27
28
29
30

---

---

1293B. JOE is on TV!

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

题意

有若干轮游戏,每轮有一个问题,答错者淘汰,游戏结束当且仅当只剩下JOE(即他能答对所有问题).初始时有$n(1\le n\le 1\mathrm{e}5)$个选手.每轮中,若当前剩下$s$个选手,其中$t(0\le t\le s)$人答错,则JOE会得到$\frac{t}{s}$的钱,同时下一轮剩下$(s-t)$人.求他最后能得到的钱的最大值,误差不超过$1\mathrm{e}-4$.

思路

最优策略:每轮淘汰$1$个人.

[证] 每轮淘汰$1$个人的收益为$\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\cdots$.

考察第一轮淘汰$2$个人,此时收益为$\frac{2}{n}$.

注意到$\frac{1}{n}+\frac{1}{n-1}>\frac{2}{n}\iff \frac{1}{n-1}>\frac{1}{n}$,故证.

代码

void solve() {
	int n; cin >> n;

   double ans = 0 ;
   for (int i = 1; i <= n; i++) ans += 1.0 / i;
   cout << fixed << setprecision(8) << ans;
}

int main() {
	solve();
}
1
2
3
4
5
6
7
8
9
10
11

---

---

1499A. Domino on Windowsill

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

题意

有一个$2\times n$的网格,其中第一行的前$k_1$个格子是白色的,第二行的前$k_2$个格子是白色的,其余格子是黑色的.有$w$个白色的$2\times 1$长方形和$b$个黑色的$2\times 1$长方形,每个长方形只能放在与自己相同颜色的网格上,不同的长方形间不能重叠,长方形可旋转,问能否放完所有的$(w+b)$个长方形.

有$t(1\le t\le 3000)$组测试数据.每组测试数据第一行输入三个整数$n,k_1,k_2(1\le n\le 1000,0\le k_1,k_2\le n)$.第二行输入两个整数$w,b(0\le w,b\le n)$.

思路

考察最多能放多少白色的长方形.第一行最多能横放$\lfloor \frac{k_1}{2}\rfloor$个,第二行最多能横放$\lfloor \frac{k_2}{2}\rfloor$个.若$k_1$和$k_2$都为奇数,则第一列还可竖放一个,故最多能放$\left(\lfloor \frac{k_1}{2}\rfloor +\lfloor \frac{k_2}{2}\rfloor +[k_1和k_2是奇数]\right)$个白色的长方形,同理可求得最多能放的黑色长方形数.

注意位运算的优先级低于加法,要加括号.

代码

int cal(int k1, int k2) {
    return k1 / 2 + k2 / 2 + ((k1 & 1) & (k2 & 1));  // 注意优先级
}

void solve() {
	int n, k1, k2; cin >> n >> k1 >> k2;
    int w, b; cin >> w >> b;

    cout << (w <= cal(k1, k2) && b <= cal(n - k1, n - k2) ? "YES" : "NO") << endl;
}

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

---

---

1514B. AND 0, Sum Big

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

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

给定两个整数$n,k$,求满足下列条件的长度为$n$的序列数,答案对$1\mathrm{e}+7$取模:①所有元素的范围为$[0,2^k-1]$;②所有元素相与得$0$;③所有元素之和最大.

有$t(1\le t\le 10)$组测试数据.每组测试数据输入两个整数$n,k(1\le n\le 1\mathrm{e}5,1\le k\le 20)$.

思路

考察一张$n\times k$的表格,其中每行代表序列中一个元素的二进制表示,初始时表格中的数都为$1$.为使得所有元素相与得$0$且所有元素之和最大,只需在每列中选一个元素置为$0$即可,故$ans=n^k$.

代码

const int MOD = 1e9 + 7;

void solve() {
	int n, k; cin >> n >> k;
  cout << qpow(n, k, MOD) << endl;
}

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

---

---

1539A. Contest Start

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

题意

有$n$个人表演,他们每个人开始表演的时间是$x$的倍数,即第一个人在$x$时刻开始表演,第二个人在$2x$时刻开始表演,$\cdots$,每个人表演持续时间$k$.每个人表演结束时,其不满程度是此时已经开始表演但未表演完的人数(包括该时刻开始表演的人).求每个人的不满程度之和.

有$t(1\le t\le 1000)$组测试数据.每组测试数据输入三个整数$n,x,t(1\le n,x,t\le 2\mathrm{e}9)$.

思路

设$n$个人编号$1\sim n$,则对第$i(1\le i\le n-1)$个人的不满程度有贡献的是编号$(i+1)\sim \left(i+\min \left\{\lfloor \frac{t}{x}\rfloor ,n\right\}\right)$的人,则前$\max \left\{0,n-\lfloor \frac{t}{x}\rfloor \right\}$个人每人的不满程度为$\lfloor \frac{t}{x}\rfloor$,后面每个人的不满程度依次$-1$,等差数列求和即可.

代码

void solve() {
	int n, x, t; cin >> n >> x >> t;
 	cout << (ll)max(0, n - t / x) * (t / x) + (ll)min(n - 1, t / x - 1) * min(n, t / x) / 2 << endl;
}

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

---

---