第二周 9.6-9.12-白红宇

第二周 9.6-9.12

阅读量：5365 次

发布时间：2019-06-15

本文共 4657 字，大约阅读时间需要 15 分钟。

9.6

FZU 1901

并不需要完整的周期。即最后一段可以不完整。

所以直接沿Next往后找就可以了。

行末不能有空格不然PE。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 int m,Next[1000100]; 7 char b[1000100]; 8  9 void getNext(void)10 {        11     Next[0]=Next[1]=0;12     for(int i=1;i
          
           >T;24     for(int kase=1;kase<=T;kase++)25     {26         scanf("%s",b);27         m=strlen(b);28         getNext();29         vector
           
             ans;30 int pos=m;31 while(pos)32 {33 pos=Next[pos];34 ans.push_back(pos);35 }36 printf("Case #%d: %d\n",kase,ans.size());37 for(int i=0;i

Aguin

HDU 5428

应该不是第一次用这种方法。但是当时想不起来。

有一种拿到素数就想快筛的感觉。

感觉这种n^0.5的分解方法应该很常用。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 typedef long long LL; 6 int cnt; 7  8 struct node 9 {10     int f,num;11 } fac[2000];12 13 bool cmp(node x,node y)14 {15     return x.f
         
          >T;21     while(T--)22     {23         int n; scanf("%d",&n);24         cnt=0;25         for(int i=0;i
          
           1)36             {37                 fac[cnt].f=x;38                 fac[cnt].num=1;39                 cnt++;40             }41         }42         sort(fac,fac+cnt,cmp);43         LL ans=1,tem=0;44         for(int i=0;i

Aguin

9.7-9.8

什么都没干。

9.9

POJ 3613

做出manacher的p数组。扫一遍。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 using namespace std; 6 const int maxn=500000+5; 7 int p[maxn*2],sum[maxn*2],alp[26]; 8 char o[maxn],s[maxn*2]; 9 10 int main(void)11 {12     int T ;cin>>T;13     while(T--)14     {15         for(int i=0;i<26;i++) scanf("%d",alp+i);16         scanf("%s",o+1);17         int len=2*strlen(o+1)+1;18         s[0]='$';19         for(int i=1;i<=len;i++)20         {21             if(i%2) s[i]='#';22             else s[i]=o[i/2];23         }24         s[len+1]='^';25         int mx=0,id; 26         for(int i=1;i<=len;i++)27         {28             if(mx>i) p[i]=min(p[2*id-i],mx-i);29             else p[i]=1;30             while(s[i+p[i]]==s[i-p[i]]) p[i]++;31             if(p[i]+i>mx) { mx=p[i]+i; id=i; }32         }33         for(int i=1;i<=len;i++)34         {35             if(s[i]=='#') sum[i]=sum[i-1];36             else sum[i]=sum[i-1]+alp[s[i]-'a'];37         }38         int ans=-2147483647;39         for(int i=3;i

Aguin

9.10-9.11

什么都没干。

9.12

打了个BC。

HDU 5432

简单二分。精度注意下QAQ。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 using namespace std; 5 int n,h[10001],b[10001]; 6 double V[10001],tot; 7  8 bool judge(double mid) 9 {10     double sum=0;11     for(int i=0;i
         
          tot/2) return false;17     return true;18 }19 20 int main(void)21 {22     int T; cin>>T;23     while(T--)24     {25         scanf("%d",&n);26         for(int i=0;i

Aguin

HDU 5433

BFS。仅当有更优值时更新且入队。

状态开二维就够了。因为k是单调递减的。

如果某个点会被k更小时的更优解覆盖。那么在覆盖之前他的后继肯定已经用原值更新过一遍了。

如果后继也有更优也会自动覆盖。（（描述不清楚。意会一下。

注意意志为0时走到也算失败QAQ。

1 # include 
      
        2 # include 
       
         3 # include 
        
          4 # include 
         
           5 # include 
          
            6 using namespace std; 7 typedef pair
           
             pii; 8 int n,m,k,h[51][51],kk[51][51]; 9 int d[][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1}};10 bool vis[51][51];11 double e[51][51];12 queue
            
              q;13 14 bool in(int i,int j)15 {16 return i>0&&i<=n&&j>0&&j<=m;17 }18 19 int main(void)20 {21 int T; cin>>T;22 while(T--)23 {24 scanf("%d%d%d",&n,&m,&k);25 for(int i=1;i<=n;i++)26 {27 char s[100]; scanf("%s",s);28 for(int j=1;j<=m;j++)29 {30 if(s[j-1]=='#') h[i][j]=-1;31 else h[i][j]=s[j-1]-'0';32 e[i][j]=-100;33 }34 }35 int x1,y1,x2,y2;36 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);37 memset(kk,-1,sizeof(kk));38 memset(vis,0,sizeof(vis));39 kk[x1][y1]=k; e[x1][y1]=0;40 while(!q.empty()) q.pop();41 q.push(pii(x1,y1));42 while(!q.empty())43 {44 pii now=q.front(); q.pop();45 int x=now.first,y=now.second;46 vis[x][y]=0;47 for(int i=0;i<4;i++)48 {49 int xx=x+d[i][0],yy=y+d[i][1];50 if(!in(xx,yy)||h[xx][yy]<0) continue;51 double tem=e[x][y]+1.0*abs(h[x][y]-h[xx][yy])/kk[x][y];52 if(e[xx][yy]<-1||e[xx][yy]>tem)53 {54 e[xx][yy]=tem;55 kk[xx][yy]=kk[x][y]-1; 56 if(kk[xx][yy]&&!vis[xx][yy])57 {58 vis[xx][yy]=1;59 q.push(pii(xx,yy));60 }61 }62 }63 }64 if(kk[x2][y2]>0) printf("%.2lf\n",e[x2][y2]);65 else puts("No Answer");66 }67 return 0;68 }