我想自己做网站,江西省上饶市城乡建设网站,wordpress无插件下载,企业网站建设策划书 前言正题 题目大意
给出一个长度为nnn的序列aaa和数字lll#xff0c;定义两个长度为lll的区间[l1,r1][l_1,r_1][l1,r1]和[l2,r2][l_2,r_2][l2,r2]的距离为有多少个不相同的数字。
然后有qqq个询问kik_iki#xff0c;要求输出有多少对距离为kik_iki的区间。 解题思路…正题 题目大意
给出一个长度为nnn的序列aaa和数字lll定义两个长度为lll的区间[l1,r1][l_1,r_1][l1,r1]和[l2,r2][l_2,r_2][l2,r2]的距离为有多少个不相同的数字。
然后有qqq个询问kik_iki要求输出有多少对距离为kik_iki的区间。 解题思路
我们发现若我们求出了[l1,r1][l_1,r_1][l1,r1]和[l2,r2][l_2,r_2][l2,r2]的距离就可以O(1)O(1)O(1)求出[l11,r11][l_11,r_11][l11,r11]和[l21,r21][l_21,r_21][l21,r21]的距离(两个ififif即可)。
我们可以枚举计算的区间对的位置差
所以我们可以用ansi,jans_{i,j}ansi,j表示区间[i,il−1][i,il-1][i,il−1]有多少个与其距离为jjj的区间。然后做个前缀和即可。
时空间复杂度都是O(n2)O(n^2)O(n2)。我们发现空间复杂度并不能胜任所以我们可以将ansi,jans_{i,j}ansi,j的jjj的意义变为有多少个与其距离为kjk_jkj的区间。
然后空间复杂度O(nq)O(nq)O(nq) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N11000;
int n,q,a[N],x[N],num[N],ans[N][110],L;
bool v[N];
int main()
{freopen(lottery.in,r,stdin);//freopen(lottery.out,w,stdout);scanf(%d%d,n,L);for(int i1;in;i)scanf(%d,a[i]);scanf(%d,q);for(int i1;iq;i)scanf(%d,x[i]),v[x[i]1]1;num[0]1;for(int i1;in;i)num[i]num[i-1]v[i];for(int l1;ln;l){int dis0;if(lLn) break; for(int i1;iL;i)if(a[i]!a[il]) dis;ans[1][num[dis]];ans[1l][num[dis]];for(int i2;in-L1;i){int jil;if(jn-L1) break;if(a[i-1]!a[j-1]) dis--;if(a[iL-1]!a[jL-1]) dis;ans[i][num[dis]];ans[j][num[dis]];}}for(int i1;inum[n];i)for(int j1;jn;j)ans[j][i]ans[j][i-1];for(int i1;iq;i){for(int j1;jn-L1;j)printf(%d ,ans[j][num[x[i]]]);putchar(\n);}
}
