Greenty_Q

未归档

/ 注册

全部文章 / 未归档（共46篇）

【CF1174E】Ehab and the Expected GCD Problem

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9+7; const int N = 1e6+5; int n; ll siz[N]; ll d[2][25][25],...

DP

2019-06-04

0 585

【模板】伪随机数生成器

#include<bits/stdc++.h> using namespace std; #define random(a,b) ((a)+Curl_rand()%((b)-(a)+1)) static unsigned int randseed; int n,cnt; unsigned...

模板杂项

2019-02-13

0 497

【CF global1 D / CF1110D】 Jongmah

题意你有n个数字，范围[1, m]，你可以选择其中的三个数字构成一个三元组，但是这三个数字必须是连续的或者相同的，每个数字只能用一次，问这n个数字最多构成多少个三元组? 分析这里想谈一下DP的一个套路，捆绑有的DP题目，它可能会要求和一些东西捆绑，求方案数，这种时候如何单点设置状态呢？ ...

2019-02-09

0 577

【笔记】数论

2019-02-08

0 527

【CF EDU59 D】Compression

题意给定一个n阶方阵A,现在要从里面取出一个n/x阶子方阵B，使得使得对于对于A中每一个元素，都有 ,求x的最大值分析考虑这个关系式 $\frac{i}{x}-1 = \frac{i-x}{x}$ 也就是说，$B[\frac{i}{x}][\frac{j}{x}] = A[i-x+p...

2019-01-29

0 562

【CF EDU59 E】 Vasya and Binary String (DP)

题意给一串01串，对该串进行若干次操作，直到串为空操作为：选择一段连续的0或者1,删除它，拼接前后两部分成为新串，得到价值为a[删除的长度]（a为给定的数组）思路一个非常规的DP 考虑题目所给的操作，我们从中删除一段，再把前后拼接起来，如何设置状态？记录下断点的位置？不行，那样我们...

2019-01-28

0 503

【cf527 E】Minimal Diameter Forest

题意给你一个森林(若干棵树),向其中加边，使得最后形成一棵树，要求最后形成的树的直径最小，输出这棵树的直径和所加的边分析每加一条边，都可以将两棵树合并成一棵树，总共有t = n - m棵树也就是说我们需要在这t棵树里面，分别选一个点，将他们连接起来，使得最后形成一棵直径最小的树这...

2018-12-19

0 569

【模板】分治FFT

题意分析如果我们已经求得了 f[L],f[L+1] ... f[mid],他们均能对f[mid+1],f[mid+2]...,f[R]产生贡献对于x ∈ [mid+1,r] f[x] += \sum_{i=L}^{mid}(f[i]*g[x-i]) 等式右边满足卷积模式具体看代...

2018-11-30

0 481

【2018沈阳现场赛I】Distance Between Sweethearts

题意分析看似是期望问题，但是没有权重，就是求平均值，而答案要求乘上方案总数，所以这是一个计数问题考虑max,若三个绝对值分别为(x,y,z),则max = max(x,y,z) distance = max ^ Ib ^ (Ib+x) ^ Ab ^ (Ab + y) ^ Gb ^...

fwt 计数

2018-11-21

0 534

【2018沈阳现场赛k】Let the Flames Begin

题意有n个人围成一圈，编号1到n，从1号开始报数，每报到第k个，此人出列，下一个人再从1开始报数，求第m个出列的人的编号(n,m,k ≤ 1e18, m,k其中一个小于1e6) 分析我们知道，约瑟夫环的出队是有O(n)的递推算法的：f(n) = (f(n-1)+k-1)%n 约瑟夫环数学推...

数学递推约瑟夫环

2018-11-16

0 598