abc 384 D（子数组-＞前缀和） +E(bfs 扩展的时候 按照数值去扩展)

D 做出来的很开心，好像本来就应该做出来><

思路：
对于连续的子序列（也就是 子数组）
一般都和 前缀和 后缀和 有关系
区间[l r] 可以用 前缀 S_r -S{l-1} ==tar来表示。(对于两个元素等于一个数字，就可以枚举一个，去查找另一个和tar 的 数值 是否存在，很常见的套路)
因为我们的元素都是正数，所以S 的逐渐增大的。
那我们可以枚举 前面的S_{l} 去查找是否有 S =tar+S_l（使用set 就可以了）

如果我的s >sum 那么说明了肯定包含了一个整的区间，先对 s 取模。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}void solve()
{int n, s;cin >> n >> s;set<int> se;vector<int> a(n);for (int i = 0; i < n; i++){cin >> a[i];}int t = 0;int sum = 0;se.insert(0);for (int i = 0; i < 2 * n; i++){t += a[i % n];if (i == n - 1)sum = t;se.insert(t);}s%=sum;for (auto i:se){int tar=i+s;if (se.find(tar)!=se.end()){cout<<"Yes\n";return ;}}cout<<"No\n";return; 
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}

E

乍一看有一点 那种bfs 求最短路的感觉，不断的把点 push 进队列，一圈一圈的扩展。
但是 有一个问题
因为我能否扩展 要求 我的v /x 要大于这个方格，我才能扩展。
并且我的v 值是变化的（我扩展一个位置，那么我的v 就加上这个方格的值）
也就是说 我的四个方向的扩展顺序时有区别的。
如果我先碰到 值较大的点，我当前的v 不能 吸收他
但要是 我先碰到 值 较小的点，在碰到较大的点，也许就可以吸收这个点。
（并且我不可能一个点反复的进队出队，这样我的复杂度无法保证）
所以是否 有之中扩展顺序（上下左右），使得我不会出现以上的情况。

可以感觉到 我应该按照值的大小 去扩展
写法有点类似 dij

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
struct node
{int x, y;double v = 0;bool operator<(const node &a) const{return a.v < v;}
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void solve()
{int n, m;cin >> n >> m;double x;cin >> x;int sx, sy;cin >> sx >> sy;sx--;sy--;vector<vector<double>> g(n, vector<double>(m));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++)cin >> g[i][j];}vector<vector<bool>> vis(n, vector<bool>(m));priority_queue<node> q; // 小根堆double nv = g[sx][sy];q.push({sx, sy, nv});vis[sx][sy] = 1;while (!q.empty()){node no = q.top();q.pop();if (nv / x > no.v){nv += no.v;}else if (no.x != sx && no.y != sy){cout << nv << "\n";return;}for (int i = 0; i < 4; i++){int nx = no.x + dx[i];int ny = no.y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m){if (vis[nx][ny])continue;q.push({nx, ny, g[nx][ny]});vis[nx][ny] = 1;}}}
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}