Codeforces 748D Santa Claus and a Palindrome

雅礼集训期间我好像考完试就开始划水了啊

给出k个长度相同的字符串,每个串有一个权值,选出一些串连成一个回文串.使得选中的串的总权值最大.

如果选一个串,必须同时选一个对称的串.还有一个特殊情况是可以在最中间放一个回文的串,求一下这种情况带来的额外的收入即可.

卡自然溢出hash....需要树同构那种奇奇怪怪的hash...

#include <cstdio>

#include <string>

#include <iostream>

#include <algorithm>

#include <vector>

#include <map>

using namespace std;

typedef unsigned long long ul;

const int maxn=100005;

int k,n;

string str[maxn];

ul Ha1[maxn],Ha2[maxn];

int w[maxn];

ul gethash1(string &A){

  ul res=233;

  for(int i=0;i<n;++i)res=(res*173323+A[i]+987)<<2^(res>>5);

  return res;

}

ul gethash2(string &A){

  ul res=233;

  for(int i=n-1;i>=0;--i)res=(res*173323+A[i]+987)<<2^(res>>5);

  return res;

}

ul Ha[maxn][2];

vector<int> a[maxn];

map<ul,int> dict;int tot=0;

map<ul,int> dict2;

long long work1(){

  long long ans=0;

  for(int i=1;i<=tot;++i){

    if(Ha[i][0]==Ha[i][1]){

      int SZ=a[i].size();

      for(int j=SZ-1;j>=1&&a[i][j]+a[i][j-1]>0;j-=2){

	ans+=a[i][j]+a[i][j-1];

      }

    }else if(Ha[i][0]<Ha[i][1]){

      int t=dict[Ha[i][1]];

      int SZ1=a[i].size(),SZ2=a[t].size();

      for(int j=0;j<SZ1&&j<SZ2&&a[i][SZ1-j-1]+a[t][SZ2-j-1]>0;++j){

	ans=ans+a[i][SZ1-j-1]+a[t][SZ2-j-1];

      }

    }

  }

  return ans;

}

long long work2(){

  long long ans=0;

  long long maxdelta=0;

  for(int i=1;i<=tot;++i){

    if(Ha[i][0]==Ha[i][1]){

      int SZ=a[i].size();

      if(SZ==1&&a[i][0]>maxdelta)maxdelta=a[i][0];

      if(SZ>=2&&a[i][SZ-1]>maxdelta&&a[i][SZ-1]+a[i][SZ-2]<=0)maxdelta=a[i][SZ-1];

      for(int j=SZ-1;j>=1&&a[i][j]+a[i][j-1]>0;j-=2){

	ans+=a[i][j]+a[i][j-1];

	if(a[i][j-1]<0&&-a[i][j-1]>maxdelta){

	  maxdelta=-a[i][j-1];

	}

	if(j>=3&&a[i][j-2]>maxdelta&&a[i][j-2]+a[i][j-3]<=0)maxdelta=a[i][j-2];

	if(j==2&&a[i][0]>maxdelta)maxdelta=a[i][0];

      }

    }else if(Ha[i][0]<Ha[i][1]){

      int t=dict[Ha[i][1]];

      int SZ1=a[i].size(),SZ2=a[t].size();

      for(int j=0;j<SZ1&&j<SZ2&&a[i][SZ1-j-1]+a[t][SZ2-j-1]>0;++j){

	ans=ans+a[i][SZ1-j-1]+a[t][SZ2-j-1];

      }

    }

  }

  return ans+maxdelta;

}

int main(){

  cin>>k>>n;

  for(int i=1;i<=k;++i)cin>>str[i]>>w[i];

  int t;

  for(int i=1;i<=k;++i){

    Ha1[i]=gethash1(str[i]);

    Ha2[i]=gethash2(str[i]);

    if(Ha1[i]==Ha2[i]){

      if(dict2[Ha1[i]]){

	t=dict2[Ha1[i]];

      }else{

	dict2[Ha1[i]]=t=++tot;

	Ha[tot][0]=Ha[tot][1]=Ha1[i];

      }

      a[t].push_back(w[i]);

    }else{

      if(dict[Ha1[i]]){

	t=dict[Ha1[i]];

      }else{

	dict[Ha1[i]]=t=++tot;

	Ha[tot][0]=Ha1[i];Ha[tot][1]=Ha2[i];

      }

      a[t].push_back(w[i]);

    }

  }

  long long ans=0;

  for(int i=1;i<=tot;++i)sort(a[i].begin(),a[i].end());

  printf("%lld\n",max(work1(),work2()));

  return 0;

}

巴特西

Codeforces 748D Santa Claus and a Palindrome

最新文章

热门文章