#
1。完成曹雪的語(yǔ)法分析器
2。完成葉慶生的項(xiàng)目
3。有道難題的資格賽 （周六晚）
4。復(fù)習(xí)和總結(jié)動(dòng)態(tài)規(guī)劃專題（包括那個(gè)自學(xué)的內(nèi)容）
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
摘要: 這題出得不錯(cuò)，在傳統(tǒng)的bfs上加了點(diǎn)改進(jìn)，好題~
#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&...
閱讀全文
周五剛好在俞研的網(wǎng)絡(luò)安全課上學(xué)了RSA，回來(lái)想實(shí)現(xiàn)以下，由于以前數(shù)論方面的積累還算比較深厚，很快就過(guò)了這一題，呵呵:-)
總結(jié)一下吧，這題可以說(shuō)是數(shù)論部分的一個(gè)大綜合題，因?yàn)樗鼘⑺惴▽?dǎo)論上數(shù)論這部分的知識(shí)點(diǎn)全部包含了進(jìn)來(lái)，包括gcd,擴(kuò)展gcd,模線性方程，a^b mod c(還是比較難的那種，相關(guān)題目可以看一下FOZ上面的2道題),miller-rabin素?cái)?shù)測(cè)試，pollard_rho質(zhì)因數(shù)分解等等，把這題搞定了說(shuō)明你對(duì)算法導(dǎo)論的數(shù)論部分已經(jīng)可以做到熟練掌握了，相當(dāng)于<算法導(dǎo)論>數(shù)論部分的期末測(cè)試，呵呵^_^。
下面簡(jiǎn)要的說(shuō)一下這題的做法，首先簡(jiǎn)要介紹一下RSA算法加密解密的過(guò)程：
我們首先生成兩個(gè)大的素?cái)?shù)P,Q,乘起來(lái)得
N=P*Q.然后算出N的歐拉函數(shù)
Phi(N)=(P-1)*(Q-1).(什么是歐拉函數(shù)？這個(gè)世界上有一種東西叫做百度...）,然后我們?nèi)∫粋€(gè)范圍在
[1,phi(N)]中且與phi(N)互質(zhì)的正整數(shù)E.它就是所謂的公鑰。得到公鑰之后，我們?cè)偎愠鯡關(guān)于
phi(N)的逆元D,即E*D mod phi(N)=1.這個(gè)D就是私鑰。在得到這些數(shù)據(jù)以后，P,Q被丟棄，E,N做為公鑰被公開(kāi)，D做為私鑰被解密人私人保存。
好了，下面看一下如何用公鑰和私鑰對(duì)數(shù)據(jù)進(jìn)行加密解密。
假設(shè)有一個(gè)明文M,那么它所對(duì)應(yīng)的密文就是
C=M^E mod N.如果我們現(xiàn)在得到一個(gè)密文C,那么它所對(duì)應(yīng)的明文就是
M=C^D mod N也就是說(shuō)，任何人都可以用公鑰對(duì)數(shù)據(jù)進(jìn)行加密，但是只有擁有私鑰的人才可以對(duì)數(shù)據(jù)進(jìn)行解密。
那么RSA算法為什么不易被破解呢？從解密的過(guò)程來(lái)看如果你能夠知道D那么你就能解密數(shù)據(jù)。而E,D是逆元關(guān)系，要求出D,需要知道phi(N)，由于N非常之大，普通的做法是從1開(kāi)始枚舉到N-1，計(jì)算和N互質(zhì)的元素個(gè)數(shù)。可是N可以是幾百位到上千位的數(shù)字，普通的計(jì)算機(jī)只能在1s內(nèi)算到10^8量級(jí)，顯然是不可能破解的。唯一有可能的方法基于大素?cái)?shù)分解，如果你能將N分解成P*Q的乘積。那么就可以直接利用公式phi(N)=(P-1)*(Q-1)繞開(kāi)暴力求解歐拉函數(shù)的過(guò)程，從而實(shí)現(xiàn)RSA的破解。
這道題就是模擬這個(gè)破解過(guò)程，下面來(lái)說(shuō)說(shuō)具體的做法：
1.首先用miller-rabin,pollard_rho做大整數(shù)的質(zhì)因數(shù)分解，得到兩個(gè)素?cái)?shù)P,Q，pollard_rho的復(fù)雜度在N^0.25次方，那么一個(gè)64位的整數(shù) 要計(jì)算的次數(shù)為 2^64^0.25=2^16 =65536次，可以瞬間出解。
2.求出phi(N)=(P-1)*(Q-1)
3.然后用ext_gcd求出E關(guān)于phi(N)的逆元。
4.用得到的私鑰對(duì)數(shù)據(jù)C進(jìn)行解密即可。
PS:對(duì)這題而言，僅僅完成上述步驟還是不夠的。因?yàn)镹達(dá)到2^62次方，即使是使用無(wú)符號(hào)long long ,也很容易因?yàn)槌龀朔ú僮鞫绯觥＿@也是網(wǎng)上說(shuō)要避免使用擴(kuò)展歐幾里德的原因。其實(shí)實(shí)現(xiàn)的時(shí)候，我們可以自己寫一個(gè)特殊的乘法（內(nèi)部用加法實(shí)現(xiàn)），由于使用的無(wú)符號(hào)的long long ，第64位剛好可以用來(lái)保存兩個(gè)數(shù)加過(guò)之后的進(jìn)位位，再模除又可以保證其在2^62范圍內(nèi)，即可避免溢出。
摘要: 做完心情不太好，1000分的水題居然因?yàn)樽约洪_(kāi)小了數(shù)組而掛掉。算了，不解釋。250
#include<iostream>#include<algorithm>#include<cstdio>#include<string>#include<vector>using namespace std;struct ...
閱讀全文
剛好課上學(xué)了平面最近點(diǎn)對(duì)的算法，回來(lái)實(shí)現(xiàn)以下，恩 ，分治的思想很重要。呵呵，又學(xué)會(huì)了一個(gè)算法。
#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這些點(diǎn)的最近點(diǎn)對(duì)
{
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;
}
越來(lái)越發(fā)現(xiàn) 其實(shí)學(xué)生的水平 很大程度上還是依賴學(xué)校的綜合實(shí)力 畢竟我們學(xué)到的東西一大部分都是從老師那里來(lái)的 看來(lái)還是要多和外校的老師和同學(xué)交流才行啊。
取整函數(shù)的一些性質(zhì)：
• x-1 < ëxû £ x £ éxù < x+1；
• ë n/2 û + é n/2 ù = n;
• 對(duì)于n ³ 0，a,b>0，有：
• é é n/a ù /b ù = é n/ab ù ;
• ë ë n/a û /b û = ë n/ab û ;
• é a/b ù £ (a+(b-1))/b; (函數(shù)值的緊上界)
• ë a/b û ³ (a-(b-1))/b; (函數(shù)值的緊下界)
• f(x)= ë x û , g(x)= é x ù 為單調(diào)遞增函數(shù)
/////////////////////快速排序,時(shí)間復(fù)雜度為O(nlog2n)///////////////////////
template<class T>
int Partion(T a[],int i,int j)//劃分函數(shù)
{
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)////////////////////////
/**////////////////////////歸并排序,時(shí)間復(fù)雜度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)///////////////////////////////