Codeforces Round 991 (Div. 3)（A~F）
文章目录
- A. Line Breaks
- 思路
- code
- B. Transfusion
- 思路
- code
- C. Uninteresting Number
- 思路
- code
- D. Digital string maximization
- 思路
- code
- E. Three Strings
- 思路
- code
- F. Maximum modulo equality
- 思路
- code
Codeforces Round 991 (Div. 3)
A. Line Breaks
思路
签到题，模拟即可
code
string s[N];
void solve(){
int n,m;
cin >> n >> m;
int ans=0,cnt=0;
for(int i=1;i<=n;++i) cin >> s[i];
for(int i=1;i<=n;++i){
if(cnt+s[i].size()<=m) cnt+=s[i].size(),ans++;
else break;
}
cout << ans << endl;
return ;
}
B. Transfusion
思路
考点：模拟
由于最终所有元素相等，先判断所有元素相加sum是否能整除n，不能整除直接输出NO
能整除则考虑将所有元素变为
s
u
m
/
n
sum/n
sum/n
正序遍历数组，则：
- a i = s u m / n , 不变 a_i=sum/n,不变 ai=sum/n,不变
- a i > s u m / n , a [ i + 2 ] + = ( a [ i ] − s u m ) a_i>sum/n,a[i+2]+=(a[i]-sum) ai>sum/n,a[i+2]+=(a[i]−sum)
- a i < s u m / n , a [ i + 2 ] − = ( s u m − a [ i ] ) a_i<sum/n,a[i+2]-=(sum-a[i]) ai<sum/n,a[i+2]−=(sum−a[i])
最后判断是否所有元素为 s u m / n sum/n sum/n即可
code
void solve(){
int n;cin >> n;
int sum=0;
for(int i=1;i<=n;++i) cin >> a[i],sum+=a[i];
if(sum%n!=0){
cout << "NO" << endl;
return ;
}
sum/=n;
for(int i=1;i<=n-2;++i){
if(a[i]!=sum){
if(a[i]>sum) a[i+2]+=(a[i]-sum);
else a[i+2]-=(sum-a[i]);
}
a[i]=sum;
}
for(int i=1;i<=n;++i){
if(a[i]!=sum){
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
return ;
}
C. Uninteresting Number
思路
考点：高精求余+思维
先判断原字符串是否能整除9，能整除直接输出YES
反之，考虑数字2和数字3的个数，显然，我们能改变的数字只有数字2和数字3
对于数字2的变换，它余数的变换为2
例如：
2 变换为4 余数变换(4-2)%9=2
20 变换为40 余数变换(40-20)%9=2
数字3的变换同理，它余数的变换为6
那么我们只需要考虑将原字符串的余数加上这些余数的变换是否能凑成9的倍数
假设原字符串余数为ans，接下来我们考虑
9
−
a
n
s
9-ans
9−ans 的奇偶性：
- 偶数：先拿6凑，在拿2凑
- 奇数：由于2和6都是偶数，显然凑不成奇数，所以我们考虑将余数变为偶数，即 9 − a n s + 9 9-ans+9 9−ans+9，将余数凑成18即可
code
void solve(){
string s;cin >> s;
int a=0,b=0;
int ans=0;
for(int i=0;i<s.size();++i){
ans = (ans * 10 + s[i] - '0') % 9;
if(s[i]=='2') a++;
else if(s[i]=='3') b++;
}
if(ans==0){
cout << "YES" << endl;
return ;
}
int k=9-ans;
if(k & 1) k+=9;
while(k>=6 && b) k-=6,b--;
if(k/2<=a) cout << "YES" << endl;
else cout << "NO" << endl;
return ;
}
D. Digital string maximization
思路
考点：贪心
对于字符串中每个下标 i i i,只要 s [ i ] < s [ i + 1 ] − 1 s[i]<s[i+1]-1 s[i]<s[i+1]−1，我们就让 s [ i + 1 ] − = 1 s[i+1]-=1 s[i+1]−=1，然后交换它的值
code
void solve(){
string s;cin >> s;
while(1){
int flag=1;
for(int i=0;i<s.size()-1;++i){
if(s[i]<s[i+1]-1){
s[i+1]-=1;
swap(s[i],s[i+1]);
flag=0;
}
}
if(flag) break;
}
cout << s << endl;
return ;
}
E. Three Strings
思路
考点：DP
赛时想到DP了，太久没写DP题了，根本不会做QAQ
定义二维数组 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示使用字符串a的前 i i i个字符和字符串b的前 j j j个字符构造出字符串 c 的前 i + j i + j i+j个字符时，最少需要替换的字符数量。
考虑状态转移方程，
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 可以由
d
p
[
i
−
1
]
[
j
]
dp[i - 1][j]
dp[i−1][j] 而来，也可以由
d
p
[
i
]
[
j
−
1
]
dp[i][j - 1]
dp[i][j−1]
显然我们是求这两种情况的最小值，因此它的状态转移方程为：
d
p
[
i
]
[
j
]
=
m
i
n
(
d
p
[
i
−
1
]
[
j
]
+
(
a
[
i
−
1
]
!
=
c
[
i
+
j
−
1
]
)
,
d
p
[
i
]
[
j
−
1
]
+
(
b
[
j
−
1
]
!
=
c
[
i
+
j
−
1
]
)
)
;
dp[i][j]=min(dp[i-1][j]+(a[i-1]!=c[i+j-1]),dp[i][j-1]+(b[j-1]!=c[i+j-1]));
dp[i][j]=min(dp[i−1][j]+(a[i−1]!=c[i+j−1]),dp[i][j−1]+(b[j−1]!=c[i+j−1]));
注意 i = 0 , j = 0 i=0,j=0 i=0,j=0边界溢出的问题，最后 d p [ a . s i z e ( ) ] [ b . s i z e ( ) ] dp[a.size()][b.size()] dp[a.size()][b.size()] 即是答案
code
int dp[N][N];
void solve(){
string a,b,c;
cin >> a >> b >> c;
int n=a.size(),m=b.size();
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j){
if(i==0 && j==0) dp[i][j]=0;
else if(i==0) dp[i][j]=dp[i][j-1]+(b[j-1]!=c[i+j-1]);
else if(j==0) dp[i][j]=dp[i-1][j]+(a[i-1]!=c[i+j-1]);
else{
dp[i][j]=min(dp[i-1][j]+(a[i-1]!=c[i+j-1]),dp[i][j-1]+(b[j-1]!=c[i+j-1]));
}
}
cout << dp[n][m] << endl;
return ;
}
F. Maximum modulo equality
思路
考点：数论+思维
由于 a i ≡ a i + 1 ( m o d m ) , a i + 1 ≡ a i + 2 ( m o d m ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ a_i \equiv a_{i+1}(mod~m),a_{i+1} \equiv a_{i+2}(mod~m)········ ai≡ai+1(mod m),ai+1≡ai+2(mod m)⋅⋅⋅⋅⋅⋅⋅⋅
我们可以对这些式子进行一个处理，即
a i + 1 − a i ≡ 0 ( m o d m ) , a i + 2 − a i + 1 ≡ 0 ( m o d m ) ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ a_{i+1}-a_{i} \equiv 0(mod~m),a_{i+2}-a_{i+1} \equiv 0(mod~m)········ ai+1−ai≡0(mod m),ai+2−ai+1≡0(mod m)⋅⋅⋅⋅⋅⋅⋅⋅
定义一个序列
b
b
b =
a
i
+
1
−
a
i
a_{i+1}-a_i
ai+1−ai
显然我们要求序列b的最大公约数，使得他们求余m都为0
那么这题就变的非常简单了，我们可以用st表、树状数组、线段树等等去维护这个区间
我用的是st表，理解题意相当于是一道板子题
code
const int N=2e5+5;
int a[N];
int st[N][31];
int n,q;
void init(){
for(int j=1;j<20;++j)
for(int i=1;i<=n-(1<<j)+1;++i){
st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
void solve(){
cin >> n >> q;
for(int i=0;i<n;++i){
cin >> a[i];
if(i) st[i][0]=a[i]-a[i-1];
}
init();
while(q--){
int l,r;
cin >> l >> r;
r--;
if(l>r) cout << 0 << " ";
else{
int len=log2(r-l+1);
cout << abs(__gcd(st[l][len],st[r-(1<<len)+1][len])) << " ";
}
}
cout << endl;
return ;
}