题目链接：http://poj.org/problem?id=1830 给一系列的开关，某两个开关之间存在依赖关系，求从原始状态到最终状态最多有多少种取值方式，这个问题可以转化成求解异或方程组的问题，异或方程组的求解可以从最大主元开始，把其余方程中这个元全部删去，最终可能得到一个右对角的矩阵，而每个等式的值都是零或者一，所以容易得到这个异或方程的解是唯一的，所以初始的时候ans就要设置成1。如果在求解的过程中，最大主元对应的方程已经...
题目链接：https://www.acwing.com/problem/content/201/ 求k对1-n所有数取模的和。 证明一段可以作为等差数列来求，证明如下：（转自ACwing） 代码如下：#include<iostream> using namespace std; typedef long long ll; int main(){int n,k;cin>>n>>k;ll ans=n*k;for(int l=1,r=0;r<=n;r=l+1){r=min(n,(int)k/(k/l));ans-=1ll*(k/l)*(l+r)*(r-l+1)/2;}cout<<ans<<endl; }
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3085 地图中有两个鬼，两个人M和G，步长不同，鬼有曼哈顿距离计算的领域，问人能否相遇，实际上可以通过双向BFS求解。 注意每次点从队列中取出来的时候进行判断是否合法，实时判断，因为鬼是先进行分裂的，并且扩展之后的点也要先判断是否在鬼的领域中。 代码：#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define maxn 81...
题目链接；http://poj.org/problem?id=1011 又是拼木棍呀，不过这次我是对他的剪枝原理完全弄清楚了，最后两条剪枝还真的是很难想到的。这次的剪枝中加入了一条：我们在某一跟木棍中拼接时，选择的木棍长度是递减的，这样就保证了搜索树中不会有重叠的部分，不过其实在木棍中，小木棒是无序的，可以用这个策略来证明剪枝的正确性，也就是说，拼第一根失败和拼最后一根失败之后，这个分支就不可能搜索到最终状态了。 代码：#include...
#include<iostream> #include<string.h> using namespace std; #define maxn 100 int ver[maxn],head[maxn],nxt[maxn],size[maxn],len[maxn]; int n,m; int vis[maxn]; int tot=0; void addedge(int u,int v,int w){ver[++tot]=v;len[tot]=w;nxt[tot]=head[u];head[u]=tot; } int ans=0x7fffffff,pos; void dfs(int x){vis[x]=1;size[x]=1;int max_part=0;for(int i=head[x];i;i=nxt[i]){int v=ver[i];if(vis[v])continue;vis[v]=1...
题目链接：http://poj.org/problem?id=2259 由于同一个队伍的一定是连续的排队的，所以用一个队列记录排队的队伍顺序，用N个记录每个队伍内部的顺序。 代码：#include<iostream> #include<queue> using namespace std; #define maxn 1006 queue<int> q[maxn]; int t,n; int f[1000010]; int id=0; void work(){for(int i=0;i<maxn;i++)while(q[i].size())q[i].pop();for(int i=1;i<=t;i++){int k;scanf("%d",&n);while(n--){sc...
题目链接：http://poj.org/problem?id=1328 给出平面上N个点，要求在横轴上放置最少的点来覆盖N个点，其中每个点的覆盖半径都是R，可以将问题转化成用点覆盖线段的问题，计算N个点中每个点的可被管辖区间， 转化成求每个线段中至少有一个点的最少的点数。贪心思想。 代码：#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 100010 const double eps=1e-6; struct node...
题目链接：http://poj.org/problem?id=3190 题目中给定N头牛的吃草开始时间和结束时间，每头牛必须单独在一个牛栏里吃草，问最少需要多少个牛栏能满足要求？ 抽象出来的模型就是最少能将N个区间不相交地分布在多少个栏目中？ 算法步骤： 将所有牛按开始吃草的时间排序；用小根堆维护当前所有畜栏的最后一头牛的吃草结束时间；如果当前的牛可以安排在堆顶的畜栏中，则将其安排进去，否则就新建一个畜栏；证明： 反证法，假设存在一种...
http://neuralnetworksanddeeplearning.com/chap4.html 总结： 1. vanishing gradient problem：神经网络的不同层学习的速度显著不同。原因：weights式服从正态分布，那么w<1，而σ(zi) 服从N(0,1/4)，那么w*σ(zi)<=1/4，而dC/db1的公式为，那么dC/dbi是逐层减少的。 2. Exploding gradient problem： 6.1 深度神经网络中训练难点 到目前为止，我们例子中使用的神经网络一共只有3层（一个隐藏层）。我们用以上神经网络（通过调参...
题目链接：http://codeforces.com/contest/670/problem/C 一个电影有影视语言以及字幕语言，有m部电影以及n个人，每个人只会一种语言，语言的编号是一个int数，如果一个人能听懂影视语言就会非常开心，如果他听不懂影视语言但是听得懂字幕语言他将会比较高兴，如果他两个语言都听不懂就会不高兴，问他们应该去看哪部电影才能使得非常开心的人最多？如果非常开心的人的数量是一样的就要选择一部电影使得比较开心的人是最多的。 题解...
题目链接：https://www.acwing.com/problem/content/102/ 给定一个序列，只能对一个区间加一或者减一，问至少需要多少步使得所有数都变成一致的？有多少种一致序列？ 利用差分，对一个区间进行加一或者减一的话，一定是一个差分+1加上另一个差分-1。 代码如下：#include<bits/stdc++.h> using namespace std; typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; #define pf printf #define mem(a,b)...
题目链接：http://poj.org/problem?id=1958 求A的B次方的所有约数之和对9901的模。使用分治算法计算等比数列的前缀和，时间复杂度为O(logC) 代码如下：#include<iostream> #include<vector> using namespace std; #define ll long long #define maxn 1000 const ll p=9901; int n; ll ksm(ll a,ll b){//快速幂 ll ans=1;a%=p;while(b){if(b&1)ans=(ans*a)%p;b>>=1;a=(a*a)%p;}return ans; } vector<pair<ll,ll>> w; void fj(ll a)...
题目链接：http://poj.org/problem?id=1958 代码：#include<iostream> #include<cstring> using namespace std; #define maxn 100 typedef long long ll; ll d[maxn],f[maxn]; int main(){memset(f,0x3f,sizeof(f));d[1]=1;f[1]=1;int n = 12;for(int i=2;i<=n;i++)d[i]=d[i-1]*2+1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){f[i]=min(f[i],2*f[j]+d[i-j]);}}for(int i=1;i<=n;i++)cout<<f[i]<<endl; }
5.1 Cross-Entropy Cost 上节实现了一个简单的神经网络所需要的所有function，包括梯度下降算法，BP算法等，利用python实现最简单的神经网络。从本节课开始介绍另外一种cost function。 我们理想情况是让神经网络学习更快。 假设简单模型：只有一个输入、一个神经元、一个输出： 我们想让这个简单模型：输入为1的时候，输出为0. 初始w=0.6，b=0.9，初始测试的输出a=0.82,需要学习，学习率为0.15： I = 1*0.6+0.9 = 1.5 O = 1/1+...
4.1 Backpropagation算法上 1）传统的分类器： 上一节，我们利用了3层神经网络算法，来识别数字，达到了95%的精确度。这里我们不以图片的像素点为输入，用神经网络算法，而以平均灰度作为衡量准确率的指标。 平均灰度（Average Darkness）：输入照片是由像素点组成的（28*28=784），每一个像素点都有一个灰度值是0~255，归一化后将这 个值降到了[0,1]。可以把所有像素点的灰度值相加，再除以784，得出来得值做为metrix去衡量。看训...