晚上有点累 打点菜就过了2签到题 第二题还中间调错了
A - Two Sequences 2
思路:从前到后走一遍 保持最大值
#include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=2e5 10; int a[N],b[N],maxa[N]; int main(){
int n; scanf("%d",&n); for(int i=1;i<=n;i ){
scanf("%d",&a[i]); } for(int i=1;i<=n;i ){
scanf("%d",&b[i]); } int maxb=0; int ap=1,bp=1; LL maxv=0; for(int i=1;i<=n;i++){
maxa[i]=max(a[i],maxa[i-1]); if(1ll*maxa[i]*b[i]>=maxv){
maxv=1ll*maxa[i]*b[i]; } printf("%lld\n",maxv); } } B - Mex Boxes
思路：用cnt[]数组做桶自低向上推一边就行 写错用很久原因是我后续推是直接模拟导致变量写错 修改后的代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10;
typedef long long LL;
int cnt[N];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
cnt[x]++;
}
int ans=0;
cnt[0]=min(k,cnt[0]);
ans+=(1)*cnt[0];
for(int i=1;i<=n;i++){
cnt[i]=min(cnt[i-1],cnt[i]);
ans+=cnt[i];
if(!cnt[i+1])break;
}
cout<<ans;
return 0;
}
C - Robot on Grid
思路:首先如果是空地方是相当于x的话那么就是简单dp 但是题目的意思是多种行走方案之和 行走方案就是多种不同地图下的多种行走方案之和 所以考虑 如果i j位置为R或者X 那么f[i][j+1]=(f[i][j]+f[i][j+1])%mod; 如果 i j位置为D或者X 那么f[i+1][j]=(f[i+1][j]+f[i][j])%mod; 当i j 位置为空时 3种情况 填入R 那么
f[i][j+1]=(f[i][j]+f[i][j+1])%mod;
填入D
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
填入X
f[i][j+1]=(f[i][j]+f[i][j+1])%mod;
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;`
综合起来就是
f[i][j+1]=(2ll*f[i][j]%mod+f[i][j+1])%mod;
f[i+1][j]=(2ll*f[i][j]%mod+f[i+1][j])%mod;
我们再考虑地图种类的情况 3种情况中只有2种情况满足满足转移 所以在这里我们转移的时候f[i][j]为便是平均值 表示的为所有地图种类下的平均方案数 因为要取模运算我们求出inv为3的逆元 即为
f[i][j+1]=(2ll*f[i][j]*inv%mod+f[i][j+1])%mod;
f[i+1][j]=(2ll*f[i][j]*inv%mod+f[i+1][j])%mod;
又地图方案为3的n*m-k次方 所以答案为1ll*f[n][m]*qpow(3,n*m-k)%mod;
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e3+10,mod=998244353;
typedef long long LL;
int f[N][N];
char g[N][N];
int qpow(int x,int k){
int res=1;
while(k){
if(k&1)res=1ll*res*x%mod;
x=1ll*x*x%mod;
k>>=1;
}
return res;
}
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)g[i][j]='.';
for(int i=1;i<=k;i++)
{
int x,y;
char op;
scanf("%d%d %c",&x,&y,&op);
g[x][y]=op;
}
int inv=qpow(3,mod-2);
f[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]=='X'||g[i][j]=='D'){
f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
}
if(g[i][j]=='X'||g[i][j]=='R'){
f[i][j+1]=(f[i][j+1]+f[i][j])%mod;
}
if(g[i][j]=='.'){
f[i][j+1]=(2ll*f[i][j]*inv%mod+f[i][j+1])%mod;
f[i+1][j]=(2ll*f[i][j]*inv%mod+f[i+1][j])%mod;
}
}
}
cout<<1ll*f[n][m]*qpow(3,n*m-k)%mod;
}