codechef专题

【codechef】 Prime Distance On Tree【求树上路经长度为i的路径条数】【点分治+FFT】

传送门：【codechef】 Prime Distance On Tree 点分治+FFT水题……竟然n*n爆int没发现…… 而且NTT TLE，FFT跑的超级快…… my code: my~~code: #include <bits/stdc++.h>using namespace std ;typedef long long LL ;#define clr( a , x ) m

Codechef Sam and Sequences（单调队列）

题目链接:http://www.codechef.com/problems/PRYS03/ 这题只要考虑每个数字，最左和最右分别能延伸到的位置，然后就能计算出每个数字需要计算的次数，由于数字可能重复，所以对于左边维护到不大于的第一个数字位置，右边维护到小于的第一个数字位置，然后维护好后，在扫一遍计算总和即可代码： #include <cstdio>#include <cstring>

codechef August Challenge 2014 第五个题目

题意：点击打开链接题目链接：点击打开链接思路：入门的状态压缩，如果按照行一行一行下来（选衣服）去选的话状态太多，无法压缩，考虑到题目中n比较小，所以改用按照列一列一列推，把人压缩到二进制里面，1表示这个人已经选了，0表示还没有选，然后递推就可以达到答案！ #include<set>#include<queue>#include<cmath>#include<cstdio

CodeChef TechFest 2013 Balancing nature（暴力）

题目链接：http://www.codechef.com/TCFST13/problems/TCFST06 我表示只能刷刷水题了~~ 计算一个数组变成前面都负数后面都正数的最小操作个数。枚举中间点就ok 代码如下 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace st

[CodeChef Jump]Jump mission

Jump mission 题解简单树套树。首先看到这道题，我们很容易想到 d p dp dp。设 d p i dp_{i} dpi表示选择跳到了第 i i i座山时总的消耗能量的最小值，容易得到 d p dp dp转移式， d p i = min ⁡ j < i ∧ p j < p i ( d p j + ( h i − h j ) 2 + a i ) = min ⁡ j < i

【bzoj3514】【Codechef MARCH14 GERALD07加强版】【lct+主席树】

Description N个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。 Input 第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。接下来M行，代表图中的每条边。接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为L xor

【bzoj4260】【Codechef REBXOR】【trie】

Description Input 输入数据的第一行包含一个整数N，表示数组中的元素个数。第二行包含N个整数A1,A2,…,AN。 Output 输出一行包含给定表达式可能的最大值。 Sample Input 5 1 2 3 1 2 Sample Output 6 HINT 满足条件的(l1,r1,l2,r2)

【codechef】 Historical Junctions（开放想方法，分类）

Input:24 41 22 33 44 14 61 22 33 44 11 32 4Output:4 41 52 63 74 80 0 http://www.codechef.com/SNCK151A/problems/HISTJUNK 当n<3||(n==3&&m==3)时：虽然4的这种情况也是，不过简单起见我们也可以选

BZOJ4260 Codechef REBXOR【01字典树】

4260: Codechef REBXOR https://www.lydsy.com/JudgeOnline/problem.php?id=4260 时间限制: 10 Sec 内存限制: 256 MB 题目描述输入输入数据的第一行包含一个整数N，表示数组中的元素个数。第二行包含N个整数A1,A2,…,AN。输出输出一行包含给定表达式可能的最大值。

[BZOJ4260] Codechef REBXOR

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=4260 题目大意给定序列,求最大的 (xl1 xor xl1+1 xor ...xr1)+(xl2 xor xl2+1 xor ...xr2) (x_{l1}~xor~x_{l1+1}~xor~...x_{r1})+(x_{l2}~xor~x_{l2+1}~xor~...x_{r2})

贪心、dfs--Codechef TKCONVEX

题目大意： n 根木棍长度分别为ai，现在想从中选出2k 根组成两个面积大于0 的凸k 边形，请找出一组解或判断无解 2k<=n<=1000 , 3<=k<=10 , 1<=ai<=109 solution： k 条边成为一个凸多边形的充要条件是最长边小于其他边之和将木棍按长度排序后，按上述条件可知可行解要么是两段不相交的连续的子序列，要么是一个连续的长为2k 的子序列使用

刷漆（Codechef October Challenge 2014：Remy paints the fence）

【问题描述】 Czy做完了所有的回答出了所有的询问，结果是，他因为脑力消耗过大而变得更虚了:)。帮助Czy恢复身材的艰巨任务落到了你的肩上。正巧，你的花园里有一个由N块排成一条直线的木板组成的栅栏，木板从左到右依次标号1到N。这N块木板中，有M块木板前面放着一桶油漆。油漆有不同的颜色，每种颜色可以由一个大写字母表示(A到Z)。而你要求Czy用他的油漆刷子给栅栏刷上油漆。已知Czy会选择一个前

[codechef July Challenge 2017] Pishty and tree

PSHTTR: Pishty 和城堡题目描述Pishty 是生活在胡斯特市的一个小男孩。胡斯特是胡克兰境内的一个古城，以其中世纪风格的古堡和非常聪明的熊闻名全国。胡斯特的镇城之宝是就是这么一座古堡，历史上胡斯特依靠这座古堡抵挡住了疯人国的大军。对于 Pishty 来说，真正吸引他的是古堡悠长的走廊和高耸的钟楼，以及深藏于其中的秘密……古堡可以用一棵 N 个节点的树的描述，树中有 N − 1 条无