@[toc] A Eddy walk 题意 给定长度为n的环，编号,起始点在0，每一次可以向前向后走一格，问走完所有的格子之后所在的位置为M的概率。 分析 暴力打表找规律 const int maxn = 100 + 10; double p[maxn]; int n; bool vis[maxn]; void dfs(int x, int n, double pro) { if (pro < 1e-10 ) return ; for (int i = 0; i < n; ++i) if (!vis[i]) { int ...

2019牛客暑期多校训练营（第一场） A Equivalent Prefixes 题意： 给定长度相等的序列A,B，求最大的x，使得 和建立的笛卡尔树相同，笛卡尔树是递归构造的，从整个序列出发，查找最小值作为根，然后将序列分成两个部分，分治构造 分析： 对两个序列都跑一遍单调栈，如果在每个位置单调栈的元素的数量都相同，那么建立的笛卡尔树肯定相同，找到最大的x即可 参考代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40901481 B Integration 题意： 给定求 分析： 我们知道1....

题意 给定n行m列数，对于 [0,2^k-1] 内的数x求 分析 1. 求 Count(x) 来自Qls,代表 1的个数的奇偶性，如果连乘式中有一个为偶， 整个就为02. 把连乘展开得到 我们知道 3. FWT_XOR 正好就是我们需要的 (C1表示i&j中1的个数奇偶性为0，C2表示i&j的1的个数的奇偶性为1) 参考代码 const LL mod = 1e9 + 7; LL qpow(LL a, LL b) {LL s = 1; while (b > 0) {if (b & 1)s = s * a % mod; a = a * a % m...

题意 给定n行m列数，对于 [0,2^k-1] 内的数x求 分析 1. 求 Count(x) 来自Qls,代表 1的个数的奇偶性，如果连乘式中有一个为偶， 整个就为02. 把连乘展开得到 我们知道 3. FWT_XOR 正好就是我们需要的 (C1表示i&j中1的个数奇偶性为0，C2表示i&j的1的个数的奇偶性为1) 参考代码 const LL mod = 1e9 + 7; LL qpow(LL a, LL b) {LL s = 1; while (b > 0) {if (b & 1)s = s * a % mod; a = a * a % m...

B 筱玛爱阅读 题目地址题意：给定n个物品，m个方案，第i个方案包含个物品，现在共有n个价格，但不确定每一个物品属于哪一个价格。问买下所有物品需要的最小价格。分析：1. 简化问题，加入价格固定，就是一个状压dp，如果暴力递推，那么复杂度，不可接受，考虑采用枚举子集的方式复杂度2. 现在考虑价格不固定，先把物品从大到小排序，考虑新加入的最后一个子集优惠的是最后一个元素即可 参考代码： #include using namespace std; // 1 排序，从大到小 // 2 状压方案 // 3 枚举子集 const int maxn = 1 << 16; int a[m...

B 筱玛爱阅读 题目地址 题意：给定n个物品，m个方案，第i个方案包含 k i k_i ki​个物品，现在共有n个价格，但不确定每一个物品属于哪一个价格。问买下所有物品需要的最小价格。 分析： 简化问题，加入价格固定，就是一个状压dp，如果暴力递推，那么复杂度 ...

文章目录 Codeforces Round #558 (Div. 2) A - Eating Soup B- Cat Party C2 - Power Transmission (Hard Edition) D - Mysterious Code E - Magical Permutation F - Indecisive Taxi Fee Codeforces Round #558 (Div. 2) 退役打cf第一场 A - Eating Soup 注意考虑全面即可 int a,b;cin...

文章目录 原版刘汝佳的代码有很多maintain语句，个人感觉这样很不符合习惯，所以做出了修改，更符合我的习惯 1： 只保留一个update时的maintain语句 2：时刻记着延迟标记只是延迟往下的标记，并不延迟节点本身，时刻修改，当延迟标记下到某个地方，它的值就应该被修改 // UVa11992 Fast Matrix Operations（更易读、更具一般性的版本） // Rujia Liu // 注意：所有叶子上总是保留set标记而不会被清除（pushdown只能针对非叶结点），因此maintain函数对于叶子来说并不会重复累加addv[o] // 本程序在query的时候...

文章目录 A Stock Arbitraging B Tiling Challenge 1A&C Prefix Sum Primes 1B&D - Three Religions div1 E Election Promises A Stock Arbitraging 暴力 B Tiling Challenge 暴力 1A&C Prefix Sum Primes 先放2，再放一个1，之后把所有的2放完，再放1，除了2，其他的质数都是奇数 1B&D - Three Religions 序列自动机...

文章目录 E. Election Promises 题意： 分析: E. Election Promises 题意： 给定一棵有向树，每个点有一个权值，两个人进行操作，可以选择任意一个节点，将其权值减小为一个非负数，并且可以将其子节点修改为任意的权值，判定是否先手必赢，如果先手必赢，给定一个先手的方案 分析: 1 我们看到有向树，就可以联想到拓扑排序有关的问题，或者直接dfs进行图的遍历， 2 博弈问题，我们应该关注其是不是一个ICG（组合博弈问题），能否使用sg函数找出其规律并求解，当你找出了sg函数的时候，你就已经可...

文章目录 C. Tree Diameter D - Frog Jumping C. Tree Diameter 题意： 有一个n个点的树，但我们不知道树的形态，需要求树的直径，你可以进行不大于10次询问，每次询问包含两个集合 x,y ,(x 与y交集为空), 之后会给出x集合中的点到y集合中的点最远的距离 分析: 本题的关键就是划分集合，你需要进行的10次询问必须将任意两个点的距离都清楚，这时候有趣的事情发生了，我们知道不同的树，二进制表达肯定不相同，所以我们可以将节点x按照二进制上的每一位是否为1划分两个集合，巧妙地利用二进制的特点 int main...

文章目录 tsy’s number 推公式看这里 https://www.cnblogs.com/acjiumeng/p/10743919.html 推出来公式为 <munder> ∑ t = 1 ...

文章目录 D. Match Stick Game I. Max answer J Distance on the tree E card Game D. Match Stick Game https://blog.csdn.net/weixin_38686780/article/details/89459343 I. Max answer https://blog.csdn.net/weixin_38686780/article/details/89457254 J Distance on the tree https://blog....

文章目录 D. Match Stick Game 分析 代码 D. Match Stick Game 分析 赛中也不会做，赛后别人说是dp，也思考了好一会儿，本来以为代码会比较难码，结果一发就过了 d p [ i ] [ ...