2014
02-09

# Engine

“包含”必须是标题中有一个词正好是给定的关键词，不区分大小写。

6
Finding the Shortest Path
120
Finding the k Shortest Path
80
Find Augmenting Path in General Graph
80
Matching in Bipartite Graph
200
Finding kth Shortest Path
50
Graph Theory and its Applications
40
6
shortest path
k shortest path
graph
path
find
application
0

Finding the Shortest Path
Finding the k Shortest Path
Finding kth Shortest Path
***
Finding the k Shortest Path
***
Matching in Bipartite Graph
Find Augmenting Path in General Graph
Graph Theory and its Applications
***
Finding the Shortest Path
Finding the k Shortest Path
Find Augmenting Path in General Graph
Finding kth Shortest Path
***
Find Augmenting Path in General Graph
***
***
---

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct record
{
int num;
int count;
int keyL;
char name[300];
char afname[300];
char key[11][21];
}Record;
Record rec[1001];
Record qy;
int divide(char a[],char b[11][21],int n)
{
int cur=0,j=0;
for(int i=0;i<n;i++)
{
if(a[i]==' ')
{cur++;j=0;}
else
b[cur][j++]=a[i];
}
return cur+1;
}
int cmp(const void *a,const void *b)
{
Record c = *(Record *)a;
Record d = *(Record *)b;
if(c.count==d.count)
return c.num - d.num;
else return d.count - c.count;//优先按coun排序，大的在前
}

int match(char qry[11][21],char tar[11][21],int qn,int tn)
{
int num=0;
for(int x=0;x<qn;x++)
{
for(int y=0;y<tn;y++)
if(strcmp(qry[x],tar[y])==0)
{
num++;
break;
}
}
if(num==qn)
return 1;
else
return 0;
}

void init(char a[],int n,char b[])
{
for(int ii=0;ii<n;ii++)
{
if(a[ii]<='Z'&&a[ii]>='A')
{
b[ii]=char(a[ii]+32);
}
else
b[ii]=a[ii];
}

}
int main()
{
int T,i;
while(scanf("%d",&T))
{
if(T==0)break;
memset(rec,0,sizeof(Record)*T);
getchar();
for(i=0;i<T;i++)
{
gets(rec[i].name);
init(rec[i].name,strlen(rec[i].name),rec[i].afname);
scanf("%d",&rec[i].count);
getchar();
rec[i].keyL=divide(rec[i].afname,rec[i].key,strlen(rec[i].name));
rec[i].num=i+1;
}
qsort(rec,T,sizeof(Record),cmp);
int k;
scanf("%d",&k);getchar();
for(i=0;i<k;i++)
{
memset(&qy,0,sizeof(Record));
gets(qy.name);
init(qy.name,strlen(qy.name),qy.afname);
qy.keyL=divide(qy.afname,qy.key,strlen(qy.name));
for(int j=0;j<T;j++)
{
if(match(qy.key,rec[j].key,qy.keyL,rec[j].keyL))
{
puts(rec[j].name);
}
}
printf("***\n");
}
printf("---\n");
}
return 0;
}

—一个事情，自己找不到原因，非常可怕。

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}