ARC 059 比赛记录(VP)

总体而言,这套比 ARC 058 要简单。

A

x 变为 y 的代价为 (xy)2,给一数组 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

ARC 059 比赛记录(VP)
https://www.llingy.top/posts/2478925347/
作者
llingy
发布于
2023年2月3日
许可协议