codeforces专题
Codeforces Round #240 (Div. 2) E分治算法探究1
Codeforces Round #240 (Div. 2) E http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一： 划分子问题。 图二： 分而治之，=> 合并 。 图三： 回溯：
Codeforces Round #261 (Div. 2)小记
A XX注意最后输出满足条件，我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m
Codeforces Beta Round #47 C凸包 （最终写法）
题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op
Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内
题目点击打开链接 凸多边形A， 多边形B， 判断B是否严格在A内。 注意AB有重点 。 将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法，只需在求凸包的时候， <= 改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int
Codeforces 482B 线段树
求是否存在这样的n个数； m次操作，每次操作就是三个数 l ，r，val a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作 最后判断 a[l] & a[l+1] &......&a[r] 是否= val import ja
Codeforces Round 971 (Div. 4) (A~G1)
A、B题太简单，不做解释 C 对于 x y 两个方向，每一个方向至少需要 x / k 向上取整的步数，取最大值。 由于 x 方向先移动，假如 x 方向需要的步数多于 y 方向的步数，那么最后 y 方向的那一步就不需要了，答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>
Codeforces#295(Div.2)A、B(模拟+BFS)
解题报告链接：点击打开链接 C. 题目链接：点击打开链接 解题思路： 对于给定的字符串，取出现次数最多的字母（可以同时有多个）。由这些字母组成长度为n的字符串，求有多少种组合。最后用数学知识即可。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <climits>
Codeforces Round #281 (Div. 2)A（构造+暴力模拟）
题目链接：http://codeforces.com/problemset/problem/493/A 解题思路： 暴力的判断，分三种情况去判断即可。注意如果之前已经被罚下场后，那么在后面的罚下情况不应该算在输出结果内。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <co
Codeforces Round #182 (Div. 2)A（水题）
题目链接：http://codeforces.com/contest/302/problem/A 解题思路： 只要通过重新排列使区间内和为0即是1，否则是0. 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#inc
Codeforces Round #233 (Div. 2)A（构造）
题目链接：http://codeforces.com/contest/399/problem/A 解题思路： 构造出来即可，考虑p-k和p+k两个边界分别于1和n作比较，对左右符号特殊处理。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include
Codeforces Round #247 (Div. 2)A（构造）
题目链接：http://codeforces.com/contest/431/problem/A 解题思路： 构造出来即可。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#include <string>#inc
Codeforces Round 970 (Div. 3)(ABCDEF)
Codeforces Round 970 (Div. 3) A:Sakurako's Exams 签到 题意:给定1,2的数量,判断是否能用加减符号使得这些1,2计算出0 void solve(){cin>>n>>m;if(n%2)cout<<"NO\n";else{if(m%2==0||n)cout<<"YES\n";else cout<<"NO\n";}return ;} B:S
Codeforces Round 970 (Div.3)
传送门 A. Sakurako's Exam 模拟，两个 2 能够自己变成 0，因此将 b 对 2 取余；多余的 2 还能跟两个 1 组合在一起变成 0；最后判断剩余的 1 的数量是奇数还是偶数。 #include <bits/stdc++.h>using namespace std;inline int read() {int x = 0, f = 1; char c = getchar
数据结构 - Codeforces Round #353 (Div. 2) D. Tree Construction
Tree Construction Problem's Link ---------------------------------------------------------------------------- Mean: 给定n个数，按照构造Binary Search Tree的方式来构造BST树，按顺序输出每一个非root结点的父节点的值。 analyse
【CodeForces】266E More Queries to Array... 线段树
E. More Queries to Array... time limit per test 5 seconds memory limit per test 256 megabytes input standard input output standard output You've got an array, consisting of n
【Codeforces】449B Jzzhu and Cities 最短路
传送门：【Codeforces】449B Jzzhu and Cities 题目大意：一个n个节点的无向图，节点编号1~n（其中1为起点），其中有m条普通普通，还有k条从起点出发的特殊边，问最多去掉多少的特殊边使得从起点到其他所有点的最短路径的距离不变。 题目分析：这题的意图很明显啊，就是要我们去求最短路啊。那么怎么求会比较好呢？其实我们可以很容易的发现如果从起点通过边权为c的特殊
【CodeForces】240F - TorCoder 线段树
传送门：【CodeForces】240F - TorCoder 题目大意：给你一个长度为n的字符串（下标从1~n）。现在给你m次操作，每次操作是一个区间【L，R】，如果这个区间内的字符串可以重排列回文串，那么这次操作就是将其变成回文串，如果可以构造多个，那么排列成字典序最小的。如果这次操作不能构成回文串，那么忽略它。最后你要输出字符串的最终形态。 题目分析：叉姐群有人提问的一道题，
【codeforces】163E. e-Government AC自动机+树状数组
传送门：【codeforces】163E. e-Government 题目分析：感觉到现在再做类似题目已经感觉很水了= =。。。这题也就是构建了fail指针树以后树状数组维护就好了。10^6个字母的意思就是说我们可以随便搞。。。 代码如下： #include <cstdio>#include <cstring>#include <algorithm>using n
【codeforces】55D. Beautiful numbers 数位DP
传送门：【codeforces】55D. Beautiful numbers 题目分析：被每一位整除则用二进制记录已经包括的数字的个数，以及对2520取模后的状态。由于对5整除当且仅当最后一个数为0或5，对2整除当且仅当最后一个数为偶数，且1~9的最小公倍数为2520，不包括2，5后的最小公倍数为252，所以除最后一层对2520取模，其余时候都对252取模即可。由于整除的状态有限，最多只有
【codeforces】480E Parking Lot 线段树+DP
传送门：【codeforces】480E Parking Lot 题目分析：很早以前在同学助攻下写出来的，想想还是放出来好了，是个不错的思想。 原题是在动态将可行区域变成不可行区域的同时求全局最大子正方形，n，m，k至多2000。 既然只有加点，于是我们离线，倒着来，这样便只有删点。 我们给每个节点（i,j）保存它向上能延伸的距离U[i][j]以及向下能延伸的距离D[i][j
【codeforces】Codeforces Round #274 (Div. 2)
A. Expression 考虑六种运算，取最大值即可，注意题目特别说明数的位置不能交换。 #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;const int INF = 0x3f3f3f3f ;int a , b , c ;void solve () {int maxv = -I
【codeforces】Codeforces Round #277 (Div. 2) 题解
传送门：Codeforces Round #277 (Div. 2) 486A. Calculating Function 裸公式= = #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;LL n ;int main () {whi
【codeforces】484E. Sign on Fence 可持久化线段树
传送门：【codeforces】484E. Sign on Fence 题目分析：看了题解才会呢，感觉太巧妙了~ 先对高度从高到低排序，然后构造可持久化线段树，每个节点保存一个高度下对应区间的左连续最大1个数，右连续最大1个数，区间最长连续1个数，然后查询一个区间内最长连续1长度就是线段树区间合并操作。每次询问【L，R，W】就是二分询问的高度（每个高度是一棵线段树），然后看询问区间的连续
【codeforces】482E. ELCA 动态树
传送门：【codeforces】482E. ELCA 题目大意：给一棵有根树，树根为1，每个节点有权值s[v]，q次操作，每次要么将以v为根的子树接到u下，要么令s[v]=t，每次操作以后，输出等概率选择两个点i,j（i可以等于$）后权值的期望，权值即s[{lca(i,j)}]值。 题目分析：写了两天啊啊啊啊！！！终于搞出来了。。。思考这题算法的时候总感觉脑子不够用啊= =于是好
【codeforces】293E. Close Vertices 点分治+树状数组
传送门：【codeforces】293E. Close Vertices 题目分析：找一棵树上有多少条路径长度不超过l且边权和不超过w的路径。 我们用点分治处理。 分治每一层，对每一个重心，预处理出到重心距离d，边权和为w的所有路径。将路径按照w排序，然后我们用双指针扫描数组，同时维护一个树状数组，树状数组中保存的是到重心距离为d的条数。因为有贡献可能来自子树，于是我们对子树进行同样的
【codeforces】gym 101137 K - Knights of the Old Republic【用最小生成树对图做集合dp】
题目链接：【codeforces】gym 101137 K - Knights of the Old Republic 考虑对图集合dp，一个连通块的dp值为两个连通块的值的和或者强制加一条新边后的最小值，取个最小值（边从小到大枚举，则强制加一条最大的边会导致连通块内较小的边一定都选，则会构成一个生成树）。用kruskal实现这个dp过程即可。 #include <bits/stdc++.h>