暑假集训 Day5 总结
前言：
数学题贼多，对于我来说十分的不友好。第二题也没看出它是个爆搜，第四题加了个剪枝还能 AC，今天痛失 分。
A.单次交换
这道题考场上蒙了个结论，错了， 分。
正解思路：
这道题真不应该没写出来，就是一个 map 的事。这道题的 是很好想的，但想要把它优化到 级别就要弄明白，每一层循环在干些什么。通过思考，我们可以发现，第二层循环可以通过一个 map 来存储。每一个字符都可以跟前面所有的不同的字符交换一次。特别的，如果有一个字符出现过两次，就可以通过相同字符交换多一个答案。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int ans = 0;
bool flag = false;
map<char, int> mp;
signed main() {
freopen("swap.in", "r", stdin);
freopen("swap.out", "w", stdout);
cin >> s;
s = " " + s;
for (int i = 1; i <= s.size() - 1; i++) {
ans += i - 1 - mp[s[i]];
mp[s[i]]++;
if (mp[s[i]] >= 2) {
flag = true;
}
}
cout << max(ans + flag, 1LL);
return 0;
}
B.开关
这道题考场上没想出是个 DFS，乱搞骗了 分。痛失 分！
正解思路：
就是爆搜，没有任何的含金量，只有含水量。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, ans;
int a[15][15];
int p[15];
int vis[15];
int check() {
for (int i = 1; i <= m; i++) {
int sum = 0;
for (int j = 1; j <= n; j++) {
if (vis[j] == 1 && a[j][i] == 1) {
sum++;
}
}
if (sum % 2 != p[i]) {
return 0;
}
}
return 1;
}
void dfs(int t) {
if (t > n) {
ans += check();
return ;
}
dfs(t + 1);
vis[t] = 1;
dfs(t + 1);
vis[t] = 0;
}
signed main() {
freopen("switch.in", "r", stdin);
freopen("switch.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int w;
cin >> w;
for (int j = 1; j <= w; j++) {
int x;
cin >> x;
a[x][i] = 1;
}
}
for (int i = 1; i <= m; i++) {
cin >> p[i];
}
dfs(1);
cout << ans;
return 0;
}
D.幸运数
这道题目比较可惜，原本的暴力代码加一个剪枝就能 AC。
正解思路：
正解也是我的暴力代码加一个剪枝······
AC 代码：
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 1e6+20;
int n, sum;
map<int, int> mp;
int vis[N], p[N], idx;
void f(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
p[++idx] = i;
}
for (int j = 1; p[j] <= n / i; j++) {
vis[p[j]*i] = 1;
if (i % p[j] == 0) {
break;
}
}
}
}
signed main() {
freopen("lucky.in", "r", stdin);
freopen("lucky.out", "w", stdout);
cin >> n;
f(1000000);
for (int i = 1; i <= idx; i++) {
for (int j = 1; j < i; j++) {
if (p[j] * p[i] * p[i] * p[i] > n) {
break;
}
sum++;
}
}
cout << sum;
return 0;
}
E.逻辑表达式
数学做这题代码量极少！！！
正解思路：
这里我们介绍一种 dp 的做法。如果当前的运算符为 AND，那么，，同时 $dp_{i,0} = dp_{i,0}+dp_{i-1,0}\times 2 + dp_{i-1,1}$。如果当前的运算符为 OR，那么，，同时 $dp_{i,1} =dp_{i,1}+ dp_{i-1,1}\times 2 + dp_{i-1,0}$。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
int op[65];
int dp[65][3];
signed main() {
freopen("expr.in", "r", stdin);
freopen("expr.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
if (s == "AND") {
op[i] = 1;
} else {
op[i] = 2;
}
}
dp[0][0] = 1;
dp[0][1] = 1;
for (int i = 1; i <= n; i++) {
if (op[i] == 1) {
dp[i][1] += dp[i - 1][1];
dp[i][0] = dp[i - 1][0] * 2 + dp[i - 1][1];
} else {
dp[i][0] += dp[i - 1][0];
dp[i][1] += dp[i - 1][1] * 2 + dp[i - 1][0];
}
}
cout << dp[n][1];
return 0;
}
F.空间跃迁
正解思路：
这道题目我们可以用动态规划的思路。创建一个三维动态规划数组，第一维表示目前跃迁了 次，第二维表示目前用方法一跃迁了 次，第三维表示目前用方法二跃迁了 次，由于四维数组会超空间，所以用第三种跃迁方式跃迁的次数为 。我们枚举三个维度，并同时算出 。通过 ，，求出当前的坐标。；。如果算出的坐标不是障碍，就对他进行 dp 状态转移。如果当前有进行第三种跃迁方式，那么 。如果当前有进行第一种跃迁方式，那么 $dp_{i,u,v} = dp_{i,u,v}+dp_{i-1,u-1,v}\bmod 998244353$。如果当前有进行第二种跃迁方式，那么 $dp_{i,u,v} = dp_{i,u,v}+dp_{i-1,u,v-1}\bmod 998244353$。如果当前是第 次跃迁，那么答案 加上 。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 320;
const int M = 998244353;
int dp[N][N][N];
int n, m, a, b, c, d, e, f, ans;
map<pair<int, int>, int> mp;
signed main() {
freopen("jump.in", "r", stdin);
freopen("jump.out", "w", stdout);
cin >> n >> m >> a >> b >> c >> d >> e >> f;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
mp[ {x, y}] = 1;
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int u = 0; u <= i; u++) {
for (int v = 0; v <= i - u; v++) {
int w = i - u - v;
int x = 1ll * a * u + 1ll * c * v + 1ll * e * w;
int y = 1ll * b * u + 1ll * d * v + 1ll * f * w;
if (!mp.count({x, y})) {
dp[i][u][v] = dp[i - 1][u][v];
if (u) {
dp[i][u][v] = (dp[i][u][v] + dp[i - 1][u - 1][v]) % M;
}
if (v) {
dp[i][u][v] = (dp[i][u][v] + dp[i - 1][u][v - 1]) % M;
}
if (i == n) {
ans = (ans + dp[n][u][v]) % M;
}
}
}
}
}
cout << ans;
return 0;
}
