- 博客(201)
- 收藏
- 关注
RSS订阅原创 pytorch入门（3）
语言模型lstmimport torchtextfrom torchtext.vocab import Vectorsimport torchimport numpy as npimport randomBATCH_SIZE = 32EMBEDDING_SIZE = 100MAX_VOCAB_SIZE = 5000import torch.nn as nnclass RNNModel(nn.Module): def __init__(self, rnn_type,vocab_
2020-05-23 13:49:02
213
原创 pytorch入门（2）
fizzbuzz游戏3倍数fizz 5倍数buzz 15倍数fizzbuzz。其余数字输出本身12fizz4buzzfizz78fizzbuzz11fizz1314fizzbuzzdef fizz_buzz_encode(i): if i %15 == 0 : return 3 elif i%5 == 0 : return 2 elif i %3 == 0: return 1 else: return 0def fizz_buzz_de
2020-05-20 17:05:00
326
原创 pytorch入门（1)
import torchimport numpy as npN, D_in, H, D_out = 64,1000,100,10x = torch.randn(N,D_in)y = torch.randn(N,D_out)w1 = torch.randn(D_in, H,requires_grad = True)w2 = torch.randn(H,D_out,requires_grad = True)learning_rate = 1e-6for t in range(500):
2020-05-20 00:50:29
313
原创 Learning Local Search Heuristics for Boolean Satisfiability 2020-04-30
Learning Local Search Heuristics for Boolean SatisfiabilityAbstractGNN (select variable) + local search algorithm.RL，初始X，GNN结合sofetmax作为policy 函数，选择p最大的variable翻转，每个Trajectory有一个reward（找到使得fai为真的reward为1），训练参数。SAT problem: 属于[决定性问题]，也是第一个被证明属于[NP完全]命
2020-05-17 03:26:00
548
原创 LEARNING A SAT SOLVER FROM SINGLE-BIT SUPERVISION 2020-05-01
LEARNING A SAT SOLVER FROM SINGLE-BIT SUPERVISIONAbstractNeuroSAT : a classifier to predict satisfiability of a propositional formulatrain NN ，2* LSTM+3* MLP （每个t ： literal & variable 相互更新）监督学习, 二分类器。contribution:虽然结果一般，但是用监督学习的过程中，运用可视化发现，sat时可以发
2020-05-17 03:25:13
605
原创 NLocalSAT: Boosting Local Search with Solution Prediction 2020-05-02
NLocalSAT: Boosting Local Search with Solution PredictionAbstractNLocalSAT ：address stochastic local search (SLS) 随机初始化的问题NLocalSAT combines SLS with a solution prediction model, which boosts SLS by changing initialization assignments with a neural net
2020-05-17 03:24:20
404
原创 Guiding High-Performance SAT Solvers with Unsat-Core Predictions 2020-05-03
Guiding High-Performance SAT Solvers with Unsat-Core PredictionsAbstractNeuroSAT is a method to improve CDCL solvers with predictions of unsat-cores.can provide effective guidance to high-performance SAT solvers on real problems.代码： https://github.com/
2020-05-17 03:23:27
347
原创 PDP: A General Neural Framework for Learning Constraint Satisfaction Solvers2020-05-04
PDP: A General Neural Framework for Learning Constraint Satisfaction SolversAbstractit is not clear how the search strategy in the learned models actually works. So propose a generic neural framework to solve CSP( constraint satisfaction problems) in a f
2020-05-17 03:22:36
325
原创 Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search 2020-05-05
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search图上常见np问题Abstractestimate the likelihood, for each vertex in a graph, of whether this vertex is part of the optimal solution.设计network 综合各种方案IntroductionGCN学习每个点的like
2020-05-17 03:21:42
1296
原创 Learning Combinatorial Optimization Algorithms over Graphs 2020-05-06
Learning Combinatorial Optimization Algorithms over GraphsAbstract解决NP-hard问题通常需要大量的专业知识和反复试验, learn algorithm to automate this challenging, tedious process. learn heuristic algorithm利用结构特征解决问题. (same structure but differ in the data)的性质,RL + graph embe
2020-05-17 03:20:24
2314
3
原创 NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING 2020-05-07
NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNINGAbstract(借用pointer network用 policy gradient 优化,)given a set of city coordinates, predicts a distribution over different city permutations.RL(reward 总路径长度相反数) + RNN (policy gradient)很好的解决100no
2020-05-17 03:18:59
2089
原创 ATTENTION, LEARN TO SOLVE ROUTING PROBLEMS 2020-05-09
ATTENTION, LEARN TO SOLVE ROUTING PROBLEMSAbstract问题描述车辆路径问题（Vehicle Routing Problem, VRP）, 车辆路线问题最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。Daima:https://g
2020-05-17 03:18:16
865
原创 On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization 2020-0...
On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing OptimizationAbstractCPO :: 设计 legal flight sequence （crew pairings），以最低的成本设计出航空公司的航班时间表机组指派问题需要考虑时间变量以及后续的事件，比如a机组从北京飞到上海就只能飞上海的航班了，而且人家还必须回到北京，这个问题的复杂度就大多了。类似的还有登机口指派问题。机组排
2020-05-17 03:17:09
317
原创 Attention is all you need 2020-05-15
Attention is all you need AbstractTransformer : 无recurrence和convolutions，只基于attentionIntroductionRecurrent models 是seq2seq model，h_t = f (position,h_t-1);不能并行运算，RNN 长期忘记，transformer: averaging attention-weighted positionsSelf-attention : relating d
2020-05-17 03:14:05
187
原创 sgu 273Game Po （区间dp）
题意：4种颜色，两个混合可以组成另一种，给出所有组合以及组合后的结果，给一串颜色，任意位置合并最后合并成一个颜色的所有可能性tip：dp[I][j][k]表示从I到j是否可以变成第k个颜色，注意可能有同样两种颜色组合，但形成不一样的颜色，所以我用了前向星把他们连起来，而且从I到j形成的颜色也可能是多个，也用了前向星，循环中间位置m 枚举I到m和m+1到j可能形成的颜色 在循环这两个颜色组成的颜色，就
2017-09-27 16:56:42
370
原创 判断线段相交并求交点
const double precision = 1e-6;const double inf = (1<<30);const int maxn = 1e6+10;int n;struct Tpoint{ double x; double y; Tpoint(double x = 0, double y = 0) : x(x) , y(y) { } void pr
2017-09-25 21:28:45
691
原创 sgu-264. Travel 稳定婚姻问题
题意：男女配对，最后没有一对男女对对方的喜欢程度都高于现在的配偶tip：感觉和二分图差不多嘛。所有男的放队列 一个个出来， 先找最喜欢的，要是她单身就结婚 不单身就问她要不要私奔 私奔了原来配的就又单身 放入队列#include <cstdio>#include <iostream>#include <algorithm>#include <map>#include <cstring
2017-09-22 01:08:01
463
原创 sgu265Wizards(计算几何)
题意：一个空间直角坐标系内，对一个点有三种操作： 1.平移(x,y,z)⇒(x+a,y+b,z+c)； 2.缩放(x,y,z)⇒(ax,by,cz)； 3.绕一个向量(x,y,z)顺时针旋转α角(角度制)。 对空间内的m个点给出n个操作，求每个点在操作后的坐标。tip：每次操作在之前的基础上左乘当前操作的矩阵，最后右乘每次给的初始坐标。#include <cstdio>#include <io
2017-09-22 00:56:33
368
原创 sgu258 Almost Lucky Numbers （数位dp）
题意：定义一个具有2n位的正整数，其前n位之和与后n位之和相等，则为lucky数。给定一个区间l,r，问有多少个正数可以通过修改某一位数从而变成lucky数？不能含前导0。tip：定义dp[i][j][p][q]表示前I位和为j其中数位上最大值是p 最小值是q的方案数。。 我们先把整个区间分开，10,99],[1000,9999],[100000,999999]。。。 然后如果[1,K]完全包含
2017-09-18 11:23:57
569
原创 SGU 271 Book Pile（deque）
题意：一开始桌子上从上到下放着N本书（从上往下输入） M组操作： 1.将前K本书翻转，2.在头上加一本书。最后输出书的顺序。（从上往下输出）tip：看起来像splay==线性做法是用deque 上面k本维护一个。。下面的一次往上添加，每次遇到add先加到上面的deque里，如果超过了k本，拿下最下面的给到另一个deque。。。需要注意的是，本题减小时间复杂度的突破口就是如何不真的旋转，而能做到
2017-09-14 11:34:56
268
原创 sgu392Cyclic Troubles
题意：n*m矩阵，每个点固定可以往左往右往上或往下走，每个点有个字母， q个循环问会不会出现出现给定的串，其中(s)num表示s串循环了多少次tip：预处理每个点往后走1，2，4，7，16。。。步走到哪，，类似倍增的思想，（询问总长度就1e9，说明只有往后走2^31就够了）void get_Hash(){ for(int i = 0 ; i <= n+1 ; i++) fo
2017-09-09 16:50:36
207
原创 sgu 237Galaxy X: Episode I - Masters of Mind （dp）
题意：给你一个包含’‘、’?’、’!’、’a’~’z’的字符串，其中’‘可以被任意字符串替换（包括空串），’?’必须恰好被一个字符替换，’!’必须恰好被三个字符替换。要求按规则替换后原串要变成一个回文串且长度要求最小；若长度相同则要求字典序最小。 tip：第一次做的时候按照dp[i][j]表示前I个和后j个能否匹配，匹配的最小长度是多少。松弛：void rel(int i,int j,int i2,
2017-09-03 10:56:59
270
原创 sgu236Greedy Path（最优比例路径）
题意：给出一个有向图，每条边有一个权值和时间花费。如果图中无环，输出0，如果有环，找出一个最大的环，最大的意思是环上的权和 / 时间和 最大。tip：最优比例的题一般二分答案，把题目就变为询问是否存在一个环使得Σcost/Σtime>=k 整理有： Σ(k∗time[v]−cost[v]) <= 0 转换为spfa判负环。输出路径：记录下返回时那个被加了n次得点，一定是负环里的，记录pre。
2017-08-31 19:15:09
332
原创 ural1223 鹰蛋（dp优化）
题意：有一堆共 M 个鹰蛋，一位教授想研究这些鹰蛋的坚硬度 E。他是通过不断 从一幢 N 层的楼上向下扔鹰蛋来确定 E 的。当鹰蛋从第 E 层楼及以下楼层落下 时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔 碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实 验。教授希望实验是成功的。 例如：若鹰蛋从第 1 层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下仍
2017-08-31 01:21:43
706
原创 zoj2318 getout（计算几何）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1318题意：你是一个圆，二维坐标中有很多其他n个圆，给出n个圆心及半径，再给你自己的圆心及半径，问这个圆能不能逃出这n个圆的包围。tip：好神奇的题。。首先考虑把自己这个圆变成点，把别的圆的半径加上自己这个半径就好了。如果某两个圆相交或相切，那么他们组成的封闭区间可以用连接其两圆心
2017-08-31 01:07:14
241
原创 SGU235The Queen(BFS)
题意：一个n∗n的棋盘，每个位置上可以放黑子，白子，皇后(有且仅有一个)或不放。问皇后走m步后能走到多少个不同的格子。皇后可以走上下左右斜任意长度只要没遇到W，遇到B后会停下，B不在存在。tip：bfs。。首先我们得知道假如p步可以到的格子，那么第p+2k(k≥1) 步都可以到，因为可以来回走，所以每个点记录奇数点来还是偶数，， 注意一个点如果因为是黑的停下了，那么像一个方向能走到的点再从那
2017-08-26 00:02:19
281
原创 sgu224Little Queens 225. Little Knights
题意：n*n（n<=10）的棋盘，求出放置m(m<=n*n)个皇后的方案数。tip：状态压缩+位运算 一行一行dfs dfs(当前行号,列状态(哪个可以选可以不选），左上来的（哪个可以选可以不选），右上来的（哪个可以选可以不选），已放置棋子数）#include <cstdio>#include <cstring>#include <iostream>using namespace std;
2017-08-25 11:26:54
280
原创 sgu226. Colored graph
题意：给你一个n(n<=200)个点，m(m<=n*n)的有向图，然后每条边都有一个颜色，然后要求求出1->n的一条最短路径，满足相邻的两条边不能是同一种颜色。输出最短路径长度。tip：bfs vis多加一维来的颜色。。#include <cstdio>#include <iostream>#include <cstring>#include <queue>using namespace s
2017-08-25 11:06:34
442
原创 sgu230（拓扑排序) 231
题意：n*n（n<=10）的棋盘，求出放置m(m<=n*n)个皇后的方案数。tip：状态压缩+位运算 ，dfs一行一行来 DFS(当前行号 ，列状态，因为左上来的 当前行哪个格子能不能放， 右上来的 当前行哪个格子能不能放，已放置的棋子数）#include <cstdio>#include <cstring>#include <iostream>using namespace
2017-08-25 11:00:54
235
原创 sgu223Little Kings（状压）
题意：两个车互不攻击，当且仅当它们不在同一行或同一列上。输入整数n和k，你需要求出在n*n的国际象棋棋盘上放k个互不攻击的车有多少种方法。 tip：你一个N*N的棋盘，要你在其中放入K个国王，每个国王会攻击到以它为中心的九宫格的相邻8个位置，求方案总数. 用F [ i ] [ j ] [ k ]来表示前i行放入k个国王，并且第 i 行的状态为第 j 个状态那么F[ i ] [ j ] [ k ]
2017-08-25 10:49:17
472
原创 sgu222 Little Rooks
题意：两个车互不攻击，当且仅当它们不在同一行或同一列上。输入整数n和k，你需要求出在n*n的国际象棋棋盘上放k个互不攻击的车有多少种方法。 tip：组合数学 Cnk*cnk*k!（n行n列选k个）#include <cstdio>#include <iostream>#include <cstring>using namespace std;const int maxn = 12;int
2017-08-25 10:43:16
252
原创 sgu220Little Bishops（dp）
题意：在n*n的棋盘上放K个象，使得两两之间不互相攻击。有多少种放法？tip：棋盘按照(i+j)的奇偶黑白染色，则在黑色格子中放的象不可能攻击到白色格子，分开考虑并将棋盘翻转45度。（旋转后就是一行一列只能放一个） f[i][j]=f[i-1][j]+f[i-1][j-1]*(a[i]-(j-1)) f[i][j]表示前i行放j个车的方案数，a[i]表示第i行的可放位置数。最后枚举在黑色格子中放
2017-08-25 10:32:45
452
原创 sgu234 Black-White King Strikes Back（二分图 输出方案）
题意：n*m的0,1矩阵(n,m<=200)，要你在1的地方放士兵，不能现 两个士兵相邻，问最多可以放多少个？tip：根据i+j的奇偶性黑白染色构建二分图，然后跑一个最大匹配，然后ans=1的个数-最大匹配数，构建图的方案时，先把没匹配的都选上，那么和这些有边的就不能选，和这些不能选有边的就要选上，dfs下去，。。最后还有一些没被访问过的，选所有黑色的或者白色的都可以#include <cstdi
2017-08-25 09:55:02
268
原创 sgu233The Greatest Angle(计算几何)
题意：给出一个圆O和严格在圆内的两点A,B，在圆上求一点C使得∠ACB最大。tip：A,B,C所构成的外接圆与圆O相切时最大。因为AB所在的圆，无论半径多大，所对应的圆周角是固定的，且半径越大角度越小，所有在相切时最好。 解方程： 设小圆的圆心为p，两圆相切： OP = R-r = R-sqrt(pc^2+AC^2) 因为∠PCO是定值，（360°-（∠OCP+90°）） 所以在三角形pc
2017-08-25 09:36:17
222
原创 sgu232（最小表示法）
题意：给出n,m，以及长度为n的原字符串S[0,n-1]。根据S构造出新的n个字符串A[n],A[i][j]=S[(i+j*m)%n]。求A中最大的串。tip:尝试nm之后 可以发现a每n次开始循环（mod后和之前的循环节是同样的几个数，可能不到n），每次由于是取mod 所以也是有循环节的，那么找出这个循环节，找到循环同构中最大的(左移或右移任意位）就可以。。。最小表示法： 例如，字符串”abc
2017-08-24 09:54:51
219
原创 欧拉回路
题意： 这道题是要求我们求出一条欧拉路，所以我们要首先判断图中是否有欧拉路。对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；如果超过2个点的度为奇数，那么它就不存在欧拉路了。 tip： 由于题目中说数据保证至少有1个解，所以一定存在欧拉路了。但是我们还要选一个点作为起点。如果没有点的度为奇数，那么任何一个点都能做起点。如果有2个奇
2017-08-16 23:03:24
294
原创 计算几何模版
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <cmath>using namespace std;const double eps = 1e-10;const int maxn = 310;int n,ca,c,e;struct Tpoint { dou
2017-08-16 22:02:43
151
原创 spoj4487（splay）
Splay不加反转(Push_down)版本，求区间最大值，维护每个点的子树的整个sum和 中间（内部）最大值：msum，lsum（左侧连续最大值）rsum右侧连续最大值，和线段树基本一致）/*Splay不加反转(Push_down)版本，求区间最大值，维护每个点的子树的整个sum和中间（内部）最大值：msum，lsum（左侧连续最大值）rsum右侧连续最大值，和线段树基本一致）*/#inc
2017-08-10 11:11:40
212
原创 #con5多校联盟 （李主席与阶乘）
http://oj.xjtuacm.com/problem/11/ 李主席对10000内的阶乘能倒背如流，有一天学妹请教李主席一个问题，需要对这样一个式子进行化简： a[i]!乘积/b[i]! 化成c 1 ！^e1*c2！^e2… t 使得c1最大情况下e1最大， 再使得c2最大。。。 tip： 思路大概是这样的： 先质因数分解ai得阶乘。。。再这一部分，3!*9
2017-08-04 15:41:50
377
原创 2017 Xian ACM Summer Training Warm-up Exercise 3
B题Bigger is Better ：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1783题意：用有限火柴棍拼数字，能整除m的最大数字。tip：f[I][j]用了I根火柴%m为j的最大数字是多少。 最多50位，用高精度，缩位#inclu
2017-07-14 19:57:41
1063
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人