Posts

uva10655题目链接 题意： # 给出a+b和ab的值，问a^n+b^n 思路： # 构造矩阵，手写一下很显然…

16年北京网络赛遇到了这个技巧…但是竟然忘记记了下来？ 快速乘是为了解决 计算a_b % mod 时a_b溢出LL 的问题 比如a=1E16,b=1E16,mod=1E18，虽然最后的结果没有溢出，但是中间溢出了。

题目链接 题意： # 给出了一段程序，程序实际算的是f[n] = (f[n-1] + n%2)%m的值，其中f[1]=1，给出n,m(1E9)，问f[n] 思路： # 显然是矩阵快速幂，终点在于构造矩阵。

hdu5015题目链接 题意： # 给出矩阵的构造规则： a[0][j] (j>=1) 分别为233,2333,23333….给出a[i][0] (i>=1)，对于其余的i,j,a[i][j]=a[i-1][j] + a[i][j-1]

刚刚看了TBBT season 11 episode 1 Sheldon 和Amy 订婚了，Bernadette又怀孕了。 想想上一季结束的时候，大概半年前。 我好像还是只单身狗，手头没啥能看的offer，还有巨大的学业压力在前方。

hdu3642题目链接 题意：给出若干个（1000）长方体，求至少交三次的空间的体积。 尺寸为[x1,x2],[y1,y2],[z1,z2]，其中x，y的坐标的绝对值不超过1E6，Z的坐标的绝对值不超过1E9。

题目链接 题意： # 求矩形周长并。 思路： # 线段树+扫描线。 和前面的求面积并比较类似，我们先考虑平行x轴的线段，考虑线段树，维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len.

题目链接 题意： # 求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。 思路： # 和矩形面积并_hdu1542解题报告 类似

hdu1542题目链接 题意： # 求n(100)个矩形的面积并。 思路： # 扫描线+线段树 题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。

zoj3606题目链接 题意：有个小女孩卖火柴，有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3，其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。

题目链接 题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x（保证集合中一定有x）,sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

题目链接 题意：给出n,p,q,r，以及n（1E5）个数，所有数的范围都是[-1E9,1E9]，现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n

题目链接 题意：有若干线段，给出起点和终点，问是否有一个线段是冗余的。冗余的意思是说，对于该线段所覆盖的所有整数点，没有该线段，也能被其他一个或者多个线段覆盖到。如果有，输出任意一个冗余线段即可。

比赛链接 10个月没写题了，菜啊。进行一点恢复性训练好了。 A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。 思路是直接删掉后面可能的出现的0再判断回文数就好。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年09月24日 星期日 13时51分06秒 4File Name :A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define PB push_back 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34bool check( int x) 35{ 36 vector<int>val; 37 while (x) 38 { 39 int tmp = x; 40 val.push_back(tmp); 41 x/=10; 42 } 43 int siz = val.size(); 44 if (siz==1) return true; 45 for ( int i = 0 ; i < siz/2 ; i++) 46 { 47 if (val[i]!=val[siz-1-i]) return false; 48 } 49 return true; 50} 51int main() 52{ 53 #ifndef ONLINE_JUDGE 54 //freopen("./in.txt","r",stdin); 55 #endif 56 int x; 57 cin>>x; 58 while(x==0) 59 { 60 x/=10; 61 } 62 if (check(x)) puts("YES"); 63 else puts("NO"); 64 65 66 #ifndef ONLINE_JUDGE 67 fclose(stdin); 68 #endif 69 return 0; 70} B: 2*n个人，每个人的重量为w[i]，要分成n-1组，每组2个人，以及2个单独的人。单独的人的不稳定性为0，每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

先说下自己目前很笼统的理解： 反向传播是用来快速计算梯度的一种方法； 过程大概是把计算过程用计算图表示，这样每一个中间步骤都有一个节点，每一个local gradient都会比较容易计算；

参考资料： 消息传递接口（MPI）维基百科 MPI_TUTORIAL MPI 在大规模机器学习领域的前景如何？ 因为要和平台组对接工作以及写我们自己的BN同步…所以来了解一下MPI相关…感谢平台组@gyz 菊苣提供指导。

参考资料： tf_doc_Reading data TENSORFLOW INPUT PIPELINE EXAMPLE tensorflow：理解tensorflow中的输入管道 第二个参考资料是第一个的翻译版本，翻译的水平一般，建议看原文，不是很长。 下面是我挑了文章中重点的部分+自己的理解。 TL;DR; # 一个适用于不是很大的数据集的pipeline input 的例子。

在这里存个备份，还有些问题没有解决。 raise ValueError(“GraphDef cannot be larger than 2GB.”) 记录一些思路好了。现在是没有生成.meta文件，爆掉应该是因为所有的变量都加载到了默认图里。 也就是说我处理完checkpoint 0 之后开始处理checkpoint1，但是checkpoint0的那些变量还是存在的…所以越来越多？

参考资料： What is the TensorFlow checkpoint meta file? TensorFlow: Restoring variables from from multiple checkpoints 合并模型的时候发现.meta一直在累加，而其他数据文件没有改变。因此来探究一下checkpoint的几个文件的含义。 This file contains a serialized MetaGraphDef protocol buffer. The MetaGraphDef is designed as a serialization format that includes all of the information required to restore a training or inference process (including the GraphDef that describes the dataflow, and additional annotations that describe the variables, input pipelines, and other relevant information). For example, the MetaGraphDef is used by TensorFlow Serving to start an inference service based on your trained model. We are investigating other tools that could use the MetaGraphDef for training.

参考资料： programmers_guide/variables tf/Variable 之前感觉对tensorflow 的variable的理解不是很深刻…跑个模型啥的倒不会有什么问题，但是涉及分布式，模型并行之类的，感觉有些地方还是要理解得仔细一点比较好。