E – Lynyrd Skynyrd
题目大意
给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\)，处理\(q\)个询问：在数组的字段\([l,r]\)内是否存在排列的环形偏移。
解法
考虑正向扫描，处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置，并同时更新自己所在的位置供下一次循环进行使用：
Codeforces 1136D:Nastya Is Buying Lunch 题解
主要思路
这道题的主要做法就是贪心了。我们枚举\(i\)从\(n-1\)到\(1\)，记\(vis[i]\)为编号为\(i\)的节点是否可以转移、\(arr[i]\)为\(i\)位置上的数，在转移关系集中寻找\((i,j), vis[j]=true\)的\(j\)。由于我们是从后向前转移，所以我们找到的这些\(j\)的位置都是在\(i\)之后的，符合转移要求。之后我们验证目前已转移的答案\(ans\)与满足条件的关系个数\(cnt\)与\(i\)的和是否为\(n\)，如果符合意味着转移符合条件，便直接进行转移；如果不符合，那么我们把该点的标记打上，意味着可以从此被转移。
Codeforces Round #548 (Div. 2) 解题报告 (CF1139)
A – Even Substrings
很简单，扫描的时候如果所在数位为偶数位，向答案添加当前数位即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
int ans = 0, len;
scanf("%d", &len), scanf("%s", str + 1);
for (int i = 1; i <= len; i++)
if (((str[i] - '0') & 1) == 0)
ans += i;
printf("%d", ans);
return 0;
}
Codeforces 2B:The least round way 题解
主要思路
这道题我一开始写的是纯暴力，然后卡在了第 6 个点上失败。在看题解之前就已经感觉到这应该跟数学有关系。我先大概地说明主要方法，在数字输入时用数组\(dp2[][]和dp5[][]\)来记录这个数字包含因子\(2\)的个数和因子\(5\)的个数，然后尾部\(0\)的个数是\(min\{numOf(2),numOf(5)\}\)。然后我们可以分开进行处理，可以先处理\(dp2[][]\)数组并记录路径数组\(f2[][]\)，之后处理\(dp2[][]和f5[][]\)。统计答案时只需要比较\(dp2[n][n]和dp5[n][n]\)，回溯\(f2[][]或f5[][]\)即可。
但是还有一种情况，那就是数字矩阵包括\(0\)的情况。我们可以考虑在预处理的时候记录下数字\(0\)的坐标，最后只要\(min\{dp2[n][n],dp5[n][n]\}>1\)，就证明\(0\)才是最优解。
代码
// CF2B.cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const int MX_N = 1010;
ll mat[MX_N][MX_N], dp2[MX_N][MX_N], dp5[MX_N][MX_N], pow2[25], pow5[25], n, zeroFlag, zeroX, zeroY;
char ans[MX_N << 1];
struct vec
{
ll x, y;
} f2[MX_N][MX_N], f5[MX_N][MX_N];
void preprocess()
{
for (int i = 0; i < 25; i++)
pow2[i] = 1 << i;
pow5[0] = 1;
for (int i = 1; i < 25; i++)
pow5[i] = pow5[i - 1] * 5;
}
void processDp()
{
// start to program dynamically;
for (int i = 2; i <= n; i++)
dp2[0][i] = dp2[i][0] = dp5[0][i] = dp5[i][0] = 2e9;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ll vald = dp2[i - 1][j], valr = dp2[i][j - 1];
dp2[i][j] += min(vald, valr);
if (vald < valr)
f2[i][j] = vec{i - 1, j};
else
f2[i][j] = vec{i, j - 1};
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ll vald = dp5[i - 1][j], valr = dp5[i][j - 1];
dp5[i][j] += min(vald, valr);
if (vald < valr)
f5[i][j] = vec{i - 1, j};
else
f5[i][j] = vec{i, j - 1};
}
}
int main()
{
scanf("%lld", &n);
preprocess();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%lld", &mat[i][j]);
if (mat[i][j] == 0)
{
zeroFlag = true, zeroX = i, zeroY = j;
continue;
}
int tmp = mat[i][j];
for (int k = 24; k >= 0; k--)
if (tmp % pow2[k] == 0)
dp2[i][j] += k, tmp /= pow2[k];
if (tmp % 2 == 0)
dp2[i][j]++;
tmp = mat[i][j];
for (int k = 24; k >= 0; k--)
if (tmp % pow5[k] == 0)
dp5[i][j] += k, tmp /= pow5[k];
if (tmp % 5 == 0)
dp2[i][j]++;
}
processDp();
// process the answer;
if (zeroFlag && min(dp2[n][n], dp5[n][n]) > 1)
{
puts("1");
for (int i = 2; i <= zeroX; i++)
putchar('D');
for (int j = 2; j <= zeroY; j++)
putchar('R');
for (int i = zeroX + 1; i <= n; i++)
putchar('D');
for (int j = zeroY + 1; j <= n; j++)
putchar('R');
return 0;
}
// secondary answer;
printf("%d\n", min(dp2[n][n], dp5[n][n]));
int cx = n, cy = n, tot = 0;
for (int counter = 1; counter <= 2 * n - 1; counter++)
{
int fx = f2[cx][cy].x, fy = f2[cx][cy].y;
if (dp2[n][n] > dp5[n][n])
fx = f5[cx][cy].x, fy = f5[cx][cy].y;
if (cx > fx)
ans[counter] = 'D';
else
ans[counter] = 'R';
cx = fx, cy = fy;
}
for (int i = 2 * n - 2; i >= 1; i--)
printf("%c", ans[i]);
return 0;
}