0%

taro之api挂载

尽管Taro在相关的d文件中已经对api接口进行了声明,但是要了解实现过程,我们需要深入taro源码去探索。
经过代码的研读,我们发现taro的api挂载采用侵入式方法,核心实现函数是processApis

1
2
3
4
5
6
7
8
9
10
11
function processApis (taro, global, config: IProcessApisIOptions = {});

interface IProcessApisIOptions {
noPromiseApis?: Set<string>
needPromiseApis?: Set<string>
handleSyncApis?: (key: string, global: IObject, args: any[]) => any
transformMeta?: (key: string, options: IObject) => { key: string; options: IObject }
modifyAsyncResult?: (key: string, res) => void
isOnlyPromisify?: boolean
[propName: string]: any
}

该函数传入一个全局taro对象,以及对应平台的全局变量global(例如wx),以及对接口的自定义配置config,函数执行后,调用Taro[PromiseApi]的时候会返回一个Promise,该Promise内部调用global[PromiseApi]并对状态进行监听(例如success,fail,complete),并绑定至Promise的各个状态(例如success绑定至resolve)

异步api

微信异步api约定

1

taro的小程序部分,以MiniPlugin为核心,以下是MiniPlugin的入口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
apply (compiler: webpack.Compiler) {
this.context = compiler.context
this.appEntry = this.getAppEntry(compiler)
const {
commonChunks,
addChunkPages,
framework,
isBuildQuickapp,
isBuildPlugin,
fileType
} = this.options
/** build mode */
compiler.hooks.run.tapAsync(
PLUGIN_NAME,
this.tryAsync(async (compiler: webpack.Compiler) => {
await this.run(compiler)
new TaroLoadChunksPlugin({
commonChunks: commonChunks,
isBuildPlugin,
addChunkPages: addChunkPages,
pages: this.pages,
framework: framework,
isBuildQuickapp
}).apply(compiler)
})
)

/** compilation.addEntry */
compiler.hooks.make.tapAsync(
PLUGIN_NAME,
this.tryAsync(async (compilation: webpack.compilation.Compilation) => {
const dependencies = this.dependencies
const promises: Promise<null>[] = []
this.compileIndependentPages(compiler, compilation, dependencies, promises)
dependencies.forEach(dep => {
promises.push(new Promise<null>((resolve, reject) => {
compilation.addEntry(this.options.sourceDir, dep, dep.name, err => err ? reject(err) : resolve(null))
}))
})
await Promise.all(promises)
await this.options.onCompilerMake?.(compilation)
})
)

compiler.hooks.compilation.tap(PLUGIN_NAME, (compilation, { normalModuleFactory }) => {
/** For Webpack compilation get factory from compilation.dependencyFactories by denpendence's constructor */
compilation.dependencyFactories.set(SingleEntryDependency, normalModuleFactory)
compilation.dependencyFactories.set(TaroSingleEntryDependency as any, normalModuleFactory)

/**
* webpack NormalModule 在 runLoaders 真正解析资源的前一刻,
* 往 NormalModule.loaders 中插入对应的 Taro Loader
*/
compilation.hooks.normalModuleLoader.tap(PLUGIN_NAME, (loaderContext, module:/** TaroNormalModule */ any) => {
const { framework, designWidth, deviceRatio } = this.options
if (module.miniType === META_TYPE.ENTRY) {
const loaderName = '@tarojs/taro-loader'
if (!isLoaderExist(module.loaders, loaderName)) {
module.loaders.unshift({
loader: loaderName,
options: {
framework,
prerender: this.prerenderPages.size > 0,
config: this.appConfig,
runtimePath: this.options.runtimePath,
blended: this.options.blended,
pxTransformConfig: {
designWidth: designWidth || 750,
deviceRatio: deviceRatio || {
750: 1
}
}
}
})
}
} else if (module.miniType === META_TYPE.PAGE) {
let isIndependent = false
this.independentPackages.forEach(pages => {
if (pages.includes(module.resource)) {
isIndependent = true
}
})
const loaderName = isIndependent ? '@tarojs/taro-loader/lib/independentPage' : this.pageLoaderName
if (!isLoaderExist(module.loaders, loaderName)) {
module.loaders.unshift({
loader: isBuildPlugin ? '@tarojs/taro-loader/lib/native-component' : loaderName,
options: {
framework,
name: module.name,
prerender: this.prerenderPages.has(module.name),
config: this.filesConfig,
appConfig: this.appConfig,
runtimePath: this.options.runtimePath
}
})
}
} else if (module.miniType === META_TYPE.COMPONENT) {
const loaderName = isBuildPlugin ? '@tarojs/taro-loader/lib/native-component' : '@tarojs/taro-loader/lib/component'
if (!isLoaderExist(module.loaders, loaderName)) {
module.loaders.unshift({
loader: loaderName,
options: {
framework,
name: module.name,
prerender: this.prerenderPages.has(module.name),
runtimePath: this.options.runtimePath
}
})
}
}
})

/**
* 与原生小程序混写时解析模板与样式
*/
compilation.hooks.afterOptimizeAssets.tap(PLUGIN_NAME, assets => {
Object.keys(assets).forEach(assetPath => {
const styleExt = fileType.style
const templExt = fileType.templ
if (new RegExp(`(\\${styleExt}|\\${templExt})\\.js(\\.map){0,1}$`).test(assetPath)) {
delete assets[assetPath]
} else if (new RegExp(`${styleExt}${styleExt}$`).test(assetPath)) {
const assetObj = assets[assetPath]
const newAssetPath = assetPath.replace(styleExt, '')
assets[newAssetPath] = assetObj
delete assets[assetPath]
}
})
})
})

/**
* 在compiler的emitHook中生成小程序的相关文件
*/
compiler.hooks.emit.tapAsync(
PLUGIN_NAME,
this.tryAsync(async (compilation: webpack.compilation.Compilation) => {
await this.generateMiniFiles(compilation)
})
)

compiler.hooks.afterEmit.tapAsync(
PLUGIN_NAME,
this.tryAsync(async (compilation: webpack.compilation.Compilation) => {
await this.addTarBarFilesToDependencies(compilation)
})
)

new TaroNormalModulesPlugin().apply(compiler)
}

this.run()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* 分析 app 入口文件,搜集页面、组件信息,
* 往 this.dependencies 中添加资源模块
*/
run (compiler: webpack.Compiler) {
if (this.options.isBuildPlugin) {
// 如果是在构建小程序插件
this.getPluginFiles()
this.getConfigFiles(compiler)
} else {
// 如果在构建小程序

// 获取小程序配置
this.appConfig = this.getAppConfig()

// 分析小程序页面
this.getPages()

// 分析小程序页面配置
this.getPagesConfig()

// 黑暗模式相关
this.getDarkMode()

// 往 this.dependencies 中新增或修改所有 config 配置模块
this.getConfigFiles(compiler)

// 在 this.dependencies 中新增或修改 app、模板组件、页面、组件等资源模块
this.addEntries()
}
}

下面我们分析一下各语句的作用,我们只关注小程序的构建模块,先看this.getAppConfig()

this.getAppConfig

时间复杂度$O(n)$,空间复杂度很高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool pan[MAXN];
int prim[MAXN],vis[MAXN],len=0;
inline void sieve(int x) {
for(int i = 2;i <= x;i ++) {
if(!vis[i]) {
prim[++len] = i;
pan[i]=1;
}
for(int j = 1;j <= len && i * prim[j] <= x;j ++) {
vis[i * prim[j]] = 1;
if(i % prim[j] == 0)//保证每个合数只被筛一次
break;
}
}
}

Treap树的定义

Treap树的名字即为Tree和Heap的结合,它既是一颗二叉查找树(BST),又满足堆的性质(通过左旋右旋不改变Treap的二叉查找树性质而又尽可能的平衡)

Treap树的结构

1
2
3
4
5
6
7
8
9
10
11
struct node{
int l,r,v,siz,rnd,cnt;
}p[manx];
int cnt;
//l:左节点id
//r:右节点id
//v:节点权重
//siz:子树大小
//p[x].cnt:v的出现次数,这样权重相同的节点作为一个点来处理
//cnt:总共的节点个数
//node节点中可以加入其他需要维护的信息

节点更新

每当节点关系更改时,需要更新节点信息,包括

  • 节点的子树大小
  • 维护的其他内容
    1
    2
    3
    inline void update(int id){
    p[id].siz=p[p[id].l].siz+p[p[id].r].siz+p[id].cnt;
    }

左旋和右旋

左旋和右旋是Treap树的核心操作,每个节点在插入时都被赋予了随机的优先级$rnd$,通过保证优先级的堆性质,进而保证了Treap树的期望高度是$\log n$,而不至于退化为链,是Treap树尽可能保持平衡的关键

  • 左旋和右旋不改变节点的二叉树查找树性质
  • 该操作保证$rnd$的小顶堆性质
  • 右旋: 左儿子的$rnd$小于父节点时,左儿子的右儿子$\Rightarrow$父节点的左儿子,父节点$\Rightarrow$左儿子的新右儿子
  • 左旋: 右儿子的$rnd$小于父节点时,右儿子的左儿子$\Rightarrow$父节点的右儿子,父节点$\Rightarrow$右儿子的新左儿子
    Treap树旋转图解
  • 右旋代码如下
    1
    2
    3
    4
    5
    6
    7
    8
    void rturn(int &k){
    int tmp=p[k].l;//记录左儿子
    p[k].l=p[tmp].r;//左儿子的右儿子变成父节点的左儿子
    p[tmp].r=k;//父节点变成左儿子的新右儿子
    p[tmp].siz=p[k].siz;//整个子树的大小不变
    update(k);//新右节点更新
    k=tmp;//左儿子变成了新父节点,完成了右旋上位
    }
  • 左旋同理

节点插入和删除

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insert(int &id,int val){
if(!id){
//如果到叶子节点了
id=++cnt;
p[id].siz=1;
p[id].cnt=1;
p[id].val=val;
p[id].rnd=rand();//随机优先级
return;
}
p[id].siz++;
if(p[id].val==val)
p[id].cnt++;
else if(p[id].val<val){
insert(p[id].r,val);
if(p[p[id].r].rnd<p[id].rnd)
lturn(id);
}else{
insert(p[id].l,val);
if(p[p[id].l].rnd<p[id].rnd)
rturn(id);
}
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void del(int &id,int val){
if(!id)
return;
if(p[id].val==val){
if(p[id].cnt>1){
p[id].cnt--;
p[id].siz--;
}else{
if(p[id].l==0||p[id].r==0)
id=p[id].l+p[id].r;//如果该节点最多只有一个子节点,那么子节点接上或者直接删除该节点
else if(p[p[id].l].rnd<p[p[id].r].rnd){
rturn(id);
del(id,val);
}else{
lturn(id);
del(id,val);
}
}
}else if(val>p[id].val){
p[id].siz--;
del(p[id].r,val);
}else{
p[id].siz--;
del(p[id].l,val);
}
}

查询val的排名

1
2
3
4
5
6
7
8
9
10
int find_rank(int id,int val){
if(id==0)
return 0;
if(p[id].val==val)
return p[p[id].l].siz+1;
else if(p[id].val<val)
return p[p[id].l].siz+p[id].cnt+find_rank(p[id].r,val);
else
return find_rank(p[id].l,val);
}

查询排名为k的数

  • 如果k小于父节点左子树的大小,那么这个数一定在左子树里面,就到左子树里查找排名为$k$的数
  • 如果k大于左子树与父节点的大小之和,那么到右子树去找排名为$k-(p[l].siz+cnt)$的数
  • 如果既不在左子树也不右子树,父节点就是我们要找的数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int kth(int id,int k)
    {
    if(k<=p[p[id].l].siz)
    return kth(p[id].l,k);
    else if(k>p[p[id].l].siz+p[id].cnt)
    return kth(p[id].r,k-(p[p[id].l].siz+p[id].cnt));
    else
    return p[id].val;
    }

查询val的前驱

1
2
3
4
5
6
7
8
9
const int INF=0x3f3f3f3f;
int pre(int id,int val){
if(!id)
return -INF;
if(p[id].val>=val)
return pre(p[id].l,val);
else
return max(p[id].val,pre(p[id].r,val));
}

查询val的后继

1
2
3
4
5
6
7
8
9
const int INF=0x3f3f3f3f;
int nxt(int id,int val){
if(!id)
return INF;
if(p[id].val<=val)
return nxt(p[id].r,val);
else
return min(p[id].val,nxt(p[id].l,val));
}

完整模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
const int INF = 0x3f3f3f3f;
struct node {
int l, r, val, siz, rnd, cnt;
} p[maxn];
int cnt;

inline void update(int id) {
p[id].siz = p[p[id].l].siz + p[p[id].r].siz + p[id].cnt;
}

void rturn(int &k) {
int tmp = p[k].l;
p[k].l = p[tmp].r;
p[tmp].r = k;
p[tmp].siz = p[k].siz;
update(k);
k = tmp;
}

void lturn(int &k) {
int tmp = p[k].r;
p[k].r = p[tmp].l;
p[tmp].l = k;
p[tmp].siz = p[k].siz;
update(k);
k = tmp;
}

void insert(int &id, int val) {
if (!id) {
id = ++cnt;
p[id].siz = 1;
p[id].cnt = 1;
p[id].val = val;
p[id].rnd = rand();
return;
}
p[id].siz++;
if (p[id].val == val)
p[id].cnt++;
else if (p[id].val < val) {
insert(p[id].r, val);
if (p[p[id].r].rnd < p[id].rnd)
lturn(id);
} else {
insert(p[id].l, val);
if (p[p[id].l].rnd < p[id].rnd)
rturn(id);
}
}

void del(int &id, int val) {
if (!id)
return;
if (p[id].val == val) {
if (p[id].cnt > 1) {
p[id].cnt--;
p[id].siz--;
} else {
if (p[id].l == 0 || p[id].r == 0)
id = p[id].l + p[id].r;
else if (p[p[id].l].rnd < p[p[id].r].rnd) {
rturn(id);
del(id, val);
} else {
lturn(id);
del(id, val);
}
}
} else if (val > p[id].val) {
p[id].siz--;
del(p[id].r, val);
} else {
p[id].siz--;
del(p[id].l, val);
}
}

int find_rank(int id, int val) {
if (id == 0)
return 0;
if (p[id].val == val)
return p[p[id].l].siz + 1;
else if (p[id].val < val)
return p[p[id].l].siz + p[id].cnt + find_rank(p[id].r, val);
else
return find_rank(p[id].l, val);
}

int kth(int id, int k) {
if (k <= p[p[id].l].siz)
return kth(p[id].l, k);
else if (k > p[p[id].l].siz + p[id].cnt)
return kth(p[id].r, k - (p[p[id].l].siz + p[id].cnt));
else
return p[id].val;
}

int pre(int id, int val) {
if (!id)
return -INF;
if (p[id].val >= val)
return pre(p[id].l, val);
else
return max(p[id].val, pre(p[id].r, val));
}

int nxt(int id, int val) {
if (!id)
return INF;
if (p[id].val <= val)
return nxt(p[id].r, val);
else
return min(p[id].val, nxt(p[id].l, val));
}

前言

待补充

React.createElement

当我们用JSX编写react代码的时候,代码会经过Babel处理后转换为React.createElement的特殊形式,例如

1
2
3
4
ReactDOM.render(
<h1 style={{"color":"blue"}}>hello world</h1>,
document.getElementById('root')
);

处理之后,就变成了
1
2
3
4
5
6
7
8
ReactDOM.render(
React.createElement(
'h1',
{ style: { "color": "blue" } },
'hello world'
),
document.getElementById('root')
);

我们来看看React源代码:
1
2
3
4
5
6
7
// 文件位置:src/isomorphic/React.js
var ReactElement = require('ReactElement');
var createElement = ReactElement.createElement;
var React = {
createElement: createElement,
}
module.exports = React;

Dicnic算法(网络最大流)

Dicnic算法优化(多路增广+炸点优化+当前弧优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
typedef long long ll;
const int maxn = 1010;
const int maxm = 20010;
struct node {
int v,net;
ll w;
node(){}
node(int v,int net,ll w):v(v),net(net),w(w){}
}e[maxm];
int head[maxn],cnt,dis[maxn],n,cur[maxn];
bool vis[maxn];
void addedge(int u,int v,ll w) {
e[cnt]=node(v,head[u],w);
head[u]=cnt++;
e[cnt]=node(u,head[v],0);
head[v]=cnt++;
}
bool bfs(int st,int ed) {
if(st==ed) return false;
for(int i=1;i<=n;i++)
dis[i]=inf,vis[i]=false;
dis[ed]=inf;
vis[ed]=false;
dis[st]=0;
queue<int>que;
que.push(st);
while(!que.empty()) {
int u=que.front();
que.pop();
vis[u]=false;
for(int i=head[u];~i;i=e[i].net) {
int v=e[i].v;
if(e[i].w>0&&dis[v]>dis[u]+1) {
dis[v]=dis[u]+1;
if(!vis[v]) {
que.push(v);
vis[v]=true;
}
}
}
}
return dis[ed]!=inf;
}
ll dfs(int st,ll maxflow,int ed) { ///maxflow表示当前的源点能流出的最大流
if(st==ed) {
return maxflow;
}
ll res=0;
for(int &i=cur[st];~i;i=e[i].net) { ///没记错的话叫当前弧优化
int v=e[i].v;
if(e[i].w>0&&dis[v]==dis[st]+1) {
ll f=dfs(v,min(maxflow-res,e[i].w),ed);
res+=f;
e[i].w-=f;
e[i^1].w+=f;
if(res==maxflow) return res;
}
}
if(!res) dis[st] = inf;///炸点优化??
return res;
}
ll Dicnic(int st,int ed) {
ll maxFlow = 0;
while(bfs(st,ed)) {
for(int i=1;i<=n;i++)
cur[i]=head[i];
maxFlow+=dfs(st,inf,ed);
}
return maxFlow;
}
int main()
{
int m;
cin>>n>>m;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++) {
int u,v;
ll w;
cin>>u>>v>>w;
addedge(u,v,w);
}
cout<<Dicnic(1,n)<<endl;
return 0;
}

哈密顿

哈密顿路径

  • 哈密顿回路:从一点出发,经过所有的点必须且只能经过一次,最终回到起点的路径.
  • 哈密顿通路:从一点出发,经过所有的点必须且只能经过一次,出发点和结束点不重合

  • 与欧拉图的区别:欧拉图讨论的实际上是图上关于边的可行便利问题,而哈密顿图的要求与点有关

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    #include <iostream>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <vector>

    using namespace std;
    typedef long long LL;
    const int maxN = 200;

    //The arv[] length is len, insert key befor arv[index]
    inline void Insert(int arv[], int &len, int index, int key){
    if(index > len) index = len;
    len++;
    for(int i = len - 1; i >= 0; --i){
    if(i != index && i)arv[i] = arv[i - 1];
    else{arv[i] = key; return;}
    }
    }

    void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
    int ansi = 1;
    ans[ansi++] = 1;
    for(int i = 2; i <= n; i++){//第一种情况,直接把当前点添加到序列末尾
    if(map[i][ans[ansi - 1]] == 1)
    ans[ansi++] = i;
    else{
    int flag = 0;
    for(int j = ansi - 2; j > 0; --j){//在当前序列中,从后往前找到第一个满足条件的点j,使得存在<Vj,Vi>且<Vi, Vj+1>.
    if(map[i][ans[j]] == 1){//找到后把该点插入到序列的第j + 1个点前.
    flag = 1;
    Insert(ans, ansi, j + 1, i);
    break;
    }
    }
    if(!flag)Insert(ans, ansi, 1, i);//否则说明所有点都邻接自点i,则把该点直接插入到序列首端.
    }
    }
    }

    int main()
    {
    //freopen("input.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--){
    int N;
    scanf("%d", &N);
    int M = N * (N - 1) / 2;
    int map[maxN + 7][maxN + 7] = {0};
    for(int i = 0; i < M; i++){
    int u, v;
    scanf("%d%d", &u, &v);
    //map[i][j]为1说明j < i,且存在弧<Vi, Vj>,因为插入时只考虑该点之前的所有点的位置,与之后的点没有关系.所以只注重该点与其之前的点的连通情况.
    if(u < v)map[v][u] = 1;
    }
    int ans[maxN + 7] = {0};
    Hamilton(ans, map, N);
    for(int i = 1; i <= N; i++)
    printf(i == 1 ? "%d":" %d", ans[i]);
    printf("\n");
    }
    return 0;
    }

最小生成树模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000005;
struct Node {
int x, y, z;
} edge[N];

int par[N];

void init(int n) {
for (int i = 0; i <= n; i++) {
par[i] = i;
}
}

bool cmp(Node x, Node y) {
return x.z < y.z;
}

int find(int x) {
if (x == par[x]) return par[x];
else return par[x] = find(par[x]);
}

int tot, ans;

int main() {
int n, m;
while (~scanf("%d", &n)) {
if (n == 0)
break;
ans = 0;
m = n * (n - 1) / 2;
init(n);
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
edge[i].x = x;
edge[i].y = y;
edge[i].z = z;
}
std::sort(edge + 1, edge + 1 + m, cmp);

for (int i = 1; i <= m; i++) {
int x = find(edge[i].x);
int y = find(edge[i].y);
if (x == y) continue;

tot++;
par[x] = y;
ans += edge[i].z;
}
if (tot < n - 1);
//生成失败
else
printf("%d\n", ans);
}
return 0;
}

魔咒词典

题意:输入魔咒输出功能,输入功能找到魔咒,否则输出”what?”
思路:直接用map会超内存,于是想到用字符串hash解决内存问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
char func[N][85];//功能
char magic[N][25];//咒语
int num=1;
struct node//Hash值对应的数组下标
{
int Hash;
int l;
} key[N],tail[N];//咒语和功能
int cmp(node a,node b)//比较函数
{
return a.Hash<b.Hash;
}

unsigned int BKDRHash(char *str)//Hash算法
{
unsigned int seed = 131;
unsigned int hash = 0;

while (*str)
{
hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
void init()//初始化,计算所有串的Hash值
{
for(int i=1; i<num; i++)
{
key[i].Hash=BKDRHash(magic[i]);
key[i].l=i;
tail[i].Hash=BKDRHash(func[i]);
tail[i].l=i;
}
sort(key,key+num,cmp);//按照Hash值排序,方便二分查找
sort(tail,tail+num,cmp);
}
int main()
{

while(scanf("%s",magic[num]))
{
if(!strcmp(magic[num],"@END@"))
break;
getchar();
gets(func[num++]);
}
init();
int n;
scanf("%d",&n);
getchar();
while(n--)
{
node tmp;
char str[120];
gets(str);
if(str[0]=='[')//是咒语
{
tmp.Hash=BKDRHash(str);
int mid=lower_bound(key,key+num,tmp,cmp)-key;
if(key[mid].Hash!=tmp.Hash)
printf("what?\n");
else
printf("%s\n",func[key[mid].l]);
}
else
{
tmp.Hash=BKDRHash(str);
int mid=lower_bound(tail,tail+num,tmp,cmp)-tail;
if(tail[mid].Hash!=tmp.Hash)
printf("what?\n");
else
{
int l=strlen(magic[tail[mid].l]);
magic[tail[mid].l][l-1]=0;
printf("%s\n",magic[tail[mid].l]+1);
}
}
}
return 0;
}