CF1864(div1++div2)题解
CF1864
A. Increasing and Decreasing
建一个数组， $ a_1=x,a_n=y ,b_i=a_{i+1}-a_i$ ，a单调递增，b单调递减。
思路：
从后往前枚举每次减1，2，3,… 若 $ a_1<x $ ,输出-1，否则输出数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
int x,y,n;
cin>>x>>y>>n;
vector<int> ans;
int last=y;
for(int i=1;i<=n;i++){
ans.push_back(last);
last-=i;
}
if(ans[n-1]>=x){
cout<<x<<" ";
for(int i=n-2;i>=0;i--)cout<<ans[i]<<" ";
cout<<"\n";
}
else cout<<"-1\n";
}
B. Swap and Reverse
题意：
给定长度为n的字符串s和整数k，可以进行以下两种操作：
- $ swap(a_i,a_{i+2}) $
- $ reverse [i,i+k-1] $
求能得到的最小字典序 思路： 对于1操作，奇数可以互换，偶数可以互换， $ [1,0,1,0,1,0,…] $
对于2操作，若k为奇数，可以发现中间数不变，左右两边互换，由于1，0一一对应交换后不改变能交换的位置，近似等于1操作，对奇偶分别排序输出
若k为偶数，$ \to [i,i+k-1] \to [i+1,i+k] $ ,可以交换0和1位置，此时可以全排序输出
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
28
29
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<char> odd, even;
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
even.pb(s[i]);
} else {
odd.pb(s[i]);
}
}
sort(all(even));
sort(all(odd));
string ans1 = "";
for (int i = 0, j = 0; i < sz(even) || j < sz(odd); ++i, ++j) {
if (i < sz(even)) {
ans1 += even[i];
}
if (j < sz(odd)) {
ans1 += odd[i];
}
}
if (k % 2 == 0) {
sort(all(s));
cout << s << "\n";
continue;
}
cout << ans1 << "\n";
C. Divisor Chain
题意：
给定一个x，每次减一个数，直至x=1
不能减一个数超过两次 思路：
易看出与 $ 2^x $ 有关，将x拆成 $ x=2^y \cdot A ,A为奇数 $，若 $ A!=1 $ ，每次将A变为偶数即 $ A-=1 $ 相当于 $x-=2^y$ ,再从A中分解2的个数加入y，最后变成 $ x=2^y $此时每次减一半直至x=1即可，每个2的倍数恰好用了两次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve(){
ll n,a=1;
cin>>n;
vector<ll> ans;
ans.pb(n);
while(n%2==0)n/=2,a*=2;
while(n!=1){
n-=1;
ans.pb(n*a);
while(n%2==0)n/=2,a*=2;
}
n*=a;
while(n!=1){
n/=2;
ans.pb(n);
}
cout<<ans.size()<<"\n";
for(auto it:ans)cout<<it<<" ";
cout<<"\n";
}
D. Matrix Cascade
题意：
给定一个只包含0和1的n*m的矩阵，选择 $ (i,j)且a_{i,j}=1 使a_{i,j}=0 $,则接下来 $ x-i>=|y-j| $的部分也会改变，问最小次数使全部变为0
思路：
改变一个点，两边斜45度包含的所有点也会改变，可以利用前缀和差分，但要注意的是不能只用一个数组(因为如果抵消1和-1抵消了就无法继续往下传递1和-1了，会影响后面的值),用pre维护往左边传递的值即加1，suf维护减1，每次求出sum后，pre的值全部往左移一位，suf往右移一位；有如下两种情况需要传递新的值：
- $ a_{i,j}=0且sum_j为偶数 $
- $ a_{i,j}=1且sum_j为奇数 $
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve(){
int n;
cin>>n;
ll ans=0;
for(int i=1;i<=n;i++)cin>>a[i]+1;
vector<ll> pre(n+1),suf(n+1);
for(int i=1;i<=n;i++){
if(i==1){
for(int j=1;j<=n;j++){
if(a[i][j]=='1'){
ans++;
if(j>1)pre[j-1]++;
else pre[j]++;
if(j<n-1)suf[j+2]++;
}
}
}
else{
vector<ll> sum(n+1);
for(int j=1;j<=n;j++){
sum[j]=sum[j-1];
if(pre[j])sum[j]+=pre[j];
if(suf[j])sum[j]-=suf[j];
}
for(int j=1;j<=n;j++){
if(pre[j]&&j>1)pre[j-1]+=pre[j],pre[j]=0;
}
for(int j=n;j>=1;j--){
if(suf[j]){
if(j<n)suf[j+1]+=suf[j],suf[j]=0;
else suf[j]=0;
}
}
for(int j=1;j<=n;j++){
if((a[i][j]=='1'&&sum[j]%2==0)||(a[i][j]=='0'&&sum[j]%2==1)){
ans++;
if(j>1)pre[j-1]++;
else pre[j]++;
if(j<n-1)suf[j+2]++;
}
}
}
}
cout<<ans<<'\n';
}