组队赛第二场：字符串哈希+DP-白红宇

组队赛第二场：字符串哈希+DP

阅读量：6257 次

发布时间：2019-06-22

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

长春现场赛

HDU 4821

思路：这题周赛的时候没做出来，有点可惜了。要是当时记起来unsigned long long自己主动取模，然后提醒一下大帝的话，后续大帝就能过了。

唉，导致让他取了好多个模，最后还是WA了。太不机智了。

范逗了。

这题我是从前面哈希的。看到题解中从后面哈希。就是不爽，所以自己从前面哈希。

事实上都一样啦。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #define INF 100007using namespace std;typedef long long ll;typedef unsigned long long ull;char s[100005];ull base[100010],hash[100010];int main(){ int m,l,i,j;//system("pause"); for(i=1,base[0]=1;i<100001;i++) base[i]=base[i-1]*131ULL; while(~scanf("%d%d",&m,&l)) { map
             
              mm; scanf("%s",s); int sum=0,len=strlen(s); for(i=1,hash[0]=0;i<=len;i++) hash[i]=hash[i-1]*131+s[i-1]-'a'+1; for(i=0;i
              
               <=len;i++) { mm.clear(); for(j=i;j

HDU 4815

这题逗逼了。刚開始大帝告诉我题意可能我理解错了。然后就用二进制枚举了。然后然后……然后就浪费了一个多小时一直WA，后面大帝发觉我理解错了之后。他又敲了背包才过……唉……发现题意真的是有点难理解了。到如今题意和解法还都是半知半懂的。

正确的解法是：总的情况是:1<<n，然后可组合的次数除以总的情况>=p的最小分数是正确答案。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;long long dp[40005];int main(){    int t;    cin>>t;    while(t--)    {        int n,i,j,sum=0,a[45];        double p;        memset(dp,0,sizeof(dp));        dp[0]=1;        cin>>n>>p;        for(i=0;i
          
           =a[i];j--) dp[j]+=dp[j-a[i]]; long long sum1=1LL<
           
            =p) { printf("%d\n",i); break; } } } return 0;}

转载地址：http://sltsa.baihongyu.com/

你可能感兴趣的文章