AT_abc442 - crazy-

F 简单dp优化

A

#include<bits/stdc++.h>
// #define int long long
using namespace std;signed main()
{string s;int ans=0;cin>>s;for(int i=0;i<s.size();i++) ans+=(s[i]=='i' || s[i]=='j');cout<<ans<<endl;return 0;
}

B

#include<bits/stdc++.h>
// #define int long long
using namespace std;signed main()
{int q;int vol,play;vol=play=0;cin>>q;while(q--){int opt;cin>>opt;if(opt==1) vol++;else if(opt==2) vol=max(vol-1,0);else play^=1;cout<<(play && vol>=3?"Yes":"No")<<endl;}return 0;
}

C

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=2e5+10;
int a[Maxn];
int n,m,ans;
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++) a[i]=n-1;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;a[x]--; a[y]--;}for(int i=1;i<=n;i++) cout<<a[i]*(a[i]-1)*(a[i]-2)/6<<" ";cout<<endl;return 0;
}

D

#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int Maxn=2e5+10;
int c[Maxn];
int n,q;
int a[Maxn];
int lowbit(int x) {return x&-x;}
void add(int x,int y)
{while(x<=Maxn-10){c[x]+=y;x+=lowbit(x);}
}
int get(int x)
{int re=0;while(x){re+=c[x];x-=lowbit(x);}return re;
}
int query(int l,int r) {return get(r)-get(l-1);}
signed main()
{cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];add(i,a[i]);}while(q--){int opt,x,l,r;cin>>opt;if(opt==1){cin>>x;add(x,-a[x]);add(x,a[x+1]);add(x+1,-a[x+1]);add(x+1,a[x]);swap(a[x],a[x+1]);}else{cin>>l>>r;cout<<query(l,r)<<endl;}}return 0;
}

F

假设第 \(i\) 行的前 \(a_i\) 个格子最终被染成了白色，显然 \(a_i\) 应该单调不增。

设 \(dp[i][j]\) 表示第 \(i\) 行将前 \(j\) 个涂白的方案数，转移显然。

#include<bits/stdc++.h>
// #define int long long
using namespace std;
int n,ans;
char c[5010][5010];
int dp[5010][5010];
int mn[5010][5010];
int cnt[5010][5010];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>c[i][j];cnt[i][j]=cnt[i][j-1]+(c[i][j]=='.');}for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){dp[i][j]=mn[i-1][j]+(j-cnt[i][j])+(cnt[i][n]-cnt[i][j]);}mn[i][n+1]=1e9;for(int j=n;j>=0;j--) mn[i][j]=min(dp[i][j],mn[i][j+1]);}ans=1e9;for(int i=0;i<=n;i++) ans=min(ans,dp[n][i]);cout<<ans<<endl;return 0;
}