第44届ICPC亚洲赛区南京站

    阅读全文
fightinggg's avatar
fightinggg 5月 10, 2021

第44届ICPC亚洲赛区银川站

    阅读全文
fightinggg's avatar
fightinggg 5月 09, 2021

2020牛客暑期多校训练营第七场

    阅读全文
fightinggg's avatar
fightinggg 5月 07, 2021

2020CCPC长春站

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接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}$$     阅读全文
fightinggg's avatar
fightinggg 5月 06, 2021

2020省赛网赛

    阅读全文
fightinggg's avatar
fightinggg 5月 05, 2021

2020CCPC威海站

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接http://codeforces.com/gym/102798 A. Golden Spirit有一个桥,桥两边都有n个老人,你桥的一边,你可以花时间x把一个老人带到对面,然后你可以接着把那边的老人带回来,你也可以原地等待,所有老人移动一次以后需要休息t分钟,问你至少花费多少时间,能让所有老人都互相跑到对面,然后又回到原本的位置。 123456789101112131415#include<bits/stdc++.h>using namespace std;#define ll long longint 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)); }}     阅读全文
fightinggg's avatar
fightinggg 5月 04, 2021

2020CCPC绵羊站

    阅读全文
fightinggg's avatar
fightinggg 5月 03, 2021

2020牛客暑期多校训练营第六场

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 比赛链接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}$$     阅读全文
fightinggg's avatar
fightinggg 5月 02, 2021

2020牛客暑期多校训练营第五场

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接https://ac.nowcoder.com/acm/contest/15801?&headNav=www B Graph题意n个点的带权树,你可以删边,但要保证删边后图联通,可以加边,但要保证加边后所有简单环的异或和为0。 现在你可以随便操作,需要操作后的树的边权和最小。 题解题目中的两个操作都不会影响两个顶点之间路径的异或和。所以实际上相当于给了一个完全图,两个点之间的边权就是原始树上这两个点之间的路径的异或和,你要求一个最小生成树。 很多人都知道最小生成树有Kruskal算法和Prim算法,但是很少有人知道第三个算法:Boruvka算法,因为这个算法不常用。     阅读全文
fightinggg's avatar
fightinggg 4月 30, 2021

2020牛客暑期多校训练营第四场

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 链接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的最大因子即可。最终使用快速幂解决。     阅读全文
fightinggg's avatar
fightinggg 4月 29, 2021