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]
其中 sum 求和时要对 status 和 k 进行校验
– 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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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[1][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.
//  Copyright © 2020 bytedance. All rights reserved.
//

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

using namespace std;
int m[4]={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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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;
}

4.3算法之图论 726:ROADS

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

思路

狄杰斯特拉直接改一下,基于优先级队列
Road 设置为二关键字排序
优先级队列 push 时只 push cost 小于等于 k 的 Road,则队列头部 Road.to 为 n 时必为满足 k 的最短路

源码

//
//  726.cpp
//  test
//
//  Created by bytedance on 2020/7/26.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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;
struct Road{
    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;
vector<vector<Road>> edge;


int main(){
    cin >> k >> n >> r;
    edge.resize(n+1,vector<Road>());
    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;
        edge[a].push_back(Road(b,c,d));
    }

    priority_queue<Road> q;
    q.push(Road(1,0,0));
    while(!q.empty()){
        Road road = q.top();
        q.pop();
        if(road.to==n){
            cout <<road.d;
            return 0;
        }
        int internal = road.to;
        for(int j = 0;j < edge[internal].size();++j){
            int des = edge[road.to][j].to;
            if(k>=road.c+edge[road.to][j].c){
                q.push(Road(des,road.d+edge[road.to][j].d,road.c+edge[road.to][j].c));
            }
        }
    }

    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.
//  Copyright © 2020 bytedance. All rights reserved.
//

#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[1] = 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 {
    //默认构造方法
    public TestThread(){}

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

这样我们已经声明了自己的线程类,对于不同的线程,他们的区别主要在于他们的run()方法内的业务逻辑不同,同时我们需要注意的是,我们还没有实例化对象,也就是说现在新的线程还没有被创建.

继续阅读

Scala 学习笔记

文章丑一定有他的原因,这是我的学习笔记,Markdown 源码直接来源于 Typora,由于 CSS 样式及 md 解析差异,造就了这篇文章,这里只是做一份副本,不具有使用价值
———— 我自己说的

声明

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

输入输出

readInt, readShort //import scala.io.StdIn._

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)

Tensorflow-reader.py

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 张量

继续阅读