Ubuntu 安裝記要

[給自己的筆記]
由於Ubuntu提供了一個圖形化的安裝界面
因此只大概紀錄一下安裝好後的軟體(分配70Gb)：


$ git
$ vim
$ python

還有關機是用：

$ sudo shutdown -h now  

UVA 10020 - Minimal coverage

[GREEDY]



#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct Line{int L,R;}lines[100010];
int save[100010];
bool operator<(Line a,Line b){return (a.L<b.L);}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int M;scanf("%d",&M);
int lcnt=0; int a,b;
while(scanf("%d %d",&a,&b))
{
if((a==0)&&(b==0)) break;
if(b<0) continue;
lines[lcnt].L=a,lines[lcnt].R=b;
lcnt++;
}
sort(lines,lines+lcnt);
//for(int lx=0;lx<lcnt;lx++)
// printf("%d %d]\n",lines[ptrs[lx].index].L,lines[ptrs[lx].index].R);
int lptr=0;
int Now=0;
int savecnt=0;
while(lptr<lcnt)
{
int mindex=-1;
int mmax=0;
while((lptr<lcnt)&&(lines[lptr].L<=Now))
{
if(mmax<lines[lptr].R)
{
mindex=lptr;
mmax=lines[lptr].R;
}
lptr++;
}
if(mindex<0) break;
Now=mmax;
save[savecnt++]=mindex;
if(Now>=M) break;
lptr=mindex+1;
}
if(Now>=M)
{
printf("%d\n",savecnt);
for(int lx=0;lx<savecnt;lx++)
printf("%d %d\n",lines[save[lx]].L,lines[save[lx]].R);
}
else
puts("0");
if(T) puts("");
}
return 0;
}

UVA 674 Coin Change

[DP]


#include<stdio.h>
#include<stdlib.h>
#define LL long long int
#define NN 7490
int co[5]={1,5,10,25,50};
LL tab[5][NN];
LL gettab(int n,int t)
{
if((n<0)||(t<0)) return 0;
if(t==0) return 1;
return tab[n][t];
}
int main()
{
int n;
for(int lx=0;lx<5;lx++)
for(int lm=1;lm<NN;lm++)
tab[lx][lm]=gettab(lx-1,lm)+gettab(lx,lm-co[lx]);
while(scanf("%d",&n)!=EOF)
printf("%lld\n",tab[4][n]);
return 0;
}

POJ 2299 Ultra-QuickSort

[merge sort]

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define N 500000
#define LL long long int
LL line[N];
LL pp[N];
int n;
LL merge(int a,int b)
{
if(b==a) return 0 ;
if(b==a+1)
{
if(line[a]>line[a+1])
{
line[a]^=line[a+1]^=line[a]^=line[a+1];
return 1;
}
return 0;
}
int mid=(a+b)>>1;
LL res=0;
res+=merge(a,mid);
res+=merge(mid+1,b);
int ptr1=a;
int ptr2=mid+1;
for(int lx=a;lx<=b;lx++)
{
if(ptr1==mid+1)
pp[lx]=line[ptr2++];
else if(ptr2==b+1)
{
pp[lx]=line[ptr1++];
res+=(LL)(b-mid);
}
else
{
if(line[ptr1]>line[ptr2])
pp[lx]=line[ptr2++];
else
{
pp[lx]=line[ptr1++];
res+=(LL)(ptr2-1-mid);
}

}
}
for(int lx=a;lx<=b;lx++)
line[lx]=pp[lx];
return res;
}
int main()
{
while(scanf("%d",&n)&&n)
{
for(int lx=0;lx<n;lx++)
scanf("%I64d",line+lx);
printf("%I64d\n",merge(0,n-1));
}
return 0;
}

AKS質數測試

[?]
=兒=

最近終於把AKS看完了@@ 下面的投影片是重點筆記，
應該有辦法幫助了解?
http://www.slideshare.net/mudream4869/aks-29609803

先備知識：分圓方程式在FINITE FIELD 上的性質、微積分