枚举贺题记录
练一练搜索水题
按照你谷上的能力提升综合题单来写的
暴力枚举
洛谷P1019 单词接龙
description:
如果两个单词之间有重叠部分 那么就可以拼接起来 两个单词不能q是包含关系
给定n个单词和一个字母k 问k起始的最长接龙是多长 每个单词最多使用两遍
Solution:
显然重叠的部分是越短越好
code
#include <bits/stdc++.h>
int check(char *s1, char *s2) {
int len1 = strlen(s1), len2 = strlen(s2);
for (int i = 1; i < min(len1, len2); i++){
bool flag = true;
for (int j = 0; j < i; j++) if (s1[len1-i+j] != s2[j]) {flag=false; break;}
if (flag) return i;
}
return 0;
}
int ans;
int n, tot[22];
char s[22][30];
void dfs(char *now, int len) {
ans = max(ans, len);
for (int i = 1; i <= n; i++) {
if (tot[i] == 2) continue;
int pos = check(now, s[i]);
if (pos == 0) continue;
tot[i]++;
dfs(s[i], len+strlen(s[i])-pos);
tot[i]--;
}
}
int main() {
// cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%s", s[i]);
scanf("%s", s[0] + 1);
s[0][0] = '%';
dfs(s[0], 1);
cout << ans;
return 0;
}
刚开始上手没读请题目 一顿敲键盘不知道在写什么...
一没有从后往前拿 而没有考虑必须打头的字母
浪费了好久的时间..
洛谷P5194 Scales S
solution
用的折半枚举 但还没一个迷惑的剪枝快 我不理解
能选的权值单调递增并且a[i+3]>=a[i+1]+a[i+2]恒成立 所以倒着拿会更容易拿到范围内的最大值
估计也是因为这个性质 加一个判断前缀和的就跑的飞快..
N理论上不超过43 还是练了下折半枚举 实际数据可能都不超过30
折半枚举的 没有从后往前拿 就当是写板子了
const int N = (1<<22)+5;
long long a[45], s1[N], s2[N];
long long C, ans, n, tot1, tot2;
void dfs(int l, int r, long long s, long long v[], long long &tot) {
if (s > C) return;
if (l > r) {v[++tot] = s; return;}
dfs(l + 1, r, s + a[l], v, tot);
dfs(l + 1, r, s, v, tot);
}
int main() {
cin >> n >> C;
// tot1 = tot2 = ans = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1, n / 2, 0, s1, tot1);
dfs(n / 2 + 1, n, 0, s2, tot2);
sort(s1 + 1, s1 + 1 + tot1);
ans = s1[tot1];
for (int i = 1; i <= tot2; i++) {
long long now = C - s2[i];
int pos = upper_bound(s1 + 1, s1 + 1 + tot1, now) - s1 - 1;
ans = max(ans, s1[pos]+s2[i]);
}
cout << ans << endl;
return 0;
}
洛谷P5440 [XR-2]奇迹
description
T组测试数据 每次给定一个长为8位的数字 表示一个日期 YYYYMMDD的形式
每个位置上是固定的数字或者 - 表示可以填写任何数字
问有多少种可能的情况满足 DD是质数 MMDD是质数 YYYYMMDD是质数
solution
tnnd用爆搜写了快一下午 要不就是segment fault要不就是发现自己写假了
自闭一下午 写的破东西狗看了都摇头
后来受不了了 构造解然后对照一下 没有用线性筛预处理 勉强卡进1s
const int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int T, n;
bool IsPrime(int x) {
if (x == 1) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
bool check(int x) {
return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0);
}
bool check(int x, char *s) {
for (int i = 8; i >= 1; x /= 10, i--) {
if (s[i] == '-') continue;
if (s[i] - '0' != x % 10) return false;
}
return true;
}
int main() {
std::vector<int> v1, v2, v;
for (int i = 1; i <= 9999; i++) {
v1.push_back(i);
}
for (int i = 1; i <= 12; i++) {
for (int j = 1; j <= day[i]; j++) {
int x = i * 100 + j;
if (IsPrime(x) && IsPrime(j)) v2.push_back(x);
}
}
for (auto x : v1) {
for (auto y : v2) {
if (!check(x) && y == 229) continue; // 润！
if (IsPrime(x * 10000 + y)) {
v.push_back(x * 10000 + y);
}
}
}
cin >> T;
for (int cs = 1; cs <= T; cs++) {
char s[10];
scanf("%s", s + 1);
int ans = 0;
for (auto x : v) ans += check(x, s);
cout << ans << endl;
}
}
rnm tq！
洛谷P1378 油滴扩展
solution
全排列 题目要求输出剩余空间 被晃了一下
next_permutation
#define PI 3.1415926535
const int N=10;
int a[N];
int n;
double x[10], y[10], r[10];
double xl, xr, yl, yr, ans;
double g1, g2, g3, g4;
vector <int> rec;
int pre(double x) {
x *= 10;
if ((int)x % 10 >= 5) x += 10;
x = (int)(x) / 10;
return (int)(x);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) a[i] = i;
cin >> g1 >> g2 >> g3 >> g4;
xl = min(g1, g3); xr = max(g1, g3);
yl = min(g2, g4); yr = max(g2, g4);
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
ans = 0;
do {
rec.clear();
for (int i = 1; i <= n; i++) r[i] = 0.0;
for (int i = 1; i <= n; i++) {
double x2 = x[a[i]], y2 = y[a[i]];
double R = 0x7fffffff;
if (!rec.empty()) {
for (auto it : rec) {
double x1 = x[it], y1 = y[it];
double d = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
R = min(R, max(d - r[it], 0.0));
}
}
R = min(R, abs(x2 - xl)); R = min(R, abs(x2 - xr));
R = min(R, abs(y2 - yl)); R = min(R, abs(y2 - yr));
r[a[i]] = R; rec.push_back(a[i]);
}
double tem = 0;
for (int i = 1; i <= n; i++)
tem += r[i] * r[i] * PI;
ans = max(ans, tem);
} while (next_permutation(a + 1, a + 1 + n));
cout << pre((xr - xl) * (yr - yl) - ans);
return 0;
}
洛谷P1443 马的遍历
solution
按时间顺序BFS即可
const int X[8] = {2, 1, 2, 1, -2, -1, -2, -1};
const int Y[8] = {-1, -2, 1, 2, 1, 2, -1, -2};
queue < pair <int, int> > q;
int n, m, x, y;
int f[410][410];
bool vis[410][410];
int main() {
cin >> n >> m >> x >> y;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
f[i][j] = -1, vis[i][j] = false;
f[x][y] = 0; vis[x][y] = true; q.push({x, y});
while (!q.empty()) {
int xx = q.front().first, yy = q.front().second; q.pop();
for (int i = 0; i < 8; i++) {
int _x = xx + X[i] , _y = yy + Y[i];
if (vis[_x][_y] || _x < 1 || _x > n || _y < 1 || _y > m) continue;
vis[_x][_y] = true; q.push({_x, _y}); f[_x][_y] = f[xx][yy] + 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%-5d", f[i][j]);
puts("");
}
return 0;
}
P3956 [NOIP2017 普及组] 棋盘
solution:
对于需要施展魔法的选择 选择和当前位置一样的颜色 贡献肯定是最优的
然后正常BFS即可
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
struct Point {
int x,y,c,s;
};
queue <Point> q;
int m,n;
int x,y,c,s,ans=0x7fffffff;
int mp[105][105],sum[105][105];
int main() {
cin>>m>>n;
memset(mp,-1,sizeof(mp));
memset(sum,0x7f,sizeof(sum));
for (int i=1; i<=n; i++) {
cin>>x>>y>>c;
mp[x][y]=c;
}
q.push((Point){1,1,mp[1][1], 0});
while (!q.empty()) {
x=q.front().x, y=q.front().y;
c=q.front().c, s=q.front().s; q.pop();
if (s > ans) continue;
if (x==m && y==m) {
ans = min(ans, s);
continue;
}
for (int i=0; i<4; i++) {
int xx=x+dx[i], yy=y+dy[i];
if (xx<1 || xx>m || yy<1 || yy>m)
continue;
int st=mp[x][y], ed=mp[xx][yy], ss=sum[xx][yy], cs;
if (st>=0 && ed>=0) { // 合理移动
cs=s+(st==ed?0:1);
if(cs<ss){
q.push((Point){xx,yy,ed,cs});
sum[xx][yy]=cs;
}
} else if(st>=0 && ed<0) { // 施展魔法 [doge]
if (s+2<ss) {
q.push((Point){xx,yy,st,s+2});
sum[xx][yy]=s+2;
}
} else if(st<0 && ed>=0){
cs=s+(c==ed?0:1);
if (cs<ss) {
q.push((Point){xx,yy,ed,cs});
sum[xx][yy]=cs;
}
}
}
}
if (ans==0x7fffffff) cout<<"-1";
else cout<<ans;
return 0;
}
洛谷 P1032 [NOIP2002 提高组] 字串变换
solution1:
BFS 正常的替换队头能替换的部分 如果是重复出现的字符串忽略 即可
但是莫名其妙被卡了最后第5个点
发现是map炸了 因为我用 map<stirng,int> 去保存对应的string需要的步数
在这个基础上做一些奇怪的剪枝 老刻舟求剑了 BFS本身就是随时间递增 答案肯定是最优的
然后45ms -> 1.2s 一开始还怀疑到string的push_back上去了 hhhh
#include <bits/stdc++.h>
using namespace std;
string start, target;
string a[10], b[10];
int tot;
map<string, int>mp;
queue<pair<string,int>>q;
int main() {
tot = 1;
cin >> start >> target;
while (cin >> a[tot] >> b[tot]) tot++;
tot--;
q.push({start,0});
string x, y, z;
int step;
int ans=-1;
while(!q.empty()) {
x = q.front().first;
step = q.front().second;
q.pop();
if (mp.count(x) == 1) continue;
if (x==target) {ans=step; break;}
mp[x] = 1;
for (int k = 1; k <= tot; k++) {
y = a[k], z = b[k];
for (int i = 0; i <= max(-1, (int)(x.size() - y.size())); i++) {
if (x[i] == y[0]) {
bool flag = true;
for (int j = 0;j < (int)y.size(); j++)
if (x[i+j] != y[j]) {flag = false; break;}
if (flag) {
string ans="";
int siz=-1;
for (int j = 0; j < i; j++) ans+=x[j];
for (int j = 0; j < (int)z.size(); j++) ans+=z[j];
for (int j = i + y.size(); j < (int)x.size(); j++) ans+=x[j];
q.push({ans, step + 1});
}
}
}
}
}
if (ans==-1||ans>10) puts("NO ANSWER!");
else cout << ans;
return 0;
}
洛谷 P1126 机器人搬重物
solution:
正常BFS 每一步走 1 2 3步或者转向
记录每个点以及朝向情况来判重
注意机器人在网格上走 本身有宽度 不能碰壁 障碍物是网格 标记要打给四个角
char ch;
int n, m, step;
int sx, sy, ex, ey;
const int dx[][3] = {{0, 0, 0}, {-1, -2, -3}, {0, 0, 0}, {1, 2, 3}};
const int dy[][3] = {{-1, -2, -3}, {0, 0, 0}, {1, 2, 3}, {0, 0, 0}};
bool a[55][55], vis[55][55][5];
struct Node {
int x, y, d;
};
queue<pair<Node,int>>q;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == true)
a[i-1][j] = a[i-1][j-1] = a[i][j-1] = true;
}
}
cin >> sx >> sy >> ex >> ey >> ch;
Node g; a[sx][sy] = 1;
if (ch == 'W') g.d = 0;
if (ch == 'E') g.d = 2;
if (ch == 'N') g.d = 1;
if (ch == 'S') g.d = 3;
g.x = sx, g.y = sy;
vis[sx][sy][g.d] = 1;
q.push({g, 0});
while (!q.empty()) {
g = q.front().first;
int x, y;
step = q.front().second;
q.pop();
if (g.x == ex && g.y == ey) {
cout << step << endl;
return 0;
}
for (int i = 0; i < 3; i++) { // 走三步
x = g.x + dx[g.d][i], y = g.y + dy[g.d][i];
if (x < 1 || x >= n || y < 1 || y >= m || a[x][y]) break;
if (vis[x][y][g.d]) continue;
vis[x][y][g.d] = true;
q.push({(Node){x, y, g.d}, step + 1});
}
int D = g.d + 1;
if (g.d + 1 == 4) D = 0;
if (!vis[g.x][g.y][D])
vis[g.x][g.y][D] = true, q.push({(Node){g.x, g.y, D}, step + 1});
D = g.d - 1;
if (g.d - 1 == -1) D = 3;
if (!vis[g.x][g.y][D])
vis[g.x][g.y][D] = true, q.push({(Node){g.x, g.y, D}, step + 1});
}
puts("-1");
return 0;
}
记忆化搜索
这个基础的东西 之前每次碰到的时候 都是下次一定
以至于我还从来没写过一道记搜的题目
说起来这个是dp的思路 为什么分类在搜索里面 emmm
没必要当一个 algorithm lawyer 斤斤计较
洛谷日报的教学 也就是OIwiki上的 讲的还行
现在的理解就是记搜就是利用重叠的信息 降低复杂度
洛谷 P1514 [NOIP2010 提高组] 引水入城
每个起点能够覆盖的路径不会发生交叉
如果分叉 有地方留不到 那么这个点就寄了 之后的源点也覆盖不了它
那么产生的区间就是左端点单调递增的
记搜的时候 如果一个点已经搜过了 那么这个点维护的左端点和右端点信息可以直接拿来用
最后贪心一下即可
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int n, m, cnt, L = 0, R;
bool vis[505][505], flag;
int main() {
cin >> n >> m;
vector h(n, vector<int>(m)), l(n, vector<int>(m, 0x3f3f3f3f)), r(n, vector<int>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> h[i][j];
for (int i = 0; i < m; i++)
l[n-1][i] = r[n-1][i] = i;
auto bfs = [&](auto self, int x, int y) -> void {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= m || h[xx][yy] >= h[x][y]) continue;
if (vis[xx][yy] == false) self(self, xx, yy); // 记搜部分 可以利用到已经搜过的部分
l[x][y] = min(l[x][y], l[xx][yy]);
r[x][y] = max(r[x][y], r[xx][yy]);
}
};
for (int i = 0; i < m; i++)
if (vis[0][i] == false)
bfs(bfs, 0, i);
for (int j = 0; j < m; j++)
if (vis[n-1][j] == false)
flag = true, cnt++;
if (flag) {
cout << '0' << '\n' << cnt << '\n';
return 0;
}
while (L < m) {
R = 0;
for (int i = 0; i < m; i++)
if (l[0][i] <= L) R = max(R, r[0][i]);
cnt++, L = R + 1;
}
cout << '1' << '\n' << cnt << '\n';
return 0;
}
洛谷 P1535 [USACO08MAR]Cow Travelling S
emm 直接bfs 复杂度到 也就是
这个也不能折半枚举 所以说要另寻记录方法
这里我想了好久 也说不上来正常bfs到底是哪里白搜了好久浪费时间
用dp[x][y][k]表示第k时刻到达点(x, y) 的方案数
(xx, yy)是与(x, y)相邻的四个点
于是我就直接 dp了
const std::pair<int, int> p[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int dp[105][105][20];
int main() {
int n, m, t;
int sx, sy, tx, ty, xx, yy;
std::cin >> n >> m >> t;
std::vector <std::string> Map(n);
for (int i = 0; i < n; i++)
std::cin >> Map[i];
std::cin >> sx >> sy >> tx >> ty;
sx--, sy--, tx--, ty--;
dp[sx][sy][0] = 1;
for (int k = 1; k <= t; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
for (auto it : p) {
xx = i + it.first, yy = j + it.second;
if (xx < 0 || xx >= n || yy < 0 || yy >= m || Map[xx][yy] == '*')
continue;
dp[i][j][k] += dp[xx][yy][k-1];
}
}
std::cout << dp[tx][ty][t] << '\n';
return 0;
}
洛谷 P1434 [SHOI2002]滑雪
我不知道为什么我写的记搜只有90分
然后中规中矩用标准记搜dfs的时候用外部变量 就过了...
90pts 不知道第二个点挂在哪里了
#define max(a, b) (a > b ? a : b)
const std::pair<int, int> d[4]={{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
int main() {
int n, m, xx, yy;
std::cin >> n >> m;
std::vector h(n, std::vector<int>(m));
std::vector dp(n, std::vector<int>(m, 1));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
std::cin >> h[i][j];
auto dfs = [&](auto self, int x, int y) -> void {
for (auto it : d) {
xx = x + it.first, yy = y + it.second;
if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
if (h[xx][yy] >= h[x][y]) continue;
if (dp[xx][yy] > dp[x][y]) continue;
dp[xx][yy] = dp[x][y] + 1;
self(self, xx, yy);
}
};
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (dp[i][j] == 1)
dfs(dfs, i, j);
int ans = -1;
for (auto iter : dp)
for (auto it : iter)
ans = max(ans, it);
std::cout << ans;
return 0;
}
100pts
const std::pair<int, int> d[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int main() {
int n, m, xx, yy, ans = -1;
std::cin >> n >> m;
std::vector h(n, std::vector<int>(m, 0)), dp(n, std::vector<int>(m, -1));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
std::cin >> h[i][j];
auto dfs = [&](auto self, int x, int y) -> int {
if (~dp[x][y])
return dp[x][y];
else
dp[x][y] = 1;
for (auto it : d) {
xx = x + it.first, yy = y + it.second;
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
continue;
if (h[x][y] <= h[xx][yy]) continue;
dp[x][y] = std::max(dp[x][y], self(self, xx, yy) + 1);
}
return dp[x][y];
};
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ans = std::max(ans, dfs(dfs, i, j));
std::cout << ans;
return 0;
}
不能沉迷各种巧妙的写法了
虽然90pts那个感觉也是记忆化 也挺快的 不知道慢在哪里了...