DS-GA-1003 Lab1 Linear Descent, SGD, and Regularization
This is my lab from DS-GA-1003 NYUI put all my code in my github
Lab1 Gradient DescentImport and Init Datasetcompile feature normalization first
123456# Importimport matplotlib.pyplot as pltimport numpyimport pandas as pdimport numpy as npfrom sklearn.model_selection import train_test_split
12345678# Init datadf = pd.read_csv('hw1-data.csv', delimiter=',')X = df.values[:, :-1]y = df.values[:, -1]X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=100, random_s ...
A Research Problem（欧拉函数，DFS）
UVA10837由唯一分解定理：
n=\prod\limits_{i=1}^{k}(p_i^{a_i})由欧拉函数定义：
\phi(n)\\=n\prod\limits_{i=1}^{k}(1-\frac{1}{p_i})\\=\prod\limits_{i=1}^{k}(p_i^{a_i})\prod\limits_{i=1}^{k}(1-\frac{1}{p_i})\\=\prod\limits_{i=1}^{k}(p_i-1)p_i^{a_i-1}因此，对于给定的$\phi(n)$，我们可以将所有符合条件$m\mod (p_i-1)==0$的素数筛选出来，然后再枚举选取多个$p_i$即可。但由于素数表只打到10000以内的素数，即$\sqrt {phi_n}$。不过由于大于$\sqrt {phi_n}$的素数至多有一个，所以在特判即可。因为最后一个素数的范围为$[2,phi_n]$，因此只要这个数与$[2,\sqrt{phi_n}]$内的所有数互质，那么它就是素数。以下函数为判断最后一个选取的素数。123456789101112131415inline bool Judgt(co ...
A Spy in the Metro
UVA1025定义：$dp[i][j]$为在第$i$时刻间谍到达第j个车站时在车站待的最短时间,$RightTrain[i][j]$表示在第$i$时刻是否有从左向右开的列车，$LeftTrain[i][j]$同理。初始化：$dp[0][1]=0$,剩下的dp元素$=inf$转移方程：在第$i$时刻间谍位于第$j$个车站时有三种转移方式：
由第$i-1$时刻在第$j$个站台等待$1$个时刻
上一次在$j$站台左边的站台并且搭上从左往右开的列车到达$j$站台
上一次在$j$站台右边的站台并且搭上从右往左开的列车到达$j$站台1234567dp[i][j] = dp[i - 1][j] + 1;//对应1。if (RightTrain[i][j]) {//对应2.dp[i][j] = min(dp[i][j], dp[i - Time[j - 1]][j - 1]);}if (LeftTrain[i][j]) {//对应3.dp[i][j] = min(dp[i][j], dp[i - Time[j]][j + 1]);}
AC代码：12345 ...
Almost Prime Numbers（素数筛）
UVA10539
枚举2到$\sqrt{high}$，分别看$i^2,i^3\cdots i^n$，是否在$[left,right]$中，统计多少个这样的次方方在范围中即可。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <cstdio>#include <cstring>using namespace std;const int MAXN = 1e7;bool IsPrime[MAXN + 1];vector<int> PTable;void InitPTable() { for (int i = 2; i <= MAXN; ++i) { if ...
And Then There Was One
题目链接
约瑟夫环问题假设有$n$个数，编号为$0,1,2,\cdots n-1$，其中0和$n-1$相连，形成一个环，如图：123456graph LR0((0))---1((1))1((1)) --- 2((2))2((2))---3((3))3((3)) -- ....... ---n((n))n---0从0开始数$k$个，将这个数从环中移除，再数$k$个，再移除，问最后一个数是多少。假设$n=7,k=3$。那么第一次删除2，数列变成:0|1|2|3|4|5|6-|-|-|-|-|-|-0|1| |3|4|5|6此时，1和3分离开了，为了使1和3连续，我们可以将列表重新编号，从被删除的下一个数开始编号，即： \ |0|1|2|3|4|5|6 -|-|-|-|-|-|-|- 编号前|0|1| |3|4|==5==|6 编号后|4|5| |0|1|==2==|3 这样新表的下一个要删除的数编号为2，而旧表中为5。 不难发现，新旧表的下一个待删除的数的编号存在这样一个关系：
DeletedNode_{新表}=（DeletedNode_{旧表}-k）\bmod 旧表中剩余的数的个数 根据 ...
Another Crisis
UVA12186 定义：$dp[i]$为要使第$i$名员工向其上级发信最少需要多少工人，$DP(i)$返回$dp[i]$的值，$Son[i]$为第$i$名员工的所有直属下级。每一个员工都只有一个直接上级，因此不会有两个工人由同一上级。1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<cmath>using namespace std;int N, T;vector<int> Son[100001];void Clear() { for (int i = 0; i <= N; ++i) { Son[i].clear(); }&# ...
Balloon Robot（模拟）
ZOJ - 3981
The 2017 China Collegiate Programming Contest Qinhuangdao Site is coming! There will be nnn teams participating in the contest, and the contest will be held on a huge round table with mmm seats numbered from 1 to mmm in clockwise order around it. The iii-th team will be seated on the sis_isi-th seat.BaoBao, an enthusiast for competitive programming, has made ppp predictions of the contest result before the contest. Each prediction is in the form of (ai,bi)(a_i,b_i)(ai,bi), which m ...
Books
ZOJ - 4067
DreamGrid went to the bookshop yesterday. There are $n$ books in the bookshop in total. Because DreamGrid is very rich, he bought the books according to the strategy below: Check the $n$ books from the 1st one to the $n$-th one in order. For each book being checked now, if DreamGrid has enough money (not less than the book price), he’ll buy the book and his money will be reduced by the price of the book. In case that his money is less than the price of the book being checked now, he ...
Brackets sequence
UVA1626这是一道区间动态规划。定义：$dp[i][j]$为从第$i$个字符到第$j$个字符组成的子串要成为正规子串最少要添加多少字符，$S$为字符串。初始化：
$dp[i][i]=1$一个字符必定需要补充另一个才能匹配。
$dp[i+1][i]=0$在转移方程中的$dp[i][j]=dp[i+1][j-1]$里，若$j=i+1$且$S[i]$与$S[j]$匹配，则$dp[i+1][j-1]=dp[i+1][i]=0$，即此时不需要补充字符。
其余$dp$元素$=|S|$需要补充的数量再长与不会超过$|S|$
判断匹配：123456bool Match(const char& Left, const char& Right) { return Left == '(' && Right == ')' || Left == '[' && Right == ']';}转移方程：1234567891011121314for (int ...
Choose and divide
Voj
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <string.h>using namespace std;const int MAXN = 10000;//素数表vector<int> PrimerTable;//计算答案的唯一分解定理中第i个素数有几个int PrimeFactor[1230];void InitPrimerTable() { bool IsNotP[10001]; memset(IsNotP, false, s ...