[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();
}

[Sdoi2010 粟粟的书架]线段树、归并排序思想、桶

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1926
【算法分析】
前半部分，直接开200*200个1000的桶，利用经典的O(1)取子矩阵和的那种思想。复杂度做到了
O(Q*1000+R*C*1000)。
后半部分，弄一个线段树然后利用归并的思想把它映射到线性表上，然后二分答案再利用线段树二分线性表上的位置，最终得出ans。
时间复杂度O(Q*lg 1000 * lg c * lg c)。

【其它】
Orz。一开始第一部分用二维线段树做，直接TLE到SB。
线性表的话复杂度达到O(Q * lg 1000 * lg r * lg c * lg r*c)。
桶的话复杂度达到O(Q * lg 1000* lg r * lg c)。但是空间受不了。。。
跑得全世界最慢。
1 23199 root 157204K 4435MS Pascal 3.82K 2010-05-14 14:07:37 2 23435 oimaster 100112K 5574MS G++ 4.15K 2010-05-15 22:54:09 3 24878 edward_mj 164928K 9324MS G++ 4.45K 2010-05-21 20:25:45 【CODE】
#include #include #include const int N=205;
const int rate=8;
int m,n,q,spt,a[N][N],b[500005];
int sp[12000005],Tong[N][N][1001];
int S[ 12000005];
struct Node_t{int l,r,st,ed;}Tr[500005*rate];

struct Solve1_t{
int Sum,Limit,Num,x1,y1,x2,y2,h,Lt;
void input(){
spt=0;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(Tong,0,sizeof(Tong));
int i,j,k;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
if (i+j==2) {Tong[i][j][a[1][1]]++;continue;}
if (i>1){
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i-1][j][k];
for (k=1;k<=j;k++)
Tong[i][j][a[i][k]]++;
}else{
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i][j-1][k];
for (k=1;k<=i;k++)
Tong[i][j][a[k][j]]++;
}
}
}

void solve(){
S[0]=0;
for (int i=1;i<=spt;i++) S[i]=S[i-1]+sp[i];
for (int i=0,j;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
int Nt;
Sum=Num=0;
for (j=1000;j>=1;j–){
Nt=0;
Nt+=Tong[x2][y2][j];
Nt-=Tong[x1-1][y2][j];
Nt-=Tong[x2][y1-1][j];
Nt+=Tong[x1-1][y1-1][j];
Sum+=Nt*j;
Num+=Nt;
if (Sum>=h){
Num-=(Sum-h)/j;
printf("%dn",Num);
break;
}
}
if (Sum }
}
}Deal1;

struct Solve2_t{
int x1,y1,x2,y2,Num,h,Limit;
int Sum;

void input(){
spt=0;
for (int i=1;i<=n;i++)
scanf("%d",&b[i]);
}

void Union(Node_t &x,Node_t &y){
for (int i=x.st,j=y.st;i<=x.ed || j<=y.ed;)
if (i<=x.ed && (j>y.ed || sp[i] else sp[++spt]=sp[j++];
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].st=Tr[p].ed=++spt;
sp[spt]=b[l];
}else{
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
Tr[p].st=spt+1;
Union(Tr[p*2],Tr[p*2+1]);
Tr[p].ed=spt;
}
S[Tr[p].ed]=sp[Tr[p].ed];
for (int i=Tr[p].ed-1;i>=Tr[p].st;i–)
S[i]=S[i+1]+sp[i];
}

void Try(int p){
if (y1<=Tr[p].l && Tr[p].r<=y2){
if (Limit>sp[Tr[p].ed]) return;
int l=Tr[p].st,r=Tr[p].ed,mid;
while (l mid=(l+r)/2;
if (sp[mid] else r=mid;
}
Sum+=S[l];
Num+=Tr[p].ed-l+1;
}else{
int mid=(Tr[p].l+Tr[p].r)/2;
if (y1<=mid) Try(p*2);
if (y2>mid) Try(p*2+1);
}
}

bool can(int tmp){
Limit=tmp;
Sum=Num=0;
Try(1);
if (Sum return true;
}

void solve(){
int l,r,mid;
for (int i=0;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
l=1,r=1000;
while (l+1 mid=(l+r)/2;
if (can(mid)) l=mid;
else r=mid-1;
}
if (can(r)) l=r;
if (!can(l)) puts("Poor QLW");
else{
Num-=(Sum-h)/l;
printf("%dn",Num);
}
}
}
}Deal2;

int main(){
freopen("susu.in","r",stdin);
freopen("susu.out","w",stdout);
scanf("%d%d%d",&m,&n,&q);
if (m>1){
Deal1.input();
Deal1.solve();
}
else{
Deal2.input();
Deal2.build(1,1,n);
Deal2.solve();
}
return 0;
}