# 4.5算法之动态规划 1413:Mondriaan’s Dream

http://noi.openjudge.cn/ch0405/1413/

#### 题目

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

#### 思路

0表示下一层对应位置必须为1，即竖向砖块的第一块砖，1表示下一层可为0可为1，无影响
dp思路
dp[i][status] = sum(dp[i-1][k]) k in [0,2^w-1]

– status｜k == 2^w-1，及保证竖向不会出现连续的两个0这种非法情况
– status&k 要保证所有出现的 1 都为连续的2 个 1，否则意味着出现了单格的错位，010的下层必定为101，则在最低端无法满足全1的要求与操作取到的1为横放的块（1有两种含义），只要保证横放的块都符合规则即可。

#### 源码

``````//
//  1413.cpp
//  test
//
//  Created by bytedance on 2020/7/29.
//

#include <stdio.h>
#include <vector>
#include <iostream>

using namespace std;
long long w,h;

//bool check(long long x){
//
//}
vector<vector<long long>> dp;
bool check(long long x){
for(long long i = 0;i < w;++i){
if((x&(1<<i))!=0){
if((x&(1<<(i+1)))!=0){
++i;
}else{
return false;
}
}
}
return true;
}
int main(){

while(cin >> h >> w){
if(h==0&&w==0)break;
if(h*w%2==1){
cout<<0<<endl;
continue;
}
long long statusNum = 1<<w;
dp.clear();
dp.resize(h+1,vector<long long>(1<<w,0));
for(long long i = 0;i < statusNum;++i){
if(check(i))
dp[i]=1;
}
for(long long i = 2;i <= h;++i){
for(long long now = 0;now < statusNum; ++now){
for(long long up = 0;up < statusNum;++up){
if((now|up)==statusNum-1){
if(check(now&up))
dp[i][now]+=dp[i-1][up];
}
}
}
}
cout << dp[h][statusNum-1]<<endl;
}
return 0;
}
``````

# 4.5算法之动态规划 1249:Humble Numbers 优先级队列

http://noi.openjudge.cn/ch0405/1249/

#### 源码

``````//
//  1249.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int m={2,3,5,7};
priority_queue<long long,vector<long long>,greater<long long>> q;
int main(){
q.push(1);
int idx = 0;
int i;
long long pre = 0;
while(cin >> i){
if(i == 0){
break;
}

while(idx<i){
while(q.top()==pre){
q.pop();
}
pre = q.top();
idx++;
for(int i = 0;i < 4;++i){
q.push(pre*m[i]);
}
}
if(i%100>=10&&i%100<=20)
printf("The %dth humble number is %lld.\n",i,pre);
else if(i%10==1)
printf("The %dst humble number is %lld.\n",i,pre);
else if(i%10==2)
printf("The %dnd humble number is %lld.\n",i,pre);
else if(i%10==3)
printf("The %drd humble number is %lld.\n",i,pre);
else
printf("The %dth humble number is %lld.\n",i,pre);
}
return 0;
}

``````

# 4.3算法之图论 1526:宗教信仰 并查集模板题

http://noi.openjudge.cn/ch0403/1526/

#### 源码

``````//
//  1526.cpp
//  test
//
//  Created by bytedance on 2020/7/28.
//

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> father;

int find(int x){
return x==father[x]?x:find(father[x]);
}
void un(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx>fy){
father[fy]=fx;
}else{
father[fx]=fy;
}
}
int main(){
int m,n;
int idx=0;
while(cin>>n>>m){
idx++;
if(n==0&&m==0)break;
father.clear();
for(int i = 0;i <=n;++i){
father.push_back(i);
}
while(m--){
int a,b;
cin >> a>>b;
un(a,b);
}
int res = 0;
for(int i = 1;i <=n;++i){
if(find(i)==i){
res++;
}
}
cout<<"Case "<< idx<<": "<<res<<endl;
}
return 0;
}

``````

# 4.3算法之图论 1538:Gopher II 匈牙利算法

http://noi.openjudge.cn/ch0403/1538/

#### 源码

``````//
//  1538.cpp
//  test
//
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int n,m,s,v;

struct Node{
float x,y;
Node(float x,float y):x(x),y(y){}
};
bool isE(Node &a,Node &b){
float dis = pow(a.x-b.x,2)+pow(a.y-b.y,2);
return dis-1.0*s*s*v*v<1e-6;
}

vector<Node> nodesA;
vector<Node> nodesB;
vector<bool> vis;//本次找增广路使
vector<int> to;//记录匹配节点
bool dfs(int x){
for(int i = 1;i <= m;++i){
if(!vis[i]&&isE(nodesB[i],nodesA[x])){
vis[i]=true;
if(to[i]==0||dfs(to[i])){
to[i]=x;
return true;
}
}
}
return false;
}

int main(){
while(cin >> n >> m){
cin >>s>>v;
to.clear();
nodesA.clear();
nodesB.clear();
vis.resize(m+1,false);
to.resize(m+1,0);
nodesA.push_back(Node(-1,-1));
nodesB.push_back(Node(-1,-1));
for(int i = 0;i < n;++i){
float x,y;
cin >> x>>y;
nodesA.push_back(Node(x,y));
}
for(int i = 0;i < m;++i){
float x,y;
cin >> x>>y;
nodesB.push_back(Node(x,y));
}
//dfs二分图匹配
int res = 0;
for(int i = 1;i <= n;++i){
vis.clear();
vis.resize(m+1,false);
if(dfs(i)){
//cout<<"zgl "<<i<<endl;
res++;
}
}
cout <<n-res<<endl;
}
return 0;
}

``````

# 4.3算法之图论 253:丛林中的路

http://noi.openjudge.cn/ch0403/253

#### 思路

kruskal，边集按照 cost 排序遍历，并查集检查连通性，如果边的两端不连通则加入集合，放进集合

##### 源码
``````//
//  253.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

struct Edge{
int st,ed,cost;
Edge(int st,int ed,int cost):st(st),ed(ed),cost(cost){}
bool operator < (const Edge & e) const{
return cost<e.cost;
}
};
using namespace std;
int find(vector<int>& father,int x){
return father[x]==x?x:find(father,father[x]);
}
void un(int x,int y,vector<int> & father){
int fx = find(father,x);
int fy = find(father,y);
if(fx>fy){
father[fy]=fx;
}else{
father[fx]=fy;
}
}
int main(){
int num;
while(cin>>num){
// cout <<"num"<< num<<endl;
if(num==0)break;
vector<int> father(num);
for(int i = 0;i < num;++i)father[i] = i;
vector<Edge> edges;
char stchar;
num--;
while(num--){
cin >> stchar;
int edgenum;
cin >> edgenum;
while(edgenum--){
char edchar;
int cost;
cin >> edchar>>cost;
edges.push_back(Edge(stchar-'A',edchar-'A',cost));
}
}
sort(edges.begin(),edges.end());
//kruskal
int res = 0;
for(int i = 0;i < edges.size();++i){
//cout <<"cost"<< edges[i].cost<<endl;
int st = edges[i].st;
int ed = edges[i].ed;
if(find(father,st)!=find(father,ed)){
res+=edges[i].cost;
un(st,ed,father);
}
}
cout << res<<endl;

}
return 0;
}

``````

http://noi.openjudge.cn/ch0403/726/

#### 源码

``````//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <queue>
#include <algorithm>
#define INT_MAX 999999999
using namespace std;
int k,n,r;
int to,d,c;
Road(int to,int d,int c):to(to),d(d),c(c){}
bool operator < (const Road &r) const {
if(d==r.d)return c<r.c;
return d > r.d;
}
};
vector<vector<bool>> vis;
vector<int> dis;

int main(){
cin >> k >> n >> r;
dis.resize(n+1,INT_MAX);
vis.resize(n+1,vector<bool>(n+1,false));
for(int i = 0;i < r;++i){
int a,b,c,d;
cin >> a>>b>>c>>d;
}

while(!q.empty()){
q.pop();
return 0;
}
int internal = road.to;
for(int j = 0;j < edge[internal].size();++j){
int des = edge[road.to][j].to;
}
}
}

return 0;
}

``````

# 4.3算法之图论 799 Heavy Transportation

http://noi.openjudge.cn/ch0403/799/

-1代表路径不通

#### AC源码

``````//
//  799.cpp
//  test
//
//  Created by bytedance on 2020/7/15.
//

#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#define INT_MAX 999999
#define close -1
using namespace std;

struct Node{
int d,u;
Node(int d,int u):d(d),u(u){}
bool operator <(const Node & a) const{
return d<a.d;
}
};
int main(){
int n;
cin >> n;
int vs,es;

for(int i = 1;i <= n;++i){
cin >> vs >> es;
vector<vector<int>> e(vs+1,vector<int>(vs+1,-1));
vector<bool> vis(vs+1,false);
vector<int> dis(vs+1,-1);
while(es--){
int a,b,c;
cin >> a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
//dijkstra

priority_queue<Node> q;
q.push(Node(-1,1));
dis = INT_MAX;
while(!q.empty()){
Node t = q.top();
q.pop();
int d = t.d;
int u = t.u;
//cout << d<<endl;
if(vis[u])continue;
vis[u]=true;
for(int j = 1;j <= vs; ++j){
if(!vis[j]&&dis[j]<min(dis[u],e[u][j])){
dis[j]=min(dis[u],e[u][j]);
q.push(Node(dis[j],j));
}
}
}
cout <<"Scenario #"<<i<<":"<<endl<<dis[vs]<<endl<<endl;
}
return 0;
}

``````

# 新人培训 – 线程&Handler

## 多线程

1.什么是线程
2.为什么Android只允许在主线程更新UI
3.如何异步进行耗时操作后在主线程执行回调更新UI
4.Handler的基本原理

• 新建线程需要调用`start()`方法才会进入就绪状态
• 处于就绪状态的线程并不一定立即被执行，而是听从CPU调度，即将被执行，所以被称为就绪
• 处于等待状态的线程不会被CPU调度

#### 如何创建新的线程

``````public class TestThread extends Thread {
//默认构造方法

//传入的String参数为线程名称
public TestThread(String name) {
super(name);
}
//该方法在线程由就绪转为执行时被调用
@Override
public void run() {
super.run();
System.out.println(this.getName());
}
}
``````

# Scala 学习笔记

———— 我自己说的

#### 声明

val 声明必须初始化

``````import java.lang._ //导入lang中所有
val myStr2：String = HelloWorld!//Scala中的字符串类直接来自于java
println(myStr2)
``````

#### 字面量

``````val i = 123
val i = true//布尔字面量
``````

#### 操作符

a 方法 b 等价于 a.方法（b）

i += 1

#### 富包装类

Int 对应 RichInt

String 对应 RichString, 这些类位于 scala.runtime 中

#### Range

``````1 to 5
1.to(5)//1,2,3,4,5
1 until 5//1,2,3,4
0.5f to 5.9f by 0.8f//步长0.8f
``````

#### 输入输出

``````val str = readLine("enter your name")
val f = readFolot()
>3.5e1
println("hello");println("world!")
printf("i = %.1f",i);//print(),println(),printf()默认所有scala程序都可以使用
``````

#### 写入文件

``````import java.io.PrintWriter
val out = new PrintWriter("out.txt")
for(i <- 1 to 5) out.println(i)
out.close()
``````

#### 读入文件

``````import scala.io.Source
val in = Source.fromFile("in.txt")
val lines = in.getLines//返回迭代器
for(line <- lines) println(line)
``````

# RNN 学习笔记

NLP (Natural Language Processing)

`os.path.join(data_path, "ptb.train.txt")`
#定义文件路径

``````#join函数为路径拼接函数
>>>os.path.join('a','b','c')
>>>a\\b\\c'
``````

`_build_vocab(train_path)`
#对输入文本进行排序,首要字段 value（频率）,次要字段 key，返回类型为字典（字符：_id）

`train_data = _file_to_word_ids(train_path, word_to_id)`
#将输入文本按照生成的字典映射为 id 序列

`vocabulary = len(word_to_id)`
#记录字典大小，未在字典中出现的字符将被忽略

`with tf.name_scope(name, "PTBProducer", [raw_data, batch_size, num_steps]):`
#定义命名空间，不同命名空间内的 Variable name 属性可以相同

``````__init__(
name,#域名
default_name=None,#域名未指定时的默认值
values=None#传入的变量列表，可在上下文中操作修改
)
``````

`raw_data = tf.convert_to_tensor(raw_data, name="raw_data", dtype=tf.int32)`
#将 python 中的数据类型转换为 tensor 张量