#include
#include
#include
using namespace std;
int main()
{
int x = 0, y = 0;
int sum = 0x3f3f3f3f;
for(int i = 2019 + 1; i <= 10000 ; i ++)
for(int j = i + 1; j <= 10000; j ++)
{
if(i * i - 2019 * 2019 == j * j - i * i)
sum = min(i + j, sum);
}
cout << sum << endl;
return 0;
}
答案：7020
B.质数拆分
题目解析：
题意：求2019拆分为若干个不同质数之和的方案数
分析：我们可以先求出1-2019的所有质数，将该问题转换为从1-2019的质数中选，总和为2019的所有方案。这时候是不是就很像01背包了。
01背包动态规划：
状态表示：从前i个质数中选，且总和为j的集合的数量（数量是状态表示的属性）
状态计算：对于f [i，j]，它的转移方案由f [i - 1，j]（不选第i个质数）和f [i - 1，j - prime[i]](选第i个质数）转移过来，所以f [i，j] = f [i - 1，j] + f[i - 1，j - prime[i]]
#include
#include
using namespace std;
const int N = 5000;
typedef long long LL;
int prime[N];
int idx = 1;
LL f[N][N];
bool st[N];
void get_primes(int x) //线性筛质数
{
for(int i = 2; i <= x; i ++)
{
if(!st[i]) prime[idx ++] = i;
for(int j = 1; prime[j] <= x / i; j ++)
{
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
int main()
{
get_primes(2019);
f[0][0] = 1;
for(int i = 1; i < idx; i ++)
for(int j = 0; j <= 2019; j ++)
{
f[i][j] = f[i - 1][j];
if(prime[i] <= j) f[i][j] += f[i - 1][j - prime[i]]; //也可以转换为一维，但在该题中没有必要。
}
cout << f[idx - 1][2019] << endl;
return 0;
}
答案：55965365465060
D.求值
题目解析：
我们可以从1开始枚举，枚举到第一位满足约数个数为100的数，把该数输出即可。
#include
#include
using namespace std;
int main()
{
for(int i = 100; i; i ++)
{
int cnt = 0;
int temp = i;
for(int j = 1; j <= temp / j; j ++)
{
if(temp % j == 0)
{
if(j == temp / j) //注意特判j == temp / j的情况，这时约数个数只会＋1
cnt ++;
else
cnt += 2;
}
}
if(cnt == 100)
{
cout << i << endl;
return 0;
}
}
}
答案：45360
E.路径计数
题目解析：
题意：从5X5的方格矩阵中以（1，1）为起点，（1，1）为终点的方案数，每个方案数应该满足题意
考虑到边长为5，我们可以考虑dfs暴力搜索
根据每个条件选择我们要记录的值：
1.总长度不超过12，用step记录我们的步数
2.返回左下角：判断x==1？y==1?
3.路线不自交：用st数组来记录该线段在该次搜索中有没有在之前被走过（注意：要恢复原状，保证下次搜索的正确性）
4.不能越界：加判断条件
#include
#include
using namespace std;
const int N = 10;
bool st[N][N];
int ans;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void dfs(int x, int y, int step)
{
if(step <= 12 && step > 2 && st[x][y])
{
if(x == 1 && y == 1)
{
ans ++;
}
}
if(step > 12)
return ;
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx < 1 || nx > 6 || ny < 1 || ny > 6)
continue;
if(st[nx][ny])
continue;
st[nx][ny] = true;
dfs(nx, ny, step + 1);
st[nx][ny] = false; //状态恢复的过程
}
}
int main()
{
dfs(1, 1, 0);
cout << ans << endl;
}
答案：206
F.最优包含
题目解析：
题意：给定两个字符串S、T，求S中至少修改多少个字符串之后能够通过抽取若干个字符变成T
分析：该题目是经典题目《编辑距离》的简化版
我们可以看成：对于S字符我们有两个操作，删除Si和修改Si，其代价分别为0，1，求让S与T匹配的最小代价
动态规划：
状态表示：f [i，j]：S的前i个字符等于T的前j个字符的最小操作数
考虑所有能转移到f[i，j]的状态，对于f[i，j]，只能从删除S的第i个字符、修改S的第i个字符和不做任何操作转移过来
对于删除S的第i个字符转移过来的f [i，j]：f [i ， j] = f [i - 1, j] + 0（删除操作的代价为0）
对于修改S的第i个字符转移过来的f [i，j]：f [i ，j] = f [i - 1, j - 1] + 1（修改操作的代价为1）
对于不做任何操作转移过来的f[i，j]： f [i ，j] = f [i - 1，j - 1]
我们可以把修改和不做任何操作归并为一类，代码如下
#include
#include
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
char a[N];
char b[N];
int main()
{
cin >> a + 1 >> b + 1;
n = strlen(a + 1);
m = strlen(b + 1);
memset(f, 0x3f, sizeof f); //状态表示中的属性为最小值，所以我们要初始化为正无穷
for(int i = 1; i <= n; i ++) f[i][0] = 0; //表示删除前i - 1个字符从Si开始与之T匹配的代价
f[0][0] = 0; //未开始匹配的操作数
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
int temp = 0;
if(a[i] == b[j]) temp = 0; //temp为0,则为不做任何操作的状态转移过来
else temp = 1; //修改操作的代价
f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + temp);
}
cout << f[n][m] << endl;
return 0;
}
G.排列数
题目解析：
题意：给定n，k，让我们求元素个数为n，1 - n的全排列中有k - 1个山峰或者山谷（山峰：该数比旁边两数大，山谷：该数比旁边两数小）的个数
分析：
这道题我没有写出来，参考了AcWing 2554. 排列数 $O(n^2k)$ DP （可能更好理解） - AcWing的题解
动态规划：
设f [i，j，k，0/1]表示前i - 1个数已经排好，且最后一个数为j的k单调序列的最后两个数递增或者递减的所有集合
考虑从 f[i - 1][r][k][0 / 1] 进行转移，将 r 分成以下几种情况：
如果 r 那么我们将 j 填入该排列后，最后两个数递增。再考虑原排列中最后两个数是否递增。
1. 如果递增，则放入 j 后，折点数不增加，那么有 f[i][j][k][1] += f[i - 1][r][k][1]
2. 如果递减，则放入 j 后，折点数增加，那么有 f[i][j][k][1] += f[i - 1][r][k - 1][0]
如果 r≥jr≥j
那么我们将 j 填入该排列后，最后两个数递减。再考虑原排列中最后两个数是否递增。
1. 如果递增，则放入 j 后，折点数增加，那么有 f[i][j][k][0] += f[i - 1][r][k - 1][1]
2. 如果递减，则放入 j 后，折点数不增加，那么有 f[i][j][k][0] += f[i - 1][r][k][0]
最后再用前缀和数组S维护f[i][r][k][0/1]
#include
#include
const int N = 505;
const int mod = 123456;
int n, m;
int f[2][N][N][2];
int s[2][N][N][2];
int main()
{
scanf("%d%d", &n, &m);
f[1][1][1][0] = 1;
f[0][1][1][0] = f[0][2][1][1] = 1;
s[0][1][1][0] = s[0][2][1][0] = s[0][2][1][1] = 1;
for (int i = 3; i <= n; i ++ )
{
memset(f[i & 1], 0, sizeof f[0]);
memset(s[i & 1], 0, sizeof s[0]);
for (int j = 1; j <= i; j ++ )
for (int k = 1; k <= i && k <= m; k ++ )
{
(f[i & 1][j][k][1] += s[i - 1 & 1][j - 1][k][1] + s[i - 1 & 1][j - 1][k - 1][0]) %= mod;
(f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k][0] - s[i - 1 & 1][j - 1][k][0]) %= mod;
(f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k - 1][1] - s[i - 1 & 1][j - 1][k - 1][1]) %= mod;
s[i & 1][j][k][0] = (s[i & 1][j - 1][k][0] + f[i & 1][j][k][0]) % mod;
s[i & 1][j][k][1] = (s[i & 1][j - 1][k][1] + f[i & 1][j][k][1]) % mod;
}
}
printf("%dn", ((s[n & 1][n][m][0] + s[n & 1][n][m][1]) % mod + mod) % mod);
return 0;
}
H.解谜游戏
题目解析
题意：给定一外圈，中圈，内圈，我们可以顺时针、逆时针同时旋转外、中、内圈，也可以把三圈中位置为 0 的灯管内外方向做一个循环移动，问我们能否使得所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。
分析：我们可以发现不论如何旋转，我们进行交换的点都会是该圈的下标%4的值相同的点，所以我们可以判断对于这些下标组成的点，绿==3？红==2？黄==1？若满足，我们可以在有限次旋转和交换操作中使得绿色全部移动到外圈，红色全部移动到中圈，黄色移动到内圈
#include
#include
#include
using namespace std;
int t;
string a, b, c;
int cnt[4][3];
void add(string a)
{
for(int i = 0; i < a.size(); i ++)
{
if(a[i] == 'G')
cnt[i % 4][0] ++;
else if(a[i] == 'R')
cnt[i % 4][1] ++;
else
cnt[i % 4][2] ++;
}
}
int main()
{
cin >> t;
while(t --)
{
cin >> a >> b >> c;
bool is_total = true;
memset(cnt, 0, sizeof cnt);
add(a), add(b), add(c);
for(int i = 0; i < 4; i ++)
{
//绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈
if(cnt[i][0] != 3 || cnt[i][1] != 2 || cnt[i][2] != 1)
{
is_total = false;
break;
}
}
if(is_total) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
I.第八大奇迹
题目解析：
（最近正好在学习线段树，正好可以用这题练手）
分析：
对于这种单点修改，区间查询的题目很容易联想到树状数组和线段树，我们这里很容易就可以发现树状数组很难去维护我们的查询操作。
所以我们用线段树来解决这一题
对于线段树，我们要考虑需要维护什么值才能保证答案的正确性。
l，r是肯定的，我们这里还需要维护一个长度为8的数组，来存储该区间的第八大的数
而且对于该题可以发现我们不需要用懒标记去把父节点的值去更新子节点的值，只需要pushup操作把子节点的值去更新父节点。
代码如下
#include
#include
#include
using namespace std;
const int N = 100010;
struct Node
{
int l, r;
int v[8];
}tr[4 * N];
int n, m;
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void pushup(Node &t, Node &l, Node &r)
{
int i = 0, j = 0, k = 0;
while(i < 8 && j < 8 && k < 8)
{
if(l.v[i] < r.v[j]) t.v[k ++] = r.v[j ++];
else t.v[k ++] = l.v[i ++];
}
if(k < 8 && j < 8) t.v[k ++] = r.v[j ++];
if(k < 8 && i < 8) t.v[k ++] = l.v[i ++];
}
void modify(int u, int x, int c)
{
if(tr[u].l == x && tr[u].r == x) tr[u].v[0] = c;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= x) modify(u << 1, x, c);
else modify(u << 1 | 1, x, c);
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
}
Node query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(mid >= r) return query(u << 1, l, r);
else if(mid < l) return query(u << 1 | 1, l, r);
else
{
Node ans;
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
pushup(ans, left, right);
return ans;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
build(1, 1, n);
while(m --)
{
char op[2];
int l, r;
cin >> op >> l >> r;
if(*op == 'C')
{
modify(1, l, r);
}
else
{
cout << query(1, l, r).v[7] << endl;
}
}
return 0;
}
最后分享一下分析时打的草稿：
