牛客网_Wannafly模拟赛1

A.矩阵

题目链接：https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4

题目意思：这个题目是中文就不加解释了，首先这个子矩阵，就说明这个矩阵是实心的，并不是只是一个框，所以为什么我强调这点呢？因为比赛的时候我傻逼了，唉，心痛。

题目思路：二维哈希+二分

　　之前没学过哈希，所以第一次遇到就碰到二维的哈希qwq，首先哈希就是为了把一个字符串通过一个基数（一般是素数）把他压缩成一个值，冲突的概率极小，所以我们可以很方便的通过一个值来比较两个字符串是否相同，这是一维的哈希，如果是二维的哈希呢？没错我们需要两个基数，我们可以把一个字符串压成一个值，那么对于一系列由字符串压成的值再通过一个基数压成一个新的值，这样这个值就代表一个矩阵了。接下来再次附上我的灵魂画作

如上图所示，[0,r]这个区间的字符串所压缩成的哈希值实际上是储存在下标为数组中r+1的格子里面。所以实际上每个下标为n的格子实际上储存了[0,n)这个左闭右开区间内部的哈希值，那么如果我们要的到某个区间的哈希值呢？我们来举一个例子，我们假设一个字符串是1234567，我们设基数为10（十进制方便理解），我们把这个情况画出来

比如现在我们想要得到区间在字符串中区间为[3,5]的哈希值,或者说从3开始长度为(5-3+1)的区间的哈希值（如果是[3,6)就是（6-3）），就是123456-123000=456，也就是说如果是区间

[L,R)我们可以通过hash_get(L,R-L)来获取哈希值，如果是[L,R]，我们可以通过hash_get（L,R-L+1）来获得哈希值，想要得到哈希值我们需要预处理基数的次方表。

那么对于二维哈希表来说其实也一样，也是一样，这里就不做多余的说明。

然后就是二分，记住最大值最小化二分时终点是mid=(L+R+1)/2;否则会死循环。

代码：

 //Author: xiaowuga

 #include <bits/stdc++.h>

 using namespace std;

 #define inf 0x3f3f3f3f

 #define MAX INT_MAX

 #define mem(s,ch) memset(s,ch,sizeof(s))

 const long long N=;

 const long long mod=1e9+;

 typedef long long LL;

 typedef int II;

 typedef unsigned long long ull;

 #define nc cout<<"nc"<<endl

 #define sp " "

 ull p1=,p2=;

 ull x1[N],x2[N];

 vector<string>a;

 II n,m;

 ull Hash[N][N];

 void init(){

     x1[]=;x2[]=;

     for(II i=;i<;i++){

         x1[i]=x1[i-]*p1;

         x2[i]=x2[i-]*p2;

    }

 }

 void hash_init(){

     mem(Hash,);

     for(II i=;i<=n;i++){

         for(II j=;j<=m;j++){

             Hash[i][j]=Hash[i][j-]*p1+a[i-][j-]-'a'+;

         }

     }

     for(II j=;j<=m;j++){

         for(II i=;i<=n;i++){

             Hash[i][j]=Hash[i-][j]*p2+Hash[i][j];

        }

     }

 }

 ull Hash_get(II x,II y,II l){

     ull ans=Hash[x+l][y+l]-Hash[x][y+l]*x2[l];

     ull res=Hash[x+l][y]-Hash[x][y]*x2[l];

     return ans-res*x1[l];

 }

 bool OK(II k){

     if(!k) return false;

     unordered_set<ull>q;

     for(II i=;i+k<=n;i++){

         for(II j=;j+k<=m;j++){

             ull ans=Hash_get(i,j,k);

             if(q.find(ans)!=q.end()) return true;

             else q.insert(ans);

         }

     }

     return false;

 }

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     init();

     while(cin>>n>>m){

         a.resize(n);

         for(II i=;i<n;i++) cin>>a[i];

         hash_init();

         II l=,r=min(n,m)+;

         while(l<r){

             II mid=l+(r-l+)/;

             if(OK(mid)) l=mid;

             else r=mid-;

         }

         if(OK(l)) cout<<l<<endl;

         else cout<<<<endl;

     }

     return ;

 }

B.树

题目链接：https://www.nowcoder.com/acm/contest/submit/86fc8c46a8ce4c1fba763b8cf311f805?ACMContestId=2&tagId=4

题目意思：一颗树，现在有k种颜色，给n个节点染色，要求同样颜色的节点直接是可以互通的,问有多少种染色方法。

题目思路：很简单，如果同样颜色的节点可以互通，这个同样颜色的连通块必定是以这个区间内某个点为根的子树，我们可以发现一颗树每去掉一条边就是会多出一个连通块，那么发现我们去掉n-1条边中选择0条边形成一个连通块，k种颜色里面选择一种，也就是C（n-1,0）*A(k,1),，然后n-1条边里去掉一条边形成两个连通块，k中颜色里面选择两种那么就是

C（n-1,1）*A(k,2)，依次类推，后面的就不多做赘述，我们可以惊奇的发现貌似和树的形态没有任何关系，就是没有关系，真是太坑爹了。

代码：（处理大组合数和阶乘数的姿势就不做赘述了）

 //Author: xiaowuga

 #include <iostream>

 #include <algorithm>

 #include <set>

 #include <vector>

 #include <queue>

 #include <cmath>

 #include <cstring>

 #include <cstdio>

 #include <ctime>

 #include <map>

 #include <bitset>

 #include <stack>

 #include <cctype>

 #define maxx INT_MAX

 #define minn INT_MIN

 #define inf 0x3f3f3f3f

 #define mem(s,ch) memset(s,ch,sizeof(s))

 #define nc cout<<"nc"<<endl

 #define sp " "

 const long long N=;

 const long long mod=1e9+;

 using namespace std;

 typedef long long LL;

 typedef int II;

 II n,k;

 vector<int>pr[N];

 LL p[N][N]={};

 LL A[N];

 void init(){

     for(int i=;i<=;i++) p[i][]=;

     for(int i=;i<=;i++)

         for(int j=;j<=i;j++){

             p[i][j]=(p[i-][j]+p[i-][j-])%mod;

         }

     A[]=;A[]=;

     for(II i=;i<N;i++) A[i]=A[i-]*i%mod;

 }

 int main() {

     ios::sync_with_stdio(false);cin.tie();

     init();

     while(cin>>n>>k){

         for(II i=;i<=n;i++) pr[i].clear();

         for(II i=;i<n-;i++){

             II x,y;cin>>x>>y;

             pr[x].push_back(y);pr[y].push_back(x);

         }

         if(k==){cout<<<<endl;continue;}

         LL ans=;

         LL li=min(n-,k-);

         for(II i=;i<=li;i++){

             LL tmp=p[k][i+]*A[i+]%mod;

             LL t=p[n-][i]*tmp%mod;

             ans=(ans+t)%mod;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

牛客网_Wannafly模拟赛1

A.矩阵

B.树

最新文章

热门文章