分类存档：默认分类

[JSOI2010 Group 部落划分]并差集、排序

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1821
【算法分析】
就是把边权从小到大排序，然后从前面搞下来，用并差集判断剩下的独立块有多少个？
如果【其它】
WA了N遍= =。
if (Num写成了
if (Num头脑有点不清醒啊。。。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const int N=1005;
struct Point{int x,y;}a[N];
struct edge{int x,y,w;}g[N*N];
int n,part,m;
int f[N];

int dis(Point A,Point B){
return sqr(A.x-B.x)+sqr(A.y-B.y);
}

void input(){
scanf("%d%d",&n,&part);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
m=0;
for (int i=1;i for (int j=i+1;j<=n;j++){
g[m].x=i;
g[m].y=j;
g[m].w=dis(a[i],a[j]);
++m;
}
}

int cmp(const void *A,const void *B){
return ((edge*)A)->w-((edge*)B)->w;
}

int GF(int k){
if (f[k]==k) return k;
else return f[k]=GF(f[k]);
}

int solve(){
int Num=n;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=0;;i++){
edge &p=g[i];
if (GF(p.x)!=GF(p.y)){
f[f[p.x]]=f[p.y];
Num–;
if (Num }
}
}

int main(){
input();
qsort(g,m,sizeof(edge),cmp);
printf("%.2lfn",sqrt(1.0*solve()));
}

[JSOI2010 Express Service 快递服务]动态规划

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1820
【算法分析】
假如用F[i][j][k][l]表示第i个要求，三个货车司机分别在j，k，l三个点时的最小费用。
那么转移就非常简单。
然后可以发现，j，k，l中总有一个是等于Q[i]的。于是删掉这维，滚动数组dp即可。
【CODE】
#include #include #include const int N=205;
int n,q;
int d[N][N],List[88888];
int F[2][N][N];

int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&d[i][j]);
for (int i=1;i<=n;i++) d[i][i]=0;
memset(F,50,sizeof(F));
List[0]=1; F[0][2][3]=F[0][3][2]=0;
q=1;
int p=1;
while (scanf("%d",&List[q])!=EOF){
memset(F[p],50,sizeof(F[p]));
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
F[p][i][j] F[p][List[q-1]][j] F[p][List[q-1]][i] }
q++;
p=1-p;
}
int ans=0x7FFFFFFF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans printf("%dn",ans);
}

[JSOI2010 Word Query 电子字典]Trie

【题目地址】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1819
【算法分析】
Trie+直接暴力枚举那些操作。
【其它】1A。跑得再一次全世界最慢。
【CODE】
#include #include #include int n,m;
struct Trie_t{
Trie_t *son[26];int key;
void Fill(){
for (int i=0;i<26;i++) son[i]=NULL;
key=0;
}
}*root;

void Insert(char *str){
Trie_t *p=root;
while (*str){
if (p->son[*str-‘a’]) p=p->son[*str-‘a’];
else{
p->son[*str-‘a’]=(Trie_t*)malloc(sizeof(Trie_t));
p=p->son[*str-‘a’];
p->Fill();
}
str++;
}
p->key++;
}

void input(){
root=(Trie_t*)malloc(sizeof(Trie_t));
root->Fill();
char str[100];
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",str);
Insert(str);
}
}

bool Find(char *str){
Trie_t *p=root;
while (*str){
if (!p->son[*str-‘a’]) return false;
p=p->son[*str-‘a’];
str++;
}
if (p->key) return true;
return false;
}

void solve(){
char str[100],str2[100],Inchar;
for (int i=1,j,k,Inchar;i<=m;i++){
scanf("%s",str);
if (Find(str)) puts("-1");
else{
int Len=strlen(str),tot,ans=0;
for (j=0;j if (str[j]==str[j+1]) continue;
tot=0;
for (k=0;k if (k!=j)
str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2)) ans++;
}

for (j=0;j<=Len;j++)
for (Inchar=’a’;Inchar<='z';Inchar++){
if (str[j]==Inchar) continue;
tot=0;
for (k=0;k str2[tot++]=str[k];
str2[tot++]=Inchar;
for (k=j;k str2[tot++]=str[k];
str2[tot]=0;
if (Find(str2))
ans++;
}

for (j=0;j char tmp=str[j];
for (Inchar=’a’;Inchar<='z';Inchar++){
str[j]=Inchar;
if (Find(str)) ans++;
}
str[j]=tmp;
}
printf("%dn",ans);
}
}
}

int main(){
input();
solve();
}

[FOJ1904 Cake,Cake,Delicious]DFS+凸包 or DFS+半平面交

【题目链接】http://acm.fzu.edu.cn/problem.php?pid=1904
【题目大意】
师傅买了一个矩形的大蛋糕，切了N刀，问这个大蛋糕剩下的块里最大的一块有多大?
【算法分析】
首先最直接的方法：
DFS每刀的直线方程>=0还是<=0，然后求半平面交。
第二种方法：
DFS每刀的直线方程>=0还是<=0，然后再枚举所有直线的交点中在这个半平面内的。
对这些点做凸包，然后算面积。
【其它】
我是傻×。。。居然WA了一遍。
AC的：
printf("Case #%d: %.3lfn",i,ans);
WA的：
printf("Case #%d: %.3lfn",Tc,ans);
样例都不过就拿去交了= =。。。。。
【CODE】
#include #include #include #include #define AA ((Point*)A)
#define BB ((Point*)B)
const int N=30;
const double eps=1e-6;
int n,pn,plt,Lt,List[N*N];
double ans,S;
struct Line{int a,b,c;}L[N];
struct Point{double x,y;}P[N*N],pl[N*N];

void Add_Line(int i,int x1,int y1,int x2,int y2){
L[i].a=y1-y2;
L[i].b=x2-x1;
L[i].c=x1*y2-x2*y1;
}

void Add_Point(Line A,Line B){
int tmp=A.a*B.b-B.a*A.b;
if (!tmp) return;
pn++;
P[pn].x=(double)(A.b*B.c-B.b*A.c)/tmp;
P[pn].y=(double)(B.a*A.c-A.a*B.c)/tmp;
}

void input(){
scanf("%d",&n);
for (int i=0;i int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Add_Line(i,x1,y1,x2,y2);
}
Add_Line(n,0,100,0,0);
Add_Line(n+1,0,0,100,0);
Add_Line(n+2,100,0,100,100);
Add_Line(n+3,100,100,0,100);
pn=0;
for (int i=0;i for (int j=i+1;j Add_Point(L[i],L[j]);
P[N*N-1].x=0;
P[N*N-1].y=0;
}

int cj(Point p0,Point p1,Point p2){
double res=(p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
if (fabs(res) if (res<0) return -1;
return 1;
}

bool In_Line(Point pp,Line ll){
double res=pp.x*ll.a+pp.y*ll.b+ll.c;
if (fabs(res) if (res>=0) return true;
return false;
}

void swap(Point &A,Point &B){
Point tmp=A;
A=B;
B=tmp;
}

int cmp(const void *A,const void *B){
return cj(P[N*N-1],*AA,*BB);
}

void TB(){
if (plt<3) return;
Point m;
int maxi=0;
m.x=1e50;
for (int i=1;i<=plt;i++)
if (pl[i].x m=pl[i];
maxi=i;
}
for (int i=1;i<=plt;i++){
pl[i].x-=m.x;
pl[i].y-=m.y;
}
swap(pl[1],pl[maxi]);
qsort(pl+2,plt-1,sizeof(Point),cmp);
pl[plt+1]=pl[1];
Lt=1; List[1]=1;
for (int i=2;i<=plt+1;i++){
while (Lt>1 && cj(pl[List[Lt-1]],pl[i],pl[List[Lt]])<=0) Lt--;
List[++Lt]=i;
}
}

void Count(){
S=0;
if (plt<3) return;
for (int i=1;i Point &pre=pl[List[i]],&now=pl[List[i+1]];
S+=pre.x*now.y-pre.y*now.x;
}
S=fabs(S)/2;
}

void Try(){
int i,j;
plt=0;
for (i=1;i<=pn;i++){
bool flag=true;
for (j=0;j if (!In_Line(P[i],L[j])){
flag=false;
break;
}
if (flag) pl[++plt]=P[i];
}
TB();
Count();
if (S>ans) ans=S;
}

void dfs(int depth){
if (depth==n) {Try(); return;}
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
dfs(depth+1);
L[depth].a=-L[depth].a;
L[depth].b=-L[depth].b;
L[depth].c=-L[depth].c;
}

int main(){
freopen("1904.in","r",stdin);
freopen("1904.out","w",stdout);
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
ans=0;
dfs(0);
printf("Case #%d: %.3lfn",i,ans);
}
}

[Sdoi2010 所驼门王的宝藏]强连通分量、猥琐优化

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1924
【算法分析】
一开始就YY裸的强连通，但是如果他们都在同一行，而且都是1的话，边数将达到n*n的级别。
然后除了这个猥琐数据，其它的一般好像没啥问题。
于是我就把在同一行的，都是1的用k条边直接连成一个圈。
在同一列的，都是2的，也用k条边直接连成一个圈。
(k表示这一行(列)为1(2)的点的个数。)
然后暴力SCC。
最后dp输出即可。
【其它】
来BS我吧。。。再一次全世界最慢。终于把Sdoi第一轮的6题都AC了~
1 23185 root 7804K 1012MS G++ 3.07K 2010-05-14 13:51:35 2 24544 maja 35592K 1041MS Pascal 3.82K 2010-05-20 09:12:35 3 24545 wu3412790 35592K 1057MS Pascal 3.82K 2010-05-20 09:13:00 4 24621 colonnello 15012K 1153MS Pascal 8.31K 2010-05-20 16:37:08 5 24566 Ksloverainboy 35700K 1167MS Pascal 5.66K 2010-05-20 12:56:19 6 23589 nehzilrz 20024K 1183MS G++ 3.71K 2010-05-16 13:52:20 7 23192 FDhyc 10932K 1232MS Pascal 5.61K 2010-05-14 13:57:22 8 23362 oimaster 11568K 1356MS G++ 3.91K 2010-05-15 15:52:05 9 24880 _gXX 36740K 1370MS Pascal 5.06K 2010-05-21 20:30:14 10 24096 tracyhenry 44520K 1371MS Pascal 5.51K 2010-05-18 19:01:05 11 23341 jsn1993 11968K 1373MS G++ 3.17K 2010-05-15 07:54:22 12 24554 cly 48776K 1574MS Pascal 7.06K 2010-05-20 10:29:23 13 24512 bonism 57724K 1636MS G++ 3.76K 2010-05-20 07:57:28 14 24901 edward_mj 6652K 1638MS G++ 4.48K 2010-05-21 21:46:52 【CODE】
#include #include #include const int E=2000005;
const int N=100005;
const int px[8]={-1,-1,-1, 0, 0, 1, 1, 1};
const int py[8]={-1, 0, 1,-1, 1,-1, 0, 1};
int n,tot,cnt,Lt;
int fa[N],order[N],List[N],F[N];
bool v[N];
struct Node{int x,y,T,w,pos;}a[N];
struct edge{int x,y;edge *next;};
struct Gtp{
int e;
edge g[E],*ls[100005];
void init(){e=0; for (int i=0;i void add(int x,int y){
if (!x || !y || x==y) return;
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void op(){
int tmp=e,i;
init();
for (i=1;i<=tmp;i++)
add(g[i].y,g[i].x);
}

void Turn_fa(){
int tmp=e,i;
init();
for (i=1;i<=tmp;i++)
add(fa[g[i].x],fa[g[i].y]);
}

void dfs(int p,bool Type){
v[p]=true;
if (Type) fa[p]=cnt;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]) dfs(t->y,Type);
if (!Type) order[++tot]=p;
}
}G;

void input(){
int r,c,i;
scanf("%d%d%d",&n,&r,&c);
for (i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].T);
a[i].pos=i;
a[i].w=0;
fa[i]=i;
}
}

int cmpR(const void *A,const void *B){
return ((Node*)A)->x-((Node*)B)->x;
}
int cmpC(const void *A,const void *B){
return ((Node*)A)->y-((Node*)B)->y;
}
int cmpFree(const void *A,const void *B){
if (((Node*)A)->x!=((Node*)B)->x) return ((Node*)A)->x-((Node*)B)->x;
return ((Node*)A)->y-((Node*)B)->y;
}
int cmpdp(const void *A,const void *B){
return ((Node*)A)->pos-((Node*)B)->pos;
}

struct R_Function{
void deal(){
qsort(a+1,n,sizeof(Node),cmpR);
int i,j,k,st,pre;
for (i=1;i<=n;i=j+1){
for (j=i;j for (k=i,st=0,pre=0;k<=j;k++)
if (a[k].T==1){
if (!st) st=a[k].pos;
else G.add(pre,a[k].pos);
pre=a[k].pos;
}
G.add(pre,st);
for (k=i;k<=j;k++)
if (a[k].T!=1)
G.add(st,a[k].pos);
}
}
}R;

struct C_Function{
void deal(){
qsort(a+1,n,sizeof(Node),cmpC);
int i,j,k,st,pre;
for (i=1;i<=n;i=j+1){
for (j=i;j for (k=i,st=0,pre=0;k<=j;k++)
if (a[k].T==2){
if (!st) st=a[k].pos;
else G.add(pre,a[k].pos);
pre=a[k].pos;
}
G.add(pre,st);
for (k=i;k<=j;k++)
if (a[k].T!=2)
G.add(st,a[k].pos);
}
}
}C;

struct Free_Function{
int Find(int x,int y){
int l=1,r=n,mid;
while (l mid=(l+r)/2;
if (a[mid].x else r=mid;
}
if (a[l].x==x && a[l].y==y) return a[l].pos;
return 0;
}

void deal(){
qsort(a+1,n,sizeof(Node),cmpFree);
int i,j;
for (i=1;i<=n;i++)
if (a[i].T==3)
for (j=0;j<8;j++)
G.add(a[i].pos,Find(a[i].x+px[j],a[i].y+py[j]));
}
}Free;

void SCC(){
G.Turn_fa();
memset(v,false,sizeof(v));
int i,j; tot=Lt=0;
for (i=1;i<=n;i++)
if (!v[i])
G.dfs(i,false);
G.op();
memset(v,false,sizeof(v));
for (j=tot;j>=1;j–){
i=order[j];
if (!v[i]){
cnt=i;
List[++Lt]=i;
G.dfs(i,true);
}
}
G.op();
G.Turn_fa();
}

void dp(){
qsort(a+1,n,sizeof(Node),cmpdp);
memset(F,0,sizeof(F));
int i,j,ans=0;
for (i=1;i<=n;i++) a[fa[i]].w++;
for (j=1;j<=Lt;j++){
i=List[j];
F[i]+=a[i].w;
for (edge *t=G.ls[i];t;t=t->next)
if (F[i]>F[t->y]) F[t->y]=F[i];
if (F[i]>ans) ans=F[i];
}
printf("%dn",ans);
}

int main(){
input();
R.deal();
C.deal();
Free.deal();
SCC();
dp();
}