抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://ac.nowcoder.com/acm/contest/16151?&headNav=www D. Fake News题意输入一个数$n$,问你$\begin{a...

比赛链接

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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接https://ac.nowcoder.com/acm/contest/15167 A. A Warm Welcome题意输出Shenzhen Institute of Computing ...

比赛链接

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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102822 D. Defuse the Bombs题意有一些炸弹,给你一个数组$a$,他们$a_i$秒后会爆炸,你是一个拆弹专家,你可以...

比赛链接

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

B Binary Vector

题意

随机n个n维01向量,询问这个n个向量线性无关的概率

题解

考虑第一个向量,可以有$2^n-1$选择,你不可以选择全为0的向量

然后考虑与第一个向量线性无关的向量,可以有$2^n-2^1$个,因为第一个向量的0倍和1倍不能选。

然后考虑与第一个和第二个向量线性无关的向量,可以有$2^n-2^2$个

于是最终的方案数为$\begin{aligned}\prod_{i=0}^{n}2^n-2^i\end{aligned}$ , 考虑分母为$2^{n\cdot n}$
$$
\begin{aligned}
&\frac{\begin{aligned}\prod_{i=0}^{n-1}2^n-2^i\end{aligned}}{2^{n\cdot n}}
\&=\begin{aligned}\prod_{i=0}^{n-1}1-\frac{2^i}{2^n}\end{aligned}
\&=\begin{aligned}\prod_{i=1}^{n}1-2^{-i}\end{aligned}
\end{aligned}
$$

集合论

集合论是群论的基础,群论是建立在集合论上的。

集合的基本操作

集合的交

$$
A \cap B = \lbrace x \vert x \in A \wedge x \in B \rbrace
$$

集合的并

$$
A \cup B = \lbrace x\vert x \in A \vee x \in B \rbrace
$$

集合的笛卡尔积

注意到笛卡尔积是一个二元组。
$$
A \times B = \lbrace (x,y) \vert x \in A \wedge y \in B \rbrace
$$

集合的映射

我们定义一个映射$f$满足 $f(x) = y $, 其中 $x\in A$, $y\in B$, 即映射可以把一个集合A中的元素映射到集合B中的一个元素。

可以称映射$f$作用于集合A,映射到集合B

链接

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$