TopCoder SRM 677 Div2

感覺T2反而是最難的。。反正代碼是越來越暴力了。。。

這次前兩題的代碼都很沒美感。。

不過T1終于上240了，T2終于上400了（然而是550啊）

T3調了半天結果竟然是數組開小了= =

T1 PalindromePrime

醜陋的暴力

#include <bits/stdc++.h>
using namespace std;

class PalindromePrime {
public:
    int count( int L, int R );
};

int pd(int x){
    if (x==) return ;
    for(int i=;i*i<=x;i++)
     if (x%i==) return ;
    return ;
}

int ppd(int x){
    if (x<) return ;
    if (x<) return x/==x%;
    if (x<) return x/==x%;
    return ;
}

int PalindromePrime::count(int L, int R) {
    int ans=;
    for(int i=L;i<=R;i++)
     if (pd(i)&&ppd(i)) ans++;
    return ans;
}
           

T2 FourStrings

醜陋的暴力

#include <bits/stdc++.h>
using namespace std;
string cc[];
int s[];

class FourStrings {
public:
    int shortestLength( string a, string b, string c, string d );
};

int pd(int i,int x,int y){
    int p1=i,p2=;
    while(p1<s[x]&&p2<s[y]){
        if (cc[x][p1]!=cc[y][p2]) return ;
        p1++;p2++;
    }
    return ;
}

int pj(int x,int y){
    for(int i=;i<s[x];i++)
     if (pd(i,x,y)) return max(,s[y]-(s[x]-i));
    return s[y];
}

int www(int i,int j,int k,int l){
    int w=i,sum=s[i];
    int v=pj(w,j);
    if (v) w=j;
    sum+=v;

    v=pj(w,k);
    if (v) w=k;
    sum+=v;

    v=pj(w,l);
    sum+=v;

    return sum;
}

int FourStrings::shortestLength(string a, string b, string c, string d) {
    cc[]=a;cc[]=b;cc[]=c;cc[]=d;
    for(int i=;i<;i++) s[i]=cc[i].size();
    int ans=s[]+s[]+s[]+s[];
    for(int i=;i<;i++)
     for(int j=;j<;j++)
      if (j!=i)
       for(int k=;k<;k++)
        if (k!=i&&k!=j){
            int l=-i-j-k;
            ans=min(ans,www(i,j,k,l));
        }
    return ans;
}
           

T3 PalindromePath

f[i][j] f [ i ] [ j ] 表示 0 0 到ii的路徑與 1 1 到jj的路徑相同時的最短路，然後跑下SPFA就行，不過好像這題bfs也一樣。

#include <bits/stdc++.h>
using namespace std;
const int N=;
const int M=;
const int INF=;
int f[N][N],cnt,head[N],Next[M],v[M],w[M],b[N][N];
struct data{
    int x,y;
};
queue<data> h;

class PalindromePath {
public:
    int shortestLength( int n, vector <int> a, vector <int> b, string c );
};

void add(int x,int y,char z){
    Next[++cnt]=head[x];
    head[x]=cnt;
    v[cnt]=y;
    w[cnt]=z;
}

void spfa(){
    while(!h.empty()) h.pop();
    h.push((data){,});
    b[][]=;
    while(!h.empty()){
        data q=h.front();
        h.pop();
        int x=q.x,y=q.y;
        b[x][y]=;
        for(int i=head[x];i!=-;i=Next[i])
         for(int j=head[y];j!=-;j=Next[j])
          if (w[i]==w[j]&&f[x][y]+<f[v[i]][v[j]]){
            f[v[i]][v[j]]=f[x][y]+;
            if (!b[v[i]][v[j]]){
                b[v[i]][v[j]]=;
                h.push((data){v[i],v[j]});
            }
          }
    }
}

int PalindromePath::shortestLength(int n, vector <int> a, vector <int> b, string c) {
    memset(f,,sizeof f);
    memset(head,-,sizeof head);
    f[][]=;cnt=;
    for(int i=;i<a.size();i++){
        add(a[i],b[i],c[i]);
        add(b[i],a[i],c[i]);
    }
    spfa();
    int ans=INF;
    for(int i=;i<n;i++) ans=min(ans,f[i][i]);
    cout<<ans<<endl;
    for(int i=;i<n;i++)
     for(int j=head[i];j!=-;j=Next[j])
      ans=min(ans,f[i][v[j]]+),cout<<f[i][v[j]]<<' ';
    if (ans>) ans=-;
    return ans;
}