NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » david942j 的個人資料 » 顯示文章
 主題

顯示文章

這裡允許您檢視這個會員的所有文章。請注意, 您只能看見您有權限閱讀的文章。

主題 - david942j

頁: [1]
1
假解O(n^2)
代碼: [選擇]
#include <iostream>
char s[50001];
int main()
{
    int T,i,m,ans,j;
    scanf("%d",&T);
    while(T--)
    {
scanf("%s",s);
ans=1;
for(i=1,m=strlen(s);i<m;i++)
{
for(j=1;i-j>=0&&i+j<m;j++)
if(s[i-j]!=s[i+j])break;
j--;
ans>?=2*j+1;
}
for(i=1;i<m;i++)
{
for(j=1;i-j>=0&&i+j-1<m;j++)
if(s[i-j]!=s[i+j-1])break;
j--;
ans>?=2*j;
}
printf("%d\n",ans);
    }
    return 0;
}


2
NPSC2009高中組決賽 / NPSC 2009 高中組決賽 E. 大風吹
« 於: 八月 24, 2010, 03:53:06 pm »
提供一個感覺比海岸線簡單多的code
程式不一定對,所以像討論版中所說測資心機一點會爆炸
不知道當時寫出來那隊是不是用類似的方法?

把整張圖切成N*N等份 (N自訂)
輸入點時就做表看每個點分別屬於哪一等份(底下是用list實現)
搜尋時只需要搜此點所在的那格以及周圍的8格 (當然保險一點就搜多一點附近的格子,相對也較慢)
底下是切成201*201份
搜尋時只搜9格,搭配優化輸入
代碼: [選擇]
#include <iostream>
const int N=201;
typedef struct {int x,y;}M;
M t[50000];
typedef struct list{int p;struct list *next;}list;
list map[N][N],v[50000];
int vtop,min,k,p;
int in()
{
int p,x;
while(p=getchar())
if(p!=' '&&p!='\n')break;
x=p-48;
while(p=getchar())
if(p==' '||p=='\n')return x;
else x=x*10+p-48;
}
void add(int k)
{
list *tmp=&v[vtop++];
tmp->p=k,tmp->next=map[t[k].x/N][t[k].y/N].next,map[t[k].x/N][t[k].y/N].next=tmp;
}
int dis(M a,M b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int d[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
void F(M a,int x,int y)
{
list *tmp=map[x][y].next;
int d;
while(tmp!=NULL)
{
if(tmp->p==k){tmp=tmp->next;continue;}
d=dis(a,t[tmp->p]);
if(d<min||(d==min&&tmp->p<p))min=d,p=tmp->p;
tmp=tmp->next;
}
}
void find(M a)
{
min=INT_MAX;
int x=a.x/N,y=a.y/N,i;
for(i=0;i<9;i++)
F(a,x+d[i][0],y+d[i][1]);
printf("%d\n",p+1);
}
int main()
{
int T,n,i,j;
T=in();
while(T--)
{
for(i=0;i<N;i++)
for(j=0;j<N;j++)
map[i][j].next=NULL;
n=in(),vtop=0;
for(i=0;i<n;i++)
t[i].x=in(),t[i].y=in(),add(i);
for(k=0;k<n;k++)
find(t[k]);
}
}

頁: [1]