Day 1
A 咕咕
题目描述
解法
DP，设 \(dp_{i,j}\) 表示从 \((1,1)\) 走到 \((n,m)\) 的方案数。
转移的时候，需要按照给定的限制走，如果一个点的（2）（3）限制冲突了，那么就标记一下，经过他的时候绕过他，时间复杂度 \(O(nm)\)。
代码
点击查看代码
int n,m,t;
int f[3001][3001];
int dp[3001][3001];
void solve()
{
cin>>n>>m>>t;
int i,j;
while(t--)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
bool flag = 0;
if(a==n&&b==m)
continue;
if((c==a+1&&d==b)||(d==b+1&&a==c))
flag = 1;
if(!flag||f[a][b]==-1)
{
f[a][b] = -1;
continue;
}
if(c==a+1)
{
if(f[a][b]==2)
f[a][b] = -1;
else
f[a][b] = 1;
}
else if(d==b+1)
{
if(f[a][b]==1)
f[a][b] = -1;
else
f[a][b] = 2;
}
}
if(f[1][1]==-1)
{
cout<<0<<endl;
return;
}
dp[1][1] = 1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(f[i][j]==-1)
dp[i][j]=0;
else
{
if(f[i-1][j]!=2)
dp[i][j] += dp[i-1][j];
if(f[i][j-1]!=1)
dp[i][j] += dp[i][j-1];
dp[i][j] %= mod;
}
}
cout<<dp[n][m]<<endl;
return;
}
B 找子串
题目描述
解法
- Subtask 1
每次删掉 \(T\) 后重新暴力再找第一个 \(T\)，时间复杂度 \(O(\dfrac{|S|}{|T|}\cdot |S| \cdot |T|)\)。
- Subtask 2
每次删掉 \(T\) 后，从删掉位置之前的 \(T\) 个位置开始，用 kmp 或哈希找 \(T\)，时间复杂度 \(O(|S|\cdot |T|)\)。
标签：int,平邑,else,cdot,flag,3001,补题,&&,集训 From： https://www.cnblogs.com/OoXiaoQioO/p/18343862