свобода

分类

题解(10)

/ 注册

全部文章（共10篇）

J斐波那契和矩阵快速幂

考虑这个会稍微好求一些。我们做差分，可以得到我们可以用矩阵快速幂的方法求出所有，考虑一个向量，维护Fib(i),Fib(i-1)和所有的，矩阵共k+3维。得到之后，我们可以展开得到关于的表达式。也就是 . 整体复杂度O(k^3 log(n))也有大佬直接用BM板子过题 #include<...

2020-05-10

1 892

I纸牌胡搞

Stratoes:首先假设k ≤ n – 1，那么我们可以这么做：将每个牌中间留一个空位，每次把牌堆顶的第一张牌放到合适的空位上，可以证明这么做是可行的。因此我们维护一个数组和一个指向牌堆顶的指针，一开始将第i张牌放在2*i-1的位置。第j次操作时将牌堆顶的牌放在(j + 1) * 2的位置即可。这...

2020-05-10

1 686

H时空栈线段树

可以先离散化，然后开线段树维护。我们对于栈的查找操作可以理解成找到插入的时间点，然后再找到对应的元素。对于插入和删除操作，可以认为是在指定时间以后+1或者-1。对于查询操作，我们首先可以确定对应时间栈内元素个数，然后用线段树查询在当前时间之前最后一个小于这个个数的时间点t，t+1就是插入的时间。整体...

2020-05-10

0 715

G硬币游戏Ⅲ 博弈

我们翻硬币的时候，可以理解成把最后一个硬币替换成最多前面k-1，最少0个硬币。因为如果在一个位置有两个同样的硬币，他们的sg函数相同，互相抵消。这样我们就转化为k堆独立的硬币问题。令2^p≤k<2^(p+1)，第i个硬币的sg函数是min(lowbit(i),2^p )。可以归纳法证明。如果i...

2020-05-10

1 769

F排列计算贪心

排列中的每个数对答案的贡献是它被查询的次数乘以它自身，因此，要最大化答案，应该在被查询次数较多的位置放置较大的数。用差分和线段树等方法统计每个位置被查询的次数，对每个位置被查询的次数排序，在较大的位置放置排列中较大的数，再计算答案即可。时间复杂度为 O(n log n)。 #include <...

2020-05-10

2 632

E弦数学

答案是2^n / (n + 1)!。概率可以通过合法方案数/总方案数来计算。合法方案数f(n)=Σf(i) * f(n-i-1), 即为卡特兰数，故f(n)=C(2n, n) / (n + 1)。总方案数为C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! ...

2020-05-10

1 840

D车辆调度码农题

将所有遥控车的位置作为状态，每次操作依次选择一辆遥控车向四个方向按题意模拟其前进的路线(注意，第一步后任意一辆车最多只有三个方向可以走)。BFS 或深度限制 DFS 判断 k 步之内能否有一辆遥控车到达其中一个终点。时间复杂度为 O((3R)^kmax(w, h))。 #include <io...

2020-05-10

0 721

C张老师的旅行 dp

观察发现，在最少时间的前提下走过的点必然是连续的区间设为[l,r]，那么唯一的变化就是终点落在l还是人r，这样我们可以通过dp来解决，我们设状态f[l][r][0]表示终点落在l的前提下走完区间[l,最小时间，f[l][r][1]同理终点落在r上，状态转移为：f[l-1][r][0]=min(f[l...

2020-05-10

1 606

B伤害计算模拟

根据+号分割开，然后分类解决。包含d的：n*(x+1)/2；不包含d的直接atoi一下就可以。注意避免浮点数运算，可以全部都乘2然后输出的时候分奇偶判断是否输出.5。注意输出浮点数的时候，如果有1000000之类的数可能会输出成1e+06的形式。全部使用整数计算可以避免此类问题。 #include&...

2020-05-10

3 708

A张老师和菜哭武的游戏，gcd

显然在1到n的这n个点中的某个点p要被走到，要满足p=xa+yb，那么显然p必须要是gcd（a，b）的倍数，所以判断n/gcd（a，b）奇偶即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; in...

2020-05-10

8 831