本文写的不是很认真，没有详细写出题解，就是记录下做题心得而已，有错误大佬多多指教！！！
第一题 迷宫
一个小的填空题，考试直接数就行了（
或者dfs，bfs都能做
或者最暴力的方式循环也行，每个点都move100次看能不能出范围就行了
下面给出部分代码：
dfs、bfs写法：
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 110;
char g[N][N];
int ans;
bool st[N][N];
bool dfs(int x, int y)
{
if(x <= 0 || x > 10 || y <= 0 || y > 10) return true;
if(st[x][y]) return false;
st[x][y] = true;
if(g[x][y] == 'U') return dfs(x - 1, y);
if(g[x][y] == 'L') return dfs(x, y - 1);
if(g[x][y] == 'R') return dfs(x, y + 1);
if(g[x][y] == 'D') return dfs(x + 1, y);
return false;
}
bool check(int x, int y)
{
if(x < 1 || x > 10 || y < 1 || y > 10) return false;
return true;
}
bool bfs(int x, int y)
{
queue<PII> q;
q.push({x, y});
st[x][y] = true;
while(q.size())
{
auto t = q.front();
q.pop();
if(g[t.first][t.second] == 'U')
{
int a = t.first - 1, b = t.second;
if(!check(a, b)) return true;
else if(!st[a][b])
{
q.push({a, b});
st[a][b] = true;
}
}
else if(g[t.first][t.second] == 'L')
{
int a = t.first, b = t.second - 1;
if(!check(a, b)) return true;
else if(!st[a][b])
{
q.push({a, b});
st[a][b] = true;
}
}
else if(g[t.first][t.second] == 'R')
{
int a = t.first, b = t.second + 1;
if(!check(a, b)) return true;
else if(!st[a][b])
{
q.push({a, b});
st[a][b] = true;
}
}
else if(g[t.first][t.second] == 'D')
{
int a = t.first + 1, b = t.second;
if(!check(a, b)) return true;
else if(!st[a][b])
{
q.push({a, b});
st[a][b] = true;
}
}
}
return false;
}
int main()
{
for(int i = 1; i <= 10; i ++)
for(int j = 1; j <= 10; j ++)
cin >> g[i][j];
for(int i = 1; i <= 10; i ++)
for(int j = 1; j <= 10; j ++)
{
memset(st, false, sizeof st);
//if(dfs(i, j)) ans ++;
if(bfs(i, j)) ans ++;
}
cout << ans << endl;
}
最暴力的循环方式也可：
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char g[12][12];
string s = "UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR";
void move(char c, int &i, int &j)
{
if(c == 'U') i --;
if(c == 'R') j ++;
if(c == 'L') j --;
if(c == 'D') i ++;
}
bool check(int x, int y)
{
if(x < 1 || x > 10 || y < 1 || y > 10) return false;
return true;
}
int main()
{
int tot = 0;
for(int i = 1; i <= 10; i ++)
for(int j = 1; j <= 10; j ++)
g[i][j] = s[tot ++];
int ans = 0;
for(int i = 1; i <= 10; i ++)
for(int j = 1; j <= 10; j ++)
{
int a = i, b = j;
int cnt = 0;
while(cnt <= 110 && check(a, b))
{
char c = g[a][b];
move(c, a, b);
cnt ++;
}
if(cnt > 100) ans ++;
}
cout << 100 - ans << endl;
return 0;
}
反正很容易嘛。
第二题：跳蚱蜢
两个点：1.盘子就一个，题目让蚱蜢跳盘子，不如让盘子跳蚱蜢；
2.原来是圆圈状，化⚪为直线；
分析：这里的跳：不管跳一个还是跳两个，可以看成空盘子和原数交换位置就行。
我们把原序列看成012345678,跳跃一次的可能结果：
102345678、210345678、812345670、712345608
最终的目标是：087654321
0~8， 9个数全排列，一共有$9!$种可能所以暴力可解；
但是中间每一步可能会跳到与前面的某步相同，而且可能性很大，所以要判重！这里直接用map就行。
在这的bfs，就是每次，每次可以进行四次变换，来改变整体的状态，最总达到某个指定的状态。
很easy的，懒得写了，鸽了鸽了，并且这题答案是20，貌似手算也能给搞出来。
第三题 魔方状态
我觉得是最难的题了，数学菜狗不会算，只能模拟，但太耽误时间，还容易写错，本来魔方玩的就不好（鸽鸽鸽
第四题 方格分割
分析可知：分割线一定经过6*6的中心，（3，3），从此开始dfs，算作一次合理的分割方法是：x,y任意一个到达0或者6即可。每走一步要把对称的位置也给标记为不能走，最终答案再除以4。（可能左上、右上、左下、右下）
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int ans;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
void dfs(int x, int y)
{
if(x == 0 || y == 0 || x == 6 || y == 6)
{
ans ++;
return;
}
//if(x < 0 || y < 0 || x > 6 || y > 6) return;
for(int i = 0; i < 4; i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a > 6 || b < 0 || b > 6) continue;
if(st[a][b]) continue;
st[a][b] = true;
st[6 - a][6 - b] = true;
dfs(a, b);
st[a][b] = false;
st[6 - a][6 - b] = false;
}
}
int main()
{
st[3][3] = true;
dfs(3,3);
cout << ans / 4<<endl;
}
第五题 dp填空题
不说了，有手就行的填空题
第六题 dp填空题
最大的公共子串
a就是平时写的dp/f, a[i][j]表示的是以$s$[HTML_REMOVED]$1$[HTML_REMOVED]$[i]$和$s$[HTML_REMOVED]$2$[HTML_REMOVED]$[j]$结尾的两个字串结尾的公共子串的$Max$。
转移方程:
$s$[HTML_REMOVED]$1$[HTML_REMOVED]$[i]$ $!=$ $s$[HTML_REMOVED]$2$[HTML_REMOVED]$[j]$ ，则 $a[i][j]$ $=$ $0$;
$s$[HTML_REMOVED]$1$[HTML_REMOVED]$[i]$ $==$ $s$[HTML_REMOVED]$2$[HTML_REMOVED]$[j]$ ，则 $a[i][j]$ $=$ $a[i-1][j-1]$ $+$ $1$。
第七题 正则问题
解释下样例：
正则表达式，又称规则表达式，通常被用来检索、替换符合某个模式(规则)的文本。
比如题目中由 x ( ) | 组成的正则表达式，括号“()”的优先级最高，或操作“|”次之。括号里面是一个整体，或的两边保留最长的一个。
((xx|xxx)x|(x|xx))xx是怎么执行的，为什么是6呢？
先执行括号，再执行或， 步骤是：
（1）先看第一个括号，发现里面还有嵌套括号，找到最内部的括号，括号内是一个或操作。($(xx|xxx)$x|(x|xx))xx，得：(xxxx|(x|xx))xx
（2）继续执行最内部括号。(xxxx|$(x|xx)$)xx，得：(xxxx|xx)xx
（3）继续执行最后括号。$(xxxx|xx)$xx，得：xxxxxx，结束，得长度为6的字符串。
本题有四种符号(,x,|,)。
(：进栈，进行一次递归dfs
)：出栈，和(相对应，完成一次递归，直接break掉就行
|：进行比较
x：统计个数就行了
代码：
#include<bits/stdc++.h>
using namespace std;
string s;
int i = 0;
int dfs(){
int cnt = 0, ans = 0;
while(i < s.size()){
if(s[i] == '(')
{
i++;
cnt += dfs();
}
else if(s[i] == ')')
{
i++;
break;
}
else if(s[i] == '|')
{
i++;
ans = max(ans, cnt);
cnt = 0;
}
else
{
i++;
cnt++;
}
}
ans = max(ans, cnt);
return ans;
}
int main(){
cin >> s;
cout << dfs() << endl;
return 0;
}
第8题 包子凑数
这题就是一个完全背包的问题：
知道一个数学结论：两个数$a,b$（当$gcd=1$时）最大不能表示出来的 数是：$(a−1)(b−1)−1$,根据数据范围，直接枚举到10000即可。
这里的状态定义也挺特殊的，不过很容易想到（
$f[i][j]$表示从前$i$个数中选，目标总质量为$j$,属性是能否达到$j$。（$true/false$）
状态转移：按照第i个物品选的数量来进行划分（
$f[i][j]$ $=$ $f[i - 1][j] | f[i - 1][j - w[i]] | f[i - 1][j - 2 * w[i]] | … | f[i - 1][j - k * w[i]]$;
和完全背包的优化一样:
$f[i][j - w[i]]$ = $f[i - 1][j - w[i]] | f[i - 1][j - 2 * w[i]] | f[i - 1][j - 3 * w[i]] | … | f[i - 1][j - k * w[i]]$;
优化：
$f[i][j]$ $=$ $f[i -1][j] | f[i][j - w[i]]$;
到一维：
$f[j] |= f[j - w[i]]$;
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10000;
int a[N], n;
bool f[M + 10];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n;
int d = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
d = gcd(d, a[i]);
}
if(d != 1) puts("INF");
else
{
f[0] = true;
for(int i = 1; i <= n; i ++)
for(int j = a[i]; j <= M; j ++)
f[j] |= f[j - a[i]];
int res = 0;
for(int i = 0; i <= M; i ++)
if(!f[i]) res ++;
cout << res << endl;
}
return 0;
}
第九题：分巧克力
就一二分板子题：
懒得写思路了，直接上代码（
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int h[N], w[N];
bool check(int x)
{
int ans = 0;
for(int i = 0; i < n; i ++)
{
ans += (h[i] / x) * (w[i] /x);
}
if(ans >= k) return true;
return false;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++) cin >> h[i] >> w[i];
int l = 1, r = 1e5;
while(l < r)
{
int mid = l + r + 1>> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << r << endl;
return 0;
}
第十题 油漆面积
标准做法是扫描线+线段树自己没写（
本题数据非常水，所以最暴力，最好想的方法就可：
就是把每个矩形划分成n个$1*1$小方格即可，每读入一个标记一个即可（
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
bool st[N][N];
int n, sum;
int main()
{
cin >> n;
while(n --)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if(x1 > x2) swap(x1, x2);
if(y1> y2) swap(y1, y2);
for(int i = x1;i < x2; i ++)
for(int j = y1; j < y2; j ++)
if(!st[i][j])
{
sum++;
st[i][j]=1;
}
}
cout << sum << endl;
return 0;
}
总结除了第三题比较难，其余都算比较简单（
