A矩陣 時(shí)間限制：1秒?空間限制：131072K

題目描述

給出一個(gè)n * m的矩陣。讓你從中發(fā)現(xiàn)一個(gè)最大的正方形。使得這樣子的正方形在矩陣中出現(xiàn)了至少兩次。輸出最大正方形的邊長。

輸入描述:

第一行兩個(gè)整數(shù)n, m代表矩陣的長和寬； 接下來n行，每行m個(gè)字符（小寫字母），表示矩陣；

輸出描述:

輸出一個(gè)整數(shù)表示滿足條件的最大正方形的邊長。 示例1

輸入

5 10 ljkfghdfas isdfjksiye pgljkijlgp eyisdafdsi lnpglkfkjl

輸出

3

備注:

對于30%的數(shù)據(jù)，n,m≤100； 對于100%的數(shù)據(jù)，n,m≤500；

---

hash好題，推薦去卿學(xué)姐講堂學(xué)hash

每一個(gè)字符串都hash一下和長度有關(guān)的哈希值

#include<cstdio> #include<algorithm> #define N 510 typedef unsigned long long LL; const LL D1=101,D2=193; int n,m,i,j,l,r,mid,ans,t; char a[N][N]; LL pow1[N],pow2[N],h[N][N],tmp,tmp2,has[N*N]; bool check(int x) {for(i=1; i<=n; i++){for(tmp=0,j=1; j<x; j++)tmp=tmp*D1+a[i][j],h[i][j]=0;for(j=x; j<=m; j++){h[i][j]=tmp=tmp*D1-pow1[x]*a[i][j-x]+a[i][j];}}for(t=0,i=x; i<=m; i++){for(tmp=0,j=1; j<x; j++)tmp=tmp*D2+h[j][i];for(j=x; j<=n; j++){has[t++]=tmp=tmp*D2-pow2[x]*h[j-x][i]+h[j][i];}}std::sort(has,has+t);for(i=1; i<t; i++)if(has[i-1]==has[i])return 1;return 0; } int main() {scanf("%d%d",&n,&m);for(i=1; i<=n; i++){scanf("%s",a[i]+1);for(j=1; j<=m; j++)a[i][j]-='a'-1;}l=1,r=n<m?n:m;for(pow1[0]=pow2[0]=i=1; i<=r; i++)pow1[i]=pow1[i-1]*D1,pow2[i]=pow2[i-1]*D2;while(l<=r)if(check(mid=(l+r)>>1))l=(ans=mid)+1;else r=mid-1;return printf("%d",ans),0; } B樹 時(shí)間限制：1秒?空間限制：131072K

題目描述

shy有一顆樹，樹有n個(gè)結(jié)點(diǎn)。有k種不同顏色的染料給樹染色。一個(gè)染色方案是合法的，當(dāng)且僅當(dāng)對于所有相同顏色的點(diǎn)對(x,y)，x到y(tǒng)的路徑上的所有點(diǎn)的顏色都要與x和y相同。請統(tǒng)計(jì)方案數(shù)。

輸入描述:

第一行兩個(gè)整數(shù)n，k代表點(diǎn)數(shù)和顏色數(shù)； 接下來n-1行，每行兩個(gè)整數(shù)x,y表示x與y之間存在一條邊；

輸出描述:

輸出一個(gè)整數(shù)表示方案數(shù)（mod 1e9+7）。 示例1

輸入

4 3 1 2 2 3 2 4

輸出

39

備注:

對于30%的數(shù)據(jù)，n≤10, k≤3； 對于100%的數(shù)據(jù)，n,k≤300。

B這個(gè)是個(gè)假樹啊，只要找到組合數(shù)的貢獻(xiàn)是k*（k-1）*……*（k-i）就好的

#include <stdio.h> const int MD=1e9+7; int dp[301][301]; int main() {int n,k;scanf("%d%d",&n,&k);dp[0][0]=1;for(int i=1; i<n; i++){dp[i][0]=1;for(int j=1; j<=i; j++)dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%MD;}int kk=k,ans=0;for(int i=0;i<=k&&i<=n;i++){ans=(ans+dp[n-1][i]*1LL*kk%MD)%MD;kk=1LL*kk*(k-i-1)%MD;}printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/BobHuang/p/7443575.html

總結(jié)

以上是生活随笔為你收集整理的牛客网Wannafly模拟赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。