Codeforces 1093F Vasya and Array
题目链接
http://codeforces.com/contest/1093/problem/F
题目大意
给你一个长度为 $n$ ，由 $1$ 到 $k$ 和 $-1$ 组成的数列，问将其中所有的 $-1$ 都改成 $1$ 到 $k$ 之间的数，有多少种方法可以使得改出来的数列没有任何一个长度为 $len$ 的连续子串为相同的数字。
题目分析
考虑使用 $DP$ 来求解这道题。定义 $f[i][j][l]$ 为匹配到第 $i$ 位，结尾是连续 $l$ 个数字 $j$ 的方法数。很容易就能写出递推式。但是复杂度太高了。但是发现其实 $i – 1$ 时的 $l \leq 1$ 的项在 $i$ 时其实都会被转移到 $l$ 处，而 $l = 1$ 的项是所有其他的 $j$ 的任何一个位置转移过来的。因此可以使用一个队列加上记录总和来记录每一项。但是复杂度是 $O(nk)$ 的还是不足以通过本题。但是注意到，在 $a[i] = -1$ 时，每一项的答案总和都可以用前一位的总和直接计算出来，有影响的只有 $a[i] \neq -1$ 的项，因此每次只需要记录总和和下一项不为 $1$ 的 $a[i]$ 是哪个数字分类讨论即可解决。复杂度只有 $O(n)$ 。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e5 + 5;
long long mod = 998244353;
int n, m, t, k;
int a[maxn];
struct dp {
queue <long long> q;
long long sum;
int push(long long x){
sum = (sum + x) % mod;
q.push(x);
if(q.size() >= m){
sum = (sum - q.front() + mod) % mod;
q.pop();
}
return 0;
}
int clear(){
int i, j;
sum = 0;
queue <long long> empty;
swap(q, empty);
return 0;
}
dp(){sum = 0;}
};
dp f[5];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j;
long long sum;
long long ans = 0;
int x, y = -1;
queue <int> q;
n = read();
k = read();
m = read();
for(i=1;i<=n;i++){
a[i] = read();
if(a[i] != -1){
q.push(a[i]);
}
}
if(a[1] == -1){
f[0].push(k);
f[1].push(1);
}else{
f[0].push(1);
x = q.front();
q.pop();
if(q.size() >= 1){
if(q.front() == x){
f[1].push(1);
}else{
f[1].clear();
}
}
}
for(i=2;i<=n;i++){
sum = f[0].sum;
if(a[i] == -1){
f[0].push(sum * (long long)(k - 1) % mod);
f[1].push((sum - f[1].sum + mod) % mod);
}else{
x = q.front();
q.pop();
f[1].push((sum - f[1].sum + mod) % mod);
f[0] = f[1];
if(q.size() >= 1){
if(q.front() != x){
f[1].clear();
}
}
}
}
ans = f[0].sum;
printf("%lld\n", ans);
return 0;
}