Category Archives: 线段树

CodeForces 480E Parking Lot (线段树,dp)

一个N * M的矩阵,里面有.和X,给出若干询问,询问将(x, y)位置变成X,求剩下部分的矩阵由.构成的最大 …

HDU 4117 GRE Words (AC自动机,dp,线段树)

给出n个字符串,以及格子的权值,按照顺序取出若干个字符串,要去前一个字符串是后一个字符串的子串。计算最大权值和 …

JAG Practice Contest for ACM-ICPC Asia Regional 2016 部分题解

这场的题目质量挺高的,学习了一些新的姿势。 A – Best Matched Pair 给出n个数 …

Codeforces 719E Sasha and Array (线段树,矩阵乘法)

给出n个数字,然后两个操作:1. l r x 将区间[l, r]的数字都加上x; 2. l r 计算区间[l, …

2016 ACM/ICPC Asia Regional Shenyang Online

1002 – List wants to travel 给出n个点的树,每条边有一种颜色,两种操作 …

Codeforces 712 E. Memory and Casinos (dp,线段树)

有n个位置,在i位置向右的概率是pi(若右边没数字表示离开点i),向左的概率是(1 – pi),给 …

CSU 1809 Parenthesis (线段树)

给出一个括号串,然后q个询问计算,询问要求交换a和b位置的括号,问交换后的串是否满足括号匹配。 将(看成1,) …

2016 Multi-University Training Contest 5

1001 – ATM Mechine 一个有在ATM机偷钱,他只知道钱的上限是K,他每次可以选择取 …

HDU 3698 Let the light guide us (dp,线段树优化)

n * m的两个矩阵,一个cost[i][j],一个magic[i][j],每行选一个数字,使得最后数字总和最 …