字符串哈希板题求调
查看原帖
字符串哈希板题求调
177000
vicky2048_2楼主2023/7/5 21:10

调麻了,找不出哪里打挂了QAQ……

求调谢谢wwwwwwww

#include<bits/stdc++.h>
#define N 206
using namespace std;
unordered_map<string,int>has;
struct P{
    int flee,x,y;
    bool cw;
}p[N];
struct E{
    int len;
    bool left;
    string ex;
}e[N];
void str(int),pre();
int n,ans,get(int);
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);
    p[0]=p[n],p[n+1]=p[1];
    for(int i=1;i<=n;++i){
        e[i].len=abs(p[i].x-p[i+1].x)+abs(p[i].y-p[i+1].y);
        if(p[i].x!=p[i+1].x)
            e[i].left=((p[i].x>p[i+1].x&&p[i-1].y<p[i].y)||(p[i].x<p[i+1].x&&p[i-1].y>p[i].y))?1:0;
        else
            e[i].left=((p[i].y>p[i+1].y&&p[i].x>p[i-1].x)||(p[i].y<p[i+1].y&&p[i].x<p[i-1].x))?0:1;
        str(i);
    } e[n+1]=e[1],e[0]=e[n];
    pre();
    for(int i=2;i<=n;i++){
        if(p[i].cw) continue;
        ans=max(ans,get(i)-p[i].flee);
    }
    printf("%d",ans);
    return 0;
}
void str(int i){
    int len=e[i].len;
    while(len)
        e[i].ex+=(char)(len%10+'0'),
        len/=10;
    e[i].ex+=e[i].left?"L ":"R ";
}
void pre(){
    string no;
    for(int i=1;i<=n;++i){
        no.clear();
        for(int j=i;j<=n;++j)
            no+=e[i].ex,
            ++has[no];
    }
    int len=0;
    for(int i=2;i<=n;i++)
        len+=e[i-1].len,
        p[i].flee=len;
    len=0;
    for(int i=n;i>1;--i)
        len+=e[i].len,
        p[i].cw=p[i].flee>len?1:0,p[i].flee=min(p[i].flee,len);
}
int get(int no){
    string pa; pa.clear();
    int len=0;
    while(has[pa]!=1&&no!=1)
        len+=e[no].len,pa+=e[no].ex,
        no=no+1>n?1:no+1;
    return len+p[no].flee*(no==1?0:1);
}
2023/7/5 21:10
加载中...