比赛总结:
牛客54,这场比赛卡在线段树的那个板子有问题了,主要还是没有仔细考虑,尽量用最简单的方法最好。
然后就是重新改好了线段树的板子。
- namespace SegmentTree {
- struct node {
- int sum, l, r, lazy;
- } tr[4 * N];
-
- void up(int k) { tr[k].sum = tr[k << 1].sum + tr[k << 1 | 1].sum; }
-
-
- void down(int k) {
- if (tr[k].lazy == 0) return;
- tr[k << 1].lazy += tr[k].lazy, tr[k << 1 | 1].lazy += tr[k].lazy;
- tr[k << 1].sum += tr[k].lazy * (tr[k << 1].r - tr[k << 1].l + 1);
- tr[k << 1 | 1].sum += tr[k].lazy * (tr[k << 1 | 1].r - tr[k << 1 | 1].l + 1);
- tr[k].lazy = 0;
- }
- // 建立
- void build(int k, int l, int r) {
- tr[k].l = l, tr[k].r = r;
- if (l == r) {
- tr[k].sum = 0;
- tr[k].lazy = 0;
- return;
- }
- int mid = (l + r) >> 1;
- build(k << 1, l, mid);
- build(k << 1 | 1, mid + 1, r);
- up(k);
- }
-
- //单点修改, 将x的值修改成v
- void modify(int k, int x, int v) {
- if (tr[k].l == tr[k].r) {
- tr[k].sum = v;
- return;
- }
- int mid = (tr[k].l + tr[k].r) >> 1;
- if (x <= mid)
- modify(k << 1, tr[k].l, mid);
- else
- modify(k << 1 | 1, mid + 1, tr[k].r);
- up(k);
- }
-
-
- // 区间修改
- void modify2(int k, int l, int r, int v) {
- if (tr[k].l >= l && tr[k].r <= r) {
- tr[k].lazy += v;
- tr[k].sum += v * (tr[k].r - tr[k].l + 1);
- return;
- }
- down(k);
- int mid = (tr[k].l + tr[k].r) >> 1;
- if (l <= mid) { modify2(k << 1, l, r, v); }
- if (r > mid) { modify2(k << 1 | 1, l, r, v); }
- }
-
-
- //区间查询
- void query(int k, int l, int r) {
- if (tr[k].l >= l && tr[k].r <= r) {
- res1 += tr[k].sum;
- return;
- }
- down(k);
- int mid = (tr[k].l + tr[k].r) >> 1;
- if (l <= mid) { query(k << 1, l, r); }
- if (r > mid) { query(k << 1 | 1, l, r); }
- }
-
- } // namespace SegmentTree
然后就是这补题,BFS+ KMP也可用DP来写,但是我的BFS+KMP小问题比较多,改了好久才搞好。主要还是出是化的问题,没有太注意。代码能力有待加强。。。
- #include
-
- using namespace std;
- struct node {
- int x, y, v, res;
- };
- int fx[] = {0, 1};
- int fy[] = {1, 0};
- int nxt[105];
- int n, m, ans;
- int vis[105][105];
- string s[105], e;
-
-
- bool check(int x, int y) {
- if (x < 0 || x >= n || y < 0 || y >= m) return 0;
- return 1;
- }
-
- void get() {
- nxt[0] = -1;
- int i = 0, j = -1;
- while (i < (int) e.size() && j < (int) e.size()) {
- if (j == -1 || e[i] == e[j]) {
- nxt[++i] = ++j;
- } else {
- j = nxt[j];
- }
- }
- }
-
- void BFS() {
- int len = e.size();
- queue
q; - if (s[0][0] == e[0]) {
- q.push({0, 0, 1, 0});
- vis[0][0] = 1;
- } else {
- q.push({0, 0, 0, 0});
- vis[0][0] = 0;
- }
- while (q.size()) {
- node now = q.front();
- q.pop();
- // cout << now.x << " " << now.y << " " << now.v << " " << now.res << endl;
- if (now.v == len) {
- now.v = 0;
- now.res++;
- }
- for (int i = 0; i <= 1; i++) {
- int xx = now.x + fx[i], yy = now.y + fy[i];
- int idx = now.v;
- if (check(xx, yy)) {
- while (true) {
- if (idx == -1 || s[xx][yy] == e[idx]) {
- idx++;
- break;
- } else {
- idx = nxt[idx];
- }
- }
- if (vis[xx][yy] < idx + now.res * len) {
- vis[xx][yy] = idx + now.res * len;
- q.push({xx, yy, idx, now.res});
- }
- }
- }
- }
- }
-
- int main() {
- cin >> n >> m;
- cin >> e;
- for (int i = 0; i < n; i++) cin >> s[i];
- memset(vis, -1, sizeof vis);
- get();
- BFS();
- cout << vis[n - 1][m - 1] / (e.size()) << endl;
- return 0;
- }
然后就是下面一个构造题目,不知道哪里有问题,真的麻烦!!!等会CF打完再看看改一下。
然后就是HX出的蔚蓝杯8,是真的难!!!!只写了一个签到题目。
然后就是CF1700分的题目练习。