- A题 树的构造
- B题 矩阵快速幂
- C题 BFS
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,...,an+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个元素an+1,要加个 an+1-k1, 所以A[n][n+1-k1] ++, 要加个 an+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;
}
