1.27
闲话
做题纪要
CF1433E Two Round Dances
CF739A Alyona and mex
1.28
闲话
做题纪要
luogu P1993 小 K 的农场
- 详见 【学习笔记】差分约束 。
luogu P3275 [SCOI2011] 糖果
- 详见 【学习笔记】差分约束 。
LibreOJ 10033. 「一本通 2.1 例 1」Oulipo | luogu P3370【模板】字符串哈希
-
\(hash\) 板子。
点击查看代码
const ll mod=998244353,base=13331; ll a[1000002],b[1000002],jc[1000002]; char s1[1000002],s2[1000002]; void sx_hash(char s[],ll a[],ll len) { for(ll i=0;i<=len;i++) { a[i]=(i==0)?0:((a[i-1]*base%mod+s[i])%mod); } } ll ask_hash(ll a[],ll l,ll r) { return (a[r]-a[l-1]*jc[r-l+1]%mod+mod)%mod; } int main() { ll t,len1,len2,ans,i,j; cin>>t; for(i=1;i<=t;i++) { cin>>(s1+1)>>(s2+1); ans=0; len1=strlen(s1+1); len2=strlen(s2+1); for(j=0;j<=max(len1,len2);j++) { jc[j]=(j==0)?1:(jc[j-1]*base%mod); } sx_hash(s1,a,len1); sx_hash(s2,b,len2); for(j=1;j+len1-1<=len2;j++) { ans+=(ask_hash(a,1,len1)==ask_hash(b,j,j+len1-1)); } cout<<ans<<endl; } return 0; }
luogu P3667 [USACO17OPEN] Bovine Genomics G
-
显然，区间长度具有单调性。考虑二分长度，然后把 \(hash\) 值丢到一个
map里面，进行判断。- 容易出错的点：对于一段区间 \([l,r]\) ，只有对于所有的 \(i(1 \le i \le n)\) 均有 \(\sum\limits_{j=1}^{n}[A_{i_{l \sim r}} \ne B_{j_{l \sim r}}]=n\) 才满足题意。
-
需要双哈希。
点击查看代码
const ll mod1=998244353,mod2=1000000007,base=13331; ll a[1002][3][1002],b[1002][3][1002],jc[3][1002]; char s1[1002],s2[1002]; void sx_hash(char s[],ll a[],ll len,ll mod) { for(ll i=0;i<=len;i++) { a[i]=(i==0)?0:((a[i-1]*base%mod+s[i])%mod); } } ll ask_hash(ll a[],ll jc[],ll l,ll r,ll mod) { return (a[r]-a[l-1]*jc[r-l+1]%mod+mod)%mod; } bool check(ll mid,ll n,ll m) { ll i,l,r,flag; for(l=1,r=l+mid-1;r<=m;l++,r++) { map<ll,bool>vis[3]; flag=0; for(i=1;i<=n;i++) { vis[1][ask_hash(a[i][1],jc[1],l,r,mod1)]=true; vis[2][ask_hash(a[i][2],jc[2],l,r,mod2)]=true; } for(i=1;i<=n;i++) { if(vis[1].find(ask_hash(b[i][1],jc[1],l,r,mod1))!=vis[1].end()&&vis[2].find(ask_hash(b[i][2],jc[2],l,r,mod2))!=vis[2].end()) { flag=1; break; } } if(flag==0) { return false; } } return true; } int main() { ll n,m,l=1,r,ans,mid,i; cin>>n>>m; r=m; for(i=0;i<=m;i++) { jc[1][i]=(i==0)?1:(jc[1][i-1]*base%mod1); jc[2][i]=(i==0)?1:(jc[2][i-1]*base%mod2); } for(i=1;i<=n;i++) { cin>>(s1+1); sx_hash(s1,a[i][1],m,mod1); sx_hash(s1,a[i][2],m,mod2); } for(i=1;i<=n;i++) { cin>>(s2+1); sx_hash(s2,b[i][1],m,mod1); sx_hash(s2,b[i][2],m,mod2); } while(l<=r) { mid=(l+r)/2; if(check(mid,n,m)==true) { l=mid+1; } else { ans=mid; r=mid-1; } } cout<<ans<<endl; return 0; }
luogu P4503 [CTSC2014] 企鹅 QQ
-
考虑枚举不同的位置，然后将前后的 \(hash\) 值再次进行 \(hash\) 然后拼起来。
-
因
map常数过大，在找一个数在区间内出现的次数时，使用sort挨个枚举进行判断，而不是使用map存储。 -
这题卡 \(hash\) 的模数，故选择
unsigned long long的自然溢出和rand()的随机数来作为模数。点击查看代码
const ull base=13331; ull a[30002][300],aa[30002],jc[70002]; char s[300],ss[300]; void sx_hash(char s[],ull a[],ull len) { for(ull i=0;i<=len;i++) { a[i]=(i==0)?0:(a[i-1]*base+s[i]); } } ull ask_hash(ull a[],ull l,ull r) { return a[r]-a[l-1]*jc[r-l+1]; } int main() { ull n,m,ss,ans=0,sum,mod1,mod2,i,j; cin>>n>>m>>ss; srand(time(0)); mod1=rand(); mod2=rand(); for(i=0;i<=m;i++) { jc[i]=(i==0)?1:(jc[i-1]*base); } for(i=1;i<=n;i++) { cin>>(s+1); sx_hash(s,a[i],m); } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { aa[j]=ask_hash(a[j],1,i-1)*mod1+ask_hash(a[j],i+1,m)*mod2; } sort(aa+1,aa+1+n); sum=1; for(j=1;j<=n-1;j++) { if(aa[j]==aa[j+1]) { ans+=sum; sum++; } else { sum=1; } } } cout<<ans<<endl; return 0; }
lougu P10114 [LMXOI Round 1] Size
-
前置知识：若 \(\sum\limits_{i=1}^{n}d_i \le V\) ，则 \(\{ d \}\) 中最多只有 \(\sqrt{V}\) 个不同的数。
-
设 \(sum_{x}\) 表示 \(x\) 在 \(\{ d \}\) 中出现的次数， \(\{ a \}\) 为 \(\{ d \}\) 去重后的序列。\(\sum\limits_{i=1}^{|a|}\sum\limits_{j=1}^{|a|}sum_{a_{i}} \times sum_{a_{j}} \times ((a_{i} \bigoplus a_{j})+(a_{i} \bigotimes a_{j}))\) 即为所求。
点击查看代码
ll d[2000001],a[2000001],sum[50000001]; int main() { ll n,m=0,ans=0,i,j; cin>>n; for(i=1;i<=n;i++) { cin>>d[i]; if(sum[d[i]]==0) { m++; a[m]=d[i]; } sum[d[i]]++; } for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { ans+=sum[a[i]]*sum[a[j]]*(__builtin_popcountll(a[i]+a[j])+__builtin_popcountll(abs(a[i]-a[j]))); } } cout<<ans<<endl; return 0; }
1.29
闲话
做题纪要
luogu P4591 [TJOI2018] 碱基序列
-
令 \(f_{i,j}(1 \le i \le k,1 \le j \le |s|)\) 表示使用第 \(i\) 个氨基酸，能匹配到原碱基串的第 \(j\) 个位置的合法方案数。
-
状态转移方程为 \(f_{i,j}=\begin{cases}1 & i=0 \\ \sum\limits_{k=1}^{a_{i}}[s_{j-|ss_{k}|+1 \sim j}=ss_{k_{1 \sim |ss_{k}|}}] \times f_{i-1,j-|ss_{k}|+1-1} & i \ne 0 \end{cases}\) ，为方便代码书写，我们选择枚举左右端点 \(l,r\) 使得 \(l=j-|ss_{k}|+1，r=j\) 。
-
\(\sum\limits_{i=1}^{|s|}f_{k,i}\) 即为所求。
点击查看代码
const ll mod=998244353,base=13331; ll a[20000],b[200][20][20],jc[20000],len[200][20],f[200][20000]; char s1[20000],s2[200][20][20]; void sx_hash(char s[],ll a[],ll len) { for(ll i=0;i<=len;i++) { a[i]=(i==0)?0:((a[i-1]*base%mod+s[i])%mod); } } ll ask_hash(ll a[],ll l,ll r) { return (a[r]-a[l-1]*jc[r-l+1]%mod+mod)%mod; } int main() { ll n,ans=0,maxlen,aa,i,j,l,r,p=1000000007; cin>>n>>(s1+1); maxlen=strlen(s1+1); for(i=0;i<=maxlen;i++) { jc[i]=(i==0)?1:(jc[i-1]*base%mod); } sx_hash(s1,a,maxlen); for(i=0;i<=maxlen;i++) { f[0][i]=1; } for(i=1;i<=n;i++) { cin>>aa; for(j=1;j<=aa;j++) { cin>>(s2[i][j]+1); len[i][j]=strlen(s2[i][j]+1); sx_hash(s2[i][j],b[i][j],len[i][j]); for(l=1,r=l+len[i][j]-1;r<=maxlen;l++,r++) { f[i][r]=(f[i][r]+(ask_hash(a,l,r)==ask_hash(b[i][j],1,len[i][j]))*f[i-1][l-1])%p; } } } for(i=1;i<=maxlen;i++) { ans=(ans+f[n][i])%p; } cout<<ans<<endl; return 0; }
luogu P3167 [CQOI2014] 通配符匹配
-
因通配符个数不超过 \(10\) ，考虑爆搜。
-
记通配符个数为 \(m\) ，时间复杂度目测为 \(O(nm^{2}|s|)\) 。
- 这个时间复杂度比较玄学，要是分析错了@我。
点击查看代码
char s1[200000],s2[200000]; bool dfs(ll sx,ll sy) { if(sx==0) { return (sy==0); } else { if(sy==0) { for(ll i=sx;i>=1;i--) { if(s1[i]!='*') { return false; } } return true; } else { if(s1[sx]=='*') { for(ll i=sy;i>=0;i--) { if(dfs(sx-1,i)==true) { return true; } } return false; } else { return ((s1[sx]=='?'||s1[sx]==s2[sy])?dfs(sx-1,sy-1):false); } } } } int main() { ll n,lens,i; cin>>(s1+1)>>n; lens=strlen(s1+1); for(i=1;i<=n;i++) { cin>>(s2+1); if(dfs(lens,strlen(s2+1))==true) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } return 0; }
LibreOJ 10150. 「一本通 5.1 练习 1」括号配对
-
令 \(f_{l,r}(1 \le l \le r \le |s|)\) 表示为使从 \(l \sim r\) 变为合法的括号序列至少需要添加的字符数。
-
定义 \(check(l,r)=\begin{cases} true &s[l]='[' \ and \ s[r]=']' \\ true &s[l]='(' \ and \ s[r]=')' \\ false & otherwise \end{cases}\) 。
-
状态转移方程为 \(f_{l,r}=\begin{cases}1 & l=r \\ \min \{f_{l,r},f_{l+1,r-1},f_{l+1,r}+1,f_{l,r-1}+1,\min\limits_{i=l}^{r-1} \{ f_{l,i}+f_{i+1,r} \} \} & check(l,r)=true \\ \min \{f_{l,r},f_{l+1,r}+1,f_{l,r-1}+1,\min\limits_{i=l}^{r-1} \{ f_{l,i}+f_{i+1,r} \} \} & check(l,r)=false \end{cases}\) 。
-
注意初始值的设定。
点击查看代码
int f[200][200]; char s[200]; int main() { ll n,len,l,r,i; cin>>(s+1); n=strlen(s+1); for(l=1;l<=n;l++) { f[l][l]=1; for(r=l+1;r<=n;r++) { f[l][r]=0x3f3f3f3f; } } for(len=2;len<=n;len++) { for(l=1,r=l+len-1;r<=n;l++,r++) { if((s[l]=='['&&s[r]==']')||(s[l]=='('&&s[r]==')')) { f[l][r]=min(f[l][r],f[l+1][r-1]); } f[l][r]=min(f[l][r],min(f[l+1][r]+1,f[l][r-1]+1)); for(i=l;i<=r-1;i++) { f[l][r]=min(f[l][r],f[l][i]+f[i+1][r]); } } } cout<<f[1][n]<<endl; return 0; }