总体而言,这套比 ARC 058 要简单。
A
将 变为 的代价为 ,给一数组 ,每个元素只能变一次,求将该数组所有元素变相同的最小代价。
最后数组中的数的大小一定在原来最小值和最大值之间。枚举这个数计算代价并比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| constexpr int N=105; int a[N]; inline void work() { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int n;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; int l=*min_element(a+1,a+n+1),r=*max_element(a+1,a+n+1); int ans=1e9; for(int i=l;i<=r;i++) { int now=0; for(int j=1;j<=n;j++) now+=(i-a[j])*(i-a[j]); ans=min(ans,now); } cout<<ans<<endl; }
CPP
|
B
给定一字符串,求一个区间使得该区间存在绝对众数(即出现次数严格大于一半)。
本题花费较长时间。结论:只需判断长度为 的子区间。首先根据上述结论,容易得到如果所有长度为 的子区间无绝对众数,则长度为 和 的子区间也无绝对众数,然后在这些长度的区间上继续拼接长度为 的子区间则可归纳的证明。判断很容易。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| constexpr int N=1e5+5; char s[N]; inline bool check(int n) { if(s[n]!=s[n+1]&&s[n+1]!=s[n+2]&&s[n]!=s[n+2]) return false; return true; } inline void work() { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cout.tie(nullptr); cin>>(s+1); int n=int(strlen(s+1)); if(n==2) { if(s[1]==s[2]) cout<<"1 2"<<endl; else cout<<"-1 -1"<<endl; return; } for(int i=1;i+2<=n;i++) { if(check(i)) return cout<<i<<" "<<i+2<<endl,void(); } cout<<"-1 -1"<<endl; }
CPP
|
C
定义 。求 。给定 。
DP。设 表示前 个, 已经使用了 时所有的贡献和。转移只需要枚举 和 即可转移。时间复杂度 ,不可过。发现对于同一个 , 的增加量可以由 的增加量递推得来。时间复杂度 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| constexpr int N=405;using ll=long long;constexpr ll mod=1e9+7; int l[N],r[N];ll f[N][N],s[N]; inline void work() { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int n,m;cin>>n>>m; for(int i=1;i<=n;i++) cin>>l[i]; for(int i=1;i<=n;i++) cin>>r[i]; f[0][0]=1; for(int i=1;i<=n;i++) { memset(s,0,sizeof(s)); for(int j=0;j<=m;j++) { for(int k=l[i];k<=r[i];k++) { s[k]=(s[k]*k+f[i-1][j])%mod; f[i][j]=(f[i][j]+s[k])%mod; } } } cout<<f[n][m]<<endl; }
CPP
|
D
给定一个字符串,保证仅由 和 组成,当前有一个空串,你可以在后面增加 或增加 ,或者删除结尾字符(如果不存在也可以删除,但操作被忽略)。求有多少种操作方式使得操作完是给定字符串。
显然并不关心字符串是什么,只关心长度,相同长度的字符串应当操作方式的数量是一定的。考虑对总和计数,最后除以长度相同字符串的总数即可。设 表示前 次操作得到长为 的字符串的操作次数。转移显然。注意在 为 的时候特判。时间复杂度 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| constexpr int N=5005;using ll=long long;constexpr ll mod=1e9+7; char s[N];ll f[N][N]; inline ll qpow(ll a,ll b) { ll ret=1;a%=mod; while(b) { if(b&1) ret=ret*a%mod; a=a*a%mod; b>>=1; } return ret; } inline void work() { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int n;cin>>n>>(s+1); int m=int(strlen(s+1)); f[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=n;j++) { if(j==0) f[i][j]=(f[i-1][j]+f[i-1][j+1])%mod; else f[i][j]=(f[i-1][j-1]*2+f[i-1][j+1])%mod; } cout<<f[n][m]*qpow(qpow(2,m),mod-2)%mod<<endl; }
CPP
|