topcoder srm 698 div1 -3-白红宇

topcoder srm 698 div1 -3

阅读量：7052 次

发布时间：2019-06-28

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

1、定义重复串$S=T+T$，即$S$可以表示成一个串的叠加。给定一个串$s$，可以通过删除字符、修改字符、增加字符来使得其变为重复串。问最少的次数。

思路：首先将$s$分成个串$s_{0},s_{1}$，然后计算将$s_{0},s_{1}$变成一样要多少次操作。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;int f[111][111];void up(int &x,int y){ if(x==-1||x>y) x=y;}int cal(string s1,string s2){ const int n=(int)s1.size(); const int m=(int)s2.size(); if(n==0) return m; if(m==0) return n; memset(f,-1,sizeof(f)); f[0][0]=0; for(int i=1;i<=m;++i) f[0][i]=i; for(int i=1;i<=n;++i) f[i][0]=i; for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { char c1=s1[i-1]; char c2=s2[j-1]; up(f[i][j],f[i-1][j]+1); up(f[i][j],f[i][j-1]+1); up(f[i][j],f[i-1][j-1]+(c1!=c2)); } } return f[n][m];}class RepeatString{public: int minimalModify(string s) { const int n=(int)s.size(); int ans=n; for(int i=0;i<=n;++i) { ans=min(ans,cal(s.substr(0,i),s.substr(i))); } return ans; }};

2、给出平面上$n$个点的集合$S$，没有三点共线。定义$CH(s)$为包含点集$s$的最小凸包。求这样的点集对$(s_{1},s_{2})$有多少：（1）$s_{1}\in S,s_{2} \in S$;（2）$s_{1},s_{2}$没有交集；（3）$CH(s_{1}),CH(s_{2})$相交。

思路：求出所有的点集对然后减去不相交的。不相交的可以通过枚举两个点$p_{0},p_{1}$来确定一条直线，然后从直线一侧选出一些点跟$p_{0}$组成一个点集，从直线另一侧选出一些点跟$p_{1}$组成一个点集。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=111;const int mod=1000000007;int C[N][N],p[N];void init(){ C[0][0]=1; for(int i=1;i
                
                 =mod) C[i][j]-=mod; } } p[0]=1; for(int i=1;i
                 
                  =mod) p[i]-=mod; }}class IntersectingConvexHull{public: int count(vector 
                  
                    x, vector 
                   
                     y) { init(); const int n=(int)x.size(); int ans=0; for(int i=3;i<=n;++i) for(int j=3;j<=n-i;++j) { ans+=(long long)C[n][i]*C[n-i][j]%mod; if(ans>=mod) ans-=mod; } for(int i=0;i
                    
                     0) ++s[0]; else ++s[1]; } if(s[0]<2||s[1]<2) continue; int t0=p[s[0]]-1-s[0]; int t1=p[s[1]]-1-s[1]; ans-=(long long)t0*t1%mod; if(ans<0) ans+=mod; } return ans; }};int main(){ IntersectingConvexHull p; printf("%d\n",p.count({-2,-1,-1,1,1,2},{1,0,2,0,2,1}));}

转载于:https://www.cnblogs.com/jianglangcaijin/p/6866207.html

你可能感兴趣的文章

在VS2015中用C++创建DLL并用C#调用且同时实现对DLL的调试