总体来说难度适中的一场SRM~
300:BearCries
题意：
给定一个长度为N(N<=200)的字符串 字符串中只含有”;”和”_“两种字符 一个合法的Cry表情为两个”;”中间含有至少一个”_“
一个合法Cry表情为字符串的一个子串(不必在原串中连续)
求题目中给出的字符串分解成若干个合法Cry表情的方案数(原字符串中的每个字符都必须出现在某个Cry表情中 并且只能出现一次)
题解：
问题可以由dp解决
我们考虑状态f[i][j][k]表示当前考虑到第I个字符 前面有J个”;”还未匹配”_“ 有K个”;”已经匹配至少一个”_“
考虑第i+1个字符
若第i+1个字符为; 我们可以分两种情况讨论
1.他和前面的某个已经至少匹配了一个”_“的”;”组合成一个合法的Cry表情
2.他不和前面的”;”匹配 他成为一个新的还未匹配”_“的”;”
若第i+1个字符为_ 我们也可以分两种情况讨论
1.他和前面某个还未匹配”_“的”;”组合成为一个已经匹配至少一个”_“的”;”
2.他和前面某个已经至少匹配一个”_“的”;”组合 仍然为一个至少匹配一个”_“的”;”
到这里问题已经得到解决 答案即为f[n][0][0]
代码：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
class BearCries
{
public:
int count(string s)
{
int n=s.size();
LL f[205][205][205];
int a[205];
LL mod=1e9+7;
int ans;
for (int i=0;i<n;++i) if (s[i]==';') a[i+1]=1;else a[i+1]=0;
memset(f,0,sizeof(f));
f[0][0][0]=1;
for (int i=1;i<=n;++i)
for (int j=0;j<=n;++j)
for (int k=0;k<=n;++k)
{
// f[j][k] j not has k has
if (a[i]==1)
{
f[i][j+1][k]+=f[i-1][j][k],f[i][j+1][k]%=mod;
if (k>=1) f[i][j][k-1]+=k*f[i-1][j][k]%mod,f[i][j][k-1]%=mod;
}
else
{
f[i][j][k]+=k*f[i-1][j][k]%mod,f[i][j][k]%=mod;
if (j>=1) f[i][j-1][k+1]+=j*f[i-1][j][k]%mod,f[i][j-1][k+1]%=mod;
}
}
cout<<f[1][1][0]<<endl;
ans=f[n][0][0];
return ans;
}
};
500: BearDarts
题意：
给定一个含有N(N<=1000)个元素的数组w 求有多少四元组(i,j,p,q)满足
- i<j<p<q
- $w[i] \times w[p]$=$w[j] \times w[q]$
题解
为了方便我们令$a=w[i]$ $b=w[j]$ $c=w[p]$ $d=w[q]$
我们先来枚举a和b 那么问题就变成了有多少对(c,d)满足条件
$a \times c$=$b \times d$
于是 $a / b$=$d / c$
于是我们可以枚举a,b,查找后面有多少个数对满足条件啦！
具体实现和我的上一篇日志CF 325 的D题很像,用个map就好啦
代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
class BearDarts
{
public:
long long count(vector <int> w)
{
int n,a,b,c,d,z;
map<pair<int,int>,LL> mp;
LL ans=0;
n=w.size();
c=w[n-2];d=w[n-1];
z=__gcd(c,d);
mp[make_pair(c/z,d/z)]++;
for (int i=n-3;i>=1;--i)
{
b=w[i];
for (int j=i-1;j>=0;--j)
{
a=w[j];
//ac=bd
//a/b=d/c
z=__gcd(a,b);
ans+=mp[make_pair(b/z,a/z)];
}
c=w[i];
for (int j=i+1;j<n;++j)
{
d=w[j];
z=__gcd(c,d);
mp[make_pair(c/z,d/z)]++;
}
}
return ans;
}
};
900: BearDestroys
题意:
给一个n$\times$m的方格图(n<=13,m<=30),每个格子可以写E或者S,所以一共有2^(n$\times$m)种图
一个人从(0,0)开始行优先行动 即从(0,0)->(0,m-1)->(1,0)->(1,m-1)->….->(n-1,0)->(n-1,m-1)
每次他到一个格子(i,j) 他执行以下操作：
1.如果该格子已经放置了骨牌 那么不做任何操作去下一格子
2.若该格子没有放置骨牌 该格子写的是E 那么如果他能放置一块1$\times$2的骨牌覆盖(i,j) (i,j+1) 则用1$\times$2的骨牌覆盖(i,j)(i,j+1) 否则如果他能放置一块2$\times$1的骨牌覆盖(i,j) (i+1,j) 则用2$\times$1的骨牌覆盖(i,j) (i+1,j)
3.若该格子没有放置骨牌 该格子写的是S 那么如果他能放置一块2$\times$1的骨牌覆盖(i,j) (i+1,j) 则用2$\times$1的骨牌覆盖(i,j)(i+1,j) 否则如果他能放置一块1$\times$2的骨牌覆盖(i,j) (i,j+1) 则用1$\times$2的骨牌覆盖(i,j) (i,j+1)
直到他到达(n-1,m-1)
一个图的得分为放置的骨牌数量
求这2^(n$\times$m)种图的得分的和对MOD取余
题解：
看到n<=13不难想到要状态压缩,然后我们来分析下放置骨牌的情况
我们考虑一下骨牌占得两个格子的位置 可以发现无论是1$\times$2的骨牌还是2$\times$1的骨牌 两个格子的坐标之和的差总是1
所以我们考虑将方格图分层
比如一个3$\times$4的方格图 可以分为6层(0~5)
0123
1234
2345
于是每层有最多N个元素 我们来对这N个元素进行状态压缩
对于一个状态now 若now的二进制表示第I位为1 则表示该格子已经被骨牌覆盖了 如果为0则为没覆盖
那么考虑dp:
f[i][j]表示到了第I层 第I层的状态为J时候的骨牌数量的总和
g[i][j]表示到了第I层 第I层的状态为J时候这种图的数量
考虑转移的时候比较麻烦 这里考虑从now状态可以转移到哪些next状态
对now状态每一行进行讨论
若now状态第r行为1 此时证明改格子已经被覆盖 那么他填E或S都无所谓 直接转移
接下来就是该格子未被覆盖的情况了
如果现在改格子右方已被覆盖(即next状态第r行为1)
此时无论该格子填E还是填S 他都是被2$\times$1的骨牌覆盖 将next状态第r+1行标志为1进行转移
如果现在该格子右方未被覆盖
此时如果该格子填E那么将next状态第R行标志为1进行转移
此时如果该格子填S那么将next状态第R+1行标志位1进行转移
这样进行转移更新后答案即为f[n+m-1][0]
具体的转移以及边界看代码有一些帮助
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
class BearDestroys
{
public:
int w,h,mod;
int f[50][10000];
int g[50][10000];
void dfs(int r,int sum,int now,int next,int ff,int gg)
{
if (r==h)
{
f[sum+1][next]=(f[sum+1][next]+ff)%mod;
g[sum+1][next]=(g[sum+1][next]+gg)%mod;
return;
}
int c=sum-r;
if (0<=c&&c<=w-1)
{
if (now&(1<<r))
{
dfs(r+1,sum,now,next,ff*2%mod,gg*2%mod);
}
else
{
if ((c==w-1)||(next&(1<<r)))
{
if (r==h-1)
{
dfs(r+1,sum,now,next,ff*2%mod,gg*2%mod);
}
else
{
dfs(r+1,sum,now,next+(1<<(r+1)),(ff*2%mod+gg*2%mod)%mod,gg*2%mod);
}
}
else
{
if (r==h-1)
{
dfs(r+1,sum,now,next+(1<<r),(ff*2%mod+gg*2%mod)%mod,gg*2%mod);
}
else
{
dfs(r+1,sum,now,next+(1<<r),(ff+gg)%mod,gg);
dfs(r+1,sum,now,next+(1<<(r+1)),(ff+gg)%mod,gg);
}
}
}
}
else
{
dfs(r+1,sum,now,next,ff,gg);
}
}
int sumUp(int W, int H, int MOD)
{
w=W;h=H;mod=MOD;
int s=w-1+h-1;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
f[0][0]=0;g[0][0]=1;
for (int i=0;i<=s;++i)
{
for (int j=0;j<(1<<h);++j)
{
if (f[i][j]==0&&g[i][j]==0) continue;
dfs(0,i,j,0,f[i][j],g[i][j]);
}
}
return f[s+1][0];
}
};