介绍

球盒模型指的是把球放入盒子里的题目模型（强行解释）

分为盒子同或不同，球同或不同，盒子允许空或不空，所以一共八种问题

结论

不妨假设n个球，m个盒子

盒异，球同，盒子允许空 $C_{m+n-1}^{m-1}$

盒异，球同，盒不允许空$C_{n-1}^{m-1}$

盒同，球同，盒子允许空$\begin{aligned}\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中的$x^n$系数

盒同，球同，盒不允许空$\begin{aligned}x^m\prod _{j=1}^{m}\frac{1}{1-x^{j}}\end{aligned}$中$x^n$的系数

盒异，球异，盒子允许空 $m^n$

盒异，球异，盒不允许空$\begin{aligned}\sum _{k=0}^{m}(C_m^k(-1)^{m-k}k^n)\end{aligned}$

盒同，球异，盒子允许空$$\begin{aligned}\sum_{i=0}^{m} \sum_{k=0}^i\frac{C_i^k(-1)^{i-k}k^n}{i!}\end{aligned}$$

盒同，球异，盒不允许空$\begin{aligned}\sum _{k=0}^m\frac{C_m^k(-1)^{m-k}k^n}{m!}\end{aligned}$

比赛链接

http://codeforces.com/gym/102832

A. Krypton

题意

充游戏币，首充可以获得优惠，之后充值就没有优惠了，问你x元最多能拿到多少游戏币。
$$
\begin{array}{|c|c|c|}
\hline
\text{Price (RMB yuan)}
& \text{Normal amount (coupons)}
& \text{First recharge reward (coupons)}
\ \hline 1 & 10 & 8
\ \hline 6 & 60 & 18
\ \hline 28 & 280 & 28
\ \hline 88 & 880 & 58
\ \hline 198 & 1980 & 128
\ \hline 328 & 3280 & 198
\ \hline 648 & 6480 & 388
\ \hline
\end{array}
$$

简介

快速幂是能快速计算一个幂的方案，他可以作用于所有满足结合律、封闭性的二元运算，即半群

定义

不妨假设这个二元运算为$\circ$,两个元素进行运算为$x\circ y$,当$xy$同为$x$时，不妨设$x^2=x\circ x$, 同样的$x^1=x$, 当然$x^0=e$, 还有$x^k=x^{k-1}\circ x$

快速幂核心思想

在半群中，只要$k=u+v$一定有$x^k=x^u\circ x^v$.

所以我们可以把k看作一个二进制数，把$x^k$分解为$x^{2^{p_1}}\circ x^{2^{p_2}}\circ x^{2^{p_3}}\circ \circ \circ x^{2^{p_n}}$

这里最多分解为$\log_2(k)$个元素，而且每个元素可以由前k个元素获取，所以只需要进行$log_2(k)$次二元计算即可的到最终答案。

链接

https://ac.nowcoder.com/acm/contest/15801?&headNav=www

B Graph

题意

n个点的带权树，你可以删边，但要保证删边后图联通，可以加边，但要保证加边后所有简单环的异或和为0。

现在你可以随便操作，需要操作后的树的边权和最小。

题解

题目中的两个操作都不会影响两个顶点之间路径的异或和。所以实际上相当于给了一个完全图，两个点之间的边权就是原始树上这两个点之间的路径的异或和，你要求一个最小生成树。

很多人都知道最小生成树有Kruskal算法和Prim算法，但是很少有人知道第三个算法：Boruvka算法，因为这个算法不常用。

链接

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

B Basic Gcd Problem

题意

定义
$$
f_c(x)=
\begin{cases}
max_{i=1}^n c\cdot f_c(\gcd(i,x)) &x\gt1\
1&x=1
\end{cases}
$$

输入c和x

题解

f函数迭代次数越多，则值越大，也就是x取gcd的次数越多越好，所以每次选择x的最大因子即可。最终使用快速幂解决。

比赛链接

https://ac.nowcoder.com/acm/contest/15688?&headNav=www

A All with Pairs

题意

给你字符串n个字符串$s_1$，$s_2$，$s_3$，… $s_n$给你函数$f(s,t)$，其值为最大的长度w，使得s的长度为w的前缀和t的长度为w的后缀相同完全。

你要计算
$$
\sum_{i=1}^{n}\sum_{i=1}^{n}f(s_i,s_j)^2 \mod 998244353
$$

数据范围

$n<10^5$, 字符串总长度小于$10^6$

前言

这几天训练的太频繁了，一天一场比赛，简直不要太👹。从四月25号到5月3号9天开了7场。

比赛地址

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

比赛链接

http://codeforces.com/gym/102798

A. Golden Spirit

有一个桥，桥两边都有n个老人，你桥的一边，你可以花时间x把一个老人带到对面，然后你可以接着把那边的老人带回来，你也可以原地等待，所有老人移动一次以后需要休息t分钟，问你至少花费多少时间，能让所有老人都互相跑到对面，然后又回到原本的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include<bits/stdc++.h>
using namespace std;

#define ll long long
int main(){
    int T; scanf("%d", &T);
    while(T--) {
        ll n, x, t; scanf("%lld %lld %lld", &n, &x, &t);
        ll y1 = max(x + 2 * t - 2 * n * t, 0ll);
        ll y2 = max(x - 2 * n * t, 0ll);
        ll ans1 = y1 + 4 * n * t, ans2 = y2 + (4 * n + 1) * t;
        printf("%lld\n", min(ans1, ans2));
    }
}