题解：CF18E Flag 2
ZMQ_Ink6556 · · 题解
题解：CF18E Flag 2
UPD：增加了亿点点内容。
一道调了
解题思路
我们由题面可推知，每一行的字母都是交替摆放的，所以可以去枚举每行所使用的两个字母分别是什么就可以了。用图片来解释一下，也就是，只能按照下图的方法放字母：
我首先写了一个记搜，结果：TLE。
这里的主要问题是记忆化不一定每个位置都能一次跑到最优，比如 CF 上的 #3，我最后一层记搜被跑了整整
有句话说得好，叫做：“任何记搜，都能写成 DP。”所以我将代码改成了 DP （这就是为什么 DP 代码里面会有 。memory 这个数组名）
此时，我们的思路可以大致理为：
- 从最后一个状态搜起，也就是说起点在最下层。
- 四重暴力确定每个位置用什么字母，用 DP 转移并且标注。
- 由标注反推最后的国旗。
接下来是最重要的推 DP 转移方程。若我们设行数为
由此，写出代码不难。但是要注意，因为我们的处理顺序是从下到上，所以我们要逆序输出。
参考代码
#include<bits/stdc++.h>
#pragma GCC optimize(2)//卡常
using namespace std;
int n , m , dp[505][30][30] , dp2[505][30][30] , dp3[505][30][30] , memory[505][30][30] , ansn , minj , mink , p , q , tmp1 , tmp2 , cost , tmp;
char a[505][505] , ans[505][505];
int main()
{
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cin >> a[i][j];
}
}
for(int i = 0 ; i <= n ; i++)
{
for(int j = 0 ; j <= 'z' ; j++)
{
for(int k = 0 ; k <= 'z' ; k++)
{
if(!i)//卡常
{
dp[i][j][k] = 0;
}
else
{
dp[i][j][k] = 1000000007;
}
}
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j1 = 0 ; j1 <= 25 ; j1++)
{
for(int k1 = 0 ; k1 <= 25 ; k1++)
{
if(j1 != k1)//卡常
{
for(int j2 = 0 ; j2 <= 25 ; j2++)
{
if(j1 != j2)//卡常
{
for(int k2 = 0 ; k2 <= 25 ; k2++)
{
if(k1 != k2 && j2 != k2)
{
if(memory[i][j2][k2] != 0)
{
cost = memory[i][j2][k2];
}
else
{
tmp = 0;
for(int l = 1 ; l <= m ; l++)
{
if(l % 2)
{
tmp += (a[i][l] != j2 + 'a');
}
else
{
tmp += (a[i][l] != k2 + 'a');
}
}
memory[i][j2][k2] = tmp;
cost = tmp;
}
if(dp[i - 1][j1][k1] + cost < dp[i][j2][k2])
{
dp[i][j2][k2] = dp[i - 1][j1][k1] + cost;
dp2[i][j2][k2] = j1;
dp3[i][j2][k2] = k1;
}
}
}
}
}
}
}
}
}
ansn = 1000000007;
for(int i = 0 ; i <= 25 ; i++)
{
for(int j = 0 ; j <= 25 ; j++)
{
if(dp[n][i][j] < ansn)
{
ansn = dp[n][i][j];
minj = i;
mink = j;
}
}
}
cout << ansn << '\n';
p = minj;
q = mink;
for(int j = n ; j >= 1 ; j--)
{
for(int i = 1 ; i <= m ; i++)
{
if(i % 2)
{
ans[j][i] = p + 'a';
}
else
{
ans[j][i] = q + 'a';
}
}
tmp1 = dp2[j][p][q];
tmp2 = dp3[j][p][q];
p = tmp1;
q = tmp2;
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cout << ans[i][j];
}
cout << "\n";
}
return 0;
}卡常
优化介绍
- 第
1 点，可以对模运算进行优化：- 若
n = 2^k ，且k 为非负整数，则代码a % n可以写为a & (n - 1)。
- 若
-
第
2 点，可以降低内存抖动：-
在电脑的 CPU 中，有
3 级 CaChe，最快的一级直接通往 CPU 进行运算，其余几级和更高一级 CaChe 进行数据交换，最低级 CaChe 和内存进程数据交换，所以我们可以通过降低交换次数来卡常。 -
在 GCC 编译器中，会优先把连续的内存位置拿进 CaChe，所以说让编辑的变量或数组尽量连续，就可以提高速度。
-
举个例子：下面这张图是我上面那份代码用
dp1和dp2存储答案的过程： -
然后我将
dp1和dp2合并进了dp，数组，并且加了一维来存储，那么存储会变为： -
所以有时对数组进行优化就会快很多。
-
最后补充一点，我们熟知的 O2 优化中的一部分优化就是调整你代码中申请空间的顺序。
-
优化后的参考代码:
#include<bits/stdc++.h>
#pragma GCC optimize(2)//卡常
using namespace std;
int n , m , dp[505][30][30][5] , memory[505][30][30] , ansn , minj , mink , p , q , tmp1 , tmp2 , cost , tmp;
char a[505][505] , ans[505][505];
int main()
{
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cin >> a[i][j];
}
}
for(int i = 0 ; i <= n ; i++)
{
for(int j = 0 ; j <= 'z' ; j++)
{
for(int k = 0 ; k <= 'z' ; k++)
{
if(!i)//卡常
{
dp[i][j][k][1] = 0;
}
else
{
dp[i][j][k][1] = 1000000007;
}
}
}
}
for(int i = 1 ; i <= n ; i++)
{
for(int j1 = 0 ; j1 <= 25 ; j1++)
{
for(int k1 = 0 ; k1 <= 25 ; k1++)
{
if(j1 != k1)//卡常
{
for(int j2 = 0 ; j2 <= 25 ; j2++)
{
if(j1 != j2)//卡常
{
for(int k2 = 0 ; k2 <= 25 ; k2++)
{
if(k1 != k2 && j2 != k2)
{
if(memory[i][j2][k2] != 0)
{
cost = memory[i][j2][k2];
}
else
{
tmp = 0;
for(int l = 1 ; l <= m ; l++)
{
if(l & 1)
{
tmp += (a[i][l] != j2 + 'a');
}
else
{
tmp += (a[i][l] != k2 + 'a');
}
}
memory[i][j2][k2] = tmp;
cost = tmp;
}
if(dp[i - 1][j1][k1][1] + cost < dp[i][j2][k2][1])
{
dp[i][j2][k2][1] = dp[i - 1][j1][k1][1] + cost;
dp[i][j2][k2][2] = j1;
dp[i][j2][k2][3] = k1;
}
}
}
}
}
}
}
}
}
ansn = 1000000007;
for(int i = 0 ; i <= 25 ; i++)
{
for(int j = 0 ; j <= 25 ; j++)
{
if(dp[n][i][j][1] < ansn)
{
ansn = dp[n][i][j][1];
minj = i;
mink = j;
}
}
}
cout << ansn << '\n';
p = minj;
q = mink;
for(int j = n ; j >= 1 ; j--)
{
for(int i = 1 ; i <= m ; i++)
{
if(i & 1)//卡常
{
ans[j][i] = p + 'a';
}
else
{
ans[j][i] = q + 'a';
}
}
tmp1 = dp[j][p][q][2];
tmp2 = dp[j][p][q][3];
p = tmp1;
q = tmp2;
}
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cout << ans[i][j];
}
cout << "\n";
}
return 0;
}优化后用时减少了