总体而言，这套比 ARC 058 要简单。
$\checkmark$ A
将 $x$ 变为 $y$ 的代价为 $(x-y)^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;
}
|
$\checkmark$ B
给定一字符串，求一个区间使得该区间存在绝对众数（即出现次数严格大于一半）。
本题花费较长时间。结论：只需判断长度为 $3$ 的子区间。首先根据上述结论，容易得到如果所有长度为 $3$ 的子区间无绝对众数，则长度为 $4$ 和 $5$ 的子区间也无绝对众数，然后在这些长度的区间上继续拼接长度为 $3$ 的子区间则可归纳的证明。判断很容易。
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;
}
|
$\checkmark$ C
定义 $f(a_1,a_2,a_3,a_4,\cdots,a_n)=\sum_{c_1+c_2+\cdots+c_n=c(\forall i,c_i\ge 0)}\sum_{i=1}^{n}a_i^{c_i}$。求 $\sum_{x_1=l_1}^{r_1}\sum_{x_2=l_2}^{r_2}\cdots\sum_{x_n=l_n}^{r_n}f(x_1,x_2,\cdots,x_n)$。给定 $n,c,l_i,r_i$。
DP。设 $f_{i,j}$ 表示前 $i$ 个，$c$ 已经使用了 $j$ 时所有的贡献和。转移只需要枚举 $c_i$ 和 $j$ 即可转移。时间复杂度 $O(n^4)$，不可过。发现对于同一个 $x$，$j$ 的增加量可以由 $j-1$ 的增加量递推得来。时间复杂度 $O(n^3)$。
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;
}
|
$\checkmark$ D
给定一个字符串，保证仅由 $\texttt{0}$ 和 $\texttt{1}$ 组成，当前有一个空串，你可以在后面增加 $\texttt{0}$ 或增加 $\texttt{1}$，或者删除结尾字符（如果不存在也可以删除，但操作被忽略）。求有多少种操作方式使得操作完是给定字符串。
显然并不关心字符串是什么，只关心长度，相同长度的字符串应当操作方式的数量是一定的。考虑对总和计数，最后除以长度相同字符串的总数即可。设 $f_{i,j}$ 表示前 $i$ 次操作得到长为 $j$ 的字符串的操作次数。转移显然。注意在 $j$ 为 $0$ 的时候特判。时间复杂度 $O(n^2)$。
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;
}
|