UPD .10.23 shift-and (2题)

Codeforces 训练

现在已经完成了：

191

【Codeforces Round #377】 (6/6)

Div 2 A Buy a Shovel 模拟

Div 2 B Cormen — The Best Friend Of a Man 贪心

Div 2 C Sanatorium 暴力枚举每种情况

Div 2 D Exams 二分+贪心

Div 2 E Sockets 贪心，考虑每个pi都用最小能覆盖它的si

Div 2 F Tourist Reform 双连通分量缩点，将点数最多的那个点作为汇点，倒着遍历整个缩点后的树

【Codeforces Round #376】 (6/6)

Div 2 A Night at the Museum 模拟

Div 2 B Coupons and Discounts 贪心+构造

Div 2 C Socks 并查集搞出最终状态，然后贪心出答案

Div 2 D 80-th Level Archeology 找出每个位置变成不合法的区间，然后找是否有一个点未被覆盖。

Div 2 E Funny Game 裸dp

Div 2 F Video Cards 暴力出以i为first video时，最大的答案，具体维护一个前缀和就行了

【Codeforces Round #375】 (6/6)

Div 2 A The New Year: Meeting Friends 模拟

Div 2 B Text Document Analysis 模拟

Div 2 C Polycarp at the Radio 贪心

Div 2 D Lakes in Berland BFS+并查集

Div 2 E One-Way Reform fleury算法乱搞

Div 2 F st-Spanning Tree 贪心+并查集乱搞

【Codeforces Round #373】 (5/6)

Div 2 A Vitya in the Countryside 模拟，分类讨论

Div 2 B Anatoly and Cockroaches 模拟，分类讨论

Div 1 A Efim and Strange Grade 贪心取最靠前的可以进位的数字

Div 1 C Sasha and Array 线段树维护f[a[n]-1],f[a[n]]，lazy标记为矩阵

Div 1 D Andrew and Chemistry 树同构，记忆化搜索

Div 1 E Matvey’s Birthday 待补。。

【Codeforces Round #372】 (6/7)

Div 2 A Crazy Computer 模拟

Div 2 B Complete the Word 模拟

Div 1 A Plus and Square Root 构造发现答案为 i∗(i+1)∗(i+1)−(i−1)

Div 1 B Complete The Graph 先二分前p条边需要被赋非无穷大的值，再二分出第p条边的边权。

Div 1 C Digit Tree 树分治+exgcd

Div 1 D Create a Maze 神奇的构造题

Div 1 E Complete the Permutations 待补。。

【Codeforces Round #371】 (6/7)

Div 2 A Meeting of Old Friends 模拟

Div 2 B Filya and Homework 模拟

Div 1 A Sonya and Queries STL，将读入数字转换成表示奇偶的二进制形式，map搞搞就行了

Div 1 B Searching Rectangles 二分，先求出两个矩形的分割线，然后对两个子区间再二分，求出每个矩形的边界

Div 1 C Sonya and Problem Wihtout a Legend STL，列出动规方程，用priority_queue维护最优决策

Div 1 D Animals and Puzzle 二分，2D ST表

Div 1 E Sonya Partymaker 待补。。

【Codeforces Round #370】 (5/5)

Div 2 A Memory and Crow 模拟

Div 2 B Memory and Trident 模拟

Div 2 C Memory and De-Evolution 反向思考，贪心

Div 2 D Memory and Scores DP，前缀和优化

Div 2 E Memory and Casinos 线段树，概率，差分

【Codeforces Round #369】 (5/5)

Div 2 A Bus to Udayland 模拟

Div 2 B Chris and Magic Square 模拟

Div 2 C Coloring Trees 动态规划

Div 2 D Directed Roads 组合数学

Div 2 E ZS and The Birthday Paradox 数论，概率，类似于扩展lucas

【Codeforces Round #368】 (5/5)

Div 2 A Brain’s Photos 模拟

Div 2 B Bakery 最短路径

Div 2 C Pythagorean Triples 毕达哥拉斯三元组

Div 2 D Persistent Bookcase 离线暴力搞

Div 2 E Garlands 二维树状数组暴力搞

【Codeforces Round #367】 (5/5)

Div 2 A Beru-taxi 模拟

Div 2 B Interesting drink 二分

Div 2 C Hard problem DP

Div 2 D Vasiliy’s Multiset trie树

Div 2 E Working routine 裸十字链表

【Codeforces Round #361】 (5/5)

Div 2 A Mike and Cellphone 模拟

Div 2 B Mike and Shortcuts BFS

Div 2 C Mike and Chocolate Thieves 二分

Div 2 D Friends and Subsequences 二分+ST表

Div 2 E Mike and Geometry Problem 扫描线

【Educational Codeforces Round 16】 (6/6)

A King Moves 模拟

B Optimal Point on a Line 排序

C Magic Odd Square 构造

D Two Arithmetic Progressions 数论，扩展欧几里得

E Generate a String DP，主要分析删除操作的价值

F String Set Queries AC自动机，首先删除操作可以看做价值-1的串，然后考虑强制在线的做法。我们维护两个AC自动机，一大一小，阈值为600。每次暴力重构小的AC自动机，当小AC自动机大小超过阈值时，将其全部扔到大AC自动机中，暴力重构大的AC自动机，答案就是两个AC自动机的答案之和。

【Educational Codeforces Round 15】 (6/6)

A Maximum Increase 模拟

B Powers of Two 预处理后STL

C Cellular Network 二分+two pointer

D Road to Post Office 贪心

E Analysis of Pathes in Functional Graph 倍增

F T-Shirts 分块暴力去做

【Educational Codeforces Round 14】 (6/6)

A Fashion in Berland 模拟

B s-palindrome 模拟

C Exponential notation 模拟

D Swaps in Permutation 并查集

E Xor-sequences 矩阵倍增

F Couple Cover 暴力出奇迹系列

【Educational Codeforces Round 13】 (6/6)

A Johny Likes Numbers 模拟

B The Same Calendar 模拟

C Joty and Chocolate 贪心

D Iterated Linear Function 矩阵倍增

E Another Sith Tournament 状压dp

F Lena and Queries cdq分治+凸壳上三分

【Educational Codeforces Round 12】 (6/6)

A Buses Between Cities 模拟

B Shopping 模拟

C Simple Strings 构造

D Simple Subset 构造

E Beautiful Subarrays trie树

F Four Divisors 数论，dp求出前n个数内有多少个质数

【Educational Codeforces Round 11】 (6/6)

A Co-prime Array 构造

B Seating On Bus 模拟

C Hard Process 暴力two pointer

D Number of Parallelograms 暴力枚举线段，map存起来

E Different Subsets For All Tuples 很好的组合数学题。考虑我们现在计算出了长度为n-1的序列的答案ans，考虑长度为n的序列的情况。由两种构成，第一种是虽然序列长度增加，但是本质不同的子列长度没有变。第二种是，序列长度增加，并且对之前本质不同的子列都加上新添进来的字符。但是这两部分会有重合，重合部分是ans-空串个数（因为新添进来的字符形成的子列，部分会变成第一种的情况，但是空串不会）。即长度为n的时候的答案为ans∗(2m−1)+mn−1。

F Bear and Bowling 4 分治，考虑所选序列一定经过当前线段中点的情况，然后整理式子，可以得到bL+aLxR+yR的情况，然后在凸包上三分即可。

【Educational Codeforces Round 10】 (6/6)

A Gabriel and Caterpillar 模拟

B z-sort 构造

C Foe Pairs 双指针

D Nested Segments 树状数组倒序搞

E Pursuit For Artifacts tarjan求边的双联通分量，然后并查集维护

F Ants on a Circle 暴力乱搞

【Educational Codeforces Round 9】 (6/6)

A Grandma Laura and Apples 模拟

B Alice, Bob, Two Teams 前缀和，暴力

C The Smallest String Concatenation 字符串拼接经典的比较方法return a+b<<script type="math/tex" id="MathJax-Element-6"><</script>b+a

D Longest Subsequence nlogn暴力求解

E Thief in a Shop 动态规划，转换思路，首先求每个数与最小数的差，然后我们dp出形成某个差，最少需要的物品数，然后再反过来判断其是否小于等于k。不难发现，只要其值小于等于k，必然存在一种构造方案

F Magic Matrix 最小生成树，容易发现matrx为MAGIC，至少满足邻接矩阵的形式，之后我们可以推出MAGIC的充要条件，即任意一个点对(i,j)在MST上的路径的边的最大值等于a[i][j]。

【Educational Codeforces Round 8】 (6/6)

A Tennis Tournament 模拟

B New Skateboard 裸dp

C Bear and String Distance 贪心构造

D Magic Numbers 数位dp

E Zbazi in Zeydabad 利用bitset暴力乱搞

F Bear and Fair Set 首先考虑网络流做法。有两个集合A,B。A[0]表示模5余0的元素的集合，A[1],A[2],A[3],A[4]以此类推。从源点向每个点连一条容量为n5的边。然后B是表示每个hint的区间，向汇点连一条容量为区间内元素个数的边。然后每个A中的点向每个B中的点连一条容量为这个区间内有多少个模5余数为0,1,2,3,4的个数的边。若最大流为n，则fair。我们可以考虑用Hall theorem来简化这个过程，只要考虑A的每个子集S，|S]<=|WS(B)|是否成立即可。

【Educational Codeforces Round 7】 (6/6)

A Infinite Sequence 模拟

B The Time 模拟

C Not Equal on a Segment 维护next数组即可

D Optimal Number Permutation 构造

E Ants in Leaves 贪心

F The Sum of the k-th Powers 拉格朗日插值，由于分母的特殊性，可以O(n)搞出系数

【Educational Codeforces Round 6】 (6/6)

A Professor GukiZ’s Robot 模拟

B Grandfather Dovlet’s calculator 模拟

C Pearls in a Row 贪心，维护剩余部分还有几组相同数字

D Professor GukiZ and Two Arrays 双指针

E New Year Tree DFS序，把颜色压位以后用线段树维护

F Xors on Segments 暴力DP

【Educational Codeforces Round 5】 (5/6)

A Comparing Two Long Integers 模拟

B Dinner with Emma 模拟

C The Labyrinth 暴力

D Longest k-Good Segment 双指针

E Sum of Remainders 根号n分段搞

F Expensive Strings 待补。。

【AIM Tech Round 3】 (7/7)

Div 2 A Juicer 模拟

Div 2 B Checkpoints 模拟&注意特殊情况

Div 1 A Letters Cyclic Shift 简单dp

Div 1 B Recover the String 构造，特殊情况比较多

Div 1 C Centroids 树形dp

Div 1 D Incorrect Flow 费用流，很经典的建模方法

Div 1 E Student’s Camp 概率，组合数学，动态规划，问题的难点主要在于推出合法的充要条件，之后就可以一行一行进行dp

【Bubble Cup 9 - Finals [Online Mirror]】 (6/9)

A Festival Organization 待补。。

B R3D3’s Summer Adventure 贪心

C Potions Homework 排序不等式

D Dexterina’s Lab 博弈+矩阵倍增

E Paint it really, really dark gray 构造

F Heroes of Making Magic III 待补。。

G Underfail 最大费用最大流

H Pokermon League challenge 随机答案（期望保证正确性）

I Cowboy Beblop at his computer 待补。。

【Experimental Educational Round: VolBIT Formulas Blitz】 (18/18)

A Again Twenty Five! 模拟

B Moore’s Law 模拟

C Lucky Numbers 模拟

D Hexagons! 组合数学

E A rectangle 推公式

F Selection of Personnel 组合数学

G Challenge Pennants 组合数学

H Benches 组合数学

I Parking Lot 组合数学

J Divisibility 模拟

K Indivisibility 模拟

L Cracking the Code 模拟

M Turn 模拟

N Forecast 二次方程的解

O Arrow 模拟

P Area of a Star 计算几何

Q Pyramids 计算几何

R Game 博弈论，对称构造

【Wunder Fund Round 】 (6/7)

A Slime Combining 模拟

B Guess the Permutation 构造

C Constellation 计算几何，贪心选取距离1、2点形成直线最近的那个点作为第三个点

D Hamiltonian Spanning Tree 树的最小路径覆盖，模拟

E Robot Arm 计算几何，线段树维护

F Double Knapsack 构造，利用鸽巢原理

G Combining Slimes 待补。。

【- CT S03E02: Codeforces Trainings Season 3 Episode 2 - - OpenCup, Volga Grand Prix】 (9/12)

A HHPaint 极角排序

B Square Root 用py自带函数

C Interesting Places 待补。。

D Road to Home 待补。。

E Ant and apples 树上dp

F Square 待补。。

G Pair 暴力

H The Fence 模拟

I Painting the natural numbers 构造

J Selection 模拟

K Parquet 数学

L Closing the Loop 贪心

【- CT S03E01: Codeforces Trainings Season 3 Episode 1 - Benelux Algorithm Programming Contest (BAPC 10)】 (9/12)

A Gene Shuffle 模拟

B Top 2000 裸dp

C The Twin Tower 状压dp

D Collatz 模拟

E Clocks 待补。。

F Maze Recognition DFS+BFS

G Snooker 模拟

H Pie Division 待补。。

I Keylogger STL list

J Wrong Answer 匈牙利

K Сunning Minister 待补。。

L 01 贪心

【 ACM Amman Collegiate Programming Contest】 (9/12)

A Coins 裸背包

B The Little Match Girl 贪心，先全改成1，然后用多余部分去造9，然后是7，如果还多余，再分类讨论就行。

C Bored Judge 用线段树维护下每一时刻的优胜者

D Rectangles 先dp求出每个位置，向下最多能扩展多少，记为d[i][j]。然后计算每个位置作为右上角对答案的贡献ff[i][j]。如果当前位置与前一位置相同：若d[i][j]>d[i][j−1]，则ff[i][j]=ff[i][j−1]+d[i][j],否则找到第一个比d[i][j]小的位置，ff[i][j]=ff[i][k]+(j−k)∗d[i][j]。

E Ya Rajaie and Books 模拟

F Exchange 贪心

G Notes 待补。。

H Cinema 模拟

I Simple Robot 两维分开考虑，然后发现每维都是单峰的，三分下即可

J Divisible Numbers 离线，用树状数组维护区间内某个数的倍数的个数。然后容斥原理，不过注意如果需要考虑2，就不用考虑4 6 8 10，以此类推，一次需要考虑的数字最多为5个，O(25∗q∗logn)

K Topological Sort 待补。。

L Starry Night 待补。。

Bestcoder 训练

现在已经完成了：

5

【BestCoder Round #86】 (5/5)

1001 Price List 模拟

1002 NanoApe Loves Sequence 排序

1003 NanoApe Loves Sequence Ⅱ 双指针

1004 Keep In Touch 动态规划优化，分步dp

1005 Price List Strike Back 动态规划，整体二分

专项训练

现在已经完成了：

7

【树上点分治】 (3/3)

bzoj2152 聪聪可可 裸点分

bzoj2599 Race 裸点分

bzoj1468 Tree 点分+treap

【动态规划】 (2/2)

CF533B Work Group 在树上背包，f[x][0]表示奇数个点合法方案中的最大值，f[x][1]表示偶数个点合法方案中的最大值。

CF234F Fence 滚动数组，f[i][j][k]表示当前到i，已经用了j个第一种燃料，最后一种颜色为k的最小花费。

【shift-and算法】 (2/2)

字符串匹配算法，其实就是暴力+bitset优化，主要的匹配方式：

dp[i]=dp[i-1]<<1&mt[t[i]]，mt[t[i]]表示能对t[i]匹配的位置有哪些。顾名思义，也叫shift(<<)-and(&)算法。

hdu5716 带可选字符的多字符串匹配 直接做

hdu5745 La Vie en rose dp[0] dp[1]分别表示交换和没交换。。然后就是裸题了