本周进行了标准OI基础组模考测试
得分情况
| 题目名称 | 做法 | 预计得分 | 实际得分 |
|---|---|---|---|
| A 默认价格 | 哈希表 | 100 | 100 |
| B 贪吃蛇迷宫 | BFS搜索 | 100 | 100 |
| C 保持距离 | DFS搜索、数学优化 | 20 | 30 |
| D 单元格 | 数论 | 10 | 20 |
| E 补充括号 | 区间DP | 10 | 10 |
点开第一题，一开始有点不懂题目什么意思，后来懂了，用一个 map 存储价格即可
用时10分钟AC
第二题，是一个搜索题目，对于我来说搜索就是语法题，所以我很快写了一个 BFS 模版出来，一遍AC，耗时10分钟
接着看第三题，开始加难度了，赛中我有一个离谱的思路，就是先得出每次+10的序列，我们每次可以把一个数+1，这样后面的数都要+1（类似差分）
而且保证最后一个元素最大，而且每次不管在哪里做差分，他肯定会+1，所以我们只需要维护这个值不超过 m 即可
我们就可以把 m - 序列最后的值 看做可以把一个数+1的总次数，然后用搜索看一下用哪几个来++
但是我写了20分钟仍然阳历不过，一筹莫展，我只好换一个思路，就是直接每次枚举+几，别管什么差分了，直接爆搜！于是我吭哧吭哧写了2分钟爆搜，TLE30分，甚好甚好！
接下来看第四题，嗯，也是不会，思考了30分钟没有任何头绪
于是我没办法，为了思考下一题直接写了一个华丽的6重循环，TLE20分
接下来第5题，我还以为是括号匹配呢，结果写完栈的括号匹配不对，发现原来是区间DP，于是我吭哧吭哧写了一个区间DP模版，结果发现样例没过，然后我调试了好久也没调出来，只好输出一个0骗了10分
赛后我居然发现，我把判断的 “或者” 写错了，写成了 “并且”，把那个错误改过来就AC了
总结：
嗯，感觉表现其实不错，就是代码有一点小问题，写代码的时候要仔细一点，如果够仔细那么就能A掉最后一题
题目讲解
非常简单，用 map 哈希表存储每一个颜色的寿司的价格，随后枚举每一个吃了的寿司看一下价格，如果没有标注就加上 P_0 即可
code
map <string, int> mp;
cin >> p[0];
for (int i = 1 ; i <= m ; i++) {
cin >> p[i];
mp[d[i]] = p[i];
}
ll res = 0;
for (int i = 1 ; i <= n ; i++) {
if (!mp[c[i]]) {
res += p[0];
} else {
res += mp[c[i]];
}
}
cout << res << endl;
非常简单，直接用BFS搜索就可以，至于那个 snuke，判断一下就好啦！
code
char mp[510][510];
bool vis[510][510];
struct node {
int x, y, id;
};
string s = "snuke";
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
void bfs() {
queue<node> q;
q.push({1, 1, 0});
vis[1][1] = true;
while (!q.empty()) {
node now = q.front();
q.pop();
if (now.x == n && now.y == m) {
cout << "Yes" << endl;
return;
}
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && mp[nx][ny] == s[(now.id + 1) % 5]) {
vis[nx][ny] = true;
q.push({nx, ny, (now.id + 1) % 5});
}
}
}
cout << "No" << endl;
}
搜索加一点数论
首先写一个暴搜，随后我们分析一下：
- 题目的元素是十进制
- 而且两个相邻的数的差值最小是10
我们可以推导出，其实 m 不需要那么多数位，只需要1位（或10）
所以出入完 m 的时候 m=(m-1) mod 10+1 ，然后就——完结散花
code
vector<ll> v;
vector<vector<ll> > res;
inline void dfs(int x, int len) {
if (len > n) {
res.push_back(v);
// cout << "todo" << endl;
return;
}
for (int i = x; i <= m; i++) {
v.push_back(i);
// cout << "todo";
dfs(i, len + 1);
v.pop_back();
}
}
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
m = (m - 1) % 10 + 1;
dfs(1, 1);
cout << res.size() << endl;
想一想，如果我们暴力枚举每个点，时间复杂度是 O(n^6) ，绝对会超时
我们不妨换一个思路：
3个点一定能形成一个矩形，这个矩形周长就是他们的总共费用
示例：
所以我们枚举每一个矩形，看一下有多少个这样子的矩形（前提是矩形周长复合标准），记录一个值 k
看一看这个矩形得边上选3个不同位置的点的方案数，记录到 p
最后 ans=(ans+p \times k) mod 1000000007
而我们通过简单的推算，发现
k=(n-i+1)\times(m-j+1)
p=(i-2)\times (j-2)\times 6
所以这题就做完了
code
for (int i = 3 ; i <= n ; i++) {
for (int j = 3 ; j <= m ; j++) {
int c = i * 2 + j * 2 - 4;
if (c <= maxt && c >= mint) {
int k = (n - i + 1) * (m - j + 1);
int p = (i - 2) * (j - 2) * 6ll;
ans = (ans + p * k) % mod;
}
}
}
区间DP模版题
首先我们想，不管这个括号时什么，单独一个括号肯定是不合法的，需要添加一个匹配的括号
所以所有的 dp[i][i]=1
其次，我们发现，在某些情况下，一个区间的两半加起来就是答案
比如序列[[[)))，很明显dp[1][3] = dp[4][6] = 3，而dp[1][6] = dp[1][3] + dp[4][6] = 6
所以在选分割点的时候， dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]) 即所有情况都可能
但是有一种不是，比如[([])]，dp[2][5]就不能用刚才的推到公式了
因为两边的括号相匹配，所以我们就视为其没有，那么长度就会莫名其妙少了2，所以我们要向外扩充各1格
code
for(int i = 0;i < n;i++) dp[i][i] = 1;
for(int len = 2;len <= n;len++){
for(int l = 0;l + len - 1 < n;l++){
int r = l + len - 1;
dp[l][r] = 0x3f3f3f3f;
if((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')){
dp[l][r] = dp[l + 1][r - 1];
}
for(int k = l;k < r;k++){
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
}
}
}
cout << dp[0][n - 1];
