个人排位赛1

UVA-1395 生成树

问题：给定一个无向图，求最大边权与最小边权差值最小的生成树

解：假定该生成树里权值最小的边为$m$，此时最优解中最大的边对应着以$m$为最小边的最小生成树$tree_{min}$的最大边（假设存在另一合法生成树$tree_p$使得$max\_edge(tree_p) < max\_edge(tree_{min})$，由Kruskal算法的证明可知，$tree_p$中有环，且存在多于1个联通分量，故不合法）

Kruskal证明

假设存在某一步，算法选择了边$E_1$但是应选择$E_2$才能得到最小生成树$tree_{min}$，那么我们在$tree_{min}$中加入边$E_1$，此时该图中存在一个环，且环中存在长度大于$E_1$的边，此时将该边替换为$E_1$则可得到更优的生成树。

HYSBZ-2257 裴蜀定理 (opens new window)

该类倒水问题可以简化为$ax + by + cz + ... = C$

问题：给定$n$个瓶子，从中选出$k$个，使得用这$k$个瓶子倒出的水的最小值最大

答：由裴蜀定理知$ax + by + cz + ...=C$有解当且仅当$gcd(a, b, c, ...)|C$

问题转化为从$n$个数中选出$k$个使得$gcd(v_1, v_2, ..., v_k)$最大

那么我们求出所有数字的所有因子，并从大往小遍历，若因子个数多于$k$，即为答案

Codeforces 757C 算法实现

题目不难，问题在于如何分组

由于$\sum{g_i}<5*10^5$，因此，我们可以使用vector<int> p[maxm]，对于在i馆的宝可梦j，我们向p[j]中push_back一下i

那么如果i可以转化为j，既有p[i] == p[j]（直接比较vector）

sort一下再比较就好

HDU6346 KM算法(二分图最佳完美匹配) (opens new window) 链接2 (opens new window) 链接3 (opens new window)

题意：求权值和最小的完全匹配

把cost取一下反即可

注意，这题不能使用dfs版本的km！！

关联

匈牙利算法 (opens new window)

Ford-Fulkerson (opens new window)

BZOJ1006 弦图 (opens new window) 链接2 (opens new window)

题意：给定一张弦图，要求相邻的点颜色不同，请你根据ppt (opens new window)第69页求出最小染色数

题解：根据ppt，弦图的最小染色数=最大团的点数

问题转变成了求最大团的点个数

注意：

1. PPT中的"诱导子图"即"导出子图"(induced subgraph)
2. 图的极大团/最大团为NP-C问题，弦图的极大团可以在多项式复杂度的时间内完成
3. ？？？

BZOJ1499 三维DP

题意：累了，自己看吧

题解：

设$dp[i][x][y]$为第$i$个时间段后，以$(x,y)$为结束位置时，走过的最长路程

假设第$i$个时间段向右倾斜，那么

$dp[i][x][y] = max(dp[i-1][x][s] + y - s)$ for s in range(max(y-时间长度, left_most_block), y+1)

那么，对于固定的$i, x$，可以用单调队列来维护$dp[i-1][x][s]$（边dp边计算上一时间段的单调队列信息）

代码较长，需要小心低级错误

小技巧: memset(v, 128, sizeof v) 可用来填充-inf

个人排位赛2

BZOJ5028 线段树上GCD

题解： $gcd(a, b, c, ...)=gcd(a, b-a, c-b, ...)$

因此可以用线段树维护差分数组、区间gcd

当对$(l, r)$加上$x$，相当于$v_l+=x,v_{r+1}-=x$

对$(l, r)$统计答案，即求$gcd(\sum_i^l{v_i}, gcd(v_{l+1}, ..., v_r))$

注意：注意在线段树中特判$ql>qr$的情况（当查询$l=r$时可能出现）

Gym101237A 线段树/主席树

题解：

巧用线段树

用线段树维护出现/未出现的值，线段树上每一个点代表其出现的时间，未出现的赋值为-inf，维护时间的最小值。

考虑对查询的区间进行排序，使得区间的右端点依次增大。从1到n依次遍历数组$A$，并向线段树中插入该数字。对于区间查询$(l, r)$，只需寻找线段树上出现时间小于$l$的位置即可。

主席树

事实上，主席树的做法同线段树差不多，只是不需要对查询区间排序而已（支持在线查询！！）。

计蒜客41413 (opens new window) 生成函数

对不起，不会

关联

整数划分 (opens new window)

广义牛顿二项式

泰勒展开

HDU6661 后缀数组

题解:

先去做POJ3693，然后注意以下几点

1. HDU给了6秒的时限。向左/右拓展请大胆的用两个SA(减少分类讨论的难度)

2. 对k为1的情况进行特判(要保证循环节出现)

3. 求向左拓展的长度时别忘了字符串时翻转过来的，对应的位置应该从$pos$变为$len-pos-1$

4. 为了避免右端重复统计，遍历$1 ... n$，当发现合法子串$str[l, r]$时，下一次应当跳转到位置$r+1$

5. 在遵循规则3的情况下，对于当前遍历的长度$i$，向左拓展的长度$lpart<i$，从而保证了左端不会重复统计

3中说的合法子串指的是向左拓展长度$lpart$+向右拓展长度$rpart \ge i$的后缀 （即连续的子串）

ac代码如下

//这里是头文件
struct suffix_array{
	// 这里是求后缀数组的代码
}SA[2];

struct RMQ{
    // 这里是求rmq的代码
}rmq[2];

ll solve(){
    ll k, len;
    cin >> k >> SA[0].s;
    len = strlen(SA[0].s);
    if(k == 1) return (len + 1) * len / 2; 
    for(int i=0; i<len; i++) SA[1].s[i] = SA[0].s[len-i-1]; // 反转字符串
    SA[1].s[len] = 0;
    SA[0].suffixArray(len, 128), SA[1].suffixArray(len, 128); // 128是字符集大小
    rmq[0].build(len, 0), rmq[1].build(len, 1);
    ll ans = 0;
    for(int i=1; i<len; i++){
        int s = 0;
        while(s + i < len){
            int lpart = rmq[1].query(len-s-1, len-(s+i)-1);
            int rpart = rmq[0].query(s, s+i);
            if(lpart + rpart < i) {s+=i; continue;} // 不能形成一个连续的子串，跳过
            int total_len = lpart + rpart + i - 1;
            if(total_len >= k * i){
                ans += total_len - k*i + 1;
            }
            s = s + i + rpart;
        }
    }
    return ans;
}

POJ3693 子串循环节最大重复次数

见""题解们"

个人排位赛3

BZOJ3894 最小割/建图

思路：关键在于建图

$S$集为文科，$T$集为理科，则从$s$向$student_i$建边($w=art[i]$)，从$student_i$向$t$建边($w=science[i]$)，

对于每个学生，新建两个个点$art_i,science_i$，建边

$s -> art_i (w=same\_art[i])$

$art_i -> neighbor_{ij}(w=INF)$

$neighbor_{ij} -> science_i(w=INF)$

$science_i->t(w=same_science[i])$

接着跑最小割即可

Codeforces 1074B 树结构

题解： https://codeforces.com/blog/entry/62985

Codefocres 741D 树上启发式合并(dsu on tree)

维护每个节点到根节点的路径，若路径上某字符x的数量为奇数，则用$(1<<(x-' a '))$表示，否则该位为0

从根节点开始往子节点dfs，先遍历轻节点（遍历结束后清除轻节点的信息），再遍历重节点（重节点信息保留）。

对于子树上的一个节点（用二进制表示其到根节点1的路径），我们用数组$arr$保存一下最大的深度，那么更新答案时，只需要：

1. 计算重子节点到当前节点(称为$rt$)的最大可行路径长度
2. 暴力遍历所有轻子节点对应的子树($subtree_i$)
   1. 先计算经过$rt$的可行路径的最大长度
   2. 将$subtree_i$中的节点$p$的深度大于$arr$中的记录值，更新$arr$

BZOJ 2118 同余最短路

同余最短路的简单题，注意$a_i=0$的情况

Codeforces 587E 差分线性基

题意：给定$a_1,a_2,...a_n$，进行下列两种操作

1. 对$a_i\ i\in[l, r] \oplus x$
2. 求$a_i\ i\in[l, r]$通过异或操作能够表示出的数的数量

对于操作2，显然是求$a_l...a_r$中"异或不相关"(参考线性不相关的概念)的个数$x$，答案为$2^x$，可用线性基求解

根据题解 (opens new window)，$a_l, a_{l+1}, ..., a_r$所能表出的数，都能由$a_l, a_l\oplus a_{l+1}, a_{l+1}\oplus a_{l+2}, ..., a_{r-1}\oplus a_r$表出。

令$b_i=a_{i-1}\oplus a_i$，考虑操作1$([l, r], x)$

该操作只会对$b_l,b_{r+1}$造成影响，只需将$b_l$修改为$b_l \oplus x$（$b_{r+1}$同理）即可！

因此我们用一棵线段树来维护$b_2...b_n$，再用一个别的什么（线段树/树状数组之类的）来维护$a_i$就好

AC代码

CodeChef Single Point of Failure 割点

个人排位赛4

BZOJ 1857 三分法套三分法

标题即题解

HDU 6191 可持久化字典树

很容易想到该问题可以转化为区间异或最大值问题

即对于区间$[l,r]$求一个数字$a_i$使得$x \oplus a_i$最大+

很显然使用字典树求解（没想到~）

可以分块，也可以可持久化来维护

UPD：

1. 可持久化真的是又臭又长又难调
2. 这题20倍空间的可持久化不能过，但是返回的居然是TLE而不是WA或RE！orz HDOJ
3. 36倍及以上稳过（不MLE的前提下）

HDU 6212 区间DP

记录所有连续的球的数量$block[n]$

$dp[l][r]$表示消除块$[l,r]$所消耗的时间，转移方程如下(学过python的同学应该都看得懂)

1. $dp[l][r]=min([dp[l][k] + dp[k+1][r]\quad for\ k\ in\ range(l, r)])$

如果块$l$与块$r$奇偶性相同（即颜色相同）（条件1），那么在1的基础上进行以下转移

2. $dp[l][r] = min(dp[l][r], dp[l+1][r-1])$

如果满足条件1且$min(block[l], block[r])==1$，那么在上面的基础上进行以下转移

3. $dp[l][r]=min([dp[l][r]] + [dp[l+1][k] + dp[k+1][r-1]\quad for\ k\ in\ range(l+r, r, 2)]\quad if\ block[k]==1)$

这里解释以下第三条转移方程

考虑左/右侧的块大小为1，那么我们可以从$(l,r)$寻找一个大小为1的块$k$并将其与左/右侧合并且不被消去，这时再消去$k$右/左侧的球并让$(l,k,r)$三个区间合并消去

POJ 3074 舞蹈链 / 常数优化 (尚缺舞蹈链解法)

比赛过后看了眼别人的代码，我傻了

---

常数优化（逃课）做法

原版DFS（bitset） 本机: 1.79s POJ: TLE

优化后DFS 本机: 0.41s POJ: 782ms

---

这里讲下用int/long long代替bitset的优化方法（仅限于64位及以下的bitset）：

首先，我们要预处理出一下数据

unordered_map<int, int> lg; // 如果mx小，可以用数组，速度更快 int lg[1<<mx];
for(int i=0; i<mx; i++) lg[1<<i] = i;

bitset<U>.count()

如果条件允许，直接用__builtin_popcount()即可，否则用以下代码

int count(int val){
    int cnt = 0;
	for(; val; val -= (-val)&val) cnt++;
    return cnt;
}
// 如果mx比较小，可以直接预处理出来
int bit_cnt[1<<mx];
for(int i=(1<<mx)-1; i>=0; i--) bit_cnt[i] = count(i);

bitset<U>._Find_first()

int find_first(int val){
    return lg[(-val) & val]; // 如果迭代次数少，但是mx大，可以直接用log2函数(不推荐)
}

bitset的遍历bitset<U>._Find_next(int v)

for(int k=val; k; k -= (-k)&k){
    int v = lg[(-k) & k];
    // do something
}

flip()/set()/reset()等方法过于简单，这里就不展开了

---

本题的$mx=9$，比较小，通过以上技巧便可以将暴力DFS从1.79s优化至0.41s

---

舞蹈链解法：

TLE

Gym 100134B 思维/策略

读题要仔细：每次$B$只会变化1位

因此，可以先想办法让$A$变为全0，接着让$A$变为全$1$，在这个过程中便可得到所有物品的质量。

接着$O(2^n)$得出最优解。

---

题解说接下来要做的是："accepting only when its gets closer to solution"

这里说的"solution"指的是正确答案对应的集合。

因此，我们需要计算出所有能通向答案的子集$can[mask]$，接着让$A$变为全$0$。只有当存在物品$i$，使得$weight[i]=B-A$且$cur\_mask\&(1<<i)=0$且$can[cur\_mask\oplus(1<<i)]=true$时才accept

个人排位赛5

我吐了，一题都没做出来

HDU 4828 卡特兰数

卡特兰数模板题，见这里

HDU 6728 dp *

目前网上找不到题解，此处留下AC代码 (opens new window)

未补

贴一份题解: https://ycdzj.xyz/ti-jie-2019-astar-fusai-1004/

BZOJ 1041 暴力搜索(数学优化)/高斯整数分解

参考题解 (opens new window)

可知圆的方程$x^2+y^2=r^2$

我们有$y^2=r^2-x^2=(r-x)(r+x)$

$y=\sqrt{(r-x)(r+x)}$

设$gcd[(r-x),(r+x)]=g$，$A=\frac{r-x}{g},B=\frac{r+x}{g}$，且$gcd(A, B)=1$，$A<\frac{r}{g}$

那么$y^2=g^2AB$，同时有$A+B=\frac{2r}{g}$，因此$g|2r$

设$a^2=A, b^2=B$

对于给定$g=G$，定有$G|2r$，且$\frac{2r}{G}=a^2+b^2$，$gcd(a^2,b^2)=gcd(a,b)=1$（必要性得证）

注意，若不判断$gcd(a, b)=1$，会导致重复统计

充分性证明可以自己推导

算法的python实现如下

# 算法说明
ans = 0
# 值得一提的是，参考题解中lim_a = int(sqrt(g/2)) 不知是哪来的
def solve(lim_a, tmp): # tmp = 2*r/g 
    for a in range(1, lim_a+1):
        b = int(sqrt(tmp-a*a))
        if b <= a: break
        if b*b+a*a == tmp and gcd(a, b) == 1:
            ans += 1

limit = int(sqrt(r))
for i in range(1, r+1): # 枚举g
    if 2*r%i != 0: continue
    solve(*list(map(int, [sqrt(r/i), 2*r/i]))) # g = i
    if 2*r/i == i: break
    solve(*list(map(int, [sqrt(r/(2*r/i)), 2*r/(2*r/i)]))) # g = 2*r/i
    
print(ans * 4 + 4)

上述代码用C++实现，耗时84ms

然而本题有更优的方法，参考博客 (opens new window)

本源勾股数组的解法见我的笔记，耗时8ms

相关

四平方和定理

.

CodeChef TREDEG (opens new window) 生成树计数 prufer序列 公式推导 *

相关

洛谷P4002 (opens new window)

Codeforces 868F 决策单调性dp + 分治

容易想到$dp[i][j]=min(dp[i-1][k] + w(k+1,j)\ for\ k\ in\ range(i-1, j-1))$，$i$表示当前分为$i$段，$j$表示遍历到第$j$个数字，$w(k+1, j)$代表从位置$k+1$到位置$j$有多少对重复的数字。复杂度$O(n^2k)$

通过翻题解，可以得到以下结论：若为$k$使得$dp[i][j]=dp[i-1][k]+w(k+1, j)$最小的值，那么对于$z > j$，定有$dp[i-1][m] + w(m+1, z) > dp[i-1][k] + w(k+1, z)\ (0<m<k)$，即转移点具有单调性。

证明如下：

若对于$x<y<z$有

$dp[i-1][y] + w(y+1, z) < dp[i-1][x] + w(x+1, z)$且

$dp[i-1][x] + w(x+1, z+1) < dp[i-1][y] + w(y+1, z+1)$

合并两式，得$w(x+1, z+1) - w(x+1, z) < w(y+1, z+1) - w(y+1, z)$

由于区间$[x+1, z]$的长度大于$[y+1, z]$，因此，对于新增的一个数字$a_{z+1}$，其对前者的贡献应大于等于后者，与上式矛盾。

那么，对于一个点$mid$，若它的最优转移点为$p$，那么对于所有点$k<mid$，其最优转移点一定小于等于$k$，反之同理

详见AC代码 (opens new window)

51Nod 1187 类欧几里得

参考 (opens new window)

核心代码

ll p, q;
void dfs(ll a, ll b, ll c, ll d){
    if(a == 0){
        p=1, q=d/c+1;
    }else if(a>=b){
        dfs(a%b, b, c-a/b*d, d);
        p += a/b*q;
    }else if(c > d){
        p = q = 1;
    }else{
        dfs(d, c, b, a);
        swap(q, p);
    }
}

类欧几里得太恐怖了

51Nod 1165 本原勾股数组/暴力搜索(数学优化)

见笔记本原勾股数组

HDU 1693 插头dp *

个人排位赛6

Codeforces 736B 哥德巴赫的猜想

ll n; cin >> n;
if(isprime(n)) print(1);
else if(isprime(n-2)) print(2);
else if((n&1)==0) print(2);
else print(3);

POJ 2987 网络流-最大权闭合子图

见我的笔记

Gym 101201F 2-SAT

2-SAT 模板题

见我的笔记

Gym 101201J 线段树找区间不大于C的数

搞了半天原来我是混过去的，复杂度不对（其实改一个值就对了，能过主要是数据没卡这个点？？）

对于当前数字$v$，用一个数$0\le x \le v$，那么$v$至少减少一半，因而对于一次查询，复杂度为$O(log_2v)$

HDU 1043 启发式搜索(IDA*/A*)/康托展开

这道题的关键在于：把拼图按行压成一维序列，忽略x，可以发现每次操作后，序列的逆序对的奇偶性不变！

当然也可以用康托展开压缩状态，然后BFS/A*

[AC代码](/post/category/暴力/IDA.html#例题 HDU 1043)

个人排位赛7

又被吊打了

BZOJ 1880/洛谷P2149 SPFA+拓扑排序

从四个点分别跑一次最短路，接着遍历点$1$到$n$

若$dist_{x1}[i]+dist_{y1}[i]=dist_{x1}[y1]$且$dist_{x2}[i]+dist_{y2}[i]=dist_{x2}[y2]$

则说明该点为两人最短路的可行公共点

那么对于这一点引出的所有边$(v, w)$

若$v$也属于可行公共点且$dist_{x1}[u]+w=dist_{x1}[v]$，那么将该边加入新图

对新图用拓扑排序跑一边最长路即可

(这种题的代码巨长，容易出错)

POJ 2778 AC自动机+矩阵快速幂

对模式串建AC自动机，在trie树上建图，点分为"危险点"和"正常点"，且"危险点"与"正常点"之间没有路

这题真的是毒瘤，时限1s，疯狂TLE。

感谢shengrang这位老哥的题解：

矩阵快速幂的时候, 不要每次加上的时候都模除. 用longlong存矩阵, 然后加完一行模除一次..

直接TLE -> 150ms

或者，在写矩阵乘法的时候要用引用传递，则TLE -> 550ms

AC代码见我的笔记

BZOJ 2243 树链剖分/LCT

一眼树剖，问题在于怎么在有限的时间里不出错地把代码敲出来

就当复习了一遍树剖吧

BZOJ 4004/洛谷P3265 实数线性基/高斯消元

题意：对于向量$\alpha_1, \alpha_2...\alpha_n$，每个向量有其对应的价格$c_i$，求极大线性无关组的最小价格

我们可以贪心的从小到大向线性基中插入向量，若该向量可以被表示，那么他就不必被选。

见笔记线性基

向线性基插入元素的这个过程其实就是高斯消元，只不过是从两种不同的角度看问题而已。

Codeforces 1153E 避免假优化

题解 (opens new window)

显然若答案为奇数，那么一定有一个端点在查询区间内，若为偶数，那么可能有也可能没有端点。

一开始我想的是将一个平面分为4个部分，然后递归询问的，但是细节比较难处理，WA了N次，另外这种方法的最坏复杂度可以达到$O(nlog\ n)$，显然不行。

一看题解发现是对行/列进行询问，找到对应行后二分（注意，不需要对最后一行/列进行询问）~

HDU 2196 树直径/树上DP

这道题我是用树上dp做的，但其实有更简单的方法。

定理

树上任意一点对应的距离最远的端点一定是树的直径的两端点之一

即设树上直径为$(u, v)$（意为$u$到$v$的路径），那么对于任意一点$p$，树上与$p$距离最远的点要么是$u$，要么是$v$

个人排位赛8

POJ 1845 二分求等比数列和/模运算

这道题我使用二分做的，但其实还可以用适当的模运算公式求解

对于等比数列$1, a, a^2, a^3, ..., a^n$，可以用$\frac{a^{n+1}-1}{a-1}$求和。对于模$p$意义下的等比数列求和，可以利用以下公式

$a/b\%c=a\%(b*c)/b$ 见笔记

即如下代码

ll get_sum(ll p, ll t){ // qpow(p, t, d) 以为p的t次方对d取余
    ll div = (p-1) * mod;
    ll ans = (qpow(p, t+1, div) - 1 + div) % div;
    ans = ans / (p-1);
    return ans % mod;
}

若使用该方法，需要用龟速乘防止爆long long

另外，本题需要特判$b=0$的情况。

CodeChef SUBLCM (opens new window) 代码技巧

题名： Subarray LCM

明显我们需要求出没有公因子的最长连续子序列的长度

代码技巧，具体解析已经写在注释中，直接贴[代码](#CodeChef SUBLCM AC代码)

CodeChef ANUGCD (opens new window) 线段树/分块/树状数组 求区间最值

题名: Maximum number, GCD condition

题解1(线段树) (opens new window) 题解2(分块) (opens new window) 题解3(树状数组) (opens new window)

对每一个质数$p$，若存在$a[i] \% p = 0$，我们新建一个查询$RMQ$的工具，并将$\{a[i]\ \ \ if\ \ a[i]\%p=0\}$插入

由于一个数字$x$最多由$log\ x$个质因数组成，因此下列解法的空间复杂度均为$O(nlog\ n)$

用线段树的话需要动态开，并且维护$pos[i]$（代表质数$i$所含的每一个数字的位置）

用分块的话，可以按照题解2中所示，可以对所有素数$p$都建一段$rmq$，然后把所有段按$p$从小到大合并。

例如$a=\{2, 3, 4, 6\}$，那么质数$2$的$RMQ$为$p_2=\{2, 4, 6\}$，质数$3$的为$p_3=\{3, 6\}$，合并后为$\{2, 4, 6, 3, 6\}$，注意合并时要保存每一段的开头位置和长度。接着按分块的思想去做就好。

用树状数组是最简洁明了的。对每一个质数$p$开一个树状数组（善用vector），并维护$pos[i]$和$cnt[i]$即可。

三种方法时间复杂度都为$O(nlog\ n)$

AC代码见我的题解

CodeChef AHWORK (opens new window) DP

题名： Akhil And Pending Homework

题解 (opens new window)

$dp[i][j][a][b]$表示从字符串$i$到字符串$j$，且$s_i$的从前往后第$a$个字符与$s_j$从后往前第$b$个字符之间的字符已经计算过了，组成回文串所要删去的最小字符串数

接下来判断$s[i][a]==s[j][strlen(s[j]) - b - 1]$

如果上述条件成立，那么$dp[i][j][a][b]$的计算范围缩小2个字符，即如下所示

int & ans = dp[i][j][a][b];
li = strlen(s[i]), lj = strlen(s[j]);

if(s[i][a] == s[j][lj-b-1]){
    if(a + 1 < li && b+1 < lj) ans = min(ans, dp[i][j][a+1][b+1]);
    else if(a + 1 < li) ans = min(ans, dp[i][j-1][a+1][0]);
    else if(b + 1 < lj) ans = min(ans, dp[i+1][j][0][b+1]);
    else ans = min(ans, dp[i+1][j-1][0][0]);
}

显然当$a=0$时，我们可以尝试直接抛弃掉串$i$，即$ans=min(ans, dp[i+1][j][0][b])$ ①

当$b=0$时同理，有$ans = min(ans, dp[i][j-1][a][0])$ ②

当 $i>j$ 或 $i=j$ 时，到达递归的边界。

对于$i>j$分两种情况:

1. 由两个指针$a,b$各自遍历到了其所在串的末尾/头部的情况转移过来（即由$i<j$转移过来），这时候返回$0$即可
2. 由$i=j$转移过来，这种情况不存在，因为$i=j$已经是递归边界

对于$i=j$，另$b=len[i]-b-1$，若$s[i][a]=s[i][b]$，返回$0$，否则返回$1$

详见[AC代码](#CodeChef CALLSCHE AC代码)

CodeChef CALLSCHE (opens new window) 网络流 *

题名： Call Center Schedule

Codeforces 718C 线段树维护矩阵

当时没做出来，后来一看代码发现是线段树写歪了，巨歪！

Codeforces 954I FFT *

前置 Codeforces 939D

并查集可解

Codeforces 850C Dp SG函数 *

看来我之前学了个假的SG函数，心累

每个质数都是独立的，可视作不同的子游戏。

对于$mask$，$mask_i=1$意为存在一个数字$val$使得$val \% p^i=0$且$val\%p^{i+1}\ne0$

那么对于一个选定的$k$，则会将状态$mask$转化为$(mask\gg k)|(mask\&((1 \ll k) - 1))$

接着用unordered_map来保存状态就好

HDU 4964 恶心模拟题 *

个人排位赛9

Codeforces 543B 多源最短路的复杂度

这题虽然AC了，但是仍然有必要记录一下学到的东西。

因为之前的个人赛里也有一道关于"公共路径"的题，很自然的想到做4次Dij，进而想到可以枚举公共路径的两个端点。接着距离就等于$dist[s1][i]+dist[j][t1]+dist[s2][i]+dist[j][t1]+dist[i][j]$

从$s、t$的最短路容易求，那么就剩下求$dist[i][j]$了。

到这里思路就卡住了，因为求任意两点间最常用的$Flody$算法复杂度是$O(n^3)$，在$n=3000$的情况下显然会TLE

卡了好久。

后来想到，我们只需要对每一个点做一次$BFS$就好，这样子复杂度为$O(n^2)$，完全可以接受！！

另外，$Dijkstra$单源最短路算法的复杂度为$O(n^2)$，二叉堆优化之后复杂度为$O(VlogV+E)$，求多源最短路的复杂度大约是$O(V(VlogV+E))$，要$Flody$何用？？

经过一番搜索，发现$Flody$似乎只适合于负权图。

因此，对于求任意两点之间的对短路：

1. 图中的所有边权相等：直接$BFS$即可，时间复杂度$O(n^2)$

2. 否则，看$n$的大小

   1. $n$很小，可以偷下懒用$Flody$
   2. $n$比较大，这时要看下有没有负权边
      1. 没有负权边，上$Dijkstra$，稠密图复杂度接近$O(n^3)$，稀疏图复杂度$O(n^2logn+ne)$
      2. 有负权边，那么可能是出题人想我死，或者思路想歪了
         1. 尝试用$SPFA$
         2. 事实上，对于负权图我们可以用改进的$Dijkstra$，详见我的笔记

Codeforces 553B 找规律

一个循环的长度不会超过2，并且靠左边的循环的数字一定小于右边的，因此对于长度为$n$的排列，有$dp[i]=dp[i-1]+dp[i-2]$种可能

---

下面尝试对上述假设进行证明：

设当前序列的长度为$n$，当$n$所在的循环长度$len=1$时显然可行，问题转化为$n'=n-1$的规模更小的问题。

当$len=2$，只需交换$val[n]$与$val[n-1]$，问题转化为$n'=n-2$的规模更小的问题

当$len=3$，设其所在的循环节为$(n, a, b)\ (n > a\ and \ n>b)$。显然$n$指向的是$b$而非$a$，与循环节的定义相背。

当$len>3$时同理。

---

问题转化为如何求第k大

我们假设位置$i=1$所在的循环长度为$1$，那么剩下的数字所组成的序列就应当是字典序第$1$到第$dp[n-i]$大的。若$k>dp[n-i]$，说明$i=1$所在的循环长度不可能为$1$，于是$k-=dp[n-i]$，并$swap(ans[i], ans[i+1])$，问题规模缩小

# include <header_files>
long long dp[60] = {0, 1, 2}, n, k;
int ans[60];
void main(){
    cin >> n >> k;
    for(int i=3; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
    for(int i=0; i<=n; i++) ans[i] = i;
    int pos = 1;
    while(pos < n){
        if(dp[n - pos] >= k){
            pos++;
        }else{
            k -= dp[n-pos];
            swap(ans[pos], ans[pos+1]);
            pos += 2;
        }
    }
    for(int i=1; i<=n; i++) cout << ans[i] << (i==n?'\n':' ');
}

Codeforces 578D 组合数学

出题人的题解根本不能看。。

题解

Codeforces 553C 思维 二分图

才发现我比赛的时候读错题了，其实这道题挺简单的

Codeforces 538H 线段树扫描线/二分图

二分图解法 (opens new window)

惊了！！不考虑$t、T$的情况下假设有解，那么$n_1=min(r_i),n_2=max(l_i)$一定是解

相关

扫描线 (opens new window)

Codeforces 573E 贪心

题解 (opens new window)

贪心解法：

对于已有的一个长度为$n$的序列$s_n$，考虑所有未加入的元素在加入后产生的贡献$a_i(i\not \in s_n)$，设最大的贡献为$a_k$且$a_k\ge0$，就把$k$加入序列中。可以证明这种贪心做法得到的序列$s_n$是长度为$n$的序列的最优解。朴素解法复杂度$O(n^2)$

Codeforces 547D 欧拉回路/贪心

贪心

把$x$坐标相同的点两两配对，在每一对点间连边，如果剩下一个点未配对，则忽略该点

把$y$坐标相同的点两两配对，，在每一对点间连边，未配对的点忽略

对得到的图进行二分染色，得到的结果输出即可

AC代码 (opens new window)

欧拉回路（标算的做法）

AC代码 (opens new window)

相关

fleury算法

Codeforces 559D 皮克定理

AC代码 (opens new window)

题解见[我的笔记](/post/category/几何/皮克定理.html#例题 Codeforces 559D)

个人排位赛10

UVA 11235 RMQ/莫队

这题我使用ST表过的，真没想到还能用莫队

关键在于如何做到$O(1)$转移。

假设$cnt[i]$表示当前区间中数字$i$出现的次数，$icnt[i]$表示当前区间中出现次数为$i$的不同数字的个数

当向区间中加入一个数字时，维护$icnt、cnt$和当前区间答案$ans$

当区间去掉一个数字$x$时，$icnt[cnt[x]]-1$且$icnt[cnt[x]-1]+1$，接着让$cnt[x]-1$。若此时$icnt[ans]=0$，那么$ans=ans-1$

另：这道题每个testcase都memset重置$cnt$和$icnt$不会TLE

HDU 6118 最小费用流

我的笔记

从源点$s$向每个村庄$i$建边，流量为$b$，费用为$a$。从每个村庄向汇点$t$建边，流量为$d$，费用为$-c$

接着按题目要求在村庄间建无向边，费用为$k$，流量无限

接着跑最小费用流即可

BZOJ 1040/洛谷P2607 基环树DP(代码技巧)

很明显我们得到的是一个森林，每颗"树"有且只有一个环。

因此对于每棵树，我们可以断开环上的一条边$e$，$e$的端点不能同时选。我们只要对这两个端点分别跑一次dp即可。

用前向星存无向图时，可以很容易的删除一条无向边 (若要删除边$i$，在dfs时不访问边$i/(i \oplus 1)$即可)

AC记录 (opens new window)

HDU 3336 KMP/后缀数组

第一反应是后缀数组+RMQ+二分，结果TLE了

后来往AC自动机的方向去考虑，结果发现这道题KMP可解，顺利AC

比赛过后看了古大哥的代码才知道后缀数组也能过，但是得加一点特效 T_T

!! 后缀数组做法待补充 !!

HDU 6381 *

没看题

一句话题解：RMQ直接维护六边形，颜色用long long来压，合并的时候相当于6个六边形的值或起来

HDU 4801 恶心模拟题 *

都是暴力搜索，我怎么就TLE了呢？？？

个人排位赛 11

CodeChef SUMAGCD GCD特性

请叫我猜结论大师！

道理我也不懂，但我猜最优解中会有$\mid A\mid =1$或$\mid B\mid =1$

很棒的题解 (opens new window)

HDU 3998 网络流建图 *

BZOJ 4552/洛谷 P2824 01线段树排序

假设序列中只由0或1组成，可以用线段树对其进行排序，复杂度$O(mlogn)$

要求第$q$位数字，我们可以二分一个$mid$，将原序列中大于等于$mid$的值设为1，小于$mid$的值设为0。由此便可直到$val[q]$相对于$mid$的大小。

Codeforces 1207F *

UVA 10559 *

Codeforces 1015F *

CodeChef CHSTR *

个人排位赛12

BZOJ 2002 LCT/分块

分块和莫队是好兄弟，想到莫队就该想到分块....

我们可以把跳转分为几种情况

1. 跳转后$pos'\ge n$ ，$next[pos]=-1$标记
2. 跳转后$pos'$与跳转前$pos$不在同一个块内，$next[pos]=pos'$直接跳转！
3. 跳转后$pos'$与跳转前$pos$在同一个块内，我们让$next[pos]=next[pos']$

修改的时候，我们直接修改整个块，查询的时候跳$next$就好

单次修改复杂度$O(n^{\frac{1}{2}})$，单次查询复杂度$O(n^{\frac{1}{2}})$

不会LCT

Codeforces 412E

其实完全不用预处理，每次遇到@都for一遍，复杂度也就$O(3n)$

太复杂的代码反而不好debug

注意细节：@后紧跟.的子串是不合法的！

Codeforces 463C *

Codeforces 429A *

POJ 1417 *

BZOJ 2125 *

个人排位赛13

LightOJ 1236

计算每个质数的贡献即可

总结教训：

1. 数组开太大，应报RE而非MLE（取决于OJ运行方式，有些可能报MLE）
2. 预处理出所有质数时，范围内有多少个质数，数组就开多大！

以后看到恶心的Memory limit 32768 kB，心里要有数

数据类型	大小	内存大小（大约）
int	1e7	39, 516kB
int	5e6	20, 000kB
int	1e6	4, 376kB
bool	1e7	10, 236kB
char	1e7	10, 240kB

Codeforces 12D CDQ/巧用树状数组

CDQ解法

由于题目要求是严格小于，需要对CDQ进行一些改造。

1. 对$a$从小到大排序
2. 在进行二分时，由于是严格小于，因而如果要产生贡献，必须有$\forall a_{left},a_{right} \ a_{left} < a_{right}$
3. 在合并的时候，要从后往前遍历，判断左半部分的人是否会suicide，如果会就给他打上标记

为了保证2，我们需要分类讨论一下

1. 如果$a[from]=a[to]$，这一部分不可能产生贡献，因而只需要将其按$b$排序即可
2. 否则，我们要寻找一个分界点$mid$，使得对于$\forall a_i,a_j(from\le i \le mid,mid \lt j \le to), a_i<a_j$，注意细节即可(哭了，细节比想法重要！！)

[AC代码](/post/category/其他/CDQ分治.html#例题 Codeforces 12D)

树状数组解法

显然我们可以通过对$a$排序降低一维，问题就转化为：如何用树状数组解决2维偏序

其实，我们可以用树状数组存最大值，即通过$query(b_i)$将得到所有符合$b_j>b_i$的最大$c$值

理论上，我们可以通过cdq辅以该做法解决四维偏序的问题（太毒瘤了吧）...

AC代码

Codeforces 55D 数位dp *

数位dp和插头dp--两大毒瘤dp

BZOJ 3562 *

BZOJ 2584 *

SGU 120 *

个人排位赛14

终于打完了...

POJ 2751 双机调度（贪心）

比赛时第一反应就是贪心，但是调了很久都没调出来。

贪心方式：对于$t_1\le t_2$的任务，我们按$t_1$单调递增方式排序；对于$t_1\gt t_2$的任务，按$t_2$单调递减的方式排序。做的时候先做前者，再做后者，然后$O(n)$模拟即可。

稍微想想就觉得这种贪心很合理

Codeforces 600E 代码技巧

一眼看出dsu on tree。但是比较难调，用了将近一个小时才做出来（主要是小错误卡了我好久）。

这里涉及到一个清空计数数组的操作，直接for或者memset肯定超时，我用一个比较麻烦的方法（打标记）来解决。

赛后看了眼队友的代码，发现只要把计数时的+1 换成它的逆操作（-1）即可实现清空...

所以说没事看看别人的AC代码还是有好处的。

BZOJ 1025 思维+完全背包

比赛的时候读错题了，还以为要求所有可能的排列的数量，于是猜想答案是$n!$，看了眼样例发现不对，就此卡住。。

问题简述：给定数字$N$，使得$x_1+x_2+...+x_n=N\ (0<x_1,x_2,...x_n\le N)$，其中$n$可为任意正整数，求$lcm(x_1,...x_n)$可能的取值的个数。

核心代码

dp[0] = 1;
for(int i=0; i<prime_cnt; i++){
    for(int j=n; j>=prime[i]; j--){
        for(int k=prime[i]; k<=j; k*=prime[i])
            dp[j] += dp[j-k];
    }
}
for(int i=0; i<=n; i++) sum += dp[i];
cout << sum << endl;

Codeforces 585D MidInMiddle *

BZOJ 1189 二分+网络流*

HDU 5890 *

POJ 1033 *

组队排位赛1

还行，基本上都是水题

组队排位赛2 (Gym 102392)

Gym 102392 J 思维转化

看上去很难，但是考虑到相邻的两条边一定连在同一个顶点上。换句话说，每个点的边一定是两两一组，那么贪心的把所有边排序，相邻的边分在一个环内就好。

vector<int> G[100010];
signed main(){
    ll sum = 0, n;
    cin >> n;
    for(int i=n*(n-1)/2, u, v, w; i>0; i--){
        cin >> u >> v >> w;
        G[u].push_back(w);
        G[v].push_back(w);
    }
    for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());
    int k = n / 2;
    for(int i=1; i<=n; i++){
        for(int j=0; j<k; j++) sum += G[i][j<<1|1];
    }
    cout << sum << endl;
}

Gym 102392F 树上dp

这道题有两个思维陷阱：

1. 棋子可以移动到它的祖先/子节点，无论是否相邻

2. 树的路径上有黑色块并不影响棋子的一定，举例：

   ​ 记$par(x)$为$x$的父节点，如果$par(x)$为黑色，只要$par(par(x))$为白色，那么$x$就可以移动到$par(par(x))$

考虑节点两两匹配，若$Alice$将棋子放在$x$上，那么$Bob$可以移动到$x$的匹配上，因此这棵树可以两两完全匹配，则$Alice$败，否则$Alice$胜

$(x,y)$匹配的条件即为：$x$为$y$的子节点或父节点

可以用设$dp[i]$为以$i$根的子树中未匹配节点的个数，令$sum_i=\sum_jdp[j]$，其中$j$为$i$的子节点

若$sum_i>0$，则$dp[i]=sum_i-1$，否则$dp[i]=1$

最后，若$dp[root]=0$，则这棵树为完美匹配，$Bob$胜。

组队排位赛3

ZOJ 4030 *

kmp:

如果字符串存在循环节，那么i % (i - next[i]) ==0，循环节的长度为 i - next[i]

否则，循环节的为字符串本身。

字符串Border的一些性质 (opens new window)

ZOJ 4031 *

ZOJ 4026 *

ZOJ 4028 *

ZOJ 4032 *

组队排位赛4

AK

组队排位赛5

Gym 102501F 求多边形面积

队友过的，我不会

已知多边形的各个顶点，求面积

已知顶点求面积

Gym 102501A Spfa/Dijkstra+记忆化搜索

关键点在于: 设$dp[i][j]$为到达节点$i$，已走路程$j$时，最小的碳排放量。

接着愉快的跑Spfa/Dijkstra即可。

Gym102501D 模拟 *

尝试用python过，结果RE/TLE

Gym 102501J 卡特兰数+观察

我的题解

Gym 102501L NIM *

Gym 102501H 分块打表（环检测算法）

[我的笔记](/post/category/其他/环检测算法.html#例题 Codeforces Gym102501H)

Gym 102501E *

组队排位赛6

Gym 102460H

队友做的，答案是$n*(n+1)\oplus(n+1)$。

然而我不会。

Gym 102460L 凸包

AC代码见我的笔记

Gym 102460M * EXLucas

组队排位赛7

Gym 102443D 构造

经验教训：

1. 题目说明了输入有序，那么就不需要用链表，直接Vector.resize即可

2. 对于有限次的询问，应当手动限制询问次数，而不是期望spj会在超出限制时返回Wa（这次就是栽在了这点上）

3. 在询问时，倾向于向下，而在回答时，倾向于向右走

   举个例子：目前已知的点有$(1,1)$和$(2,2)$，又因为查询的时候是倾向于先向下到达$(2,1)$再向右到达$(2,2)$，且$(2,1)$不在答案中。对于这种情况，只需在回答时让程序先向右再向下即可。

Gym 102443F 几何

题意：给定一个正$n$边形，求等腰三角形的个数

队友做的，我不会...

分析 (opens new window)：

设三角形两条腰外侧（及底边对面）的边数为$k$，显然$0<k<n$且$k$为偶数

因此有$n*\large\lfloor\frac{n-1}{2}\rfloor$种方案

但是由于等边三角形会被重复计算，因此如果$n\mid3$，则要减去$\large\frac{2}{3}n$

n = int(input())
ans = (n-1)//2 * n - (n//3*2 if n % 3 == 0 else 0)
print(ans)

Gym 102443B 几何 *

Gym 102443C 生成序列第k项

最讨厌这种求第k大的题。

这题真的是太恶心了

AC代码 (opens new window)

Gym 102443L *

Gym 102443G *

Gym 102443K *

组队排位赛8

Gym 102536 C 向量的几何意义 1e-10精度控制

把$w$与$P_i'$想象成一个$q$维向量，$\sum (P_i'(t))^2 \le g$即向量$P'$的模长不超过$g$，而$P'w$相当于$P'$在 $w$方向上的投影。显然，当两个向量的夹角$\theta=0$($cos\theta=1$)且$\mid\mid P'\mid\mid=g$时投影的模长最大，为$g\mid\mid w\mid\mid$

ll q, g, sum_f = 0, sum_c = 0, sum_w = 0;
cin >> q >> g;
for(ll i=0, w; i<q; i++){
    cin >> w;
    sum_w += w * w;
}
for(ll i=0, f, c; i<q; i++){
    cin >> f >> c;
    sum_f += f, sum_c += c;
}
long double k = sqrt(sum_w) * g;
cout << fixed << setprecision(14);
if(k <= sum_f || sum_c <= 0){
    cout << 0.0 << '\n';
}else{
    if(fabs(k - sum_f) <= 1e-6){ // 精度控制
        cout << (sum_c * (k + sum_f) / (g*g*sum_w-sum_f*sum_f)) << '\n';
    }else{
        cout << (sum_c / (k - sum_f)) << '\n';
    }
}

Gym 102536 H FFT 观察*

Gym 102536 G *

Gym 102536 M *

Gym 102536 L *

Gym 102536 F *

Gym 102536 J *

组队排位赛9

自闭

Gym 102500A 思维

赛后看别人队的代码，发现我原来是水过去的

红框为其他队伍的提交

---

以下是800ms的做法：

注意一个特性：当一个人的分数增加时，只有当前分数与他相同的人排名会改变

在统计排名时设当前周数为$i$(1-indexed)，总共有$m$周，当更新玩家$x$时，进行如下操作

$ans[x]=ans[x]+sum[score[x]]-sum[score[x]+1]$

$ans[x]=ans[x]-cnt[score[x]+1]*(m-i+1)$

$sum[score[x]]=sum[socre[x]]+(m-i+1)$

$cnt[score[x]]-=1,cnt[score[x]+1]++,score[x]++$

最终的答案为

$(sum[score[x]]+ans[x])/m$

Gym 102500H 思维转化

4个关键点：

1. 要求$(h[r]-h[l])/(r-l)\ge g$的最长段，可以先预处理出$y[i]=h[i]-1000/100*ig$(注意单位)

2. 问题转化为，求$y[r]-y[l]\ge 0$的最长段，可以维护一个$y[i]$单调递减的序列，对于一个固定的右端点$r$，二分查找可行的左端点$l$

3. 找到左端点$l$、右端点$r$后，尝试向左/右拓展不超过1km

4. 由于找到的$l$是递减序列中的最优解， 因而定有$y[l-1]>y[l],(y[r]-y[l])/(y[l-1]-y[l])<1$，但向右拓展时，可能有$(y[r]-y[l])/(y[r]-y[r+1])\ge 1,\ (y[r]>y[r+1])$，此时要与$1$比较

Gym 102500J *

Gym 102500D *

Gym 102500B *

Gym 102500K *

组队排位赛10

这套题很棒！

33M的题解压缩包很吓人！

Gym 102433L DFS细节

对于一个数$a=a_na_{n-1}...a_0$，其中$a_0$为最低位。

设$b=b_kb_{k-1}...b_0$，且$a*a=b$，那么在不进位的情况下有$b_k=\sum_{i=0}^k{a_i*a_{k-i}}$

Gym 102433B 贪心

队友过的，然而我还不会

贪心策略如下：

There are two cases to consider when considering the ith integer in the input list.

1. The given integer is already present in our subsequence. We do nothing.
2. The given integer is not present in our subsequence. This is the interesting case to consider. While our tentative subsequence is not empty, we will compare the given integer to the last integer in our subsequence. If the given integer is larger than the last integer in our subsequence, then append it to the end of our subsequence. Otherwise, it is smaller than the last integer. We can safely remove this integer if and only if there is another appearance of this integer that will be considered later in the sweep. We repeat this removal process until we can no longer remove an integer, at which we perform the append.

Gym 1012433K 线段树*

我特别好奇这题该怎么做....

Gym 102433J 代码技巧

我特别好奇这题该怎么做....

首先，能量对于角度的导数是常数（不严谨的说法），因而最佳方向一定是指向某个星星。

接着，对于每个星星，有三个量，分别称为$l,mid,r$，其中$l,r$为它能够产生贡献的左/右端点，$mid$为峰值点，那么在$[l,mid]$有斜率$s$，$[mid,r]$有斜率$-s$，因而只需要向队列中插入三个值$\{l,s\},\{mid,-2*s\},\{r,s\}$即可表示出上述情况

要特别注意影响范围越过$2\pi/0$的情况

核心代码如下

double det = 0, engery = 0, angle = 0, ans = 0;
for(int i=0; i<n; i++){
    double t, s, a, l, r;
    cin >> t >> s >> a;
    engery += max(0., t - s * min(a, 2*pi-a));
    l = a - min(pi, t / s), r = a + min(pi, t / s);
    if(l < 0.) det += s, l += 2 * pi;
    if(r > 2 * pi) det -= s, r -= 2 * pi;
    vec.push_back({l, s});
    vec.push_back({a, -2 * s});
    vec.push_back({r, s});
}
sort(vec.begin(), vec.end());

Gym 102433I 二分图上最大独立集 *

队友过的，看了他的代码发现是二分图

Gym 102433H 几何 思维 暴力*

我特别好奇这题该怎么做....

题解给了两份AC代码，一份神仙做法（看不懂），一份暴力

Gym 102433G 思维

我特别好奇这题该怎么做....

很棒的题目，见我的题解

Gym 102433F *

最讨厌字典序第k大

附录

CodeChef SUBLCM AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read(); // 快速读

const int maxn = 1e6 + 100;
int factor[maxn], pos[maxn];

void solve(){ // pos[i]里存放上一个质因子i所在的位置
    memset(pos, -1, sizeof pos); // 不会TLE
    int n = read(), ans = 0, a, tmp=-1;
    for(int i=0; i<n; i++){
        a = read();
        while(a > 1){
            int p = factor[a];
            tmp = max(tmp, pos[p]); // tmp+1 为可行范围的最左端
            pos[p] = i;
            while(a % p == 0) a/=p;
        }
        ans = max(ans, i - tmp);
    }
    cout << (ans > 1?ans:-1) << '\n';
}

int prime[maxn], prime_cnt=0, not_prime[maxn]={0};
signed main(){
    for(int i=2; i<maxn; i++){ // factor[i]中存放i的最小因子,显然可用线性筛求factor数组
        if(!not_prime[i]) prime[prime_cnt++] = i, factor[i] = i;
        for(int j=0; j<prime_cnt && i * prime[j] < maxn; j++){
            not_prime[i * prime[j]] = true;
            factor[i * prime[j]] = prime[j];
            if(i % prime[j] == 0) break; // 要放在最后一行
        }
    }
    int t = read();
    while(t--) solve();
}

CodeChef CALLSCHE AC代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 100;

char str[maxn][5];
int len[maxn], dp[maxn][maxn][3][3], n;

int search(int i, int j, int a, int b){
    if(i > j) {
        assert(a == 0 && b == 0);
        return 0;
    }
    int & ans = dp[i][j][a][b];
    if(ans != -1) return ans;
    if(i == j) {
        assert(a <= len[i]-b-1);
        return ans = (str[i][a]!=str[i][len[i]-b-1]);
    }
    ans = inf;
    if(b == 0) ans = min(ans, 1 + search(i, j-1, a, 0));
    if(a == 0) ans = min(ans, 1 + search(i+1, j, 0, b));
    if(str[i][a] == str[j][len[j]-b-1]){
        if(a + 1 < len[i] && b + 1 < len[j]) ans = min(ans, search(i, j, a+1, b+1));
        else if(a+1 < len[i]) ans = min(ans, search(i, j-1, a+1, 0));
        else if(b+1 < len[j]) ans = min(ans, search(i+1, j, 0, b+1));
        else ans = min(ans, search(i+1, j-1, 0, 0));
    }
    return ans;
}

void solve(){
    memset(dp, -1, sizeof dp);
    cin >> n;
    for(int i=0; i<n; i++) cin >> str[i], len[i] = strlen(str[i]);
    cout << search(0, n-1, 0, 0) << endl;
}

int main(){
    int t; cin >> t;
    while(t--) solve();
}