杭电|2021.杭电中超 第三场
- Forgiving Matching FFT/NTT、 字符串匹配问题
思路:通过这道题算是长见识了。FFT/NTT 是可以用来求解字符串匹配问题的，尤其是在处理含有通配符或者不完全匹配的问题上，FFT/NTT 和KMP 相比更有优势。
首先我们先不考虑通配符的问题。 F(x) 表示 S 中以 下标 x 结尾 的 子字符串和 T 匹配的字符个数，当S i = T j S_i=T_j Si?=Tj? 则 F ( i ? j + m ? 1 ) F(i-j+m-1) F(i?j+m?1)++（模拟一下容易看出）。显然直接暴力枚举是不行的。我们仔细想想要求的是什么，假设我们确定以某个子字符串结尾下标为 x, F(x)实际通过的i,j, 满足 i-j+m-1=x,来求的 x。这不就是求卷积嘛。把 i,j 搞成次幂，最终系数就是我们要求的F(x)。当然对于 -j 的处理我们可以通过加个偏移量，除此之外，我们可以考虑把字符串 T 翻转，这样 j 就变成了 m-1-j。i-j+m-1 就变成了 i+j。接下来就是具体怎么求出 F 的点值表示法进而求出系数表示法。因为字符种类不多，我们可以去枚举字符，当等于当前枚举的字符时设置为系数设置为1，否则设置为0，只有全都为1，即字符相等时才有贡献。然后就是考虑通配符的问题。总的匹配的字符的个数=不考虑通配符匹配的个数+S中通配符的个数+T中通配符的个数-S和T通配符匹配的个数。就是个简单容斥。
代码如下：
#include
using namespace std;
const int N=200010,M=998244353;
typedef long long LL;
int n,m,limit,l,R[N<<2],sum[N],ans[N];
LL A[N<<2],B[N<<2],f[N<<2];
char s[N<<2],t[N<<2];
LL qmi(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1)res=res*a%M;
a=a*a%M;
b>>=1;
}
return res%M;
}
void init()
{
memset(s,0,sizeof(s));
//注意s,t一定要初始化，因为我们遍历的时候用的 limit
memset(t,0,sizeof(t));
memset(ans,0,sizeof(ans));
memset(sum,0,sizeof(sum));
memset(f,0,sizeof(f));
limit=1,l=-1;
while(limit<=n+m) limit<<=1,l++;
for(int i=0;
i>1]>>1)|((i&1)<>_;
while(_--)
{
cin>>n>>m;
init();
cin>>s>>t;
reverse(t,t+m);
for(int k=0;
k<=10;
k++)
{
char ch;
if(k<=9)ch='0'+k;
else ch='*';
for(int i=0;
i=m)f[i]=(f[i]-sum[i-m]+M)%M;
}
for(int i=m-1;
i
总结：FFT/NTT 求字符串匹配问题关键在于通过卷积求 F数组，进而处理相关问题。
- Game on Plane 思维、签到,
思路：用优先队列从后往前贪心就好了。
- ? Kart Race 前缀和、签到
思路：简单的前缀和问题，如果某段区间内存在类型1，相当于从类型1的位置往后计算颜色，所以维护每个位置最左边的1在哪就行了。最后和255取个min
代码如下：
#include
using namespace std;
const int N=100010;
int sum[N][4],lt[N];
int n,q;
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d%d",&n,&q);
for(int i=1,op,x;
i<=n;
i++)
{
scanf("%d%X",&op,&x);
lt[i]=(op==1) ? i : lt[i-1];
for(int j=3;
j>=1;
j--)
{
sum[i][j]=x%256;
x/=256;
sum[i][j]+=sum[i-1][j];
}
}
for(int i=1,l,r;
i<=q;
i++)
{
scanf("%d%d",&l,&r);
if(l<=lt[r])l=lt[r];
for(int j=1;
j<=3;
j++)printf("%02X",min(255,sum[r][j]-sum[l-1][j]));
puts("");
}
}
return 0;
}
- Rise in Price IDA* 、动态规划
大意：给定一个 n*n 的地图，从起点为(1,1)，终点为(n,n)。每个位置都有两个数字a i , j a_{i,j} ai,j?和 b i , j b_{i,j} bi,j? 每次只能向下或者向右走， S a S_a Sa?表示走到终点处a的数字之和， S b S_b Sb?表示走到终点b的数字之和。求 S a ? S b S_a * S_b Sa??Sb?的最大值。n<=100,a i , j , b i , j a_{i,j},b_{i,j} ai,j?,bi,j?均为正数。
思路：这题大致扫一眼，这不是一道很简单的dp吗？然后迅速的敲完代码，然后果断wa。其实仔细想想这题是没有最优子结构的。很容易举出反例，假设 2*2d的地图，在(1,2)时 a为 1000，b为 1，但是在 (2,1)时候a=500,b=3。那么我们会从 (2,1)的时候转移过来，但是如果(2,2)处a=1,b=50。那么显然从(1,2)处转移过来是最优的。所以我们是不能用简单的dp写的。
方法1:时间复杂度并不是很有，但是思路很新奇，觉得有必要写一下。因为n<=100，数据还是很小的，所以就放心大胆的搞。我们在动态规划转移的时候虽然不能确定哪个是最有的，但是我们可以很容易知道哪个一定不是最优的，我们可以把一定不是最优的给去掉，然后把所有可能的结果都存下来。那么什么时候一定不是最优的呢？显然对于两对( a 1 , b 1 ) , ( a 2 , b 2 ) (a_1,b_1),(a_2,b_2) (a1?,b1?),(a2?,b2?)a 1 < a 2 , b 1 < b 2 a_1a1?
#include
using namespace std;
const int N=110;
typedef long long LL;
typedef pair PII;
PII stk[N*N*N];
int top;
vector dp[N][N];
int a[N][N],b[N][N],n;
void check(PII x)
{
while(top&&stk[top].second<=x.second)top--;
if (!top || stk[top].first < x.first) stk[++top] = x;
}
void cale(vector a,vector b,vector &ans)
{
top=0;
int sa=a.size(),sb=b.size();
int i=0,j=0;
while(i> _;
while(_ --)
{
cin>>n;
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++)
cin>>a[i][j],dp[i][j].clear();
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++)
cin>>b[i][j];
dp[1][1].push_back({a[1][1],b[1][1]});
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++)
{
if(i==1&&j==1)continue;
cale(dp[i][j-1],dp[i-1][j],dp[i][j]);
for(auto &x:dp[i][j])x.first+=a[i][j],x.second+=b[i][j];
}
LL ans=0;
for(auto x:dp[n][n])ans=max(ans,(LL)x.first*x.second);
cout<
方法2：既然没有最优子结构，那我们就爆搜呗，直接搜肯定不行，得剪枝，想来想去也就也没有什么好的剪枝策略，没办法了，只能设计预估函数了，还以为永远遇不到 IDA*了，这下子终于给遇到了。接下来就是想想怎么设计预估函数。虽然我们没办法求权值之和的乘积，但是要求a,b的权值之和的最大值还是很好求的。我们先预先求出来，即已知S=A+B。求A * B 的最大值，我们当前位置的权值之和为
a,b。则最理想的情况下最终结果为 (A+a)*(B+b)=(A+a) *(S-A+b) 化简得： ? A 2 + ( S + b ? a ) A + x y -A^2+(S+b-a)A+xy ?A2+(S+b?a)A+xy 二次函数求最值。当2A=S+b-a取最值。
代码如下：
#include
using namespace std;
typedef long long LL;
const int N=110;
int n,a[N][N],b[N][N],dp[N][N];
LL ans;
LL cale(int aa,int bb,int S)
{
int A=(S+bb-aa)/2;
int B=S-A;
return (LL)(A+aa)*(B+bb);
}
void dfs(int x,int y,int aa,int bb)
{
if(x==n&&y==n)
return (void)(ans=max(ans,1LL*aa*bb));
if(xans)dfs(x+1,y,aa+a[x+1][y],bb+b[x+1][y]);
if(yans)dfs(x,y+1,aa+a[x][y+1],bb+b[x][y+1]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
cin>>n;
ans=0;
for(int i=1;
i<=n;
i++)for(int j=1;
j<=n;
j++)cin>>a[i][j];
for(int i=1;
i<=n;
i++)for(int j=1;
j<=n;
j++)cin>>b[i][j];
for(int i=0;
i<=n+1;
i++)for(int j=0;
j<=n+1;
j++)dp[i][j]=0;
for(int i=n;
i>=1;
i--)
for(int j=n;
j>=1;
j--)
{
int sum=a[i][j]+b[i][j];
if(i==n&&j==n)dp[i][j]=sum;
else dp[i][j]=max(dp[i+1][j],dp[i][j+1])+sum;
}
dfs(1,1,a[1][1],b[1][1]);
cout<
总结:逆向思维的动态规划很奇妙，IDA*真的牛，预估函数设计的好快到飞起。
- Segment Tree with Pruning 签到，记忆化搜索
大意：本来是构建线段树时当l=r即区间长度为 1 时return ,现在改成(r - l + 1 <= k) return ;
问总共需要多少个节点。
思路：比赛时想的是模拟构建往下推，写的很麻烦，实际上直接写个记忆化搜索就好了，但是l,r<=1e18,数组存不下，所以用unorder_map存。
代码如下：
#include
using namespace std;
typedef long long LL;
LL n,k;
unordered_map dp;
LL dfs(LL l,LL r)
{
if(r-l+1<=k)return 1;
if(dp.count(r-l+1))return dp[r-l+1];
LL v=1;
LL mid=l+r >> 1;
v+=dfs(l,mid);
v+=dfs(mid+1,r);
dp[r-l+1]=v;
return v;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int _;
cin>>_;
while(_--)
{
cin>>n>>k;
cout<
【杭电|2021.杭电中超 第三场】总结：多次用到同一内容可以考虑同dp，dp+搜索=记忆化搜索。
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 杭电oj——2030汉字统计
- 【秀娟习惯养成记—2021.3.11】
- 2021.4.8日《我们为什么无法摆脱慢性疾病》常斌
- 2021.5.5|2021.5.5 五一第五天
- 2021.5.27阅读思考题
- 2021.3.9
- 鲁能6比1上港太惊艳！中超冠军还不好说，但这一点上港真比不了
- mac|mac 磁盘空间的其他文件怎么处理
- 2021.2.25工作复盘
- 静心读书吧