AtCoder Beginner Contest 253(E,F)
E （dp,前缀和）
大意就是求满足以下要求的的序列的个数
\(1\),满足\(a_i\)都在\([1,m]\)的范围里面
\(2\),满足$ \vert a_i-a_{i+1}\vert $ 大于\(k\)
之前做过一个类似的题目,是绝对值小于\(k\)，不过大同小异
这里我使用了前缀和来优化
但是这里\(k\)是可以为\(0\)的，我没有特判，错了，所以我们最好特判为\(0\)的情况
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1000+10;
const int maxm=5000+10;
const int mod=998244353;
int n,m,k;
int dp[maxn][maxm];
int sum[maxn][maxm];
int add(int x,int c)
{
x+=c;
if(x>=mod)
{
x-=mod;
}
else if(x<0)
{
x+=mod;
}
return x;
}
signed main()
{
ios;
cin>>n>>m>>k;
if(k==0)
{
int ans=1;
for (int i=1;i<=n;i++)
{
ans=(ans*m)%mod;
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
for (int i=1;i<=m;i++)
{
dp[1][i]=1;
sum[1][i]=add(sum[1][i-1],dp[1][i]);
}
for (int i=2;i<=n;i++)
{
for (int now=1;now<=m;now++)
{
if(now>k)
{
int l=1,r=now-k;
int tmp=add(sum[i-1][r],-sum[i-1][l-1]);
dp[i][now]=add(dp[i][now],tmp);
}
if(now+k<=m)
{
int l=now+k,r=m;
int tmp=add(sum[i-1][r],-sum[i-1][l-1]);
dp[i][now]=add(dp[i][now],tmp);
}
sum[i][now]=add(sum[i][now-1],dp[i][now]);
}
}
int ans=sum[n][m];
cout<<ans<<"\n";
system ("pause");
return 0;
}
F(树状数组)
这个题大意就是有一个矩阵，初始每一个位置上都是\(0\),有下面几种操作
操作\(1\),输出\(l,r,x\),把\(l\)到\(r\)列都加上\(x\)
操作\(2\),输出\(pos,x\),把\(pos\)行所有的数都变成\(x\)
操作\(3\),输出\(r,x\),输出此时这个位置上的数
我这里把每一个操作的顺序看做了“时间”。
我们可以发现，能真正影响最后的答案的是第二个操作，所以，每次查询答案，我们首先要知道这个位置最后一次（到查询为止）被替换的值是多少，然后我们再来加上被替换之后进行了操作\(1\)改变了多少
查询这一次查询行位置的最后一次替换值很简单，我们可以在进行操作\(2\)的时候对\(last[pos]\)记录下来
然后我们还需要知道在最后一次替换到目前的操作\(1\)进行了多少，可是我们发现如果按照时间的顺序来，不仅要判断这个是否在操作\(1\)的范围，还有可能前面的操作\(1\)可能会有很多，导致超时，所以在操作\(3\)的时候再一个一个来变是行不通的
既然是以操作\(2\)的时间为界限的，那么不如我们先保存操作，然后每次在操作\(2\)的时候，来判断这一个操作\(2\)会对哪些答案会存在影响，然后一律把那些受到影响的值顺便变成这一个操作替换后的值，然后我们再考虑操作\(1\)的影响，但是我们一个一个找显然是不太现实的，既然是求求这一段时间到查询这一段时间里面变化的数，不如把时间看做下标，对一段里面的加上的值进行一次前缀和，我们可以先减去前面用不到的，操作\(1\)按照时间对前缀和数组不断更新，直到查询的时候，加上这个位置此时的前缀和，那么答案就是操作\(2\)的\(x\)加上这一段时间这一列的变化值\(val\)
对于以上的前缀数组，我们这里用的是树状数组，只不过下标是行的位置，按照时间的顺序来进行加减
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=2e5+10;
const int mod=998244353;
int n,m;
int q;
int bit[maxn];
struct node
{
int op,l,r,x;
//op==1, op,l,r,x
//op===2, op,pos,x,id
//op==3 op,x,y,ans_id,第几个答案
}a[maxn];
vector<int>ans;
int last[maxn];
vector<int>Queryin[maxn];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
while (x<=m)
{
bit[x]+=val;
x+=lowbit(x);
}
return ;
}
void Update(int l,int r,int val)
{
update(l,val);
update(r+1,-val);
return ;
}
int query(int x)
{
int res=0;
while (x)
{
res+=bit[x];
x-=lowbit(x);
}
return res;
}
void op1(int id)
{
int l,r,x;
cin>>l>>r>>x;
a[id]={1,l,r,x};
return ;
}
void op2(int id)
{
int pos,x;
cin>>pos>>x;
last[pos]=id;
a[id]={2,pos,x,id};
return ;
}
void op3(int id)
{
int x,y;
cin>>x>>y;
int ans_id=ans.size();
ans.push_back(0);
int last_x=last[x];
Queryin[last_x].push_back(id);//Queryin里面记录的是第last_x时操作二影响的查询操作的答案，在后面进行操作的时候对答案赋初值，并减去这时间前面的列的变化
a[id]={3,x,y,ans_id};
return ;
}
void solve1(int id)
{
auto [op,l,r,x]=a[id];
Update(l,r,x);
return ;
}
void solve2(int i)
{
auto [op,pos,x,id]=a[i];
for (auto effect:Queryin[id])
{
auto [opp,posx,posy,ans_id]=a[effect];
ans[ans_id]=x;//赋初值
ans[ans_id]-=query(posy);//减去前面的变化
}
return ;
}
void solve3(int id)
{
auto [op,x,y,ans_id]=a[id];
ans[ans_id]+=query(y);//加上查询此时的列的总变化，实现了前缀和的效果
return ;
}
signed main()
{
cin>>n>>m>>q;
for (int i=1;i<=q;i++)
{
int op;
cin>>op;
if(op==1)
{
op1(i);
}
else if(op==2)
{
op2(i);
}
else if(op==3)
{
op3(i);
}
}
for (int i=1;i<=q;i++)
{
int op=a[i].op;
if(op==1)
{
solve1(i);
}
else if(op==2)
{
solve2(i);
}
else if(op==3)
{
solve3(i);
}
}
for (auto x:ans)
{
cout<<x<<"\n";
}
system ("pause");
return 0;
}