A题

题意

给一个括号序列,对于不相交的每一对满足条件的子串，求能把它们包以来的满足条件的最小子串，答案加上这个子串的长度。

题解

我们可以把满足条件的括号序列看成棵树并把他构造出来，（详见树的括号表示）。
构造需要用0(n)的算法不然要TLE


//相关代码
#include<cstdio>
typedef long long ll;
const int MAXN = 1e5+1e3;
struct Node{
    int l, r;
}q[MAXN];
char s[MAXN];
int len, sz, tot;
void build(int u) {
    q[u].l = tot;
    while(s[++tot]=='(') {
        addedge(u,sz++);
        build(sz-1);
    }
    q[u].r = tot;
}

题意就是对每对节点，答案加上他们最近公共祖先对应串的长度。
我们不可能枚举每对节点这样是复杂度是O(n^2)的，所以我们可以枚举每个结点，并求有多少对结点的最近公共祖先是它。
当前结点有2个亲儿子，亲儿子对应子树结点个数为k1,k2的话，结果为k1*k2
有3个的话是 k1*k2+k1*k3+k2*k3
有n个的话是 ((k1+k2+...+kn)^2 - k1^2 - k2^2 -...-kn^2)/2
dfs遍历一遍就可以了

B题

题意

给你前n项以及线性递推关系，求am

题解

由于1 ≤ m ≤ 10^18 O(m)算法要TLE，需使用矩阵快速幂。
矩阵快速幂详见《算法入门经典训练指南》现只讨论如何构造矩阵
假设有个列向量（a1,a2,a3,..,an）,需要左乘一个n*n方阵,得到新的列向量（a2,a3,a4,...,a_n+1）
新的列向量第i个元素只跟方阵第i行有关，如果它要加个aj则，A[i][j]++;
前n-1个元素中新向量的第i个元素就是旧向量的第i+1个元素，所以第一行A[1][2]=1, 第二行A[2][3]=1, 直到第n-1行A[n-1][n]等于1
新向量的第n个元素a_n+1,要加个 a_n+1-k1, 所以A[n][n+1-k1] ++, 要加个 a_n+1-k2, 所以A[n][n+1-k2]++，以此类推。


//矩阵构造代码
void init() {
    for(int i=1; i<=n; ++i)
        B[i][i] = 1;
    for(int i=1; i<=n-1; ++i)
        A[i][i+1] = 1;
    for(int i=0; i<c; ++i)
        ++A[n][n+1-k[i]];
}

C题

题意

一个英雄在森林里取宝石，森林的守卫在抓他,求英雄最少走多少步能获得宝石。

守卫怎么走取决与英雄的位置和他自己的位置，所以虽然我们只管英雄怎么走但状态包括英雄的坐标和守卫的坐标。
如果经过一段时间状态曾经遇到过，这明显是无益的，要把访问过的状态存下来加以避免重新访问
求最小步数用bfs


//bfs代码
#include<algorithm>
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
#define xx first
#define yy second
const int MAXN = 32;
bool vis[MAXN][MAXN][MAXN][MAXN];
int step[][2] = {0,1,0,-1,1,0,-1,0};
struct Node{
    pii pa, pg;
    int step;
}q[1<<20];
int n, m, sz;
pii pt;

int bfs() {
    sz = 1;
    q[0].step = 0;
    vis[q[0].pa.xx][q[0].pa.yy][q[0].pg.xx][q[0].pg.yy] = true;
    for(int i=0; i<sz; ++i) {
    //bfs遍历有些变形
        pii& pa = q[i].pa;
        pii& pg = q[i].pg;
        if(pa==pt) return q[i].step;
        for(int j=0; j<4; ++j) {
            pii npa = make_pair(pa.xx+step[j][0],
                   pa.yy+step[j][1]);
            if(valid(npa)) {
                pii npg = mov(npa, pg);
                if(npg!=npa&&!vis[npa.xx][npa.yy][npg.xx][npg.yy]) {
                    vis[npa.xx][npa.yy][npg.xx][npg.yy] = true;
                    Node& nxt = q[sz++];
                    nxt.pa = npa;
                    nxt.pg = npg;
                    nxt.step = q[i].step+1;
                }
            }
        }
    }
    return -1;
}