#
1。完成曹雪的语法分析器
2。完成叶庆生的项目
3。有道难题的资格赛 （周六晚）
4。复习和总结动态规划专题（包括那个自学的内容）
The MS-RT professional masters degree program trains future leaders of robotics and intelligent automation enterprises and agencies in the principles and practices of robotics and automation science and engineering, software engineering, and management. The program is appropriate for students with backgrounds in an engineering or science discipline and practical abilities in computer systems and software engineering. Classroom training is reinforced by an extensive supervised practicum designed to expose the students to research laboratory and industrial environments. They will thus acquire - and be expected to demonstrate - individual and group competence in the skills and practices that will be needed to support the entrepreneurial teams they will lead upon their return to their home countries.
The two-year program is composed of two one-year phases. First year studies are at an international partner institution's campus via distance education materials produced by the Robotics Institute and delivered by the partner's faculty. Successful students transition to Carnegie Mellon's main campus to complete a second year of classes and an extensive practicum. Graduates are eligible to pursue additional practical training in the US before returning to their home countries.
Preferably the additional training will be an internship with a company in the US that, afterwards, will employ the student at a division in his or her home country. The program's intention is for graduates to return home to entrepreneurial activities that will contribute to sustainable development there.
Historical Note: In 2005 some graduates of this program received Master of Science in Information Technology - Robotics Technology (MSIT-RT) degrees and others received MSIT degrees. In 2006 and 2007 all graduates received MSIT-RT degrees. Subsequently the program name was changed to Master of Science - Robotics Technology (MS-RT) to better reflect its actual content. For additional simplicity, all graduates are listed here as having received MS-RT degrees.
Additional information
摘要: 这题出得不错，在传统的bfs上加了点改进，好题~
#include<iostream>#include<cmath>using namespace std;int const maxn=110;int mm[maxn][maxn];int v[maxn][maxn][4];//0上，1右，2下，3左struct&...
阅读全文
周五刚好在俞研的网络安全课上学了RSA，回来想实现以下，由于以前数论方面的积累还算比较深厚，很快就过了这一题，呵呵:-)
总结一下吧，这题可以说是数论部分的一个大综合题，因为它将算法导论上数论这部分的知识点全部包含了进来，包括gcd,扩展gcd,模线性方程，a^b mod c(还是比较难的那种，相关题目可以看一下FOZ上面的2道题),miller-rabin素数测试，pollard_rho质因数分解等等，把这题搞定了说明你对算法导论的数论部分已经可以做到熟练掌握了，相当于<算法导论>数论部分的期末测试，呵呵^_^。
下面简要的说一下这题的做法，首先简要介绍一下RSA算法加密解密的过程：
我们首先生成两个大的素数P,Q,乘起来得
N=P*Q.然后算出N的欧拉函数
Phi(N)=(P-1)*(Q-1).(什么是欧拉函数？这个世界上有一种东西叫做百度...）,然后我们取一个范围在
[1,phi(N)]中且与phi(N)互质的正整数E.它就是所谓的公钥。得到公钥之后，我们再算出E关于
phi(N)的逆元D,即E*D mod phi(N)=1.这个D就是私钥。在得到这些数据以后，P,Q被丢弃，E,N做为公钥被公开，D做为私钥被解密人私人保存。
好了，下面看一下如何用公钥和私钥对数据进行加密解密。
假设有一个明文M,那么它所对应的密文就是
C=M^E mod N.如果我们现在得到一个密文C,那么它所对应的明文就是
M=C^D mod N也就是说，任何人都可以用公钥对数据进行加密，但是只有拥有私钥的人才可以对数据进行解密。
那么RSA算法为什么不易被破解呢？从解密的过程来看如果你能够知道D那么你就能解密数据。而E,D是逆元关系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是从1开始枚举到N-1，计算和N互质的元素个数。可是N可以是几百位到上千位的数字，普通的计算机只能在1s内算到10^8量级，显然是不可能破解的。唯一有可能的方法基于大素数分解，如果你能将N分解成P*Q的乘积。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)绕开暴力求解欧拉函数的过程，从而实现RSA的破解。
这道题就是模拟这个破解过程，下面来说说具体的做法：
1.首先用miller-rabin,pollard_rho做大整数的质因数分解，得到两个素数P,Q，pollard_rho的复杂度在N^0.25次方，那么一个64位的整数 要计算的次数为 2^64^0.25=2^16 =65536次，可以瞬间出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E关于phi(N)的逆元。
4.用得到的私钥对数据C进行解密即可。
PS:对这题而言，仅仅完成上述步骤还是不够的。因为N达到2^62次方，即使是使用无符号long long ,也很容易因为出乘法操作而溢出。这也是网上说要避免使用扩展欧几里德的原因。其实实现的时候，我们可以自己写一个特殊的乘法（内部用加法实现），由于使用的无符号的long long ，第64位刚好可以用来保存两个数加过之后的进位位，再模除又可以保证其在2^62范围内，即可避免溢出。
摘要: 做完心情不太好，1000分的水题居然因为自己开小了数组而挂掉。算了，不解释。250
#include<iostream>#include<algorithm>#include<cstdio>#include<string>#include<vector>using namespace std;struct ...
阅读全文
刚好课上学了平面最近点对的算法，回来实现以下，恩 ，分治的思想很重要。呵呵，又学会了一个算法。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-8
const int maxn=200001;
const double INF=999999999;
typedef struct point
{
double x,y;
//int flag;
point(){};
}point;
point p[maxn];
int n;
int cmp(double x,double y)
{
if(x==y)return 0;
if(x>y)return 1;
return -1;
}
bool cmp1(point a,point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
bool cmp2(int i,int j)
{
return cmp(p[i].y,p[j].y)<0;
}
double dist(point &a,point &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int y[maxn],len;
double cp(point p[],int l,int r)//求从l到r这些点的最近点对
{
int i,j;
int mid=(l+r)>>1;
double ret=INF;
if(l>=r)
return ret;
for(i=mid;i>=l&&!cmp(p[i].x,p[mid].x);i--);
double t1=cp(p,l,i);
for(i=mid;i<=r&&!cmp(p[i].x,p[mid].x);i++);
double t2=cp(p,i,r);
if(t1<t2)
ret=t1;
else ret=t2;
len=0;
for(i=l;i<=r;i++)
{
if(fabs(p[i].x-p[mid].x)<ret)
y[++len]=i;
}
sort(y+1,y+len+1,cmp2);
for(i=1;i<=len;i++)
{
int cnt=1;
for(j=i+1;j<=len&&cnt<=7;j++)
{
ret=min(ret,dist(p[y[i]],p[y[j]]));
cnt++;
}
}
return ret;
}
bool check(int n)
{
int i;
for(i=2;i<=n;i++)
{
if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
return true;
}
return false;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
int i;
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+1,p+n+1,cmp1);
if(check(n))
{
printf("0.00\n");
continue;
}
double ans=cp(p,1,n)/2;
printf("%.2lf\n",ans);
}
return 0;
}
越来越发现 其实学生的水平 很大程度上还是依赖学校的综合实力 毕竟我们学到的东西一大部分都是从老师那里来的 看来还是要多和外校的老师和同学交流才行啊。
取整函数的一些性质：
• x-1 < ëxû £ x £ éxù < x+1；
• ë n/2 û + é n/2 ù = n;
• 对于n ³ 0，a,b>0，有：
• é é n/a ù /b ù = é n/ab ù ;
• ë ë n/a û /b û = ë n/ab û ;
• é a/b ù £ (a+(b-1))/b; (函数值的紧上界)
• ë a/b û ³ (a-(b-1))/b; (函数值的紧下界)
• f(x)= ë x û , g(x)= é x ù 为单调递增函数
/////////////////////快速排序,时间复杂度为O(nlog2n)///////////////////////
template<class T>
int Partion(T a[],int i,int j)//划分函数
{
T temp;
temp=a[i];
while(i<j)
{
while(i<j && temp<=a[j])
j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j && a[i]<=temp)
i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
return i;
}
template <class T>
void qsort(T a[],int l,int h)
{
int m;
if(l<h)
{
m=Partion(a,l,h);
qsort(a,l,m-1);
qsort(a,m+1,h);
}
}
template<class T>
void SortWizard<T>::QuickSort()
{
qsort(a,0,n-1);
}
/**/////////////////////QuickSort_O(nlog2n)////////////////////////
/**////////////////////////归并排序,时间复杂度O(nlog2n)/////////////////////////////
template <class T>
void Merge(T sr[],T tr[],int l,int m,int n)
{
int i,j,k;
i=l;
j=m+1;
k=l-1;
while(i<=m && j<=n)
{
if(sr[i]<sr[j])
tr[++k]=sr[i++];
else
tr[++k]=sr[j++];
}
while(i<=m)
tr[++k]=sr[i++];
while(j<=n)
tr[++k]=sr[j++];
for(i=l;i<=n;i++)
sr[i]=tr[i];
}
template <class T>
void Msort(T a[],T st[],int s,int t)
{
int m;
if(s<t)
{
m=(s+t)>>1;
Msort(a,st,s,m);
Msort(a,st,m+1,t);
Merge(a,st,s,m,t);
}
}
template <class T>
void SortWizard<T>::MergeSort()
{
T *st=new T[n];
Msort(a,st,0,n-1);
delete [ ]st;
}
/**//**//**///////////////////////MergeSort_O(nlog2n)///////////////////////////////